Building a Better Heuristic for the Traveling Salesman Problem: Combining Edge Assembly Crossover and Partition Crossover

Autor(es)

Sanches, Danilo ; Whitley, Darrell ; Tinos, Renato ; ACM

• Tipo de documento: Artigo Científico
• Fonte: PROCEEDINGS OF THE 2017 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE (GECCO'17); v. N/A, p. 8-pg., 2017-01-01.

Resumo

A genetic algorithm using Edge Assemble Crossover (EAX) is one of the best heuristic solvers for large instances of the Traveling Salesman Problem. We propose using Partition Crossover to recombine solutions produced by EAX. Partition Crossover is a powerful deterministic recombination that is highly exploitive. When Partition Crossover decomposes two parents into q recombining components, partition crossover returns the best of 2(q) reachable offspring. If two parents are locally optimal, all of the offspring are also locally optimal in a hyperplane subspace that contains the two parents. One disadvantage of Partition Crossover, however, is that it cannot generate new edges. By contrast, the EAX operator is highly explorative; it not only inherits edges from parents, it also introduces new edges into the population of a genetic algorithm. Using both EAX and Partition Crossover together produces better performance, with improved exploitation and exploration. (AU)

• Processo FAPESP: 15/06462-1 - Recombinação por decomposição em computação evolutiva
• Beneficiário: Renato Tinós
• Modalidade de apoio: Auxílio à Pesquisa - Regular