Applying Level Based Analysis to Optimal Mixing Evolutionary Algorithms.

Abstract

In recent years a new variant of Drift Analysis was introduced in the field of computational complexity called Level Based Analysis. The Level Based Analysis provides a one-size-fits-all framework to analyze Evolutionary Algorithms. This paper analyzes how the Level Based Theorem works and applies it to GOMEA algorithms to get upper bounds on their computational time complexity. The Univariate GOMEA algorithm will be analyzed on the Onemax domain using the Level Based Theorem and more traditional methods. This paper will compare the use and bounds of the Level Based Analysis with these more traditional methods and supply loose upper bounds for more GOMEA algorithms on different domains as benchmarks for future work.