masterThesis
Algoritmo evolucionário de múltiplas populações híbridas aplicado ao problema da árvore geradora mínima com restrição de grau multiobjetiva
Fecha
2017-02-17Registro en:
MARQUES, Raimundo Leandro Andrade. Algoritmo evolucionário de múltiplas populações híbridas aplicado ao problema da árvore geradora mínima com restrição de grau multiobjetiva. 2017. 104f. Dissertação (Mestrado em Sistemas e Computação) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2017.
Autor
Marques, Raimundo Leandro Andrade
Resumen
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.