<i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization
Deterioration of the searchability of Pareto dominance-based, many-objective evolutionary optimization algorithms is a well-known problem. Alternative solutions, such as scalarization-based and indicator-based approaches, have been proposed in the literature. However, Pareto dominance-based algorith...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-11-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/15/11/420 |
| _version_ | 1797469422055587840 |
|---|---|
| author | Jean Ruppert Marharyta Aleksandrova Thomas Engel |
| author_facet | Jean Ruppert Marharyta Aleksandrova Thomas Engel |
| author_sort | Jean Ruppert |
| collection | DOAJ |
| description | Deterioration of the searchability of Pareto dominance-based, many-objective evolutionary optimization algorithms is a well-known problem. Alternative solutions, such as scalarization-based and indicator-based approaches, have been proposed in the literature. However, Pareto dominance-based algorithms are still widely used. In this paper, we propose to redefine the calculation of Pareto-dominance. Instead of assigning solutions to non-dominated fronts, they are ranked according to the measure of dominating solutions referred to as <i>k</i>-Pareto optimality. In the case of probability measures, such re-definition results in an elegant and fast approximate procedure. Through experimental results on the many-objective <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>0</mn><mo>/</mo><mn>1</mn></mrow></semantics></math></inline-formula> knapsack problem, we demonstrate the advantages of the proposed approach: (1) the approximate calculation procedure is much faster than the standard sorting by Pareto dominance; (2) it allows for achieving higher hypervolume values for both multi-objective (two objectives) and many-objective (25 objectives) optimization; (3) in the case of many-objective optimization, the increased ability to differentiate between solutions results in a better compared to NSGA-II and NSGA-III. Apart from the numerical improvements, the probabilistic procedure can be considered as a linear extension of multidimentional topological sorting. It produces almost no ties and, as opposed to other popular linear extensions, has an intuitive interpretation. |
| first_indexed | 2024-03-09T19:21:10Z |
| format | Article |
| id | doaj.art-866c755e76bc41bbbd7b0d98caf1ed69 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-09T19:21:10Z |
| publishDate | 2022-11-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-866c755e76bc41bbbd7b0d98caf1ed692023-11-24T03:23:14ZengMDPI AGAlgorithms1999-48932022-11-01151142010.3390/a15110420<i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic OptimizationJean Ruppert0Marharyta Aleksandrova1Thomas Engel2Mathematics and Computing S.à r.l., L-2360 Luxembourg, LuxembourgDepartment of Computer Science, Faculty of Science, Technology and Medicine, University of Luxembourg, 2 Avenue de l’Universite, L-4365 Esch-sur-Alzette, LuxembourgDepartment of Computer Science, Faculty of Science, Technology and Medicine, University of Luxembourg, 2 Avenue de l’Universite, L-4365 Esch-sur-Alzette, LuxembourgDeterioration of the searchability of Pareto dominance-based, many-objective evolutionary optimization algorithms is a well-known problem. Alternative solutions, such as scalarization-based and indicator-based approaches, have been proposed in the literature. However, Pareto dominance-based algorithms are still widely used. In this paper, we propose to redefine the calculation of Pareto-dominance. Instead of assigning solutions to non-dominated fronts, they are ranked according to the measure of dominating solutions referred to as <i>k</i>-Pareto optimality. In the case of probability measures, such re-definition results in an elegant and fast approximate procedure. Through experimental results on the many-objective <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mn>0</mn><mo>/</mo><mn>1</mn></mrow></semantics></math></inline-formula> knapsack problem, we demonstrate the advantages of the proposed approach: (1) the approximate calculation procedure is much faster than the standard sorting by Pareto dominance; (2) it allows for achieving higher hypervolume values for both multi-objective (two objectives) and many-objective (25 objectives) optimization; (3) in the case of many-objective optimization, the increased ability to differentiate between solutions results in a better compared to NSGA-II and NSGA-III. Apart from the numerical improvements, the probabilistic procedure can be considered as a linear extension of multidimentional topological sorting. It produces almost no ties and, as opposed to other popular linear extensions, has an intuitive interpretation.https://www.mdpi.com/1999-4893/15/11/420genetic algorithmsmulti-objective optimizationtopological sortinglinear extension of multidimensional sorting |
| spellingShingle | Jean Ruppert Marharyta Aleksandrova Thomas Engel <i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization Algorithms genetic algorithms multi-objective optimization topological sorting linear extension of multidimensional sorting |
| title | <i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization |
| title_full | <i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization |
| title_fullStr | <i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization |
| title_full_unstemmed | <i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization |
| title_short | <i>k</i>-Pareto Optimality-Based Sorting with Maximization of Choice and Its Application to Genetic Optimization |
| title_sort | i k i pareto optimality based sorting with maximization of choice and its application to genetic optimization |
| topic | genetic algorithms multi-objective optimization topological sorting linear extension of multidimensional sorting |
| url | https://www.mdpi.com/1999-4893/15/11/420 |
| work_keys_str_mv | AT jeanruppert ikiparetooptimalitybasedsortingwithmaximizationofchoiceanditsapplicationtogeneticoptimization AT marharytaaleksandrova ikiparetooptimalitybasedsortingwithmaximizationofchoiceanditsapplicationtogeneticoptimization AT thomasengel ikiparetooptimalitybasedsortingwithmaximizationofchoiceanditsapplicationtogeneticoptimization |