An estimation of distribution algorithm based on linkage discovery and factorization
Sandeep Pulavarty · The Mathematics Enthusiast · 2005
Estim ation of D istribution Algorithm s (EDA) are a class of algorithms that con struct an explicit probabilistic m odel of distribution based on high fitness individ uals in the search space.N ew individuals are generated by sam pling this distribu tion.The generated individuals guide in constructing the probability distribution for next iteration.For a black box function w ith A-bounded epistasis that satis fies a property called running intersection property, we show that it is possible to determ ine the optim um w ith high probability.This is done by applying the linkage detection algorithm on the black box function, w hich gives an additively decom posable structure of the black box function.The Boltzmann distribution of a fitness function is the exponential of the fitness norm alized to a probability distri bution.The factorization of the Boltzmann distribution for the additively decom posable structure is then com puted by using the factorization theorem proposed by M iihlenbein et al.The constructed factorization is then sam pled to determ ine the optim um w ith high probability.As the exponentiation factor in Boltzmann distribution is increased, the probability will be concentrated near optim al points.