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

research-article

MMAS vs. population-based EA on a family of dynamic fitness functions

Authors:

Andrei Lissovoi,

Carsten WittAuthors Info & Claims

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Pages 1399 - 1406

https://doi.org/10.1145/2576768.2598301

Published: 12 July 2014 Publication History

Abstract

We study the behavior of a population-based EA and the Max-Min Ant System (MMAS) on a family of deterministically-changing fitness functions, where, in order to find the global optimum, the algorithms have to find specific local optima within each of a series of phases. In particular, we prove that a (2+1) EA with genotype diversity is able to find the global optimum of the Maze function, previously considered by Kötzing and Molter (PPSN 2012, 113--122), in polynomial time. This is then generalized to a hierarchy result stating that for every μ, a (μ+1) EA with genotype diversity is able to track a Maze function extended over a finite alphabet of μ symbols, whereas population size μ-1 is not sufficient. Furthermore, we show that MMAS does not require additional modifications to track the optimum of the finite-alphabet Maze functions, and, using a novel drift statement to simplify the analysis, reduce the required phase length of the Maze function.

References

[1]

Enrique Alba, Amir Nakib, and Patrick Siarry. Metaheuristics for Dynamic Optimization. Studies in Computational Intelligence. Springer, 2013.

Digital Library

[2]

Anne Auger and Benjamin Doerr, editors. Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific Publishing, 2011.

Digital Library

[3]

Benjamin Doerr and Sebastian Pohl. Run-time analysis of the (1

[4]

1) evolutionary algorithm optimizing linear functions over a finite alphabet. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012). ACM Press, 2012. 1317--1324.

Digital Library

[5]

Stefan Droste. Analysis of the (1+1) EA for a dynamically bitwise changing OneMax. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2003), pages 909--921. Springer, 2003.

Digital Library

[6]

Christian Gunia. On the analysis of the approximation capability of simple evolutionary algorithms for scheduling problems. In Hans-Georg Beyer and Una-May O'Reilly, editors, GECCO, pages 571--578. ACM, 2005.

Digital Library

[7]

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

[8]

Thomas Jansen and Ulf Schellbach. Theoretical analysis of a mutation-based evolutionary algorithm for a tracking problem in the lattice. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2005), pages 841--848. ACM Press, 2005.

Digital Library

[9]

Timo Kötzing and Hendrik Molter. Aco beats ea on a dynamic pseudo-boolean function. In Parallel Problem Solving from Nature-PPSN XII, pages 113--122. Springer, 2012.

Digital Library

[10]

Per Kristian Lehre and Carsten Witt. General drift analysis with tail bounds. Technical Report, arXiv:1307.2559, http://arxiv.org/abs/1307.2559, 2013.

[11]

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

Digital Library

[12]

Trung Thanh Nguyen, Shengxiang Yang, and Jürgen Branke. Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation, 6:1--24, 2012.

[13]

Pietro S. Oliveto and Christine Zarges. Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of change. In Proc. of the fifteenth annual conference on Genetic and Evolutionary Computation conference, pages 837--844. ACM, 2013.

Digital Library

[14]

Philipp Rohlfshagen, Per Kristian Lehre, and Xin Yao. Dynamic evolutionary optimisation: An analysis of frequency and magnitude of change. In Proc. of the Genetic and Evolutionary Computation Conference (GECCO 2009), pages 1713--1720. ACM Press, 2009.

Digital Library

[15]

Tobias Storch. On the choice of the parent population size. Evolutionary Computation, 16(4):557--578, 2008.

Digital Library

[16]

Thomas Stützle and Holger H. Hoos. Max-min ant system. Future Generation Comp. Syst., 16(8):889--914, 2000.

Digital Library

[17]

Dirk Sudholt. Using markov-chain mixing time estimates for the analysis of ant colony optimization. In Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, FOGA '11, pages 139--150, New York, NY, USA, 2011. ACM.

Digital Library

[18]

Carsten Witt. Fitness levels with tail bounds for the analysis of randomized search heuristics. Information Processing Letters, 114(1):38--41, 2014.

Digital Library

Cited By

Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Doerr BDoerr CKötzing T(2018)Static and Self-Adjusting Mutation Strengths for Multi-valued Decision VariablesAlgorithmica10.1007/s00453-017-0341-180:5(1732-1768)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0341-1
Doerr B(2017)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067713(389-412)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3067713
Show More Cited By

Index Terms

MMAS vs. population-based EA on a family of dynamic fitness functions
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the Utility of Island Models in Dynamic Optimization
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

A simple island model with λ islands and migration occurring after every τ iterations is studied on the dynamic fitness function Maze. This model is equivalent to a (1+λ) EA if τ=1, i.e., migration occurs during every iteration. It is proved that even ...
MMAS Versus Population-Based EA on a Family of Dynamic Fitness Functions

We study the behavior of a population-based EA and the Max---Min Ant System (MMAS) on a family of deterministically-changing fitness functions, where, in order to find the global optimum, the algorithms have to find specific local optima within each of ...
The choice of the offspring population size in the (1,λ) EA
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,λ) EA. We establish a sharp threshold at λ = log{\frac{e}{e-1}} n ≈5 log₁₀ n between exponential and polynomial running times on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

July 2014

1478 pages

ISBN:9781450326629

DOI:10.1145/2576768

Editor-in-chief:
Christian Igel
Ruhr University of Bochum, University of Copenhagen
,
General Chair:
Dirk V. Arnold
Dalhousie University

Copyright © 2014 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 the author(s) 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: 12 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '14

Sponsor:

SIGEVO

GECCO '14: Genetic and Evolutionary Computation Conference

July 12 - 16, 2014

BC, Vancouver, Canada

Acceptance Rates

GECCO '14 Paper Acceptance Rate 180 of 544 submissions, 33%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
107
Total Downloads

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

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BTakadama K(2018)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207889(389-414)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207889
Doerr BDoerr CKötzing T(2018)Static and Self-Adjusting Mutation Strengths for Multi-valued Decision VariablesAlgorithmica10.1007/s00453-017-0341-180:5(1732-1768)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s00453-017-0341-1
Doerr B(2017)Theory for non-theoreticiansProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3067713(389-412)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3067713
Doerr BDoerr CNeumann FSutton A(2016)Theory for Non-TheoreticiansProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2926982(463-482)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2926982
Doerr BDoerr CKoetzing TNeumann FSutton A(2016)The Right Mutation Strength for Multi-Valued Decision VariablesProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908891(1115-1122)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908891
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
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
Dang DJansen TLehre PEsparcia-Alcázar A(2015)Populations can be Essential in Dynamic OptimisationProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754808(1407-1414)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754808
Lissovoi AWitt CEsparcia-Alcázar A(2015)On the Utility of Island Models in Dynamic OptimizationProceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation10.1145/2739480.2754734(1447-1454)Online publication date: 11-Jul-2015
https://dl.acm.org/doi/10.1145/2739480.2754734

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