Interactive Genetic Algorithms for the Traveling Salesman Problem

Sushil J. Louis
Genetic Adaptive Systems Lab
Dept. of Computer Science/171
University of Nevada, Reno
Reno, NV 89557
sushil@cs.unr.edu
Rilun Tang
Genetic Adaptive Systems Lab
Dept. of Computer Science/171
University of Nevada, Reno
Reno, NV 89557
tang@cs.unr.edu

Abstract:

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.