Submitted by Automação e Estatística (sst@bczm.ufrn.br) on 2018-07-31T22:06:58Z
No. of bitstreams: 1
RaimundoLeandroAndradeMarques_DISSERT.pdf: 2113159 bytes, checksum: 05abba5f2d3fdeb23f1c146143f0833c (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2018-07-31T22:11:47Z (GMT) No. of bitstreams: 1
RaimundoLeandroAndradeMarques_DISSERT.pdf: 2113159 bytes, checksum: 05abba5f2d3fdeb23f1c146143f0833c (MD5) / Made available in DSpace on 2018-07-31T22:11:47Z (GMT). No. of bitstreams: 1
RaimundoLeandroAndradeMarques_DISSERT.pdf: 2113159 bytes, checksum: 05abba5f2d3fdeb23f1c146143f0833c (MD5)
Previous issue date: 2017-02-17 / O problema da árvore geradora mínima com restrição de grau multiobjetiva, vem sendo
estudado por pesquisadores da área de otimização combinatória há pouco mais de uma década,
em grande parte por sua ampla aplicação em problemas práticos relacionados à modelagem de
redes. Esse problema é considerado NP-difícil, ainda em sua versão mono-objetiva, para um
grau de restrição de pelo menos
= 3. Esse trabalho propõe a resolução do problema através
de um algoritmo evolucionário chamado AEMPH. Essa abordagem utiliza-se de arquivos
externos compartilhados e de diferentes técnicas de otimização multiobjetiva executadas
paralelamente, visando uma melhor cobertura do espaço de busca. As técnicas escolhidas para
sua implementação foram o MPAES, o NSGA2, e o SPEA2, as quais também foram utilizadas
para comparação de desempenho computacional. Foram realizados 5040 testes ao todo,
envolvendo instâncias de 3 diferentes tipos, com tamanhos variando entre 50 e 1000 vértices.
Devido à natureza multiobjetiva do problema, os resultados dos experimentos são expressos
através dos indicadores de qualidade hipervolume e épsilon binário, e avaliados quanto a sua
significância através do teste estatístico de Mann-Whitney / The Multiobjective Degree Constrained Minimum Spanning Tree Problem, has been studied
by combinatorial optimization researchers within a little more than a decade, especially due to its
wide usability in network modeling design problems. This is a NP-hard problem, even in its
mono-objective version for a degree of at least
= 3. The new algorithm proposed here called
AEMPH, uses shared external archives and different multiobjective optimization techniques in
a parallel execution to a better survey of the search space. This AEMPH version adopts the
MPAES, NSGA2 and SPEA2 algorithms in its implementation which also are used in the
comparison tests. A total of 5040 empirical tests are presented here, involving 3 different graph
generators, and instances of size 50 up to 1000 nodes. For a matter of multi-objective trait, the
results for these experiments are presented by means of hypervolume and -binary
indicators. The significance of computational experiments is evaluated by the Mann-Whitney statistical
test.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/25647 |
| Date | 17 February 2017 |
| Creators | Marques, Raimundo Leandro Andrade |
| Contributors | 25841025953, Goldbarg, Elizabeth Ferreira Gouvea, 81652011749, Cabral, Lucídio dos Anjos Formiga, 37383388372, Menezes, Matheus da Silva, 03329300418, Maia, Silvia Maria Diniz Monteiro, 01397968435, Goldbarg, Marco César |
| Publisher | PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO, UFRN, Brasil |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0351 seconds