On the Convergence of an Estimation of Distribution Algorithm Based on Linkage Discovery and Factorization

posted 11/23/05


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

S. V. P. M. Sandeep Pulavarty
Computer Science Dept.  Univ. of Montana Missoula, MT 59812 USA
sandeep_pulavarty@yahoo.com

Abstract

Estimation of distribution algorithms construct an explicit model
of the problem to be solved, and then use this model to guide the
search for good solutions.  For an important class of fitness functions,
namely those with $k$-bounded epistasis, it is possible to construct
a complete explicit representation of the fitness function by
sampling the fitness function.  A very natural model of the
problem to be solved is the Boltzmann distribution of the fitness
function, which is an exponential of the fitness normalized to
a probability distribution.  As the exponentiation factor
(inverse temperature) of the Boltzmann distribution is increased,
probability is increasingly concentrated on the set of optimal points.
We show that for fitness functions of $k$-bounded epistasis
that satisfy an additional property called the running intersection
property, an explicit computable exact factorization of the Boltzmann
distribution with an arbitrary exponentiation factor can be constructed.
This factorization allows the Boltzmann distribution to be efficiently
sampled, which leads to an algorithm which finds the optimum
with high probability.