Interactive genetic algorithms for the traveling salesman problem
Sushil J. Louis, Rilun Tang · 1999
We use an interactive genetic algorithm to divide and conquer large traveling salesperson problems. Current genetic algorithm approaches are computationally intensive and may not produce acceptable tours within the time available. Instead of applying a genetic algorithm to the entire problem, we let the user interactively decompose a problem into subproblems, let the genetic algorithm separately solve these subproblems and then interactively connect subproblem solutions to get a global tour for the original problem. Our approach significantly reduces the computing time to find high quality solutions for large traveling salesperson problems. We believe that an interactive approach can be extended to other visually decomposable problems. 1 INTRODUCTION The traveling salesperson problem (TSP) is a classical example of an NP-Hard combinatorial optimization problem (Garey and Johnson, 1979). Given N cities and distances among them, the aim is to find the shortest tour that visits each cit...