Algoritmo evolucionário de múltiplas populações híbridas aplicado ao problema da árvore geradora mínima com restrição de grau multiobjetiva
dc.contributor.advisor | Goldbarg, Marco César | |
dc.contributor.advisorID | pt_BR | |
dc.contributor.author | Marques, Raimundo Leandro Andrade | |
dc.contributor.authorID | pt_BR | |
dc.contributor.referees1 | Goldbarg, Elizabeth Ferreira Gouvea | |
dc.contributor.referees1ID | pt_BR | |
dc.contributor.referees2 | Cabral, Lucídio dos Anjos Formiga | |
dc.contributor.referees2ID | pt_BR | |
dc.contributor.referees3 | Menezes, Matheus da Silva | |
dc.contributor.referees3ID | pt_BR | |
dc.contributor.referees4 | Maia, Silvia Maria Diniz Monteiro | |
dc.contributor.referees4ID | pt_BR | |
dc.date.accessioned | 2018-07-31T22:11:47Z | |
dc.date.available | 2018-07-31T22:11:47Z | |
dc.date.issued | 2017-02-17 | |
dc.description.abstract | 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. | pt_BR |
dc.description.resumo | 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 | pt_BR |
dc.identifier.citation | 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. | pt_BR |
dc.identifier.uri | https://repositorio.ufrn.br/jspui/handle/123456789/25647 | |
dc.language | por | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.initials | UFRN | pt_BR |
dc.publisher.program | PROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃO | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Algoritmos genéticos | pt_BR |
dc.subject | Algoritmos genéticos híbridos | pt_BR |
dc.subject | Programação multiobjetivo | pt_BR |
dc.subject | Árvore geradora mínima com restrição de grau | pt_BR |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO | pt_BR |
dc.title | Algoritmo evolucionário de múltiplas populações híbridas aplicado ao problema da árvore geradora mínima com restrição de grau multiobjetiva | pt_BR |
dc.title.alternative | Multi mixed population evolutionary algorithm applied to the multiobjective degree constrained minimum spanning tree problem | pt_BR |
dc.type | masterThesis | pt_BR |
Arquivos
Pacote Original
1 - 1 de 1
Carregando...
- Nome:
- RaimundoLeandroAndradeMarques_DISSERT.pdf
- Tamanho:
- 2.02 MB
- Formato:
- Adobe Portable Document Format
Carregando...