Evolutionary Algorithms For Traveling Salesman Problems

Evolutionary algorithms are new kinds of modern optimization algorithms which are inspired by the principle of nature evolution. As new kinds of random search algorithms, they have some advantages such as global search ability, implicit parallelism, robustness, simple operation and so on. In the recent decades, evolutionary algorithms have a wide range of applications in the area of combinatorial optimization. They have been used to solve many classical combinatorial optimization problems (e.g. Traveling Salesman Problem) and show their good performance and effectiveness.Firstly, a new evolution strategy based on clustering and local search scheme is proposed for some kind of large-scale traveling salesman problems in which the cities can be classified into several groups and in each group the cities crowd together. This algorithm is then proved to converge to the global optimal solution with probability 1.Secondly, a new evolutionary algorithm is proposed to deal with the symmetric traveling salesman problems. In this new algorithm, a new crossover operator and a new mutation operator are designed to generate offspring. Then a local search scheme is used to improve the solutions. Also, the global convergence with probability 1 of the proposed algorithm is proved.Finally, the simulation results show the effectiveness of the two proposed algorithms.