Algoritmo Colônia de Formigas com uma Busca VND para o Problema da Máxima Interseção de k-Subconjuntos

Vol 54, 2022 - 152648
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

Neste trabalho, apresentamos um algoritmo baseado na meta-heurística Colônia de Formigas para o Problema da Máxima Interseção de $k$-Subconjuntos. Este problema é definido como: dado uma coleção $\mathcal{S}$ de subconjuntos do conjunto finito $B$ e um inteiro $k$, deseja-se selecionar $k$ subconjuntos $S_1, S_2, \ldots, S_k \in \mathcal{S}$, tal que $|S_1 \cap \ldots \cap S_k|$ seja máxima. O algoritmo proposto, denominado $ANT_{VND}$, se utiliza regra de proporcionalidade pseudoaleatória como regra de transição de estados e da busca local VND. Os resultados dos testes computacionais mostram que o algoritmo $ANT_{VND}$ supera o algoritmo do estado da arte com relação a qualidade de solução encontrada.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal do Ceará
  • 2 UNIVERSIDADE FEDERAL DO CEARÁ
Eixo Temático
  • 13 - MH – Metaheurísticas
Palavras-chave
Metaheurística
Algoritmo de Otimização da Colônia de Formigas
Problema da Máxima Interseção de k-Subconjuntos