META-HEURÍSTICA OTIMIZAÇÃO POR COLÔNIA DE FORMIGAS PARA O PROBLEMA DA MÁXIMA INTERSEÇÃO DE K-SUBCONJUNTOS

Encontros Universitários 2018 - Quixadá

José Robertty de Freitas Costa, Fábio Carlos Sousa Dias, Wladimir Araujo Tavares

Neste trabalho, estudamos o Problema da M´axima Interseção de k-Subconjuntos (kMIS). Dado dois conjuntos L e R, onde L é uma coleção de n conjuntos (L = fS1; S2; :::; Sng) de R e um natural k, temos que encontrar k conjuntos de L tal que a interseção deles seja máxima. Este problema possui aplicações importantes como, por exemplo, em redes sociais. O algoritmo do estado da arte para o problema é o algoritmo VNS Reativo apresentado em [Costa 2018]. Apresentamos um novo algoritmo baseado na Meta-heurística Otimização por Colônia de Formigas, que denominamos de AS PCV, para o Problema da Máxima Interseção de k-Subconjuntos. Apresentamos uma comparação deste algoritmo com o principal algoritmo heurístico da literatura a partir de testes computacionais realizados.

Palavras-chave: .

Encontros Universitários da UFC, Fortaleza, v. 3, n. 2, 2018

166