research-article

Closed state model for understanding the dynamics of MOEAs

Authors:

Kiyoshi TanakaAuthors Info & Claims

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 609 - 616

https://doi.org/10.1145/3071178.3071259

Published: 01 July 2017 Publication History

Get Access

Abstract

This work proposes the use of simple closed state models to capture, analyze and compare the dynamics of multi- and many-objective evolutionary algorithms. Two- and three-state models representing the composition of the instantaneous population are described and learned for representatives of the major approaches to multi-objective optimization, i.e. dominance, extensions of dominance, decomposition, and indicator algorithms. The model parameters are trained from data obtained running the algorithms with various population sizes on enumerable MNK-landscapes with 3, 4, 5 and 6 objectives. We show ways to interpret and use the model parameter values in order to analyze the population dynamics according to selected features. For example, we are interested in knowing how parameter values change for a given population size with the increase of the number of objectives. We also show a graphical representation capturing in one graph how the parameters magnitude and sign relate to the connections between states.

References

[1]

Hernán Aguirre, Arnaud Liefooghe, Sébastien Verel, and Kiyoshi Tanaka. 2014. An Analysis on Selection for High-Resolution Approximations in Many-Objective Optimization. In Parallel Problem Solving from Nature - PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13--17, 2014. Proceedings. 487--497.

Google Scholar

[2]

Hernán Aguirre, Akira Oyama, and Kiyoshi Tanaka. 2013. Adaptive ϵ-Sampling and ϵ-Hood for Evolutionary Many-Objective Optimization. In Evolutionary Multi-Criterion Optimization: 7th International Conference, EMO 2013, Sheffield, UK, March 19--22, 2013. Proceedings. 322--336.

Crossref

Google Scholar

[3]

Hernán Aguirre and Kiyoshi Tanaka. 2004. Insights on properties of multiobjective MNK-landscapes. In Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753), Vol. 1. 196--203 Vol.1.

Crossref

Google Scholar

[4]

Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T. Meyarivan. 2000. A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. In Parallel Problem Solving from Nature PPSN VI: 6th International Conference Paris, France, September 18--20, 2000 Proceedings. 849--858.

Digital Library

Google Scholar

[5]

Nikolaus Hansen and Andreas Ostermeier. 2001. Completely Derandomized Self-Adaptation in Evolution Strategies. Evol. Comput. 9, 2 (June 2001), 159--195.

Digital Library

Google Scholar

[6]

Hisao Ishibuchi, Noritaka Tsukamoto, and Yusuke Nojima. 2008. Evolutionary many-objective optimization: A short review. In 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence). 2419--2426.

Crossref

Google Scholar

[7]

Günter Rudolph". 1994. Convergence analysis of canonical genetic algorithm. IEEE Transactions on Neural Networks 5, 1 (1994), 96--101.

Digital Library

Google Scholar

[8]

Christian von Lücken, Benjamín Barán, and Carlos Brizuela. 2014. A survey on multi-objective evolutionary algorithms for many-objective problems. Computational Optimization and Applications 58, 3 (2014), 707--756.

Digital Library

Google Scholar

[9]

Michael D. Vose. 1995. Modeling Simple Genetic Algorithms. Evol. Comput. 3, 4 (Dec. 1995), 453--472.

Digital Library

Google Scholar

[10]

Qingfu Zhang and Hui Li. 2007. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation 11, 6 (Dec 2007), 712--731.

Digital Library

Google Scholar

[11]

Eckart Zitzler and Simon Künzli. 2004. Indicator-Based Selection in Multiobjective Search. In Parallel Problem Solving from Nature - PPSN VIII: 8th International Conference, Birmingham, UK, September 18--22, 2004. Proceedings. 832--842.

Google Scholar

Cited By

View all

Monzón HAguirre HVerel SLiefooghe ADerbel BTanaka K(2020)Dynamic Compartmental Models for Large Multi-objective Landscapes and Performance EstimationEvolutionary Computation in Combinatorial Optimization10.1007/978-3-030-43680-3_7(99-113)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1007/978-3-030-43680-3_7
Monzón HAguirre HVerel SLiefooghe ADerbel BTanaka KAuger AStützle T(2019)Dynamic compartmental models for algorithm analysis and population size estimationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326912(2044-2047)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326912
Monzón HAguirre HVerel SLiefooghe ADerbel BTanaka KTakadama K(2018)Studying MOEAs dynamics and their performance using a three compartmental modelProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3205739(191-192)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3205739
Show More Cited By

Index Terms

Closed state model for understanding the dynamics of MOEAs
1. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Discrete optimization
        Optimization with randomized search heuristics
        Evolutionary algorithms

Recommendations

Studying MOEAs dynamics and their performance using a three compartmental model
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

The road to a better design of multi- and many-objective evolutionary algorithms requires a deeper understanding of their behavior. A step on this road has recently been taken with the proposal of compartmental models to study population dynamics. In ...
Pareto dominance-based MOEAs on problems with difficult pareto set topologies
GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Despite the extensive application of multi-objective evolutionary algorithms (MOEAs) to solve multi-objective optimization problems (MOPs), understanding their working principles is still open to research. One of the most popular and successful MOEA ...
Studying com partmental models interpolation to estimate MOEAs population size
GECCO '19: Proceedings of the Genetic and Evolutionary Computation Conference Companion

Dynamical compartmental models capture the population dynamics of Multi-objective Optimization Evolutionary Algorithms. In these models, solutions at each generation are classified in compartments according to Pareto dominance. The size of each model ...

Comments

Information & Contributors

Information

Published In

GECCO '17: Proceedings of the Genetic and Evolutionary Computation Conference

July 2017

1427 pages

ISBN:9781450349208

DOI:10.1145/3071178

General Chair:
Peter A. N. Bosman
Centrum Wiskunde & Informatica (CWI)

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '17

Sponsor:

SIGEVO

GECCO '17: Genetic and Evolutionary Computation Conference

July 15 - 19, 2017

Berlin, Germany

Acceptance Rates

GECCO '17 Paper Acceptance Rate 178 of 462 submissions, 39%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
63
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Monzón HAguirre HVerel SLiefooghe ADerbel BTanaka K(2020)Dynamic Compartmental Models for Large Multi-objective Landscapes and Performance EstimationEvolutionary Computation in Combinatorial Optimization10.1007/978-3-030-43680-3_7(99-113)Online publication date: 15-Apr-2020
https://dl.acm.org/doi/10.1007/978-3-030-43680-3_7
Monzón HAguirre HVerel SLiefooghe ADerbel BTanaka KAuger AStützle T(2019)Dynamic compartmental models for algorithm analysis and population size estimationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3326912(2044-2047)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3326912
Monzón HAguirre HVerel SLiefooghe ADerbel BTanaka KTakadama K(2018)Studying MOEAs dynamics and their performance using a three compartmental modelProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3205739(191-192)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3205739
Derbel BLiefooghe AZhang QVerel SAguirre HTanaka KTakadama K(2018)A set-oriented MOEA/DProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205575(617-624)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205575

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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Studying MOEAs dynamics and their performance using a three compartmental model

Pareto dominance-based MOEAs on problems with difficult pareto set topologies

Studying com partmental models interpolation to estimate MOEAs population size

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations