Session:

ECT - Evolutionary Computation Theory

Title:

Feasible Approaches to Convergence Results for Evolutionary Algorithms Part II: Runtime analysis of evolutionary algorithms and summary

Authors:

Stefan Droste
Lothar M. Schmitt

Abstract:

Despite many successes of evolutionary algorithms (EAs) in real-world applications, theoretical knowledge in regard to these algorithms is still in its infancy. In this work, we discuss a number of approaches to theory for EAs in regard to strengths and weaknesses of statements for convergence-speed obtained with these methods. This includes the general convergence-analysis of a broad class of EAs in an arbitrary-fitness-function black-box scenario similar to the setting for the simulated annealing algorithm, and the runtime-analysis of specific EAs on limited classes of fitness-functions within the framework of asymptotic runtime-analysis for randomized algorithms. We propose that a suitable merger of ideas put forward through the latter two types of convergence-analysis may yield substantial progress towards understanding convergence behavior of EAs. In particular, this may yield a unified theoretical framework for EAs as well as probabilistic estimates for runtimes of EAs used in real-world applications.