Algoritmo memetico para o problema do caixeiro viajante assimetrico como parte de um framework para algoritmos evolutivos

Autor(es)

Luciana Salete Buriol

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Faculdade de Engenharia Elétrica e de Computação
• Data de defesa: 2000-02-21

Membros da banca

Paulo Morelato França; Felipe Martins Muller; Marco Aurelio Amaral Henriques

• Orientador: Paulo Morelato França

Resumo

Dentre a gama de técnicas heurísticas e exatas existentes para a resolução de problemas combinatórios, os algoritmos populacionais genéticos e meméticos têm se destacado devido a sua boa performance. Em especial, os algoritmos meméticos podem ser considerados atualmente como uma das técnicas melhores sucedidas para a resolução de vários problemas combinatórios, dentre eles, o problema do caixeiro viajante. Nesta dissertação será apresentado um algoritmo memético aplicado ao problema do caixeiro viajante assimétrico, com a proposta de uma nova busca local: Recursive Arc Insertion. Os resultados computacionais considerando as 27 instâncias assimétricas da TSPLIB são apresentados, analisados e comparados com resultados obtidos por outros métodos propostos para o problema. O mesmo algoritmo é também aplicado a 32 outras instâncias assimétricas e a 30 instâncias reduzidas do problema de ciclos hamiltonianos não direcionados. Um framework para algoritmos evolutivos é apresentado, já incluindo o algoritmo memético implementado e a redução de instâncias do problema de ciclos hamiltonianos não direcionados para o problema do caixeiro viajante simétrico. Além disso, dois geradores portáveis de instâncias com solução ótima conhecida são descritos: um para o problema do caixeiro viajante assimétrico e outro para o problema de ciclos hamiltonianos (AU)

• Processo FAPESP: 98/00707-5 - Desenvolvimento de uma estrutura, linguagem e ambiente de programacao para otimizacao evolutiva.
• Beneficiário: LUCIANA SALETE BURIOL
• Modalidade de apoio: Bolsas no Brasil - Mestrado