Research On Multiobjective Evolution Optimization For Traveling Salesman Problem

Traveling Salesman Problem(TSP)is a kind of classical combinatorial optimization problem.Many problems in scientific research and engineering calculation can be described as TSP.It is important to study the algorithm for solving this problem.The differential evolution(DE)and evolutionary multi-objective optimization methods of the TSP problem are researched in this paper.The major works are organized as follows:Firstly,the differential evolution algorithm performs outstandingly in solving continuous optimization problems,but there is less applied in TSP combinatorial optimization problems.To simulate the evolutionary mechanism of differential evolution algorithms better,a discrete differential evolution algorithm(DDE)for solving TSP is proposed.Different from the arithmetic operators used in traditional DE,DDE uses the position ordinal number of the city in the individual to guide individual mutation and crossover,and a simplified strategy of 2-opt is used for local search to improve the solution in the population.We also prove that DDE converges to the global optimal solution with a probability of 1 by Markov theory.Secondly,taking into account the implicit adaptive diversity retention mechanism of the multi-objective evolutionary algorithm(MOEA)population evolution process,a bi-objective optimization model for solving TSP is established in this paper,and a multi-objective evolutionary algorithm(NSGAII-TSP)is proposed for solving TSP.The algorithm uses a Non-dominated Sorting Genetic Algorithm II(NSGA-II)as the MOEA framework,using a strategy that turns different feasible solutions within the same path length into evaluation of mutually exclusive feasible solutions.The candidate solutions are generated by embedding the discrete differential evolution operator to NSGA-II in DDE.Finally,numerical simulations show that compared the existing algorithm,the new solution algorithm has stronger robustness and better abilities of global optimization,which is an effective algorithm for solving TSP.