Repositório Institucional da UFPB

Tipo:	Dissertação
Título:	Otimização por Nuvem de Partículas e Busca Tabu para Problema da Diversidade Máxima
Autor(es):	Bonotto, Edison Luiz
Primeiro Orientador:	Cabral, Lucídio dos Santos formiga
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.
Palavras-chave:	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
CNPq:	CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma:	por
País:	Brasil
Editor:	Universidade Federal da Paraíba
Sigla da Instituição:	UFPB
Departamento:	Informática
Programa:	Programa de Pós-Graduação em Informática
Citação:	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.
Tipo de Acesso:	Acesso aberto
URI:	https://repositorio.ufpb.br/jspui/handle/tede/9036
Data do documento:	31-Jan-2017
Aparece nas coleções:	Centro de Informática (CI) - Programa de Pós-Graduação em Informática

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