Navegando por Autor "Prestes, álvaro Nunes"
Agora exibindo 1 - 1 de 1
- Resultados por página
- Opções de Ordenação
Dissertação Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante(Universidade Federal do Rio Grande do Norte, 2006-07-27) Prestes, álvaro Nunes; Gouvêa, Elizabeth Ferreira; Ramos, Iloneide Carlos de Oliveira; ; http://lattes.cnpq.br/0613948277011672; ; http://lattes.cnpq.br/2888641121265608; ; http://lattes.cnpq.br/3479036429463819; Goldbarg, Marco César; ; http://lattes.cnpq.br/1371199678541174; Oliveira, Carla Silva; ; http://lattes.cnpq.br/0691141675196929Devido à grande dificuldade de solução exata dos Problemas de Otimização Combinatória, vários métodos heurísticos têm sido desenvolvidos e durante muitos anos, a análise de desempenho dessas abordagens não foi realizada de maneira sistemática. A proposta deste trabalho é fazer uma análise estatística de abordagens heurísticas aplicadas ao Problema do Caixeiro Viajante. O foco da análise é avaliar o desempenho de cada abordagem em relação ao tempo computacional necessário até a obtenção da solução ótima para uma determinada instância do PCV. Para essa análise, foi utilizada uma metodologia estatística chamada Análise de Sobrevivência, auxiliada por métodos para o teste da hipótese de igualdade entre funções. Para uma melhor compreensão, as abordagens avaliadas foram divididas em três classes: Algoritmos Lin-Kernighan, Algoritmos Evolucionários e Algoritmos de Otimização por Nuvem de Partículas. Além das abordagens já existentes, foi incluído na análise, um algoritmo memético (para instâncias simétricas e assimétricas do PCV) que utiliza o algoritmo de Lin e Kernighan como procedimento de busca local