not all linear functions are equally difficult for the compact genetic algorithm
Estimation of distribution algorithms (EDAs) try to solve an optimization problem by finding a probability distribution focussed around its optima. For this purpose they conduct a sampling-evaluation-adjustment cycle, where search points are sampled with respect to a probability distribution, which is adjusted according to the evaluation of the sampled points. Although there are many successful experiments suggesting the usefulness of EDAs, there are only few rigorous theoretical results apart from convergence results without time bounds. Here we present first rigorous runtime analyses of a simple EDA, the compact genetic algorithm, for linear pseudo-boolean functions on n variables. We prove a number of results showing that not all linear functions have the same asymptotical runtime.
compact genetic algorithm runtime theoretical analysis