Uma proposta de algoritmo genético híbrido para o problema do caixeiro viajante

Abstract

Resumo: Este trabalho apresenta a implementação de um Algoritmo Genético (AG) adaptado e um AG híbrido com a heurística 3-Opt para resolver o Problema do Caixeiro Viajante (PCV). Modificações nas regras internas de funcionamento de um AG clássico foram realizadas, transformando-o na versão denominada AGA (AG Adaptado) que posteriormente foi hibridizada por meio da versão denominada AGAH (AG Adaptado e Híbrido Com 3-Opt). Também são propostos três novos operadores genéticos de cruzamento (Cortes Não Paralelos com 4 Trechos (CNP4), Máxima Preservação Heurística (MPH) e Máxima Preservação Heurística - Versão b (MPHb)). O operador CNP4 foi associado ao AGA e ao AGAH enquanto que o MPH e o MPHb foram implementados somente para o AGAH com a finalidade de contribuir com o ajuste fino das soluções. A heurística 3-Opt também foi incorporada ao AGAH, o que lhe conferiu o caráter híbrido. Esta heurística foi modificada para considerar a ordem com que as cidades são escolhidas ao realizar trocas de arestas inerentes a aplicação da mesma. O critério apresentado determina a ordem das cidades, ranqueando-as por duas medidas estatísticas: a distância média de cada cidade aos seus vizinhos mais próximos e o desvio padrão obtido do mesmo conjunto de vizinhos. Para validar a eficácia das modificações, propô-se 4 versões de AGs (AG Trechos, AG Rinap, AG Acs, AG Padronizar) contendo as modificações individualmente. O desempenho destas versões foi comparado ao desempenho de um AG clássico e, na sequência, elas foram agrupadas para formar o AGA, cujo desempenho também foi avaliado. Para validar a eficiência do AGAH foram realizados testes computacionais com a biblioteca de problemas disponível na internet e conhecida como Traveling Salesman Problem Library (TSPLIB). Os resultados encontrados foram comparados aos obtidos pelo algoritmo LK-H de Helsgaun (2000) que representa uma das mais poderosas heurísticas para resolução do PCV. O AGAH se mostrou muito eficaz para instâncias com até 400 cidades, chegando a encontrar a solução ótima em 100% das execuções para instâncias em que o LK-H não apresentou o mesmo sucesso. A qualidade das soluções para problemas maiores foi inferior às obtidas pelo LK-H, principalmente devido a restrições de tempo de processamento. Ao final são recomendadas ações para trabalhos futuros que podem tanto melhorar o tempo de execução quanto a qualidade das soluções para instâncias de grande porte, também são sugeridos testes para avaliar se as adaptações presentes no AGA agregam melhor desempenho aos AGs em outras aplicações. Palavras-chave: Otimização Combinatória. Programação Matemática. Métodos Heurísticos. Problema do Caixeiro Viajante.

Abstract: This work presents the implementation of a adapted Genetic Algorithm (GA) and one GA hybrid with the 3-Opt heuristic to solve the Traveling Salesman Problem (TSP). Changes in the rules of procedure of a classic GA were made, turning it into the version denominated as AGA (Adapted GA) which was subsequently hybridized generating AGAH (adapted GA hybrid with 3-Opt). It is also proposed three new crossing genetic operators (Non Parallel Cuts with 4 Stretches (CNP4), Maximum Heuristic Preservation (MPH) and Maximum Heuristic Preservation version b (MPH-b)). The operator CNP4 was associated with AGA and AGAH while MPH and MPH-b were implemented only to AGAH for contributing to the fine adjustment of the solutions. The 3-Opt heuristic was also incorporated to AGAH, which confers it the hybrid character. This heuristic was modified to consider the order in which the cities are selected while performing the edges exchanges inherent to the application of itself. The criteria presented determines the order of the cities, ranking them by two statistical measures: the average distance of each city to its closest neighbors and the standard deviation obtained from the same set of neighbors. In order to validate the efficiency of the modifications, it was proposed four version of GAs (GA Stretches, GA Rinap, GA Acs, GA Standardize) containing the modifications individually. The performance of these versions were compared to that of a classic GA and, subsequently, they were clustered to form AGA, whose performance was also evaluated. In order to validate the efficiency of AGAH is was conducted computational tests with the problem library available on the internet known as Traveling Salesman Problem Library (TSPLIB). The results obtained were compared to the ones acquired by the algorithm LK-H from Helsgaun (2000), which represents one of the most powerful heuristics for the resolution of the TSP. AGAH has proven to be very effective for instances with up to 400 cities, being able to find the optimal solution in 100% of the executions for instances in which LK H did not present the same result. The quality of solutions for larger problems was inferior to those obtained by LK-H, mostly due to restriction in processing time. In the end, actions are recommended for future works, which can improve both execution time and quality of solutions for large instances. Tests are also suggested to evaluate if the adaptations present in AGA aggregate better performance to the GAs in other applications. Key-words: Combinatorial Optimization. Mathematical Programming. Heuristic Methods. Traveling Salesman Problem.