Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/82813
Registro completo de metadados
Campo DCValorIdioma
dc.contributor.advisorRodrigues, Carlos Diego-
dc.contributor.authorCosta, Dario Filipe da Silva-
dc.date.accessioned2025-10-01T13:40:02Z-
dc.date.available2025-10-01T13:40:02Z-
dc.date.issued2025-
dc.identifier.citationCOSTA, 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á.-
dc.identifier.urihttp://repositorio.ufc.br/handle/riufc/82813-
dc.language.isopt_BRpt_BR
dc.rightsAcesso Abertopt_BR
dc.titleAplicação de heurísticas ao K-MISpt_BR
dc.typeTCCpt_BR
dc.description.abstract-ptbrO 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.pt_BR
dc.subject.ptbrHeurísticaspt_BR
dc.subject.ptbrVizinhança variadapt_BR
dc.subject.ptbrMáxima interseção de k-subconjuntospt_BR
dc.subject.ptbrColônia de formigaspt_BR
dc.subject.ptbrGreedy randomized adaptive Search Procedurept_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRApt_BR
local.author.orcidhttps://orcid.org/0009-0005-9380-2153pt_BR
local.author.latteshttp://lattes.cnpq.br/5615290126856617pt_BR
local.advisor.latteshttp://lattes.cnpq.br/4351787196667659pt_BR
local.date.available2025-
Aparece nas coleções:MATEMÁTICA INDUSTRIAL - Monografias

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2025_tcc_dfscosta573,08 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.