Probabilistic analysis of the (1+1)-evolutionary algorithm

2014/09/17 by Hsien-Kuei Hwang, Hsien‐Kuei Hwang, Alois Panholzer +10
Computer Science · Mathematics · #60C05 #60F06 #65Q30 (Secondary) #68W40 (Primary) #Advanced Multi-Objective Optimization Algorithms #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Probability (math.PR) #cs.DS #math.PR #msc:60C05 #msc:60F06 #msc:65Q30 #msc:68W40

paper · pdf · doi:10.48550/arxiv.1409.4955

53 pages with 8 figures and 4 appendices

arxiv created 2014/09/17 · openalex publication_date 2014/09/17 · arxiv updated 2014/09/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a detailed analysis of the cost used by the (1+1)-evolutionary algorithm. The problem has been approached in the evolutionary algorithm literature under various views, formulation and degree of rigor. Our asymptotic approximations for the mean and the variance represent the strongest of their kind. The approach we develop is also applicable to characterize the limit laws and is based on asymptotic resolution of the underlying recurrence. While most approximations have their simple formal nature, we elaborate on the delicate error analysis required for rigorous justifications.

Cited by

• Unbiased Black-Box Complexities of Jump Functions

Related

• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• A Reinforcement Learning Perspective on the Optimal Control of Mutation\n Probabilities for the (1+1) Evolutionary Algorithm: First Results on the\n OneMax Problem
• Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise
• Optimal Parameter Choices via Precise Black-Box Analysis
• Multiple-gain Estimation for Running Time of Evolutionary Combinatorial Optimization