The Improved Genetic Algorithm And Estimation Of Distribution Algorithms To TSP Problem

Traveling salesman problem (TSP) is a classical combinatorial optimizationproblem. It is a predigested form of various complex problems. The searching space ofthe TSP problem as the number of cities increases, searching for the optimal solution inlarge space, often need a lot of solving time, therefore to seek a solution of short time,high precision of algorithm to solve the problem has become the research focus in thescientific research workers.In the process of study and research about the influence parameters of geneticalgorithm mainly has the quality of the initial population, population size, crossoverprobability and mutation probability values. Therefore,put forward a kind of improvedgenetic algorithm for solving TSP problems.Due to the basic genetic algorithm is based on schema theorem and "buildingblocks", When it is on a large number of building blocks to choose and restructuring,often lead to building blocks to break the fast, make the algorithm convergence and localoptimum. With the aid of introducing probability model evolutionary algorithmestimation of distribution algorithm for solving TSP problem is a very natural idea. Papermain research is as follows:（1）Towards the genetic algorithm for solving TSP problem, proposed to classifythe population according to the individual fitness, adopting the mode of subgroup forparallel breeding. Let the individuals with higher fitness to exploit the most optimalsolution to ensure the convergence of algorithm; Let the individuals with lower fitness toexplore new solution space to ensure the diversity of population.（2）This paper designs a combined crossover operator, that is PMX and heuristiccrossover operator, which can maintain the good mode of the parent and can producebetter children individuals in big probability.（3）In this paper, the thesis to the mutation operator is improved, using a hybridmutation algorithm.2-opt and a greedy inversion mutation operator.（4）Estimation of distribution algorithms is characterized by adopting the means ofstatistical learning, describes the solution distribution probability model is established.The method is effective to avoid the destruction of the building block problem in geneticalgorithm, for solving TSP problem provides a new kind of evolutionary algorithm.The improved genetic algorithm for TSP problem, embodies the algorithm to search for the best solution to the required time is shorter, and the advantage of high precision ofsolution. Estimation of distribution algorithms to solve TSP problem not only provides anew kind of evolutionary algorithm, but also expand the application range of distributionestimation algorithm.