An adaptive genetic algorithm with double populations for solving traveling salesman problems

Abstract

Traveling salesman problem (TSP) is a typical combinatorial optimization problem which is regarded as an NP (nondeterministic polynomial)-hard problem. When the TSP in a large scale are solved by traditional optimization methods, the computation is large, the iteration time is long, and the result may not be optimal. The genetic algorithm is a highly favored optimization algorithm, but due to the lack of diversity in population and genetic individuals, it also has the same limitations when solving large-scale TSPs. In order to improve the solving speed and solution accuracy of TSPs, an adaptive genetic algorithm with double populations (DPAGA) is proposed. A dominant population and an auxiliary population are introduced in the algorithm. The algorithm distinguishes genetic individuals into male and female individuals, and only heterosexual individuals can perform crossover operations. The dominant population and auxiliary population execute different adaptive crossover and mutation strategies during the evolution process. The DPAGA is used to solve TSPs; the experimental results prove that it is completely feasible, and its convergence speed and solution quality have been improved. When solving the TSPs with scales of 20, 30 and 50 cities, the optimal path lengths of DPAGA were reduced by the maximum of 0.2491, 9.1071 and 15.7086, respectively, compared with other optimization algorithms.

Keywords

• traveling salesman problem
• adaptive genetic algorithm
• dominant population
• auxiliary population