Significance-based estimation-of-distribution algorithms
- Estimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based cGA (sig-cGA) optimizes the commonly regarded benchmark functions OneMax (OM), LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed stable compact genetic algorithm-an EDA that tries to prevent erratic model updates by imposing a bias to the uniformlyEstimation-of-distribution algorithms (EDAs) are randomized search heuristics that create a probabilistic model of the solution space, which is updated iteratively, based on the quality of the solutions sampled according to the model. As previous works show, this iteration-based perspective can lead to erratic updates of the model, in particular, to bit-frequencies approaching a random boundary value. In order to overcome this problem, we propose a new EDA based on the classic compact genetic algorithm (cGA) that takes into account a longer history of samples and updates its model only with respect to information which it classifies as statistically significant. We prove that this significance-based cGA (sig-cGA) optimizes the commonly regarded benchmark functions OneMax (OM), LeadingOnes, and BinVal all in quasilinear time, a result shown for no other EDA or evolutionary algorithm so far. For the recently proposed stable compact genetic algorithm-an EDA that tries to prevent erratic model updates by imposing a bias to the uniformly distributed model-we prove that it optimizes OM only in a time exponential in its hypothetical population size. Similarly, we show that the convex search algorithm cannot optimize OM in polynomial time.…
Author details: | Benjamin DoerrORCiDGND, Martin S. KrejcaORCiD |
---|---|
DOI: | https://doi.org/10.1109/TEVC.2019.2956633 |
ISSN: | 1089-778X |
ISSN: | 1941-0026 |
Title of parent work (English): | IEEE transactions on evolutionary computation |
Publisher: | Institute of Electrical and Electronics Engineers |
Place of publishing: | New York, NY |
Publication type: | Article |
Language: | English |
Date of first publication: | 2020/12/01 |
Publication year: | 2020 |
Release date: | 2023/05/15 |
Tag: | algorithm (EDA); benchmark testing; estimation-of-distribution; genetic algorithms; heuristic algorithms; history; logic; probabilistic; run time analysis; sociology; statistics; theory |
Volume: | 24 |
Issue: | 6 |
Number of pages: | 10 |
First page: | 1025 |
Last Page: | 1034 |
Funding institution: | Investissement d'avenir ProjectFrench National Research Agency (ANR); [ANR-11-LABX-0056-LMH]; LabEx LMH; COST ActionEuropean Cooperation in; Science and Technology (COST) [CA15140] |
Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer review: | Referiert |