A Polynomial Time Evolution Algorithm for the Traveling Salesman Problem

Author

Dang, Jianwu ; Zhang, Zhenhai

Author_Institution

Coll. of Inf. & Electr. Eng., Lanzhou Jiaotong Univ.

Volume

1

fYear

2005

Firstpage

47

Lastpage

49

Abstract

A genetic algorithm simulating evolution is proposed to yield near optional solution to the traveling salesman problem. Noting that Darwinian evolution is itself optimization process, we propose a heuristic algorithm that incorporates the tents of natural selection. The time complexity of this algorithm is equivalent to the fastest sorting scheme. The algorithm is used to solve the China - traveling salesman problem, the shortest route is obtained in this paper

Keywords

computational complexity; genetic algorithms; transportation; travelling salesman problems; Darwinian evolution; genetic algorithm; heuristic algorithm; optimization process; polynomial time evolution algorithm; time complexity; traveling salesman problem; Cities and towns; Clocks; Genetic algorithms; Genetic mutations; Heuristic algorithms; Iterative algorithms; Organisms; Polynomials; Sorting; Traveling salesman problems; evolution; neural network; time complexity; traveling salesman problem;

fLanguage

English

Publisher

ieee

Conference_Titel

Neural Networks and Brain, 2005. ICNN&B '05. International Conference on

Conference_Location

Beijing

Print_ISBN

0-7803-9422-4

Type

conf

DOI

10.1109/ICNNB.2005.1614565

Filename

1614565