Please use this identifier to cite or link to this item: https://repositorio.ufpb.br/jspui/handle/tede/9036
metadata.dc.type: Dissertação
Title: Otimização por Nuvem de Partículas e Busca Tabu para Problema da Diversidade Máxima
metadata.dc.creator: Bonotto, Edison Luiz
metadata.dc.contributor.advisor1: Cabral, Lucídio dos Santos formiga
metadata.dc.description.resumo: O Problema da Diversidade Máxima (MDP) é um problema da área de Otimização Combinatória que tem por objetivo selecionar um número pré-estabelecido de elementos de um dado conjunto de maneira tal que a soma das diversidades entre os elementos selecionados seja a maior possível. O MDP pertence a classe de problemas NP-difícil, isto é, não existe algoritmo conhecido que o resolva de forma exata em tempo polinomial. Por apresentarem uma complexidade de ordem exponencial, exigem heurísticas eficientes que forneçam resultados satisfatórios em tempos aceitáveis. Entretanto, as heurísticas não garantem otimalidade da solução encontrada. Este trabalho propõe uma nova abordagem híbrida para a resolução do Problema da Diversidade Máxima e está baseada nas meta-heurísticas de Otimização por Nuvem de Partículas (PSO) e Busca Tabu(TS). O algoritmo foi denominado PSO_TS. Para a validação do método, os resultados encontrados são comparados com os melhores existentes na literatura.
Abstract: The Maximu m Diversity Problem (MDP) is a problem of combinatorial optimization area that aims to select a pre-set number of elements in a given set so that a sum of the differences between the selected elements are greater as possible. MDP belongs to the class of NP-Hard problems, that is, there is no known algorithm that solves in polynomial time accurately. Because they have a complexity of exponential order, require efficient heuristics to provide satisfactory results in acceptable time. However, heuristics do not guarantee the optimality of the solution found. This paper proposes a new hybrid approach for a resolution of the Maximum Diversity Problem and is based on the Particle Swarm Optimization (PSO) and Tabu Search (TS) metaheuristics, The algorithm is called PSO_TS. The use of PSO_TS achieves the best results for known instances testing in the literature, thus demonstrating be competitive with the best algorithms in terms of quality of the solutions.
Keywords: Problema da Diversidade Máxima (MDP)
Otimização por Nuvem de Partículas (PSO)
Busca Tabu (TS)
Otimização Combinatória
Problema NP-Difícil
Maximum Diversity Problem (MDP)
Particle Swarm Optimization (PSO)
Tabu Search (TS)
Combinatorial Optimization
NP-Hard Problem
metadata.dc.subject.cnpq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.language: por
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal da Paraíba
metadata.dc.publisher.initials: UFPB
metadata.dc.publisher.department: Informática
metadata.dc.publisher.program: Programa de Pós-Graduação em Informática
Citation: BONOTTO, Edison Luiz. Otimização por Nuvem de Partículas e Busca Tabu para Problema da Diversidade Máxima. 2017. 66 f. Dissertação (Mestrado em Informática) - Universidade Federal da Paraíba, João Pessoa, 2017.
metadata.dc.rights: Acesso aberto
URI: https://repositorio.ufpb.br/jspui/handle/tede/9036
Issue Date: 31-Jan-2017
Appears in Collections:Centro de Informática (CI) - Programa de Pós-Graduação em Informática

Files in This Item:
File Description SizeFormat 
arquivototal.pdf1,36 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.