The Distribution Of The Maximum Entropy Estimation Algorithm And Its Application

Estimation of Distribution Algorithm (EDA) is currently a hot researchtopic in the field of evolutionary computation，which is a novel optimizationalgorithm. This paper reviews the development history and theory basis of EDA,and briefly introduces the development of the EDA and traveling salesmanproblem (TSP). Traditional EDA not only requires priori knowledge and largeamount of calculation, but also easily falls into local optimum situation when theproblem scale is larger in dealing with a problem. A new Maximum EntropyEstimation of Distribution Algorithm (MEEDA) is improved in this paper. Thetheory of the maximum entropy improves the distribution probability model andstrategy of generating a population. This paper applies the improved algorithmin solving TSP and makes a comparison with other EDA.The main contributions of this paper are as follows:1. A new Estimation of Distribution Algorithm based on maximum entropyprinciple is improved in this paper. Learning and reasoning on the principle ofthe maximum entropy and based on the idea of the maximum entropy principle,and through the entropy of random variables to estimate the probabilitydistribution, the maximum entropy distribution is under the condition of ensuresample statistic characteristics, by adjusting P(x) that is the probability densitydistribution of a random variable x to maximize the distribution of entropy H(x),to improve the distribution probability of the algorithm model and to generate apopulation strategy.2. The improved Maximum Entropy Estimation of Distribution Algorithmis applied to solve TSP. By studying and researching of the TSP, the simulationexperiments about some test case in the TSPLAB have been made by theMEEDA. And by comparing with other EDA, the effectiveness and stability ofthe proposed algorithm for TSP can be confirmed.The global search ability of the MEEDA is improved. The building of thisprobabilistic model no longer needs the Prior knowledge, but has to extractinformation from the selected advantage population and apply the maximum entropy principle to estimate the probabilistic distribution model of population.The amount of calculation of the algorithm reduces, so it improves theperformance of the algorithm effectively, and the probabilistic distributionmodel has good convergence and stability.