Runtime Analysis of Evolutionary Diversity Optimization and the Vertex Cover Problem
Wanru Gao, Mojgan Pourhassan, Frank Neumann · 2015
Using evolutionary algorithms to generate a diverse set of solutions where all of them meet a given quality criteria has gained increasing interest in recent years. In order to gain theoretical insights on the working principle of population-based evolutionary algorithms for this kind of diversity optimization a first runtime analysis has been presented by Gao and Neumann [1] on the example problems OneMax and LeadingOnes. We continue this line of research and examine the diversity optimization process of population-based evolutionary algorithms on complete bipartite graphs for the classical vertex cover problem.