Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/82813| Type: | TCC |
| Title: | Aplicação de heurísticas ao K-MIS |
| Authors: | Costa, Dario Filipe da Silva |
| Advisor: | Rodrigues, Carlos Diego |
| Keywords in Brazilian Portuguese : | Heurísticas;Vizinhança variada;Máxima interseção de k-subconjuntos;Colônia de formigas;Greedy randomized adaptive Search Procedure |
| Knowledge Areas - CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA |
| Issue Date: | 2025 |
| Citation: | COSTA, Dario Filipe da Silva. Aplicação de heurísticas ao K-MIS. 2025. 56 f. Trabalho de conclusão de curso (Graduação em Matemática Industrial) - Centro de Ciências, Universidade Federal do Ceará. |
| Abstract in Brazilian Portuguese: | O problema da Máxima Interseção de k-Subconjuntos (kMIS), N P-difícil e sem algoritmo α-aproximado, possui aplicações na área de privacidade de dados e redes sociais. Há abordagens exatas e meta-heurísticas indicadas na literatura, mas, como se trata de um problema desafiador, existe espaço para avanços, pois as abordagens exatas tomam um tempo proibitivo, em instâncias maiores, e as meta-heurísticas parecem sempre poder evoluir. O kMIS consiste em escolher k subconjuntos distintos Si1,··· ,Sik ⊂ R pertencentes a L = {S1,...,Sn}, de modo que a interseção |Si1 ∩ ... ∩ Sik| seja máxima. As Meta-Heurísticas Greedy Randomized Adaptive Search Procedure (GRASP) e Colônia de Formigas (ANT) obtêm relativo sucesso na prática, sobretudo quando combinadas com intensificações como a Vizinhança Variada (VND) ou Busca Tabu (TS). Neste trabalho, são propostas modificações ao ANT e ao VND, em busca de obter melhores resultados. E, em especial, é proposta uma metodologia simplificada para a comparação entre as heurísticas, padronizando o tempo de execução em função do tamanho do conjunto L de cada instância, pois comumente, na literatura, os testes computacionais são realizados com discrepância de tempo de execução, fazendo a comparação ocorrer tanto no quesito qualidade da solução, quanto tempo. Portanto, fixar o tempo possibilita focar apenas na qualidade da solução, tornando mais claros os resultados do experimento. Os procedimentos heurísticos são organizados em duas componentes: (i) a meta-heurística principal, responsável pela construção das soluções, e (ii) o método de intensificação, acionado para aprimorá-las. Este estudo realizou experimentos computacionais com nove combinações distintas entre os três métodos principais, GRASP, ANT e ANT Modificado, e três técnicas de intensificação, TS, VND e VND Modificado. |
| URI: | http://repositorio.ufc.br/handle/riufc/82813 |
| Author's ORCID: | https://orcid.org/0009-0005-9380-2153 |
| Author's Lattes: | http://lattes.cnpq.br/5615290126856617 |
| Advisor's Lattes: | http://lattes.cnpq.br/4351787196667659 |
| Access Rights: | Acesso Aberto |
| Appears in Collections: | MATEMÁTICA INDUSTRIAL - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2025_tcc_dfscosta | 573,08 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.