Study on a Polynomial Time Evolution Algorithm for the Travelling Salesman Problem
Jianwu Dang · 2001
A genetic algorithm simulating evolution is proposed to yield near-optional solution to the Travelling 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 alogrithm is used to solve the China-Travelling Salesman Problem, the shortest route is obtained in this paper.