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

  • Eglon Rhuan Salazar Guimarães
  • Filipe Ribeiro Viana de Almeida
  • Dalessandro Soares Vianna
Palavras-chave: Algoritmos Genéticos, Arvore Mínima com Grupamentos, Otimização Combinatória

Resumo

Este trabalho objetiva propor heurísticas baseadas em Algoritmos Genéticos (AGs) para resolver o problema da Árvore Mínima com Grupamentos (AMG), avaliando seus resultados e identificando qual delas melhor se aplica ao problema. A principal estratégia para resolver este tipo de problema classificado como NP-Difícil é utilizar metaheuríticas. A methaeurística escolhida para tratar o cenário abordado foi a dos AGs, que tem se mostrado muito eficientes no tratamento de problemas de otimização. Os AGs são iniciados com um conjunto de soluções (denominadas indivíduos) chamado população. Soluções que formam uma população são utilizadas para, através de combinações (cruzamentos), formarem uma nova população inspirada na Teoria da Evolução Natural de Charles Darwin. Neste trabalho foram propostos quatro AGs distintos, o primeiro é um Algoritmo Genético com cruzamento entre genes de indivíduos (AG-CGIN), o segundo utiliza o cruzamento uniforme entre indivíduos (AG-CUIN), os demais consistem respectivamente em variações dos dois anteriores com o método de refinamento Busca Local (AG-CGINBL e AGCUINBL). Para a execução dos experimentos computacionais foram geradas 20 instancias de testes de dimensões variadas. Cada instancia foi executada 5 vezes para cada AG e o resultadoconsiderado para cada AG é a média dos 5 resultados obtidos do mesmo. Os algoritmos AGCUINBLe AG-CGINBL apresentaram resultados idênticos para todas as instancias, estes resultados foram melhores ou iguais aos apresentados pelo AG-CUIN e AG-CGIN, porém com um tempo de execução consideravelmente maior, levando pouco mais de 10 segundos de execução 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 é considerado NP-Difícil e sua complexidade é bastante elevada tornando inviável o uso de algoritmos exatos. Os resultados obtidos mostram aeficiência dos AGs propostos neste trabalho para a resolução de problemas reais que se assemelham ao problema da AMG.