Informações:

Publicações do PESC

Título
Um Enfoque Analógico para a Solução do Problema do Caixeiro Viajante Através do Método Elástico
Linha de pesquisa
Inteligência Artificial
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
26/2/1992
Resumo

É apresentada neste trabalho, uma versão modificada do Algoritmo Elástico denominada por Filtro, aplicada sobre um problema de otimização combinatória muito famoso, o problema do Caixeiro Viajante. Com o objetivo de reduzir o tempo de processamento do Algoritmo Elástico, desenvolveu-se uma modificação do mesmo, no sentido de minimizar o número de cálculos de distâncias necessários em cada iteração do algoritmo. A aplicação do método em vários conjuntos de cidades gerou resultados que foram comparados com aqueles gerados por outro algoritmo, implementado também neste trabalho, o algoritmo LK. Foi observado que tanto o Elástico quanto o Filtro geraram resultados piores que o LK, em termos de custo de tour, porém num tempo de processamento substancialmente melhor. Os testes foram desenvolvidos nas estações de trabalho SUN, utilizando a linguagem C como linguagem de programação.

Abstract

It is presented in this work, a modified version of Elastic Net denoted by the Filter. The method is applied to a classical problem in the field of combinatorial optimization, the Travelling Salesman Problem. The main computacional cost is in calculating the distances at each iteration. Concerned with the redution of the computational time required, it was proposed in this work, a minirnization of this calculation. The application of the method on random sets of cities, gives worse quality solutions, but much better computational times than another algorithm developed here, the LK. The tests have been performed on a workstation (SUN), utilizing the C language as programming tool.

Arquivo
Topo