Estimation of distribution algorithms on non-separable problems

Abstract

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.

Keywords:

• evolutionary algorithms
• order statistic
• stochastic convergence

2000 AMS Subject Classification :

• 68W20
• 68Q25
• 62G30

CCS Category :

• G.2.1. Combinatorial algorithms
• F.2.0

Acknowledgements

Part of this work was done while the author was with Fraunhofer Institute AIS, Sankt Augustin, Germany. The scientific support from Dr Heinz Mühlenbein and Dr Robin Höns is gratefully acknowledged.

Notes

In the binary case , so p _i (1, t) – abbrevivated p _i (t), or even p _i – characterizes completely the marginal probability on loci i.