61ª Reunião Anual da SBPC
A. Ciências Exatas e da Terra - 2. Ciência da Computação - 6. Inteligência Artificial e Redes Neurais
ALGORITMOS EVOLUTIVOS APLICADOS NO PROBLEMA DA ÁRVORE MÍNIMA COM GRUPAMENTOS
Eglon Rhuan Salazar Guimarães 1, 2
Filipe Ribeiro Viana de Almeida 1
Dalessandro Soares Vianna 1, 2, 3
Fábio Duncan de Souza 1, 4
1. Instituto Federal Fluminense
2. Universidade Candido Mendes
3. Prof. Dsc / Orientador
4. Prof. Msc / Orientador
INTRODUÇÃO:
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 em questão. No problema da AMG, dado um grafo G = (V, E), onde V representa um conjunto de nós(vértices), e E o conjunto de arestas que ligam dois vértices, o conjunto V é particionado em k grupamentos, V = V1 U V2 U ... U Vk, sendo estes disjuntos entre si. O objetivo da AMG é encontrar o menor subgrafo que passe em um vértice de cada grupamento(cluster). Uma possível aplicação para este problema é a otimização de uma rede de irrigação onde a área total é dividida em setores que possuem vários pontos de irrigação e a água é distribuída através de uma rede central que passa em um ponto de cada setor. A complexidade do problema torna inviável o uso de algoritmos exatos, portanto a principal estratégia para resolver este tipo de problema, classificado na literatura como NP-difícil, é utilizar metaheuríticas, que são heurísticas direcionadas a encontrar ótimos globais evitando a parada prematura em ótimos locais. 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.
METODOLOGIA:
Os AGs são iniciados com um conjunto de soluções (denominados 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 (processo de evolução). Os AGs já demonstraram sucesso no tratamento de diversos problemas de otimização combinatória e são baseados na Teoria da Evolução Natural de Darwin, assumindo que os indivíduos mais aptos devem “sobreviver” enquanto os menos aptos tendem a “extinção”. Neste trabalho foram propostos 4 AGs distintos, o primeiro é uma versão de Algoritmo Genético com cruzamento entre indivíduos particionados (AG-CIP), o segundo utiliza o cruzamento conhecido na literatura como Cruzamento Uniforme entre indivíduos (AG-CUIN), os outros consistem respectivamente em variações dos dois anteriores com o método de refinamento Busca Local (AG-CIPBL e AG-CUINBL).
RESULTADOS:
Para a execução dos experimentos computacionais foram geradas instancias de testes de dimensões variadas, as instancias simulam grafos com diferentes quantidades de clusters e vértices, os seus nomes seguem o seguinte padrão: [número de vértices]v[número de clusters]c, exemplo: 50v6c representa 50 vértices divididos em 6 clusters. Cada instancia foi executada 5 vezes para cada AG e o resultado considerado para cada AG é a média aritmética dos 5 resultados obtidos do mesmo. Foram criadas 20 instancias para serem submetidas aos algoritmos propostos, estas representam problemas com número de vértices entre 50 e 500 e número de clusters entre 4 e 14. Os algoritmos AG-CUINBL e AG-CIPBL apresentaram resultados idênticos para todas as instancias, estes resultados foram melhores ou iguais aos apresentados pelo AG-CUIN e AG-CIP, 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-CIPBL e 7 segundos para o AG-CUINBL , enquanto o AG-CIP gastou pouco mais de 6 segundos e o AG-CUIN pouco mais de 3 segundos.
CONCLUSÃO:
Como já apresentado, o problema da AMG é considerado NP-Difícil e sua complexidade é bastante elevada tornando inviável o uso de algoritmos exatos. Dos Algoritmos Genéticos apresentados, aqueles que utilizaram a Busca Local como método de refinamento obtiveram os melhores resultados na maioria dos testes realizados e apresentaram as soluções em um tempo de execução aceitável. O que comprova a eficiência de métodos de refinamento aplicados nas soluções obtidas pelos AGs. Deve-se ressaltar também o desempenho do AG-CUIN que apresentou resultados satisfatórios em um tempo consideravelmente menor do que os demais. O tempo de execução do AG-CUIN foi em média 45% menor do que o tempo gasto pelo AG-CUINBL que foi o segundo AG com resultados mais rápidos. Os resultados obtidos mostram a eficiência dos AGs propostos neste trabalho para a resolução de problemas reais que se assemelham ao problema da AMG, como o problema da irrigação que pode ter seus custos de implantação minimizados através da utilização destes AGs no seu processo.
Palavras-chave: Algoritmos Genéticos, Arvore Mínima com Grupamentos, Otimização Combinatória.