A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis
Pages 493 - 501
Abstract
We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into k blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale optimization problems such as airline scheduling, however its use in multi-objective optimization is less studied. We propose a block-coordinate version of GSEMO and compare its running time to the standard GSEMO algorithm. Theoretical and empirical results on a bi-objective test function, a variant of LOTZ, serve to demonstrate the existence of cases where block-coordinate descent is faster. The result may yield wider insights into this class of algorithms.
References
[1]
Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.
[2]
Amir Beck and Luba Tetruashvili. 2013. On the convergence of block coordinate descent type methods. SIAM Journal on Optimization 23, 4 (2013), 2037--2060.
[3]
Nicola Beume, Boris Naujoks, and Michael Emmerich. 2007. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research 181 (2007), 1653--1669.
[4]
Chao Bian, Yawen Zhou, Miqing Li, and Chao Qian. 2023. Stochastic population update can provably be helpful in multi-objective evolutionary algorithms. In International Joint Conference on Artificial Intelligence, IJCAI 2023. ijcai.org, 5513--5521.
[5]
Dimo Brockhoff, Tobias Friedrich, Nils Hebbinghaus, Christian Klein, Frank Neumann, and Eckart Zitzler. 2009. On the effects of adding objectives to plateau functions. IEEE Transactions on Evolutionary Computation 13, 3 (2009), 591--603.
[6]
Jamie Caldwell, Joshua Knowles, Christoph Thies, Filip Kubacki, and Richard Watson. 2022. Deep optimisation: Transitioning the scale of evolutionary search by inducing and searching in deep representations. SN Computer Science 3, 3 (2022), 253.
[7]
Sacha Cerf, Benjamin Doerr, Benjamin Hebras, Jakob Kahane, and Simon Wietheger. 2023. The first proven performance guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a combinatorial optimization problem. In International Joint Conference on Artificial Intelligence, IJCAI 2023. ijcai.org, 5522--5530.
[8]
Carlos A Coello. 2000. An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys (CSUR) 32, 2 (2000), 109--143.
[9]
David W Corne, Kalyanmoy Deb, Peter J Fleming, and Joshua D Knowles. 2003. The good of the many outweighs the good of the one: Evolutionary multiobjective optimization. IEEE Connections Newsletter 1, 1 (2003), 9--13.
[10]
Kerstin Dächert, Benjamin Doerr, Joshua D Knowles, Aneta Neumann, Frank Neumann, Andrea Raith, Anita Schöbel, and Margaret M Wiecek. 2024. Modeling and decomposition --- biobjective block-coordinate descent. Dagstuhl Reports 13, 9 (2024), 45--55.
[11]
Kalyanmoy Deb. 2015. Multi-objective evolutionary algorithms. In Springer Handbook of Computational Intelligence. Springer, 995--1015.
[12]
Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182--197.
[13]
Kalyanmoy Deb and Himanshu Jain. 2014. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Transactions on Evolutionary Computation 18, 4 (2014), 577--601.
[14]
Matthieu Dinot, Benjamin Doerr, Ulysse Hennebelle, and Sebastian Will. 2023. Runtime analyses of multi-objective evolutionary algorithms in the presence of noise. In International Joint Conference on Artificial Intelligence, IJCAI 2023. ijcai.org, 5549--5557.
[15]
Anh Viet Do, Aneta Neumann, Frank Neumann, and Andrew M. Sutton. 2023. Rigorous runtime analysis of MOEA/D for solving multi-objective minimum weight base problems. In Advances in Neural Information Processing Systems, NeurIPS 2023. https://openreview.net/forum?id=ORmVvN94B9
[16]
Benjamin Doerr. 2019. Analyzing randomized search heuristics via stochastic domination. Theoretical Computer Science 773 (2019), 115--137.
[17]
Benjamin Doerr. 2020. Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Benjamin Doerr and Frank Neumann (Eds.). Springer, 1--87.
[18]
Benjamin Doerr. 2021. Runtime analysis of evolutionary algorithms via symmetry arguments. Information Processing Letters 166 (2021), 106064.
[19]
Benjamin Doerr, Thomas Jansen, Carsten Witt, and Christine Zarges. 2013. A method to derive fixed budget results from expected optimisation times. In Genetic and Evolutionary Computation Conference, GECCO 2013. ACM, 1581--1588.
[20]
Benjamin Doerr, Bojana Kodric, and Marco Voigt. 2013. Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In IEEE Congress on Evolutionary Computation, CEC 2013. IEEE, 432--439.
[21]
Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation---Recent Developments in Discrete Optimization. Springer.
[22]
Benjamin Doerr, Dirk Sudholt, and Carsten Witt. 2013. When do evolutionary algorithms optimize separable functions in parallel?. In Foundations of Genetic Algorithms, FOGA 2013. ACM, 48--59.
[23]
Benjamin Doerr and Weijie Zheng. 2021. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In Conference on Artificial Intelligence, AAAI 2021. AAAI Press, 12293--12301.
[24]
Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, and Carsten Witt. 2010. Approximating covering problems by randomized search heuristics using multi-objective models. Evolutionary Computation 18 (2010), 617--633.
[25]
Tobias Friedrich, Timo Kötzing, Aneta Neumann, Frank Neumann, and Aishwarya Radhakrishnan. 2023. Analysis of (1+1) EA on LeadingOnes with constraints. In Genetic and Evolutionary Computation Conference, GECCO 2023. ACM, 1584--1592.
[26]
Oliver Giel. 2003. Expected runtimes of a simple multi-objective evolutionary algorithm. In IEEE Congress on Evolutionary Computation, CEC 2003. IEEE, 1918--1925.
[27]
Oliver Giel and Per Kristian Lehre. 2006. On the effect of populations in evolutionary multi-objective optimization. In Genetic and Evolutionary Computation Conference, GECCO 2006. ACM, 651--658.
[28]
Christian Horoba and Frank Neumann. 2010. Approximating Pareto-optimal sets using diversity strategies in evolutionary multi-objective optimization. In Advances in multi-objective nature inspired computing. Studies in Computational Intelligence, Vol. 272. Springer, 23--44.
[29]
Zhengxin Huang, Yuren Zhou, Zefeng Chen, and Xiaoyu He. 2019. Running time analysis of MOEA/D with crossover on discrete optimization problem. In Conference on Artificial Intelligence, AAAI 2019. AAAI Press, 2296--2303.
[30]
Zhengxin Huang, Yuren Zhou, Chuan Luo, and Qingwei Lin. 2021. A runtime analysis of typical decomposition approaches in MOEA/D framework for many-objective optimization problems. In International Joint Conference on Artificial Intelligence, IJCAI 2021. ijcai.org, 1682--1688.
[31]
Sven Jäger and Anita Schöbel. 2020. The blockwise coordinate descent method for integer programs. Mathematical Methods of Operations Research 91, 2 (2020), 357--381.
[32]
Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.
[33]
Jörg Lässig and Dirk Sudholt. 2010. The benefit of migration in parallel evolutionary algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2010. ACM, 1105--1112.
[34]
Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer.
[35]
Andre Opris, Duc Cuong Dang, Frank Neumann, and Dirk Sudholt. 2024. Runtime analyses of NSGA-III on many-objective problems. In Genetic and Evolutionary Computation Conference, GECCO 2024. ACM. To appear.
[36]
Vahid Roostapour, Aneta Neumann, Frank Neumann, and Tobias Friedrich. 2022. Pareto optimization for subset selection with dynamic cost constraints. Artificical Intelligence 302 (2022), 103597.
[37]
Günter Rudolph. 1997. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovâc.
[38]
Anita Schöbel. 2017. An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research Part C: Emerging Technologies 74 (2017), 348--365.
[39]
Simon Wietheger and Benjamin Doerr. 2023. A mathematical runtime analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In International Joint Conference on Artificial Intelligence, IJCAI 2023. ijcai.org, 5657--5665.
[40]
Qingfu Zhang and Hui Li. 2007. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (2007), 712--731.
[41]
Weijie Zheng and Benjamin Doerr. 2023. Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II). Artificial Intelligence 325 (2023), 104016.
[42]
Weijie Zheng and Benjamin Doerr. 2024. Runtime analysis of the SMS-EMOA for many-objective optimization. In Conference on Artificial Intelligence, AAAI 2024. AAAI Press.
[43]
Zhi-Hua Zhou, Yang Yu, and Chao Qian. 2019. Evolutionary Learning: Advances in Theories and Algorithms. Springer.
[44]
Eckart Zitzler, Marco Laumanns, and Lothar Thiele. 2001. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-report 103 (2001).
Index Terms
- A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis
Recommendations
Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
Parallel Problem Solving from Nature – PPSN XVIIIAbstractDespite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing ...
A first mathematical runtime analysis of the non-dominated sorting genetic algorithm II (NSGA-II): (hot-off-the-press track at GECCO 2022)
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference CompanionThe non-dominated sorting genetic algorithm II (NSGA-II) is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. However, in contrast to several simple MOEAs analyzed also via mathematical means, no such ...
Hot off the Press: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
GECCO '24 Companion: Proceedings of the Genetic and Evolutionary Computation Conference CompanionThe NSGA-II was recently proven to have difficulties in many-objective optimization. In contrast, the literature experimentally shows a good performance of the SMS-EMOA, which can be seen as a steady-state NSGA-II that uses the hypervolume contribution ...
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
- Australian Research Council
- FMJH Program Gaspard Monge for optimization and operations research and their interactions with data science
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
- 43Total Downloads
- Downloads (Last 12 months)43
- Downloads (Last 6 weeks)24
Reflects downloads up to 26 Sep 2024
Other Metrics
Citations
View 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