Rule Coding for Genetic Algorithms: An Alternative Solution to the Traveling Salesman Problem

摘要

The Traveling salesman problem is well known in computer science and a good solution to it can be used to solve a large group of similar problems. There are numerous techniques for solving the traveling salesman problem using genetic algorithms, but most involve encoding and manipulating actual paths. Non-genetic algorithm approaches, however, rely on heuristics or various rules to find a short path. This paper proposes an approach that combines these two techniques. We will show that a good genetic algorithm solution to the traveling salesman problem using strings of heuristic rules instead of actual paths is not only possible, but quite successful. The ideas developed in this paper should prove very useful in the application of genetic algorithms to a wide range of minimization problems.