Submitted by Maike Costa (maiksebas@gmail.com) on 2017-06-29T14:15:20Z
No. of bitstreams: 1
arquivototal.pdf: 1397036 bytes, checksum: 303111e916d8c9feca61ed32762bf54c (MD5) / Made available in DSpace on 2017-06-29T14:15:20Z (GMT). No. of bitstreams: 1
arquivototal.pdf: 1397036 bytes, checksum: 303111e916d8c9feca61ed32762bf54c (MD5)
Previous issue date: 2017-01-31 / 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. / 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:tede.biblioteca.ufpb.br:tede/9036 |
| Date | 31 January 2017 |
| Creators | Bonotto, Edison Luiz |
| Contributors | Cabral, Lucídio dos Santos formiga |
| Publisher | Universidade Federal da Paraíba, Programa de Pós-Graduação em Informática, UFPB, Brasil, Informática |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFPB, instname:Universidade Federal da Paraíba, instacron:UFPB |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 4679641312648529202, 600, 600, 600, 7879657947546587587, 3671711205811204509 |
Page generated in 0.0028 seconds