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

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