Por favor, use este identificador para citar o enlazar este ítem:
http://repositorio.ufc.br/handle/riufc/82813| Tipo: | TCC |
| Título : | Aplicação de heurísticas ao K-MIS |
| Autor : | Costa, Dario Filipe da Silva |
| Tutor: | Rodrigues, Carlos Diego |
| Palabras clave en portugués brasileño: | Heurísticas;Vizinhança variada;Máxima interseção de k-subconjuntos;Colônia de formigas;Greedy randomized adaptive Search Procedure |
| Áreas de Conocimiento - CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA |
| Fecha de publicación : | 2025 |
| Citación : | 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á. |
| Resumen en portugués brasileño: | 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 |
| ORCID del autor: | https://orcid.org/0009-0005-9380-2153 |
| Lattes del autor: | http://lattes.cnpq.br/5615290126856617 |
| Lattes del tutor: | http://lattes.cnpq.br/4351787196667659 |
| Derechos de acceso: | Acesso Aberto |
| Aparece en las colecciones: | MATEMÁTICA INDUSTRIAL - Monografias |
Ficheros en este ítem:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 2025_tcc_dfscosta | 573,08 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.