Illinois Genetic Algorithms Laboratory

Some time ago I’ve read a few papers from Marc Toussaint from the University of Edinburgh, who proposes and discusses Compression Evolutionary Algorithms (CEAs). CEAs can be seen as an alternative to standard Estimation of Distribution Algorithms (EDAs), such as ECGA and BOA. Some papers can be found at Marc’s webpage.

The basic idea in EDAs is to ensure effective recombination by building and sampling a probabilistic model that encodes important interactions between problem variables. CEAs look at the same problem from another perspective. Specifically, CEAs map (or compress) the current representation so that the variables become independent (or nearly independent). As a result, simple univariate models or other simple recombination operators can be used to generate new strings and ensure effective exploration of the search space for nearly decomposable problems of limited order.