A new approach to the traveling salesman problem using genetic algorithms with priority encoding
Jyh-Da Wei, Dong-Hyun Lee · 2005
The traveling salesman problem is difficult to solve by traditional genetic algorithms because of the requirement that each node must be visited exactly once. In response to this critical requirement, many researchers used specialized operators to adapt traditional genetic algorithms. Although some of these operators are useful, they are ad hoc. We propose a priority-based encoding scheme instead. We assign priorities to all the edges and then perform a greedy algorithm to find a suboptimal solution. The greedy algorithm constructs a legal tour and the priority encoding makes it possible to follow traditional genetic evolution. This approach retains generality in applications and also gains remarkable experimental results.