View in EDS

Self-adjusting population sizes for the (1,λ)-EA on monotone functions.

Saved in:
Bibliographic Details
Title: Self-adjusting population sizes for the (1,λ)-EA on monotone functions.
Authors: Kaufmann, Marc1 (AUTHOR) marc.kaufmann@inf.ethz.ch, Larcher, Maxime1 (AUTHOR) larcherm@inf.ethz.ch, Lengler, Johannes1 (AUTHOR) johannes.lengler@inf.ethz.ch, Zou, Xun1 (AUTHOR) xun.zou@inf.ethz.ch
Source: Theoretical Computer Science. Nov2023, Vol. 979, pN.PAG-N.PAG. 1p.
Subjects: Evolutionary algorithms
Abstract: We study the (1 , λ) -EA with mutation rate c / n for c ≤ 1 , where the population size is adaptively controlled with the (1 : s + 1) -success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c = 1 is efficient on OneMax for s < 1 , but inefficient if s ≥ 18. Surprisingly, the hardest part is not close to the optimum, but rather at linear distance. We show that this behaviour is not specific to OneMax. If s is small, then the algorithm is efficient on all monotone functions, and if s is large, then it needs super-polynomial time on all monotone functions. In the former case, for c < 1 we show a O (n) upper bound for the number of generations and O (n log ⁡ n) for the number of function evaluations, and for c = 1 we show O (n log ⁡ n) generations and O (n 2 log ⁡ log ⁡ n) evaluations. We also show formally that optimization is always fast, regardless of s , if the algorithm starts in proximity of the optimum. All results also hold in a dynamic environment where the fitness function changes in each generation. An extended abstract, containing only the results without proofs, has been published at the PPSN conference [1]. [ABSTRACT FROM AUTHOR]
Copyright of Theoretical Computer Science is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:We study the (1 , λ) -EA with mutation rate c / n for c ≤ 1 , where the population size is adaptively controlled with the (1 : s + 1) -success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c = 1 is efficient on OneMax for s < 1 , but inefficient if s ≥ 18. Surprisingly, the hardest part is not close to the optimum, but rather at linear distance. We show that this behaviour is not specific to OneMax. If s is small, then the algorithm is efficient on all monotone functions, and if s is large, then it needs super-polynomial time on all monotone functions. In the former case, for c < 1 we show a O (n) upper bound for the number of generations and O (n log ⁡ n) for the number of function evaluations, and for c = 1 we show O (n log ⁡ n) generations and O (n 2 log ⁡ log ⁡ n) evaluations. We also show formally that optimization is always fast, regardless of s , if the algorithm starts in proximity of the optimum. All results also hold in a dynamic environment where the fitness function changes in each generation. An extended abstract, containing only the results without proofs, has been published at the PPSN conference [1]. [ABSTRACT FROM AUTHOR]
ISSN:03043975
DOI:10.1016/j.tcs.2023.114181