research-article

Theoretical analysis of diversity mechanisms for global exploration

Authors:

Tobias Friedrich,

Pietro S. Oliveto,

Carsten WittAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 945 - 952

https://doi.org/10.1145/1389095.1389276

Published: 12 July 2008 Publication History

Abstract

Maintaining diversity is important for the performance of evolutionary algorithms. Diversity mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the global exploration capabilities of mutation-based algorithms. Using a simple bimodal test function and rigorous runtime analyses, we compare well-known diversity mechanisms like deterministic crowding, fitness sharing, and others with a plain algorithm without diversification. We show that diversification is necessary for global exploration, but not all mechanisms succeed in finding both optima efficiently.

References

[1]

N. Chaiyaratana, T. Piroonratana, and N. Sangkawelert. Effects of diversity control in single-objective and multi-objective genetic algorithms. Journal of Heuristics, 13(1):1--34, 2007.]]

Digital Library

[2]

S. Fischer and I. Wegener. The one-dimensional Ising model: Mutation versus recombination. Theoretical Computer Science, 344(2-3):208--225, 2005.]]

Digital Library

[3]

T. Friedrich, N. Hebbinghaus, and F. Neumann. Rigorous analyses of simple diversity mechanisms. In Proc. of GECCO '07, pages 1219--1225. ACM Press, 2007.]]

Digital Library

[4]

O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem. In Proc. of STACS '03, pages 415--426. Springer, 2003.]]

Digital Library

[5]

D. E. Goldberg, C. Van Hoyweghen, and B. Naudts. From twomax to the Ising model: Easy and hard symmetrical problems. In Proc. of GECCO '02, pages 626--633. Morgan Kaufmann, 2002.]]

[6]

B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, 14:502--525, 1982.]]

[7]

J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57--85, 2001.]]

Digital Library

[8]

T. Jansen and I. Wegener. Evolutionary algorithms: How to cope with plateaus of constant fitness and when to reject strings of the same fitness. IEEE Transactions on Evolutionary Computation, 5(6):589--599, 2001.]]

Digital Library

[9]

T. Jansen and I. Wegener. Real royal road functions: where crossover provably is essential. Discrete Applied Mathematics, 149(1-3):111--125, 2005.]]

Digital Library

[10]

S. W. Mahfoud. Niching methods. In T. Bäck, D. B. Fogel, and Z. Michalewicz, editors, Handbook of Evolutionary Computation, pages C6.1:1-4. Institute of Physics Publishing and Oxford University Press, Bristol, New York, 1997.]]

[11]

P. Oliveto, J. He, and X. Yao. Population-based evolutionary algorithms for the vertex cover problem. In Proc. of CEC '08, 2008.]]

[12]

P. S. Oliveto, J. He, and X. Yao. Computational complexity analysis of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4(3):281--293, 2007.]]

[13]

M. Pelikan and D. E. Goldberg. Genetic algorithms, clustering, and the breaking of symmetry. In Proc. of PPSN VI, pages 385--394. Springer, 2000.]]

Digital Library

[14]

T. Storch and I. Wegener. Real royal road functions for constant population size. Theoretical Computer Science, 320:123--134, 2004.]]

Digital Library

[15]

D. Sudholt. Crossover is provably essential for the Ising model on trees. In Proc. of GECCO '05, pages 1161--1167. ACM Press, 2005.]]

Digital Library

[16]

D. Sudholt. Memetic algorithms with variable-depth search to overcome local optima. In Proc. of GECCO '08, 2008. To appear.]]

Digital Library

[17]

R. K. Ursem. Diversity-guided evolutionary algorithms. In Proc. of PPSN VII, pages 462--471. Springer, 2002.]]

Digital Library

[18]

C. Witt. Runtime analysis of the (μ+1) EA on simple pseudo-Boolean functions. Evolutionary Computation, 14(1):65--86, 2006.]]

Digital Library

Cited By

Hadikhani PLai DOng W(2024)Human Activity Discovery With Automatic Multi-Objective Particle Swarm Optimization Clustering With Gaussian Mutation and Game TheoryIEEE Transactions on Multimedia10.1109/TMM.2023.326660326(420-435)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TMM.2023.3266603
Mukhlish FPage JBain M(2018)Evolutionary-learning framework: improving automatic swarm robotics designInternational Journal of Intelligent Unmanned Systems10.1108/IJIUS-06-2018-00166:4(197-215)Online publication date: 8-Oct-2018
https://doi.org/10.1108/IJIUS-06-2018-0016
Bhattacharya M(2016)Evolutionary Landscape and Management of Population DiversityCombinations of Intelligent Methods and Applications10.1007/978-3-319-26860-6_1(1-18)Online publication date: 28-Jan-2016
https://doi.org/10.1007/978-3-319-26860-6_1
Show More Cited By

Index Terms

Theoretical analysis of diversity mechanisms for global exploration
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Rigorous analyses of simple diversity mechanisms
GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

It is widely assumed and observed in experiments that the use of diversity mechanisms in evolutionary algorithms may have a great impact on its running time. Up to now there is no rigorous analysis pointing out the use of different mechanisms with ...
Analysis of diversity-preserving mechanisms for global exploration*

Maintaining diversity is important for the performance of evolutionary algorithms. Diversity-preserving mechanisms can enhance global exploration of the search space and enable crossover to find dissimilar individuals for recombination. We focus on the ...
Comparison of simple diversity mechanisms on plateau functions

It is widely assumed and observed in experiments that the use of diversity mechanisms in evolutionary algorithms may have a great impact on its running time. Up to now there is no rigorous analysis pointing out how different diversity mechanisms ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
253
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hadikhani PLai DOng W(2024)Human Activity Discovery With Automatic Multi-Objective Particle Swarm Optimization Clustering With Gaussian Mutation and Game TheoryIEEE Transactions on Multimedia10.1109/TMM.2023.326660326(420-435)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TMM.2023.3266603
Mukhlish FPage JBain M(2018)Evolutionary-learning framework: improving automatic swarm robotics designInternational Journal of Intelligent Unmanned Systems10.1108/IJIUS-06-2018-00166:4(197-215)Online publication date: 8-Oct-2018
https://doi.org/10.1108/IJIUS-06-2018-0016
Bhattacharya M(2016)Evolutionary Landscape and Management of Population DiversityCombinations of Intelligent Methods and Applications10.1007/978-3-319-26860-6_1(1-18)Online publication date: 28-Jan-2016
https://doi.org/10.1007/978-3-319-26860-6_1
Segura CCoello CMiranda GLeón C(2015)Using multi-objective evolutionary algorithms for single-objective constrained and unconstrained optimizationAnnals of Operations Research10.1007/s10479-015-2017-z240:1(217-250)Online publication date: 22-Sep-2015
https://doi.org/10.1007/s10479-015-2017-z
Doncieux SMouret J(2014)Beyond black-box optimization: a review of selective pressures for evolutionary roboticsEvolutionary Intelligence10.1007/s12065-014-0110-x7:2(71-93)Online publication date: 3-Jul-2014
https://doi.org/10.1007/s12065-014-0110-x
Akhtar Awais Koshul (2013)Putting Peirce's Theory to the Test: Peircean Evolutionary AlgorithmsTransactions of the Charles S. Peirce Society10.2979/trancharpeirsoc.49.2.20349:2(203)Online publication date: 2013
https://doi.org/10.2979/trancharpeirsoc.49.2.203
Črepinšek MLiu SMernik M(2013)Exploration and exploitation in evolutionary algorithmsACM Computing Surveys10.1145/2480741.248075245:3(1-33)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1145/2480741.2480752
Gießen CAlba E(2013)Hybridizing evolutionary algorithms with opportunistic local searchProceedings of the 15th annual conference on Genetic and evolutionary computation10.1145/2463372.2463475(797-804)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2463372.2463475
Akhtar JKoshul BAwais M(2013)A framework for evolutionary algorithms based on Charles Sanders Peirce's evolutionary semioticsInformation Sciences: an International Journal10.1016/j.ins.2013.02.044236(93-108)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1016/j.ins.2013.02.044
Segura CCoello Coello CMiranda GLeón C(2013)Using multi-objective evolutionary algorithms for single-objective optimization4OR10.1007/s10288-013-0248-x11:3(201-228)Online publication date: 4-Oct-2013
https://doi.org/10.1007/s10288-013-0248-x
Show More Cited By

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.

Figures

Tables

Media

View Table of Conten