NI Xuanming, ZHAO Qiaochu, HUANG Song, YU Lian
Journal of Systems Science & Complexity.
Accepted: 2024-08-19
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 $(\mu,\lambda)$ 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, we 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.