Greedy Versus Curious Parent Selection for Multi-objective Evolutionary Algorithms
Pages 86 - 101
Abstract
From the literature we know that simple evolutionary multi-objective algorithms can optimize the classic two-objective test functions OneMinMax and CountingOnesCountingZeroes in expected time. We extend this result to any pair of generalized OneMax functions and show that, if the optima of the two functions are d apart, then (G)SEMO has an expected optimization time of .
In an attempt to achieve better optimization times, some algorithms consider parent selection. We show that parent selection based on the curiosity-based novelty search can improve the optimization time to on OneMinMax. By contrast, we show that greedy parent selection schemes can be trapped with an incomplete Pareto front for superpolynomial time.
Finally, we provide experimental results on the two-objective optimization of linear functions.
References
[1]
Antipov, D., Kötzing, T., Radhakrishnan, A.: Supplementary material - greedy versus curious parent selection for multi-objective evolutionary algorithms (2024). https://zenodo.org/records/10990807
[2]
Antipov, D., Neumann, A., Neumann, F.: Rigorous runtime analysis of diversity optimization with GSEMO on OneMinMax. In: Foundations of Genetic Algorithms (FOGA 2023), pp. 3–14. ACM (2023)
[3]
Brockhoff, D., Friedrich, T., Hebbinghaus, N., Klein, C., Neumann, F., Zitzler, E.: Do additional objectives make a problem harder? In: Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation GECCO 2007, pp. 765–772. ACM (2007)
[4]
Covantes Osuna, E., Gao, W., Neumann, F., Sudholt, D.: Speeding up evolutionary multi-objective optimisation through diversity-based parent selection. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2017), pp. 553–560. ACM (2017)
[5]
Covantes Osuna E, Gao W, Neumann F, and Sudholt D Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation Theor. Comput. Sci. 2018 832 123-142
[6]
Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation - Recent Developments in Discrete Optimization, pp. 1–87. Springer, Cham (2020).
[7]
Doerr B, Doerr C, and Ebel F From black-box complexity to designing new genetic algorithms Theoret. Comput. Sci. 2015 567 87-104
[8]
Doerr, B., Gao, W., Neumann, F.: Runtime analysis of evolutionary diversity maximization for oneminmax. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016 (GECCO 2016), pp. 557–564. ACM (2016)
[9]
Doerr B and Kötzing T Lower bounds from fitness levels made easy Algorithmica 2024 86 2 367-395
[10]
Doerr B and Qu Z A first runtime analysis of the NSGA-II on a multimodal problem IEEE Trans. Evol. Comput. 2023 27 5 1288-1297
[11]
Doerr, B., Qu, Z.: Runtime analysis for the NSGA-II: provable speed-ups from crossover. In: Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 12399–12407. AAAI Press (2023)
[12]
Doerr, B., Zheng, W.: Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives: (hot-off-the-press track at GECCO 2021). In: Proceedings of the 2021 Annual Conference on Genetic and Evolutionary Computation GECCO 2021, pp. 25–26. ACM (2021)
[13]
Doerr, C., Lengler, J.: Onemax in black-box models with several restrictions. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO 2015), pp. 1431–1438. ACM (2015)
[14]
Droste S, Jansen T, and Wegener I On the analysis of the (1+1) evolutionary algorithm Theor. Comput. Sci. 2002 276 1–2 51-81
[15]
Droste S, Jansen T, and Wegener I Upper and lower bounds for randomized search heuristics in black-box optimization Theory Comput. Syst. 2006 39 4 525-544
[16]
Eiben AE and Smith JE Introduction to Evolutionary Computing 2015 2 Heidelberg Springer
[17]
Friedrich, T., Hebbinghaus, N., Neumann, F.: Plateaus can be harder in multi-objective optimization. In: 2007 IEEE Congress on Evolutionary Computation CEC, pp. 2622–2629 (2007)
[18]
Friedrich T, Horoba C, and Neumann F Illustration of fairness in evolutionary multi-objective optimization Theor. Comput. Sci. 2011 412 17 1546-1556
[19]
Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: The 2003 Congress on Evolutionary Computation CEC, vol. 3, pp. 1918–1925 (2003)
[20]
Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimization. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation GECCO 2006, pp. 651–658. ACM (2006)
[21]
Kötzing T and Krejca MS First-hitting times under drift Theoret. Comput. Sci. 2019 796 51-69
[22]
Laumanns M, Thiele L, and Zitzler E Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions IEEE Trans. Evol. Comput. 2004 8 2 170-182
[23]
Laumanns, M., Thiele, L., Zitzler, E., Welzl, E., Deb, K.: Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In: Proceedings of the 7th International Conference on Parallel Problem Solving from Nature PPSN 2002, pp. 44–53. Springer (2002)
[24]
Li YL, Zhou YR, Zhan ZH, and Zhang J A primary theoretical study on decomposition-based multiobjective evolutionary algorithms IEEE Trans. Evol. Comput. 2016 20 4 563-576
[25]
Qian, C., Tang, K., Zhou, Z.H.: Selection hyper-heuristics can provably be helpful in evolutionary multi-objective optimization. In: Parallel Problem Solving from Nature PPSN 2016. Springer (2016)
[26]
Qian, C., Yu, Y., Zhou, Z.H.: An analysis on recombination in multi-objective evolutionary optimization. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO 2011), pp. 2051–2058. ACM (2011)
[27]
Witt C Tight bounds on the optimization time of a randomized search heuristic on linear functions Comb. Probab. Comput. 2013 22 2 294-318
[28]
Zheng W and Doerr B Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II) Artif. Intell. 2023 325
Index Terms
- Greedy Versus Curious Parent Selection for Multi-objective Evolutionary Algorithms
Index terms have been assigned to the content through auto-classification.
Recommendations
Multi-Objective Quantum Evolutionary Algorithm for Discrete Multi-Objective Combinational Problem
TAAI '10: Proceedings of the 2010 International Conference on Technologies and Applications of Artificial IntelligenceWeighted linear scalar, which transfers a multiobjective problem to many single objective sub-problems, is a basic strategy in traditional multi-objective optimization. However, it is not well used in many multi-objective evolutionary algorithms because ...
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 ...
Multi-parent Mutation in Differential Evolution for Multi-objective Optimization
ICNC '09: Proceedings of the 2009 Fifth International Conference on Natural Computation - Volume 04Differential evolution (DE) is a fast and effective computing method and technique. In differential evolution for global optimization, mutation plays a key role in the performance and there are several mutation variants, which have been widely used in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sep 2024
435 pages
ISBN:978-3-031-70070-5
DOI:10.1007/978-3-031-70071-2
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 14 September 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 31 Dec 2024