We presented a new interactive genetic algorithm to solve the traveling salesperson problem. A user visually partitioned the TSP into sub-problems and the GA solved each subproblem separately. The user then visually recombined the sub-tours into a global tour. We tested this methodology with a set of TSPs benchmarks using a relatively untuned genetic algorithm and compared the results with the same GA running on the complete un-decomposed problem. The IGA takes much less time to provide better quality results for large problems. For TSPs with more than 200 cities, this methodology greatly reduced the running time.
Although we can divide and conquer problems where the cities are randomly distributed, non-random distributions amenable to clustering bring out the real strength of our approach. Clusters can be easily picked out and the interactive genetic algorithm can exploit this structure to quickly solve the problem. We believe that this method can be extended to other visualizable, decomposable problems. A Java version of the IGA can be found and used from http://gaslab.cs.unr.edu/.
We did not expend much effort in tuning our genetic algorithm for the TSP. Using a well-tuned GA or other search algorithm that quickly and near-optimally solves small TSPs (from our decomposition) should also result in better quality global tours [Jog et al., 1989]. We plan to investigate other interactive genetic algorithm applications.