Estimation of distribution algorithms on non-separable problems
Alexandru Agapie · International Journal of Computer Mathematics · 2008
The evolutionary algorithms discussed in this paper do not use crossover, nor mutation. Instead, they estimate and evolve a marginal probability distribution, the only distribution responsible for generating new populations of chromosomes. So far, the analysis of this class of algorithms was confined to proportional selection and additive decomposable functions. Dropping both assumptions, we consider here truncation selection and non-separable problems with polynomial number of distinct fitness values. The emergent modelling is half theoretical – with respect to selection, completely characterized by stochastic calculus – and half empirical – concerning the generation of new individuals. For the latter operator, we sample the chromosomes arbitrarily, one for each selected level of fitness. That is the break-symmetry point, making the difference between the finite and infinite population cases, and ensuring the convergence of the model.