2016/06/10 by Chao Qian, Yang Yu, Qian, Chao +3 · 1 citation
Computer Science · #Advanced Multi-Objective Optimization Algorithms #Computational Complexity (cs.CC) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.1606.03326
openalex publication_date 2016/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Evolutionary algorithms (EAs) are population-based general-purpose optimization algorithms, and have been successfully applied in various real-world optimization tasks. However, previous theoretical studies often employ EAs with only a parent or offspring population and focus on specific problems. Furthermore, they often only show upper bounds on the running time, while lower bounds are also necessary to get a complete understanding of an algorithm. In this paper, we analyze the running time of the (μ+λ)-EA (a general population-based EA with mutation only) on the class of pseudo-Boolean functions with a unique global optimum. By applying the recently proposed switch analysis approach, we prove the lower bound Ω(n ln n+ μ+ λnlnln n/ ln n) for the first time. Particularly on the two widely-studied problems, OneMax and LeadingOnes, the derived lower bound discloses that the (μ+λ)-EA will be strictly slower than the (1+1)-EA when the population size μ or λ is above a moderate order. Our results imply that the increase of population size, while usually desired in practice, bears the risk of increasing the lower bound of the running time and thus should be carefully considered.