A General Dichotomy of Evolutionary Algorithms on Monotone Functions

被引:29
作者
Lengler, Johannes [1 ]
机构
[1] Swiss Fed Inst Technol, Dept Comp Sci, CH-8092 Zurich, Switzerland
关键词
Runtime; Evolutionary computation; Genetic algorithms; Sociology; Statistics; Heuristic algorithms; Standards; Computational and artificial intelligence; evolutionary computation; genetic algorithms; DRIFT ANALYSIS; COMPLEXITY; SEARCH; BOUNDS; TIME;
D O I
10.1109/TEVC.2019.2917014
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
It is known that the (1 + 1)-EA with mutation rate c/n optimizes every monotone function efficiently if c < 1, and needs exponential time on some monotone functions (HOTTOPIC functions) if c >= 2.2. We study the same question for a large variety of algorithms, particularly for the (1 + lambda)-EA, (mu + 1)-EA, (mu + 1)-GA, their "fast" counterparts, and for the (1 + (lambda, lambda))-GA. We find that all considered mutation-based algorithms show a similar dichotomy for HOTTOPIC functions, or even for all monotone functions. For the (1 + (lambda, lambda))-GA, this dichotomy is in the parameter c gamma, which is the expected number of bit flips in an individual after mutation and crossover, neglecting selection. For the fast algorithms, the dichotomy is in m(2)/m(1), where m(1) and m(2) are the first and second falling moment of the number of bit flips. Surprisingly, the range of efficient parameters is not affected by either population size mu nor by the offspring population size lambda. The picture changes completely if crossover is allowed. The genetic algorithms (mu + 1)-GA and (mu+1)-fGA are efficient for arbitrary mutations strengths if mu is large enough.
引用
收藏
页码:995 / 1009
页数:15
相关论文
共 32 条
  • [1] Fitness Probability Distribution of Bit-Flip Mutation
    Chicano, Francisco
    Sutton, Andrew M.
    Whitley, L. Darrell
    Alba, Enrique
    [J]. EVOLUTIONARY COMPUTATION, 2015, 23 (02) : 217 - 248
  • [2] Standard Steady State Genetic Algorithms Can Hillclimb Faster Than Mutation-Only Evolutionary Algorithms
    Corus, Dogan
    Oliveto, Pietro S.
    [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2018, 22 (05) : 720 - 732
  • [3] Fast Genetic Algorithms
    Doerr, Benjamin
    Huu Phuoc Le
    Makhmara, Regis
    Ta Duy Nguyen
    [J]. PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'17), 2017, : 777 - 784
  • [4] Doerr B, 2018, ALGORITHMICA, V80, P1658, DOI 10.1007/s00453-017-0354-9
  • [5] Optimal Parameter Settings for the (1+(λ, λ)) Genetic Algorithm
    Doerr, Benjamin
    [J]. GECCO'16: PROCEEDINGS OF THE 2016 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2016, : 1107 - 1114
  • [6] A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
    Doerr, Benjamin
    Doerr, Carola
    [J]. GECCO'15: PROCEEDINGS OF THE 2015 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2015, : 1423 - 1430
  • [7] Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings
    Doerr, Benjamin
    Doerr, Carola
    [J]. GECCO'15: PROCEEDINGS OF THE 2015 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2015, : 1335 - 1342
  • [8] From black-box complexity to designing new genetic algorithms
    Doerr, Benjamin
    Doerr, Carola
    Ebel, Franziska
    [J]. THEORETICAL COMPUTER SCIENCE, 2015, 567 : 87 - 104
  • [9] Doerr B, 2013, GECCO'13: PROCEEDINGS OF THE 2013 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, P781
  • [10] Mutation Rate Matters Even When Optimizing Monotonic Functions
    Doerr, Benjamin
    Jansen, Thomas
    Sudholt, Dirk
    Winzen, Carola
    Zarges, Christine
    [J]. EVOLUTIONARY COMPUTATION, 2013, 21 (01) : 1 - 27