An Estimation of Distribution Algorithm Based on Maximum Entropy

posted 8/16/04


Alden H. Wright
Computer Science Dept.  Univ. of Montana Missoula, MT 59812 USA
wright@cs.umt.edu
(406) 243-4790

Riccardo Poli
Department of Computer Science, University of Essex, Colchester, UK

Chris Stephens
Instituto de Ciencias Nucleares, UNAM, Mexico DF 04510

W. B.  Langdon
Computer Science, University~College,~London

Sandeep Pulavarty
Computer Science Dept.  Univ. of Montana Missoula, MT 59812 USA


Abstract

Estimation of distribution algorithms (EDA) are similar to genetic
algorithms except that they replace crossover and mutation with sampling
from an estimated probability distribution.  We develop a framework for 
estimation of distribution algorithms based on the principle of maximum 
entropy and the conservation of schema frequencies.  An algorithm of this
type gives better performance than a standard genetic algorithm (GA) on a
number of standard test problems involving deception and epistasis 
(i. e. Trap and NK).