Algoritmo Evolucionário de Múltiplas Populações Híbridas Aplicado ao Problema da Árvore Geradora Mínima com Restrição de Grau Multiobjetiva
Algoritmos Genéticos, Algoritmos Genéticos Híbridos, Programação Multiobjetivo, Árvore Geradora Mínima com Restrição de Grau.
O problema da árvore geradora mínima com restrição de grau multiobjetiva vem ganhando nos últimos anos, a atenção dos pesquisadores da área de otimização combinatória, em grande parte por sua ampla aplicação em problemas práticos relacionados à modelagem de redes. Esse problema é considerado NP-difícil, ainda em sua versão mono-objetiva, para um grau de restrição de pelo menos . Esse trabalho propõe a resolução do problema através de um algoritmo evolucionário chamado MMPEA. Essa abordagem utiliza-se de arquivos externos compartilhados e diferentes técnicas de otimização multiobjectivo executadas paralelamente, para uma melhor cobertura do espaço de busca. As técnicas escolhidas para implementação do MMPEA foram o MPAES, o NSGA2, e o SPEA2, as quais também foram utilizadas para comparação de desempenho computacional. Foram realizados 5040 testes ao todo, incluindo instâncias de diferentes tipos, com tamanhos entre 50 e 1000 vértices. Devido à natureza multiobjetiva do problema, os resultados dos experimentos são expressos através dos indicadores de qualidade hipervolume e épsilon binário, e avaliados quanto a sua significância através do teste estatístico de Mann-Whitney.