Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/58964
Tipo: | TCC |
Título: | Abordagens Heurísticas e Exatas para o Problema da Máxima Interseção de k-Subconjuntos |
Autor(es): | Costa, José Robertty de Freitas |
Orientador: | Dias, Fábio Carlos Sousa |
Coorientador: | Tavares, Wladimir Araújo |
Palavras-chave: | Otimização Combinatória;Heurística;Branch and Bound;Programação Linear Inteira |
Data do documento: | 2020 |
Citação: | COSTA, José Robertty de Freitas. Abordagens Heurísticas e Exatas para o Problema da Máxima Interseção de k-Subconjuntos. 2020. 64 f. Trabalho de Conclusão de Curso (Graduação em Engenharia de Computação)- Universidade Federal do Ceará, Campus de Quixadá, Quixadá, 2020. |
Resumo: | O Problema da Máxima Interseção de k-Subconjuntos pode ser definido como: dados dois conjuntos L e R, onde L = {S1,S2,··· ,Sp} é uma coleção de p subconjuntos de R = {e1, e2,··· , eq}, e um número inteiro positivo k, temos que encontrar k subconjuntos pertencentes a L, tal que a interseção deles seja máxima. Este problema já foi demonstrado pertencer à classe N P-difícil e possui aplicações na área de privacidade de dados e redes sociais. O objetivo deste trabalho foi propor novas abordagens, exatas e heurísticas, para o Problema da Máxima Interseção de k-Subconjuntos. Neste trabalho, foram propostas duas heurísticas gulosas, dois algoritmos Meta-heuríticos, um algoritmo Branch and Bound e uma formulação de Programação Linear Inteira. Além disso, foi proposto um novo procedimento de Teste de Redução, que visa diminuir a dimensão do problema. Foram geradas instâncias aleatórias e realizados diversos testes computacionais. Os resultados computacionais evidenciaram que os algoritmos Meta-heurísticos propostos superam o algoritmo heurístico de estado da arte em qualidade de solução ou em tempo de execução. Em relação às abordagens exatas, o algoritmo Branch and Bound proposto se mostrou mais eficiente que o método do estado da arte em instâncias onde o grafo possui uma densidade baixa ou média. |
Abstract: | The Maximum k-Subset Intersection Problem can be defined as follows: given two sets L and R, where L = {S1,S2,··· ,Sp} is a collection of p subsets of R = {e1, e2,··· , eq}, and a positive integer k, we have to find k subsets belonging to L such that their intersection is maximum. This problem has already been shown to belong to the class N P-hard and has applications in the area of data privacy and social networks. The objective of this work was to propose new approaches, exact and heuristic, for the Maximum k-Subset Intersection Problem. In this work, we propose two greedy heuristics, two Metaheuristics algorithms, a Branch and Bound algorithm and a formulation of Integer Linear Programming. In addition, a new Reduction Test procedure has been proposed, which aims to reduce the scale of the problem. Random instances were generated and several computational tests were performed. The computational results showed that the proposed Metaheuristic algorithms surpass the state-of-the-art heuristic algorithm in solution quality or in execution time. Regarding the exact approaches, the proposed Branch and Bound algorithm proved to be more efficient than the state-of-the-art method for instances where the graph has a low or medium density. |
URI: | http://www.repositorio.ufc.br/handle/riufc/58964 |
Aparece nas coleções: | ENGENHARIA DE COMPUTAÇÃO-QUIXADÁ - Monografias |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
2020_tcc_jrdefcosta.pdf | 607,87 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.