This paper outlines a new approach to generating solutions to Traveling Salesman Problems. A new operator is introduced which recombinesthe edges (or links) between cities from two parents to create a single new offspring. This operator is different from past operators that emphasized edges in that 95compose the offspringare inherited from one of the two parents. The recombination operator does not use information about the distance between cities or any heuristic operators. This operator has foundknown solutions and matched "best known" solutions for every problem on which it has beentested. The functionality of this new operator can be explained using a variation on Holland's original schema theorem. Because this operator uses no information about the actualcost associated with edges and requires the use of no additional heuristics, it can also be usedon sequencing problems where there are no actual distances to measure, but rather only someoverall evaluation of the total sequence. An example is given of how this operator has beenused to generate job shop schedules.
@InProceedings{whitley:1989:sptsgero,
author = "Darrell L. Whitley and Timothy Starkweather and D'Ann
Fuquay",
title = "Scheduling Problems and Travelling Salesman: The
Genetic Edge Recombination Operator",
booktitle = "Proc. of the {T}hird {I}nt. {C}onf. on {G}enetic
{A}lgorithms",
editor = "J. David Schaffer",
year = "1989",
publisher = "Morgan Kaufmann",
address = "San Mateo, CA",
pages = "133--140",
}
This paper is the first proposal of the Genetic Edge Recombination operator. A more useful summary is probably the one in RefWhitleyEtAl1991.