Problema do Caixeiro Viajante abordado pelo Algoritmo de Evolução Diferencial

Danielle Durski Figueiredo, Carlos Ropelatto Fernandes, Alessandra Beatriz Pachas Zavala

Resumo


Os problemas de otimização classificados como N P -hard podem apresentar dificuldades quando são abordados com métodos exatos, especialmente nos casos de dimensões elevadas, uma vez que o tempo computacional necessário para a obtenção do valor ótimo global cresce exponencialmente à medida que os dados de entrada aumentam. Os algoritmos de Evolução Diferencial (ED) são poderosos algoritmos de otimização evolucionária, propostos inicialmente, para problemas em espaços contı́nuos. Recentemente, tem sido propostas adaptações ao seu mecanismo de mutação diferencial para aplicação em problemas combinatórios. Neste trabalho, uma proposta deste tipo de adaptação é apresentada para este algoritmo, para resolver o Problema do Caixeiro Viajante (PCV). O estudo dos PCV’s se relaciona diretamente com problemas organizacionais da sociedade. Testes computacionais foram realizados com instâncias da literatura e os resultados encontrados sugerem que a técnica proposta é promissora e apropriada para a resolução dos problemas abordados.


Palavras-chave


Otimização, Evolução Diferencial Discreta, Problema do Caixeiro Viajante.

Texto completo:

PDF


DOI: https://doi.org/10.5540/03.2018.006.02.0314

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 


Normas para publicação | Contato