ALGORITMOS EVOLUTIVOS APLICADOS NO PROBLEMA DA ÁRVORE MÍNIMA COM GRUPAMENTOS

Este trabalho objetiva propor heuristicas baseadas em Algoritmos Geneticos (AGs) para resolver o problema da Arvore Minima com Grupamentos (AMG), avaliando seus resultados e identificando qual delas melhor se aplica ao problema. A principal estrategia para resolver este tipo de problema classificado como NP-Dificil e utilizar metaheuriticas. A methaeuristica escolhida para tratar o cenario abordado foi a dos AGs, que tem se mostrado muito eficientes no tratamento de problemas de otimizacao. Os AGs sao iniciados com um conjunto de solucoes (denominadas individuos) chamado populacao. Solucoes que formam uma populacao sao utilizadas para, atraves de combinacoes (cruzamentos), formarem uma nova populacao inspirada na Teoria da Evolucao Natural de Charles Darwin. Neste trabalho foram propostos quatro AGs distintos, o primeiro e um Algoritmo Genetico com cruzamento entre genes de individuos (AG-CGIN), o segundo utiliza o cruzamento uniforme entre individuos (AG-CUIN), os demais consistem respectivamente em variacoes dos dois anteriores com o metodo de refinamento Busca Local (AG-CGINBL e AGCUINBL). Para a execucao dos experimentos computacionais foram geradas 20 instancias de testes de dimensoes variadas. Cada instancia foi executada 5 vezes para cada AG e o resultado considerado para cada AG e a media dos 5 resultados obtidos do mesmo. Os algoritmos AGCUINBL e AG-CGINBL apresentaram resultados identicos para todas as instancias, estes resultados foram melhores ou iguais aos apresentados pelo AG-CUIN e AG-CGIN, porem com um tempo de execucao consideravelmente maior, levando pouco mais de 10 segundos de execucao no teste mais demorado para o AG-CGINBL e 7 segundos para o AG-CUINBL, enquanto o AG-CGIN gastou pouco mais de 6 segundos e o AG-CUIN pouco mais de 3 segundos. O problema da AMG e considerado NP-Dificil e sua complexidade e bastante elevada tornando inviavel o uso de algoritmos exatos. Os resultados obtidos mostram a eficiencia dos AGs propostos neste trabalho para a resolucao de problemas reais que se assemelham ao problema da AMG.