A Rigorous Complexity Analysis of the (1+1) Evolutionary Algorithm for Separable Functions with Boolean Inputs

被引：62
|
作者：
Droste, Stefan [1 ]
Jansen, Thomas [1 ]
Wegener, Ingo [1 ]
机构：
[1] Univ Dortmund, FB Informat, D-44221 Dortmund, Germany
来源：
EVOLUTIONARY COMPUTATION | 1998年 / 6卷 / 02期
关键词：
Evolutionary algorithm; separable function; random walk; complexity analysis;
D O I：
10.1162/evco.1998.6.2.185
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Evolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In this paper a rigorous theoretical complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs is given. Different mutation rates are compared, and the use of the crossover operator is investigated. The main contribution is not the result that the expected run time of the (1 + 1) evolutionary algorithm is Theta(n ln n) for separable functions with n variables but the methods by which this result can be proven rigorously.
引用
收藏
页码：185 / 196
页数：12
相关论文
共 34 条
  • [11] Convergence Rate of the (1+1)-ES on Locally Strongly Convex and Lipschitz Smooth Functions
    Morinaga, Daiki
    Fukuchi, Kazuto
    Sakuma, Jun
    Akimoto, Youhei
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2024, 28 (02) : 501 - 515
  • [12] Improved Running Time Analysis of the (1+1)-ES on the Sphere Function
    Jiang, Wu
    Qian, Chao
    Tang, Ke
    INTELLIGENT COMPUTING THEORIES AND APPLICATION, PT I, 2018, 10954 : 729 - 739
  • [13] Running Time Analysis of the (1+1)-EA Using Surrogate Models on OneMax and LeadingOnes
    Zhang, Zi-An
    Bian, Chao
    Qian, Chao
    PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XVII, PPSN 2022, PT II, 2022, 13399 : 512 - 525
  • [14] VARIABLE SELECTION IN QSAR STUDIES .1. AN EVOLUTIONARY ALGORITHM
    KUBINYI, H
    QUANTITATIVE STRUCTURE-ACTIVITY RELATIONSHIPS, 1994, 13 (03): : 285 - 294
  • [15] An Evolutionary Algorithm with Masked Mutation for 0/1 Knapsack Problem
    Khan, Mozammel H. A.
    2013 INTERNATIONAL CONFERENCE ON INFORMATICS, ELECTRONICS & VISION (ICIEV), 2013,
  • [16] Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problem
    Shi, Feng
    Neumann, Frank
    Wang, Jianxin
    THEORETICAL COMPUTER SCIENCE, 2021, 893 : 159 - 175
  • [17] Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions
    周诗源
    彭雪
    王英林
    夏小云
    JournalofShanghaiJiaotongUniversity(Science), 2018, 23 (06) : 827 - 833
  • [18] Rigorous Running Time Analysis of a Simple Immune-Based Multi-Objective Optimizer for Bi-Objective Pseudo-Boolean Functions
    Zhou S.
    Peng X.
    Wang Y.
    Xia X.
    Journal of Shanghai Jiaotong University (Science), 2018, 23 (6) : 827 - 833
  • [19] XTALOPT version r 1 1: An open-source evolutionary algorithm for crystal structure prediction
    Avery, Patrick
    Falls, Zackary
    Zurek, Eva
    COMPUTER PHYSICS COMMUNICATIONS, 2018, 222 : 418 - 419
  • [20] Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights
    Xie, Yue
    Neumann, Aneta
    Neumann, Frank
    Sutton, Andrew M.
    PROCEEDINGS OF THE 2021 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'21), 2021, : 1187 - 1194
1234