Advanced Tutorials - Runtime Analysis of Population-Based Evolutionary Algorithms

Dive into an advanced tutorial on the runtime analysis of population-based evolutionary algorithms. Explore the heart of evolutionary algorithms through a comprehensive examination of population dynamics. Gain insights into the 20-year-old rich theory of runtime analysis, also known as time-complexity analysis, which aims to demonstrate how evolutionary algorithms' performance depends on parameter settings and fitness landscape characteristics. Learn about techniques for analyzing evolutionary algorithms with realistic population sizes, moving beyond simplified models like the (1+1) EA. Begin with an overview of population-based evolutionary algorithms, stochastic selection mechanisms, and selection pressure measurement. Delve into specialized techniques for population analysis, including random family trees, branching processes, drift and concentration of measure in populations, and level-based analyses. Investigate fundamental questions about the necessity of populations for efficient optimization, the balance between exploration and exploitation, and factors determining an evolutionary algorithm's tolerance for uncertainty. Presented by Per Kristian Lehre and Pietro Simone Oliveto at GECCO 2021, this 2-hour 13-minute tutorial covers topics such as introduction to evolution algorithms, blackbox optimization, drift analysis, nonelitistic generational evolution algorithms, and the level-based theorem.