Runtime Analysis for the Parameter-less Population Pyramid

Runtime analysis of black-box search algorithms provides rigorous performance guarantees, aiding in algorithm design and comparison. Unfortunately, deriving bounds can be challenging and as a result existing literature has focused on simplistic algorithms. The Parameter-less Population Pyramid (P3) is a recently proposed (Goldman and Punch, GECCO 2014) unbiased black-box search algorithm that combines local search, model based mixing, and population layering. In empirical studies P3 has outperformed leading genetic algorithms across a variety of problems. We provide a runtime analysis on n-bit problems to help shed light on the reason for P3's effectiveness. We derive upper runtime bounds of n+1 for linear functions, {n 2 +1} for LeadingOnes, and O(2 k n log(n/k)) for Concatenated Traps of size k. For a simplified version of P3 we obtain a bound of O(n log 3 n) for H-IFF. These results show P3 is competitive with the best known unbiased genetic algorithms on each of these problems, suggesting its performance generalizes well. Furthermore, we find that P3's effectiveness relies on all three of its major components, lending support to the algorithm's design.