Developing Partition Crossovers for Combinatorial Optimisation Problems

Abstract

Os operadores de recombinação desempenham um papel importante no desempenho de Algoritmos Evolucionários. Eles geram uma nova solução através da combinação de informação de outras duas soluções. O Problema da Recombinação Ótima (PRO) consiste na geração da melhor solução descendente segundo um dado operador. No entanto, em muitos casos este problema é NP-Difícil. Em particular, isto é verdade para o Problema do Caixeiro Viajante (PCV) quando se considera a recombinação com respeito e trasmissão de arestas.Os Cruzamentos de Partição são operadores de recombinação determinística que resolvem ou aproximam o PRO, explorando as decomposições naturais dos pais tendo em vista a geração de soluções de elevada qualidade, dadas essas decomposições.Geralmente, os Cruzamentos de Partição são combinados com operadores de procura local. As regras sobre as quais estes operadores funcionam definem a estrutura de vizinhança do espaço de procura. No entanto, não se sabe como é que os Cruzamentos de Partição se relacionam com esta estrutura de vizinhança. Mostramos que de facto todos os Cruzamentos de Partição podem ser geométricos sob alguma distância e que, para o caso particular dos Cruzamentos de Partição para o PCV existentes, eles são geométricos de acordo com a distância de bond.Adicionalmente, os Cruzamentos de Partição têm sido aplicados com sucesso em vários problemas de otimização. Apesar das diferenças entre problemas, a sua implementação segue um padrão comum que pode ser generalizado até certo ponto. Portanto, propomos uma Interface de Programação de Aplicações (IPA) para o desenvolvimento de cruzamentos de partição, que identifica claramente as suas operações fundamentais e separa a parte dependente do problema destes operadores, do resto do operador que é independente do problema.Tal IPA realça as relações entre componentes que surgem das decomposições das soluções involvidas e fornece oportunidades para melhorar os cruzamentos de partição existentes. Apresentamos uma análise experimental do Cruzamento de Partição GPX2 à luz do PRO e mostramos como é que a IPA proposta pode ser usada para o melhorar.

Recombination operators play an important role in the performance of Evolutionary Algorithms. They generate a new solution by combining information from other two parent solutions.The Optimal Recombination Problem (ORP) concerns the generation of the best possible offspring solution by a given operator. However, in many cases, this problem is NP-Hard. In particular, this is true for the Traveling Salesman Problem (TSP) when respectful, edge-transmitting recombination is considered.Partition crossovers are deterministic recombination operators that solve or approximate the ORP. They do so by exploiting natural decompositions of the parents in order to generate high-quality solutions given those decompositions. Partition Crossovers are usually combined with local search operators. The rules on which these operators operate define the neighbourhood structure of the search space. However, it is not known how Partition Crossovers relate to this neighbourhood structure. We show that indeed, all Partition Crossovers may be geometric under some distance and, for the particular case of current Partition Crossovers for the TSP, they are geometric for the bond distance.Moreover, partition crossovers have been successfully applied in several optimisation problems. Despite the differences between problems, their implementation follows a common pattern that is generalisable to some extent. Thus, we propose an API for the development of partition crossovers that clearly identifies their basic operations, and separates a problem-dependent part of these operators from the rest of the operator, which is problem-independent.Such an API brings focus to the relations between the components arising throught the decompositions of the solutions involved, and provide opportunities for improving existing partition crossovers. We present an experimental analysis of the GPX2 partition crossover in the light of the ORP, and show how the proposed API could be used to improve it.