More Web Proxy on the site http://driver.im/

research-article

Population size matters: rigorous runtime results for maximizing the hypervolume indicator

Authors:

Anh Quang Nguyen,

Andrew M. Sutton,

Frank NeumannAuthors Info & Claims

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

Pages 1613 - 1620

https://doi.org/10.1145/2463372.2463564

Published: 06 July 2013 Publication History

Abstract

Using the hypervolume indicator to guide the search of evolutionary multi-objective algorithms has become very popular in recent years. We contribute to the theoretical understanding of these algorithms by carrying out rigorous runtime analyses. We consider multi-objective variants of the problems OneMax and LeadingOnes called OMM and LOTZ, respectively, and investigate hypervolume-based algorithms with population sizes that do not allow coverage of the entire Pareto front. Our results show that LOTZ is easier to optimize than OMM for hypervolume-based evolutionary multi-objective algorithms which is contrary to the results on their single-objective variants and the well-studied (1+1)~EA.

References

[1]

Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In FOCS, pages 218--223. IEEE, 1979.

Digital Library

[2]

Anne Auger, Johannes Bader, Dimo Brockhoff, and Eckart Zitzler. Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences. 11th annual Conference on Genetic and Evolutionary Computation (GECCO '09), pages 563--570. ACM Press, 2009.

Digital Library

[3]

Anne Auger, Johannes Bader, Dimo Brockhoff, and Eckart Zitzler. Hypervolume-based multiobjective optimization: Theoretical foundations and practical implications. Theoretical Computer Science, 425:75--103, 2012.

Digital Library

[4]

Rudolf Berghammer, Tobias Friedrich, and Frank Neumann. Convergence of set-based multi-objective optimization, indicators and deteriorative cycles. Theoretical Computer Science, 456:2--17, 2012.

Digital Library

[5]

Nicola Beume, Boris Naujoks, and Michael T. M. Emmerich. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181:1653--1669, 2007.

[6]

Karl Bringmann and Tobias Friedrich. Approximating the volume of unions and intersections of high-dimensional geometric objects. Computational Geometry: Theory and Applications, 43:601--610, 2010.

Digital Library

[7]

Karl Bringmann and Tobias Friedrich. Approximation quality of the hypervolume indicator. Artif. Intell., 195:265--290, 2013.

Digital Library

[8]

Dimo Brockhoff. Optimal μ-distributions for the hypervolume indicator for problems with linear bi-objective fronts: Exact and exhaustive results. 8th International Conference on Simulated Evolution And Learning (SEAL '10), volume 6457 of LNCS, pages 24--34, 2010.

Digital Library

[9]

Dimo Brockhoff, Tobias Friedrich, and Frank Neumann. Analyzing hypervolume indicator based algorithms. In Günter Rudolph, Thomas Jansen, Simon M. Lucas, Carlo Poloni, and Nicola Beume, editors, Parallel Problem Solving from Nature--PPSN X, volume 5199 of Lecture Notes in Computer Science, pages 651--660. Springer, 2008.

Digital Library

[10]

C. A. Coello Coello, D. A. Van Veldhuizen, and G. B. Lamont. Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, New York, 2002.

Digital Library

[11]

K. Deb. Multi-objective optimization using evolutionary algorithms. Wiley, Chichester, UK, 2001.

Digital Library

[12]

Michael T. M. Emmerich, Nicola Beume, and Boris Naujoks. An EMO algorithm using the hypervolume measure as selection criterion. Third International Conference on Evolutionary Multi-Criterion Optimization (EMO '05), pages 62--76. Springer, 2005.

Digital Library

[13]

Oliver Giel and Per Kristian Lehre. On the effect of populations in evolutionary multi-objective optimisation. Evolutionary Computation, 18(3):335--356, 2010.

Digital Library

[14]

Edda Happ, Daniel Johannsen, Christian Klein, and Frank Neumann. Rigorous analyses of fitness-proportional selection for optimizing linear functions. In Conor Ryan and Maarten Keijzer, editors, GECCO, pages 953--960. ACM, 2008.

Digital Library

[15]

Marco Laumanns, Lothar Thiele, and Eckart Zitzler. Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Trans. Evolutionary Computation, 8(2):170--182, 2004.

Digital Library

[16]

Frank Neumann and Carsten Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[17]

Eckart Zitzler and Simon Künzli. Indicator-based selection in multiobjective search. 8th International Conference Parallel Problem Solving from Nature (PPSN VIII), volume 3242 of LNCS, pages 832--842. Springer, 2004.

Cited By

Yang TZhou Y(2024)Analysis of Multiobjective Evolutionary Algorithms on Fitness Function With Time-Linkage PropertyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2024.337151928:3(837-843)Online publication date: Jun-2024
https://doi.org/10.1109/TEVC.2024.3371519
Nguyen ASutton ANeumann F(2015)Population size mattersTheoretical Computer Science10.1016/j.tcs.2014.06.023561:PA(24-36)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.06.023
Wei KDinneen M(2014)Hybridizing the dynamic mutation approach with local searches to overcome local optima2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900360(74-81)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900360

Index Terms

Population size matters: rigorous runtime results for maximizing the hypervolume indicator
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Population size matters

Evolutionary multi-objective optimization is one of the most successful areas in the field of evolutionary computation. Using the hypervolume indicator to guide the search of evolutionary multi-objective algorithms has become very popular in recent ...
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 Companion

The 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 ...
Speeding up evolutionary multi-objective optimisation through diversity-based parent selection
GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Parent 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

cover image ACM Conferences

GECCO '13: Proceedings of the 15th annual conference on Genetic and evolutionary computation

July 2013

1672 pages

ISBN:9781450319638

DOI:10.1145/2463372

Editor:
Christian Blum
IKERBASQUE and University of the Basque Country UPV/EHU, Spain
,
General Chair:
Enrique Alba
University of Malaga, Spain

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '13

Sponsor:

SIGEVO

GECCO '13: Genetic and Evolutionary Computation Conference

July 6 - 10, 2013

Amsterdam, The Netherlands

Acceptance Rates

GECCO '13 Paper Acceptance Rate 204 of 570 submissions, 36%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
130
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang TZhou Y(2024)Analysis of Multiobjective Evolutionary Algorithms on Fitness Function With Time-Linkage PropertyIEEE Transactions on Evolutionary Computation10.1109/TEVC.2024.337151928:3(837-843)Online publication date: Jun-2024
https://doi.org/10.1109/TEVC.2024.3371519
Nguyen ASutton ANeumann F(2015)Population size mattersTheoretical Computer Science10.1016/j.tcs.2014.06.023561:PA(24-36)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.06.023
Wei KDinneen M(2014)Hybridizing the dynamic mutation approach with local searches to overcome local optima2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900360(74-81)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900360

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents