Convergence Analysis On Estimation Of Distribution Algorithm With Proportional Selection Schema

Estimation of distribution algorithm（EDA）is a kind of novel stochastic optimization algorithms.Up to now,impressive improvements and applications of EDA are fruitful,but there are only few rigorous theoretical analyses.In this situation,this paper studies the convergence of EDA from the view of the theory of probability and statistics.Mathematical description and strict proof of the convergence are presented.The main contents of this paper are as follows:1.The paper studies the convergence and convergence rate of theoretical model of EDA.For the theoretical model,we prove that the EDAs with proportional selection can converge to the global optimal set in probability.In the discrete case,we find that the convergence rate is determined by the ratio of the second maximum and the maximum value of the objective function.In the continuous case,the convergence rate of EDA is depended on the ratio of function values,which is a fix value within the e neighborhood of the optimum set and the max value of its complement set for the continuous objective function.For the iteration rule of probability densities in practical applications,the feasibility and effectiveness is verified by theoretical analysis and numerical experiments.2.In the second part,we study the population behavior of EDA based on the Markov chains theory.For the classic finite populations EDA with proportional selection（EDA-FP-PS）,we prove that it cannot converge to the global optimum in probability,but there exist the exact upper and lower bounds for the probability converging to the optimal solution set.Besides,we figure out the expression of the upper and lower bounds.For the modified EDA-FP-PS algorithm,we prove that the algorithm can converge to the global optimal set.Meanwhile,we investigate the mean fisrt hitting time（FIT）that the population reach to optimum set for classical and modified EDA-FP-PS.The mean FIT of modified EDA-FP-PS has the exact upper and lower bounds while the unconditional expectation FIT of classical EDA-FP-PS tends to infinity.3.Some simple numerical experiments are given to verify the theoretical analysis,the results are consistent with the theoretical analysis.The experimental results are as follows.When the population size reaches to a certain size（at least 8times of problem size）,the difference of optimal probability（the frequencies of the population trapped in the optimal set）is within 10^-2in different problem scale.For different test functions,the larger ratio of population size and problem size the bigger optimum probability,but the critical ratio reaching to the probability one is different.