A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMax
Pages 467 - 475
Abstract
Real-world optimization problems often require finding not only one good solution, but a diverse set of good solutions. Evolutionary algorithms (EAs) have been shown to suit well for such a task. However our theoretical understanding of their behavior remains unsatisfying, especially in the multi-objective domain.
In this paper, we study how one of such EAs, the GSEMOD, finds a diverse population when optimizing the bi-objective benchmark problem OneMinMax. We show empirically that the expected runtime of this algorithm grows with problem size n approximately as fast as n2 ln(n). We prove that there exists a sub-optimal population from which the algorithm cannot reach the optimal diversity using only one-bit flips, which suggests that we need to use a mutation operator which can make two-bits flips (e.g., the standard bit mutation) to have a finite expected runtime. We complement these results with an empirical study of the population dynamics by observing how the Hamming distances between the individuals which are neighbors on the Pareto front change during the optimization.
References
[1]
Denis Antipov, Aneta Neumann, and Frank Neumann. 2023. Rigorous runtime analysis of diversity optimization with GSEMO on OneMinMax. In Foundations of Genetic Algorithms, FOGA 2023. ACM, 3--14.
[2]
Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. 2019. Evolving diverse TSP instances by means of novel and creative mutation operators. In Foundations of Genetic Algorithms, FOGA 2019. ACM, 58--71.
[3]
Jakob Bossek, Aneta Neumann, and Frank Neumann. 2021. Breeding diverse packings for the knapsack problem by means of diversity-tailored evolutionary algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 556--564.
[4]
Jakob Bossek and Frank Neumann. 2021. Evolutionary diversity optimization and the minimum spanning tree problem. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 198--206.
[5]
Maximilian Böther, Leon Schiller, Philipp Fischbeck, Louise Molitor, Martin S. Krejca, and Tobias Friedrich. 2021. Evolutionary minimization of traffic congestion. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 937--945.
[6]
Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2016. Escaping local optima with diversity mechanisms and crossover. In Genetic and Evolutionary Computation Conference, GECCO 2016. ACM, 645--652.
[7]
Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2018. Escaping Local Optima Using Crossover With Emergent Diversity. IEEE Transactions on Evolutionary Computation 22, 3 (2018), 484--497.
[8]
Kenneth A. De Jong and William M. Spears. 1989. Using genetic algorithms to solve NP-complete problems. In International Conference on Genetic Algorithms, ICGA 1989. Morgan Kaufmann Publishers Inc., 124--132.
[9]
Anh Viet Do, Jakob Bossek, Aneta Neumann, and Frank Neumann. 2020. Evolving diverse sets of tours for the travelling salesperson problem. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 681--689.
[10]
Anh Viet Do, Mingyu Guo, Aneta Neumann, and Frank Neumann. 2022. Analysis of Evolutionary Diversity Optimization for Permutation Problems. ACM Transactions on Evolutionary Learning and Optimization 2, 3 (2022), 11:1--11:27.
[11]
Benjamin Doerr, Wanru Gao, and Frank Neumann. 2016. Runtime analysis of evolutionary diversity maximization for OneMinMax. In Genetic and Evolutionary Computation Conference, GECCO 2016. ACM, 557--564.
[12]
Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation - Recent Developments in Discrete Optimization. Springer.
[13]
Per Galle. 1989. Branch & Sample: A Simple Strategy for Constraint Satisfaction. BIT 29, 3 (1989), 395--408.
[14]
Wanru Gao, Samadhi Nallaperuma, and Frank Neumann. 2021. Feature-Based Diversity Optimization for Problem Instance Classification. Evolutionary Computation 29, 1 (2021), 107--128.
[15]
Wanru Gao and Frank Neumann. 2014. Runtime analysis for maximizing population diversity in single-objective optimization. In Genetic and Evolutionary Computation Conference, GECCO 2014. ACM, 777--784.
[16]
Wanru Gao, Mojgan Pourhassan, and Frank Neumann. 2015. Runtime analysis of evolutionary diversity optimization and the vertex cover problem. In Genetic and Evolutionary Computation Conference, GECCO 2015, Companion Material. ACM, 1395--1396.
[17]
Oliver Giel and Per Kristian Lehre. 2010. On the Effect of Populations in Evolutionary Multi-Objective Optimisation. Evolutionary Computation 18, 3 (2010), 335--356.
[18]
Robert W. Haessler and Paul E. Sweeney. 1991. Cutting Stock Problems and Solution Procedures. European Journal of Operational Research 54 (1991), 141--150.
[19]
Daniel Kobler. 2009. Evolutionary Algorithms in Combinatorial Optimization. In Encyclopedia of Optimization, Second Edition. Springer, 950--959.
[20]
Ching-Chung Kuo, Fred Glover, and Krishna S. Dhir. 1993. Analyzing and Modeling the Maximum Diversity Problem by Zero-One Programming. Decision Sciences 24, 6 (1993), 1171--1185.
[21]
Aneta Neumann, Jakob Bossek, and Frank Neumann. 2021. Diversifying greedy sampling and evolutionary diversity optimisation for constrained monotone sub-modular functions. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 261--269.
[22]
Aneta Neumann, Wanru Gao, Carola Doerr, Frank Neumann, and Markus Wagner. 2018. Discrepancy-based evolutionary diversity optimization. In Genetic and Evolutionary Computation Conference, GECCO 2018. ACM, 991--998.
[23]
Aneta Neumann, Wanru Gao, Markus Wagner, and Frank Neumann. 2019. Evolutionary diversity optimization using multi-objective indicators. In Genetic and Evolutionary Computation Conference, GECCO 2019. ACM, 837--845.
[24]
Adel Nikfarjam, Jakob Bossek, Aneta Neumann, and Frank Neumann. 2021. Computing diverse sets of high quality TSP tours by EAX-based evolutionary diversity optimisation. In Foundations of Genetic Algorithms, FOGA 2021. ACM, 9:1--9:11.
[25]
Adel Nikfarjam, Jakob Bossek, Aneta Neumann, and Frank Neumann. 2021. Entropy-based evolutionary diversity optimisation for the traveling salesperson problem. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM, 600--608.
[26]
Adel Nikfarjam, Aneta Neumann, and Frank Neumann. 2022. Evolutionary diversity optimisation for the traveling thief problem. In Genetic and Evolutionary Computation Conference, GECCO 2022. ACM, 749--756.
[27]
Günther R. Raidl, Gabriele Koller, and Bryant A. Julstrom. 2006. Biased Mutation Operators for Subgraph-Selection Problems. IEEE Transactions on Evolutionary Computation 10, 2 (2006), 145--156.
[28]
Tamara Ulrich and Lothar Thiele. 2011. Maximizing population diversity in single-objective optimization. In Genetic and Evolutionary Computation Conference, GECCO 2011. ACM, 641--648.
[29]
Zhi-Hua Zhou, Yang Yu, and Chao Qian. 2019. Evolutionary Learning: Advances in Theories and Algorithms. Springer.
Index Terms
- A Detailed Experimental Analysis of Evolutionary Diversity Optimization for OneMinMax
Recommendations
Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax
FOGA '23: Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic AlgorithmsThe evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we ...
Runtime Analysis of Evolutionary Diversity Optimization on a Tri-Objective Version of the (LeadingOnes, TrailingZeros) Problem
Parallel Problem Solving from Nature – PPSN XVIIIAbstractDiversity optimization is a class of optimization problems in which we aim to find a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse ...
Speeding up evolutionary multi-objective optimisation through diversity-based parent selection
GECCO '17: Proceedings of the Genetic and Evolutionary Computation ConferenceParent selection in evolutionary algorithms for multi-objective optimization is usually performed by dominance mechanisms or indicator functions that prefer non-dominated points, while the reproduction phase involves the application of diversity ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
1657 pages
This work is licensed under a Creative Commons Attribution-NonCommercial International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
GECCO '24
Sponsor:
GECCO '24: Genetic and Evolutionary Computation Conference
July 14 - 18, 2024
VIC, Melbourne, Australia
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 36Total Downloads
- Downloads (Last 12 months)36
- Downloads (Last 6 weeks)15
Reflects downloads up to 26 Sep 2024
Other Metrics
Citations
Cited By
View allView Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in