Researching On The Estimation Of Distribution Algorithm And Its Application In TSP

Estimation of distribution algorithm(EDA) is a class evolutionary algorithm based on probability analysis, it combines the genetic algorithm with the knowledge of statistical studies, the EDA plays the advantages of both to solve the problem of “the building blocks” is damaged in genetic algorithm(GA). The EDA takes advantages of the individual structure information among the advantage groups, which is used to establish the probability distribution model,sampling from the probability model, a new population was generated, and so on., repeat this process, complete the evolution of the population. And finally find a satisfactory solution of the problem.In this paper, for the discrete complex optimization problems, the binomial probability distribution and the empirical Copula are introduced to the EDA,improving the establishment ways of the probability distribution model in algorithms, then the improved algorithm is applied to solve the traveling salesman problem(TSP).The binomial distribution is a kind of important discrete distribution. For the discrete complex optimization problems, we analyzed the feasibility of the probability model which is established by the binomial distribution in the discrete optimization problems. According to statistic the times of each variate in the relative position of the individual from the advantage group, the binomial probability is calculated to establish the probability model. Sampling from the probability model, a new population was generated. Finally, the EDA is applied to the TSP, the experimental results shows that the improved EDA has a better performance.Copula is a typical connection function, which can effectively describe the nonlinear relationship between variables. In view of existing constructed problems of two-dimensional Copula function, this paper proposes a new structure means of two-dimensional Copula based on F class function, And completed the theoretical derivation. In addition, this paper introduces the multidimensional Copula to the EDA. For the selected dominant groups, we usethe empirical distribution function to statistics the frequency of each variate,which performed as marginal distribution. Then, the marginal distribution by the empirical Copula connecting, we obtain a multidimensional joint probability distribution model. In the end, we guide the production of a new group through sampling from the probability model. So the EDA realized the evolutionary process. Finally we applies the EDA to the TSP. The simulation experimental results shows that the improved algorithm has a better performance in solving TSP.