Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/82813| Tipo: | TCC |
| Título: | Aplicação de heurísticas ao K-MIS |
| Autor(es): | Costa, Dario Filipe da Silva |
| Orientador: | Rodrigues, Carlos Diego |
| Palavras-chave em português: | Heurísticas;Vizinhança variada;Máxima interseção de k-subconjuntos;Colônia de formigas;Greedy randomized adaptive Search Procedure |
| CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA |
| Data do documento: | 2025 |
| Citação: | 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á. |
| Resumo: | 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 do(s) Autor(es): | https://orcid.org/0009-0005-9380-2153 |
| Currículo Lattes do(s) Autor(es): | http://lattes.cnpq.br/5615290126856617 |
| Currículo Lattes do Orientador: | http://lattes.cnpq.br/4351787196667659 |
| Tipo de Acesso: | Acesso Aberto |
| Aparece nas coleções: | MATEMÁTICA INDUSTRIAL - Monografias |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2025_tcc_dfscosta | 573,08 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.