Title :
An Advanced Genetic Algorithm for Traveling Salesman Problem
Author :
Youping, Wang ; Liang, Li ; Lin, Chen
Author_Institution :
Coll. of Comput. Sci., Yangtze Univ., Jingzhou, China
Abstract :
By analyzing the deficiency of traditional genetic algorithm in solving the Traveling Salesman Problem, an improved genetic algorithm is proposed for TSP. In this paper, the ordinal real-number encoder is used for chromosome encoding and ordered crossover operators is advanced that utilizes local and global information to construct offspring. In order to guarantee global convergence, heuristic knowledge and self-learning is employed for mutation. Then, a city network which contains 31 city nodes is employed to test the algorithm. The simulation result of MATLAB shows that the proposed method can get feasible result with a higher convergent rate and success rate than existing heuristics.
Keywords :
convergence; genetic algorithms; travelling salesman problems; unsupervised learning; Matlab; advanced genetic algorithm; global convergence; heuristic knowledge; ordinal real-number encoder; self-learning; traveling salesman problem; Algorithm design and analysis; Biological cells; Cities and towns; Convergence; Encoding; Genetic algorithms; Genetic mutations; MATLAB; Testing; Traveling salesman problems; Genetic algorithm; crossover; heuristic knowledge; mutation;
Conference_Titel :
Genetic and Evolutionary Computing, 2009. WGEC '09. 3rd International Conference on
Conference_Location :
Guilin
Print_ISBN :
978-0-7695-3899-0
DOI :
10.1109/WGEC.2009.127
