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.advisorGoldbarg, Marco César
dc.contributor.advisorIDpt_BR
dc.contributor.authorMarques, Raimundo Leandro Andrade
dc.contributor.authorIDpt_BR
dc.contributor.referees1Goldbarg, Elizabeth Ferreira Gouvea
dc.contributor.referees1IDpt_BR
dc.contributor.referees2Cabral, Lucídio dos Anjos Formiga
dc.contributor.referees2IDpt_BR
dc.contributor.referees3Menezes, Matheus da Silva
dc.contributor.referees3IDpt_BR
dc.contributor.referees4Maia, Silvia Maria Diniz Monteiro
dc.contributor.referees4IDpt_BR
dc.date.accessioned2018-07-31T22:11:47Z
dc.date.available2018-07-31T22:11:47Z
dc.date.issued2017-02-17
dc.description.abstractThe 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.resumoO 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-Whitneypt_BR
dc.identifier.citationMARQUES, 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.urihttps://repositorio.ufrn.br/jspui/handle/123456789/25647
dc.languageporpt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.initialsUFRNpt_BR
dc.publisher.programPROGRAMA DE PÓS-GRADUAÇÃO EM SISTEMAS E COMPUTAÇÃOpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgoritmos genéticospt_BR
dc.subjectAlgoritmos genéticos híbridospt_BR
dc.subjectProgramação multiobjetivopt_BR
dc.subjectÁrvore geradora mínima com restrição de graupt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAOpt_BR
dc.titleAlgoritmo evolucionário de múltiplas populações híbridas aplicado ao problema da árvore geradora mínima com restrição de grau multiobjetivapt_BR
dc.title.alternativeMulti mixed population evolutionary algorithm applied to the multiobjective degree constrained minimum spanning tree problempt_BR
dc.typemasterThesispt_BR

Arquivos

Pacote Original

Agora exibindo 1 - 1 de 1
Carregando...
Imagem de Miniatura
Nome:
RaimundoLeandroAndradeMarques_DISSERT.pdf
Tamanho:
2.02 MB
Formato:
Adobe Portable Document Format
Carregando...
Imagem de Miniatura
Baixar