Alleles, loci, and the traveling salesman problem. (English) Zbl 0674.90095

Goldberg, David E.; Lingle, Robert jun.

Genetic algorithms and their applications, Proc. 1st Int. Conf., Pittsburgh/PA 1985, 154-159 (1988).

Summary: [For the entire collection see Zbl 0671.00021.]
We have examined a new type of crossover operator, partially-mapped crossover (PMX), for the exploration of codings where ordering and allele information may directly or indirectly effect fitness values. The mechanics of the operator have been described, and an ordering-only implementation has been presented in Pascal. The power of effect of the new operator has been analyzed using an extension to the concept of schemata called the o-schemata (ordering schemata). Simple counting arguments have been put forward which show the vast amount of information contained in the o-schemata, and survival probabilities have been estimated for o-schemata under the PMX operator. The result is an operation which preserves ordering building blocks (and allele building blocks if they are attached) so orderings and allele combinations may be explored with implicit parallelism.
The new operator is tested in an ordering-only problem, the traveling salesman problem. Using \(reproduction+PMX\) in two runs, optimal or very near optimal results are found in a well-known 10 city problem after exploring a small portion of the tour search space. We are continuing our work by testing the method in larger problems, but we are encouraged with the GA-like performance obtained on our first test.
This work has important implications for improving more general GA-search in problems where both allele combinations and ordering information are important. The binary operation of PMX does permit the randomized, yet structured, information exchange among both alleles and ordering building blocks which simple crossover promotes among allele schemata alone. This should assist us in our efforts to successfully apply genetic algorithms to ever more complex problems.

MSC:

90C35	Programming involving graphs or networks
68T05	Learning and adaptive systems in artificial intelligence

Keywords:

crossover operator; partially-mapped crossover; o-schemata; allele building blocks; traveling salesman

Citations:

Zbl 0671.00021