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

Authors

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

DOI:

https://doi.org/10.5540/03.2018.006.02.0314

Keywords:

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

Abstract

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.

Downloads

Download data is not yet available.

Published

2018-12-19

Issue

Section

Trabalhos Completos