Distribution Estimation Algorithm Based On Discrete Optimization Problems And Application Research

Estimation of distribution algorithms, combining with Genetic Algorithmsand the knowledge of statistical studies, is a class of novel evolutionaryalgorithms based on the probability models in the field of evolutionarycomputation. According to the information of the individuals in the superiorpopulation, the model of probability is built. Then a new population can begenerated by sampling from this model of probability. This process improvesthe solution iteratively.In this paper, the ideas such as chi-square distribution in bivariate marginaldistribution algorithm and Bayesian statistical inference, are introduced toimproving the way of building the probability model. The proposed algorithm isused to solve the traveling salesman problem. In this paper, the mainachievement is as follow:1. Based on chi-square distribution theory, a new bivariate correlationestimation of distribution algorithm is proposed. Firstly, the correlation betweenvariables is calculated through chi-square distribution, and the adjacentrelationship between the two variables is concluded by statistical superiorpopulation. Then the probability model for optimization problems is establishedthrough combined the correlation with the adjacent relationship，and is used forguiding new populations generated. The proposed algorithm is used to solvetraveling salesman problem，and the simulation results show that the algorithmhas a better performance.2. The theory of Bayesian statistical inference is used to set up the model ofprobability, and a new estimation of distribution algorithm is proposed. Firstly,the prior distribution probability model of the samples is built by estimating theinformation of individuals. Then, the correlation between variables is calculatedthrough chi-square distribution, and the adjacent relationship between twovariables is concluded by statistical superior population. The conditional distribution probability model is built by combining the correlation with theadjacent relationship. Lastly, the posterior distribution probability model isobtained, through the bayesian formula, to guiding new populations generated.Meanwhile，the algorithm is applied to the traveling salesman problem, whichverify the validity of the algorithm.3. The simulation experiments in three different estimation of distributionalgorithms whose probability model is built through three different ways havebeen done. The simulation results show that the way of establishing probabilitymodel could affect the performance of algorithm.