Algoritmos Simulated Annealing em paralelo + Genético Grossover: um abordagem híbrida

Abstract

Problemas combinatorias são utilizados em muitas áreas de pesquisa, devido a sua simplicidade de compreensão e a sua aplicabilidade prática em vários domínios. Porém são intratáveis devido ao elevado tempo de processamento e de armazenamento de dados, sendo assim conhecidos e classificados como problemas NP-completos. Visando resolver estes problemas, diversos algoritmos têm sido propostos ao longo de vários anos de estudo, entre eles os Algoritmos Genéticos (AG) e o Algoritmo Simulated Annealing (SA). Estes algoritmos dão um tratamento polinomial aos problemas de otimização, buscando uma boa solução próxima a ótima em um tempo de processamento aceitável. Este trabalho concentra-se no estudo do AG e do SA aplicados ao clássico "Problema do Caixeiro Viajante". Propõe-se uma abordagem híbrida baseada no desenvolvimento do algoritmo SA em ambiente distribuído acrescido do operador "crossover" dos AG. A utilização em conjunto destas abordagens busca aumentar a potencialidade de obtenção de melhores resultados quando aplicados a problemas de otimização, sendo avaliado através de testes computacionais com instâncias públicas disponíveis via internet e instâncias construídas, também com suas soluções, conhecidas a priori.