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

research-article

Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change

Authors:

Pietro S. Oliveto,

Christine ZargesAuthors Info & Claims

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

Pages 837 - 844

https://doi.org/10.1145/2463372.2463478

Published: 06 July 2013 Publication History

Abstract

Evolutionary dynamic optimisation has become one of the most active research areas in evolutionary computation. We consider the BALANCE function for which the poor performance of the (1+1) EA at low frequencies of change has been shown in the literature. We analyse the impact of populations and diversity mechanisms towards the robustness of evolutionary algorithms with respect to frequencies of change. We rigorously prove that for each population size mu, there exists a sufficiently low frequency of change such that the (μ+1) EA without diversity requires expected exponential time. Furthermore we prove that a crowding as well as a genotype diversity mechanism do not help the (μ+1) EA. On the positive side we prove that, independent of the frequency of change, a fitness-diversity mechanism turns the runtime from exponential to polynomial. Finally, we show how a careful use of fitness-sharing together with a crowding mechanism is effective already with a population of size 2.

References

[1]

A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics. World Scientific Review, 2011.

Digital Library

[2]

J. Branke. Evolutionary Optimization in Dynamic Environments. Kluwer Academic Publishers, 2002.

Digital Library

[3]

C. Cruz, J. Gonzales, and D. Pelta. Optimization in dynamic environments: a survey on problems, methods and measures. Soft Computing, 15(7):1427--1448, 2011.

Digital Library

[4]

S. Droste. Analysis of the (1 + 1) EA for a dynamically changing onemax-variant. In Proc. of CEC'02, pages 55--60. IEEE Press, 2002.

[5]

S. Droste. Analysis of the (1 + 1) EA for a dynamically bitwise changing onemax. In Proc. of GECCO '03, LNCS 2723, pages 909--921. Springer, 2003.

Digital Library

[6]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science, 276:51--81, 2002.

Digital Library

[7]

T. Friedrich, N. Hebbinghaus, and F. Neumann. Comparison of simple diversity mechanisms on plateau functions. Theoretical Computer Science, 410(26):2455--2462, 2009.

Digital Library

[8]

T. Friedrich, P. S. Oliveto, D. Sudholt, and C. Witt. Analysis of diversity-preserving mechanisms for global exploration. Evolutionary Computation, 17(4):455--476, 2009.

Digital Library

[9]

C.-K. Goh and K. C. Tan. Evolutionary Multi-objective Optimization in Uncertain Environments. Springer, 2009.

Digital Library

[10]

D. E. Goldberg. Genetic Algorithms for Search, Optimization, and Machine Learning. Addison-Wesley, 1989.

Digital Library

[11]

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

Digital Library

[12]

T. Jansen. Analyzing Evolutionary Algorithms. The Computer Science Perspective. Springer, 2013.

Digital Library

[13]

T. Jansen and U. Schellbach. Theoretical analysis of a mutation-based evolutionary algorithm for a tracking problem in the lattice. In Proc. of GECCO '05, pages 841--848. ACM Press, 2005.

Digital Library

[14]

T. Jansen and R. P. Wiegand. The cooperative coevolutionary (1 + 1) EA. Evolutionary Computation, 12(4):405--434, 2004

Digital Library

[15]

Y. Jin and J. Branke. Evolutionary optimization in dynamic environments -- a survey. IEEE Transactions on Evolutionary Computation, 9(3):1427--1448, 2005.

Digital Library

[16]

T. Kötzing and H. Molter. Aco beats EA on a dynamic pseudo-boolean function. In Proc. of PPSN'12, LNCS 7491, pages 113--122. Springer, 2012.

Digital Library

[17]

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. IOP Publishing and Oxford University Press, 1997.

[18]

R. W. Morrison. Designing Evolutionary Algorithms for Dynamic Environments. Springer, 2004.

Digital Library

[19]

F. Neumann, P. S. Oliveto, and C. Witt. Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In Proc. of GECCO '09, pages 835--842. ACM Press, 2009.

Digital Library

[20]

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

Digital Library

[21]

T. T. Nguyen, S. Yang, and J. Branke. Evolutionary dynamic optimization: a survey of the state of the art. Swarm and Evolutionary Computation, 6:1--24, 2012.

[22]

P. S. Oliveto, J. He, and X. Yao. Analysis of population-based evolutionary algorithms for the vertex cover problem. In Proc. of CEC '08, pages 1563--1570. IEEE Press, 2008.

[23]

P. Rohlfshagen, P. K. Lehre, and X. Yao. Dynamic evolutionary optimisation: an analysis of frequency and magnitude of change. In Proc. of Gecco '09, pages 1713--1720. ACM Press, 2009.

Digital Library

[24]

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

Digital Library

[25]

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

Digital Library

[26]

S. Yang. Non-stationary problem optimization using the primal-dual genetic algorithm. In Proc. of CEC '03, pages 2246--2253. IEEE Press, 2003.

Cited By

Lv ZBian CQian CSun YLi XHandl J(2024)Runtime Analysis of Population-based Evolutionary Neural Architecture Search for a Binary Classification ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654003(358-366)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654003
Liu YZhou AZhang HTakadama K(2018)Termination detection strategies in evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205466(1063-1070)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205466
Lissovoi AWitt C(2016)MMAS Versus Population-Based EA on a Family of Dynamic Fitness FunctionsAlgorithmica10.1007/s00453-015-9975-z75:3(554-576)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00453-015-9975-z
Show More Cited By

Index Terms

Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change

Evolutionary dynamic optimisation has become one of the most active research areas in evolutionary computation. We consider the Balance function for which the poor expected performance of the ( 1 + 1 ) EA at low frequencies of change has been shown in ...
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 ...
On the benefits and risks of using fitness sharing for multimodal optimisation
Abstract
Fitness sharing is a well-known diversity mechanism inspired by the idea that individuals in the population that are close to each other have to share their fitnesses in a similar way to how species in nature occupying the same ...

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

13
Total Citations
View Citations
120
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lv ZBian CQian CSun YLi XHandl J(2024)Runtime Analysis of Population-based Evolutionary Neural Architecture Search for a Binary Classification ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654003(358-366)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654003
Liu YZhou AZhang HTakadama K(2018)Termination detection strategies in evolutionary algorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205466(1063-1070)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205466
Lissovoi AWitt C(2016)MMAS Versus Population-Based EA on a Family of Dynamic Fitness FunctionsAlgorithmica10.1007/s00453-015-9975-z75:3(554-576)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1007/s00453-015-9975-z
Neumann FWitt C(2015)On the runtime of randomized local search and simple evolutionary algorithms for dynamic makespan schedulingProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832747.2832771(3742-3748)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832747.2832771
Jansen TZarges C(2015)Analysis of randomised search heuristics for dynamic optimisationEvolutionary Computation10.1162/EVCO_a_0016423:4(513-541)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1162/EVCO_a_00164
Davila JEsparcia-Alcázar A(2015)An Empirical Comparison of Genetically Evolved Programs and Evolved Neural Networks for Multi-agent Systems Operating under Dynamic EnvironmentsProceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739482.2764717(1373-1374)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739482.2764717
Kötzing TLissovoi AWitt CHe JJansen TOchoa GZarges C(2015)(1+1) EA on Generalized Dynamic OneMaxProceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII10.1145/2725494.2725502(40-51)Online publication date: 17-Jan-2015
https://dl.acm.org/doi/10.1145/2725494.2725502
Oliveto PZarges C(2015)Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of changeTheoretical Computer Science10.1016/j.tcs.2014.10.028561:PA(37-56)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.1016/j.tcs.2014.10.028
Jansen TZarges CArnold D(2014)Evolutionary algorithms and artificial immune systems on a bi-stable dynamic optimisation problemProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598344(975-982)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598344
Oliveto PSudholt DArnold D(2014)On the runtime analysis of stochastic ageing mechanismsProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598328(113-120)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598328
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.

Media

Figures

Other

Tables

View Table of Contents