<p>In recent decades, significant advancements have been made in the rigorous runtime analysis of evolutionary algorithms (EAs). However, in the context of non-elitist EAs and the use of crossover, it is challenging to engage in any meaningful theoretical discussion due to the increasing complexity of the EA’s population distribution as the EA runs. This paper aims to gain insight into the rigorous runtime analysis of the (<i>μ</i>, <i>λ</i>) EA with crossover, focusing on its optimization of the JUMP test function, by investigating the population distribution during the optimization process. It is proposed that, under typical circumstances, the population distribution will first reach a stable and fully-diverged state before attaining the global optimum. Consequently, the optimization process is divided into two parts, based on whether the population distribution has reached this state. By investigating this state, the authors are able to provide a better upper bound on the runtime of the EA. Furthermore, a series of experiments were conducted to validate our theoretical results, which also offered insights into the impact of different parameters on this state.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Runtime Analysis in Non-Elitist Evolutionary Algorithms via Population Distribution

  • Xuanming Ni,
  • Qiaochu Zhao,
  • Song Huang,
  • Lian Yu

摘要

In recent decades, significant advancements have been made in the rigorous runtime analysis of evolutionary algorithms (EAs). However, in the context of non-elitist EAs and the use of crossover, it is challenging to engage in any meaningful theoretical discussion due to the increasing complexity of the EA’s population distribution as the EA runs. This paper aims to gain insight into the rigorous runtime analysis of the (μ, λ) EA with crossover, focusing on its optimization of the JUMP test function, by investigating the population distribution during the optimization process. It is proposed that, under typical circumstances, the population distribution will first reach a stable and fully-diverged state before attaining the global optimum. Consequently, the optimization process is divided into two parts, based on whether the population distribution has reached this state. By investigating this state, the authors are able to provide a better upper bound on the runtime of the EA. Furthermore, a series of experiments were conducted to validate our theoretical results, which also offered insights into the impact of different parameters on this state.