PROGRAMAÇÃO DISTRIBUIDA PARA OTIMIZAÇÃO DE HEURÍSTICA ILS APLICADA A PROBLEMAS DO CAIXEIRO VIAJANTE

Resumo

Atualmente há uma grande procura por técnicas que agilizam o processamento de algoritmos usados na resolução de problemas cujo tempo computacional cresce exponencialmente. Este trabalho tem o objetivo de analisar os tempos computacionais de uma solução proposta para o Problema do Caixeiro Viajante utilizando o algoritmo ILS com programação distribuída. A comunicação entre as máquinas é facilitada por meio de Socket TCP, viabilizando o compartilhamento de recursos e fornecendo sincronização no envio dos dados. Os resultados foram obtidos por meio da execução do algoritmo em 1, 10, 15 e 20 máquinas remotas utilizando três instâncias distintas, sendo estas providas da biblioteca TSPLIB. A contribuição para os diversos estudos relacionados com a otimização de tempos computacionais caracteriza a importância deste trabalho. Além disso, o mesmo aborda um modelo genérico e eficiente para distribuição de heurísticas baseadas em busca local.