Algoritmo Genético para o Problema da Árvore de Cobertura com Representação Mínima

O Problema da Árvore de Cobertura com Representação Mínima (PACRM) tem como objetivo, dado um grafo com arestas rotuladas G = (V, E, L), sendo V o conjunto de vértices de G, E o conjunto de arestas, L o conjunto de rótulos, e L(e) o rótulo associado à aresta e, encontrar uma árvore geradora, T = (V, E′, L′), tal que E′ ⊆ E, L′ ⊆ L, e a soma dos rótulos representados em cada vértice seja minimizada. Neste trabalho, propomos um algoritmo genético para o problema e três novas estruturas de vizinhança adotadas na fase de educação do algoritmo. Os experimentos computacionais realizados demonstraram que a meta-heurística proposta obteve resultados melhores que as heurísticas da literatura, além de baixar o upper bound conhecido dos métodos exatos em um conjunto de instâncias de dimensão média com pouco esforço computacional.