research-article

Theoretical analysis of genetic algorithms in noisy environments based on a Markov Model

Author:

Takehiko NakamaAuthors Info & Claims

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

Pages 1001 - 1008

https://doi.org/10.1145/1389095.1389283

Published: 12 July 2008 Publication History

Abstract

In this study, we take a first step towards theoretically analyzing genetic algorithms (GAs) in noisy environments using Markov chain theory. We explicitly construct a Markov chain that models GAs applied to fitness functions perturbed by either additive or multiplicative noise that takes on finitely many values, and we analyze the chain to investigate the transition and convergence properties of the GAs. For the additive case, our analysis shows that GAs eventually (i.e., as the number of iterations goes to infinity) find at least one globally optimal solution with probability 1. In contrast, GAs may eventually with probability 1 fail to do so in the multiplicative case, and we establish a condition that is both necessary and sufficient for eventually finding a globally optimal solution. In addition, our analysis shows that the chain has a stationary distribution that is also its steady-state distribution. Based on this property, we derive an upper bound for the number of iterations sufficient to ensure with certain probability that a GA has reached the set of globally optimal solutions and continues to include in each subsequent population at least one globally optimal solution whose observed fitness value is greater than that of any suboptimal solution.

References

[1]

D. V. Arnold. Noisy Optimization with Evolution Strategies. Kluwer Academic Publishers, Boston, 2002.]]

Digital Library

[2]

H. G. Beyer. Evolutionary algorithms in noisy environments: theoretical issues and guidelines for practice. Computer Methods in Applied Mechanics and Engineering, 186:239--267, 2000.]]

[3]

A. Chen, K. Subprasom, and Z. Ji. A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem. Optimization and Engineering, 7:225--247, 2006.]]

[4]

T. E. Davis and J. Principe. A Markov chain framework for the simple genetic algorithm. Evolutionary Computation, 1:269--288, 1993.]]

Digital Library

[5]

A. Di Pietro, L. White, and L. Barone. Applying evolutionary algorithms to problems with noisy, time-consuming fitness functions. In Proceedings of the 2004 Congress on Evolutionary Computation, volume 2, pages 1254--1261, 2004.]]

[6]

D. E. Goldberg and M. W. Rudnick. Genetic algorithms and the variance of fitness. Complex Systems, 5:265--278, 1991.]]

[7]

W. E. Hopkins. Optimal stabilization of families of linear stochastic differential equations with jump coefficients and multiplicative noise. SIAM Journal on Control and Optimization, 25:1587--1600, 1987.]]

Digital Library

[8]

Y. Jin and J. Branke. Evolutionary optimization in uncertain environments|a survey. IEEE Transactions on Evolutionary Computation, 3:303--317, 2005.]]

Digital Library

[9]

S. Karlin and H. M. Taylor. A Second Course in Stochastic Processes. Academic Press, New York, 1981.]]

[10]

K. S. Leung, Q. H. Duan, Z. B. Xu, and C. K. Wong. A new model of simulated evolutionary computation|convergence analysis and specifications. IEEE Transactions on Evolutionary Computation, 5:3--16, 2001.]]

Digital Library

[11]

B. L. Miller and D. E. Goldberg. Genetic algorithms, selection schemes, and the varying effects of noise. Evolutionary Computation, 4:113--131, 1996.]]

Digital Library

[12]

V. Nissen and J. Propach. On the robustness of population-based versus point-based optimization in the presence of noise. IEEE Transactions on Evolutionary Computation, 2:107--119, 1998.]]

Digital Library

[13]

A. Nix and M. D. Vose. Modeling genetic algorithm with Markov chains. Annals of Mathematics and Artificial Intelligence, 5:27--34, 1992.]]

[14]

J. A. Primbs. Portfolio optimization applications of stochastic receding horizon control. In Proceedings of the 2007 American Control Conference, volume 1, pages 1811--1816, 2007.]]

[15]

L. I. Rudin and S. Osher. Total variation based image restoration with free local constraints. In Proceedings of the 2004 International Conference on Image Processing, volume 1, pages 31--35, 2004.]]

[16]

G. Rudolph. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, 5:96--101, 1994.]]

Digital Library

[17]

J. Suzuki. A Markov chain analysis on simple genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 25:655--659, 1995.]]

[18]

M. D. Vose. The Simple Genetic Algorithm. MIT Press, Cambridge, Massachusetts, 1999.]]

Digital Library

[19]

M. D. Vose and G. E. Liepins. Punctuated equilibria in genetic search. Complex Systems, 5:31--44, 1991.]]

Cited By

Wang XWang YShi XGao LLi P(2021)A probabilistic multimodal optimization algorithm based on Buffon principle and Nyquist sampling theorem for Noisy EnvironmentApplied Soft Computing10.1016/j.asoc.2020.107068(107068)Online publication date: Feb-2021
https://doi.org/10.1016/j.asoc.2020.107068
Jebalia MAuger AHansen N(2018)Log-Linear Convergence and Divergence of the Scale-Invariant (1+1)-ES in Noisy EnvironmentsAlgorithmica10.5555/3118791.311928859:3(425-460)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.5555/3118791.3119288
Nakama T(2018)Markov chain analysis of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noiseComputational Optimization and Applications10.1007/s10589-010-9371-151:2(601-622)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s10589-010-9371-1
Show More Cited By

Index Terms

Theoretical analysis of genetic algorithms in noisy environments based on a Markov Model
1. Mathematics of computing
  1. Probability and statistics
2. Theory of computation
  1. Design and analysis of algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Markov decision processes

Recommendations

Markov chain analysis of genetic algorithms in a wide variety of noisy environments
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

We examine the convergence properties of genetic algorithms (GAs) in a wide variety of noisy environments where fitness perturbation can occur in any form for example, fitness functions can be concurrently perturbed by additive and multiplicative noise. ...
Markov chain analysis of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noise

We analyze the transition and convergence properties of genetic algorithms (GAs) applied to fitness functions perturbed concurrently by additive and multiplicative noise. Both additive noise and multiplicative noise are assumed to take on finitely many ...
Comparison of a crossover operator in binary-coded genetic algorithms

Genetic algorithms (GAs) represent a method that mimics the process of natural evolution in effort to find good solutions. In that process, crossover operator plays an important role. To comprehend the genetic algorithms as a whole, it is necessary to ...

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

10
Total Citations
View Citations
206
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang XWang YShi XGao LLi P(2021)A probabilistic multimodal optimization algorithm based on Buffon principle and Nyquist sampling theorem for Noisy EnvironmentApplied Soft Computing10.1016/j.asoc.2020.107068(107068)Online publication date: Feb-2021
https://doi.org/10.1016/j.asoc.2020.107068
Jebalia MAuger AHansen N(2018)Log-Linear Convergence and Divergence of the Scale-Invariant (1+1)-ES in Noisy EnvironmentsAlgorithmica10.5555/3118791.311928859:3(425-460)Online publication date: 31-Dec-2018
https://dl.acm.org/doi/10.5555/3118791.3119288
Nakama T(2018)Markov chain analysis of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noiseComputational Optimization and Applications10.1007/s10589-010-9371-151:2(601-622)Online publication date: 30-Dec-2018
https://dl.acm.org/doi/10.1007/s10589-010-9371-1
Allmendinger RKnowles J(2014)Ephemeral Resource Constraints in OptimizationEvolutionary Constrained Optimization10.1007/978-81-322-2184-5_4(95-134)Online publication date: 14-Dec-2014
https://doi.org/10.1007/978-81-322-2184-5_4
Jiang JMeng LXu X(2012)The Study on Convergence and Convergence Rate of Genetic Algorithm Based on an Absorbing Markov ChainApplied Mechanics and Materials10.4028/www.scientific.net/AMM.239-240.1511239-240(1511-1515)Online publication date: Dec-2012
https://doi.org/10.4028/www.scientific.net/AMM.239-240.1511
Jebalia MAuger AHansen N(2010)Log-Linear Convergence and Divergence of the Scale-Invariant (1+1)-ES in Noisy EnvironmentsAlgorithmica10.1007/s00453-010-9403-359:3(425-460)Online publication date: 16-Apr-2010
https://doi.org/10.1007/s00453-010-9403-3
Nakama T(2009)Transition and convergence properties of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noiseProceedings of the Eleventh conference on Congress on Evolutionary Computation10.5555/1689599.1689953(2662-2669)Online publication date: 18-May-2009
https://dl.acm.org/doi/10.5555/1689599.1689953
Gorissen DDhaene TTurck F(2009)Evolutionary Model Type Selection for Global Surrogate ModelingThe Journal of Machine Learning Research10.5555/1577069.175585410(2039-2078)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.5555/1577069.1755854
Nakama TRothlauf F(2009)Markov chain analysis of genetic algorithms in a wide variety of noisy environmentsProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570015(827-834)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570015
Nakama T(2009)Transition and convergence properties of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noise2009 IEEE Congress on Evolutionary Computation10.1109/CEC.2009.4983276(2662-2669)Online publication date: May-2009
https://doi.org/10.1109/CEC.2009.4983276

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