An Improved Genetic Algorithm for the Traveling Salesman Problem

TIAN Yuan; PING Xue-Liang; BAI Liang-Liang; JIANG Yi

The traveling salesman problem concerns the best way to visit a set of cities and to minimize the length of the tour over all the cities. The problem is a typical NP-complete problem, which is of major importance in real world applications. An effective genetic algorithm is proposed for the problem in this paper, which combines elitist with the novel genetic algorithm. What’s more, tournament selection, partially mapped crossover (PMX) and 2-opt mutation are applied to evolve the individuals. Four testes (bays29, att48, kroa100 and pr137) from the TSPLIB are chosen as the text bed. The conducted experiments demonstrate that the combination of partially mapped crossover with 2-opt mutation greatly enhance the ability to find the global optimum. Compared with the simple genetic algorithm and the nearest neighbor algorithm the computation time, stability of global convergence and accuracy of the proposed algorithm are much better.

Select Volume / Issues:

• Volume 6,Issue 6, Nov. 2015

Year:

2015

Type of Publication:

Article

Keywords:

Traveling Salesman Problem; Genetic Algorithm; Partially Mapped Crossover; 2-Opt

Journal:

IJECCE

Volume:

6

Number:

6

Pages:

671-673

Month:

November