Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
2014 Impact factor:

Evolutionary Computation

Winter 1993, Vol. 1, No. 4, Pages 313-333
(doi: 10.1162/evco.1993.1.4.313)
© 1993 by the Massachusetts Institute of Technology
Evolutionary Divide and Conquer (I): A Novel Genetic Approach to the TSP
Article PDF (1.1 MB)

Experiments with genetic algorithms using permutation operators applied to the traveling salesman problem (TSP) tend to suggest that these algorithms fail in two respects when applied to very large problems: they scale rather poorly as the number of cities n increases, and the solution quality degrades rapidly. We propose an alternative approach for genetic algorithms applied to hard combinatoric search which we call Evolutionary Divide and Conquer (EDAC). This method has potential for any search problem in which knowledge of good solutions for subproblems can be exploited to improve the solution of the problem itself. The idea is to use the genetic algorithm to explore the space of problem subdivisions rather than the space of solutions themselves. We give some preliminary results of this method applied to the geometric TSP.