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

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

Resumo

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.
Publicado
2015-09-09
Seção
Encontros Universitários 2018 - Campus Quixadá