Heurísticas e algoritmos evolutivos para formulações mono e multiobjetivo do problema do roteamento multicast

dc.contributorOliveira, Gina Maira Barbosa de
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4784553Y0
dc.contributorRosa, Pedro Frosi
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4791965U0
dc.contributorTakahashi, Ricardo Hiroshi Caldeira
dc.contributorhttp://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4785097T0
dc.creatorBueno, Marcos Luiz de Paula
dc.date2016-06-22T18:32:18Z
dc.date2011-02-09
dc.date2016-06-22T18:32:18Z
dc.date2010-08-04
dc.date.accessioned2023-09-28T21:12:40Z
dc.date.available2023-09-28T21:12:40Z
dc.identifierBUENO, Marcos Luiz de Paula. Heurísticas e algoritmos evolutivos para formulações mono e multiobjetivo do problema do roteamento multicast. 2010. 131 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2010.
dc.identifierhttps://repositorio.ufu.br/handle/123456789/12501
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/9065964
dc.descriptionIn this work, we investigate evolutionary models applied to the Multicast Routing Problem (MRP), in which we want to calculate multicast trees from a connected weighted graph, optimizing one or more objective functions related to Quality of Service and Trac Engineering requirements. MRP can be seen as an extension of the well-known Steiner Tree Problem, which is in the NP-hard class of problems. Thus, starting from models based on Canonical and Multiobjective Genetic Algorithms from the literature, we propose three heuristics to be used in crossover and mutation operators of the resultant evolutionary model, which are based on more determinists strategies (using Dijkstra's algorithm), more random ones or a combination of these. The usage of such heuristic occurs in a crossover/mutation phase known as subtrees reconnection, which guides the generation of new solutions combining common parts of parents and new parts added by such reconnection algorithm. MRP was considered under several formulations (one mono-objective and seven multiobjective ones under Pareto dominance), aiming to achieve a comprehensive experimental evaluation of the proposed methods. Three well-known algorithms (NSGA-II, SPEA and SPEA2) were used as underlying search mechanism, in which two variations of a mating selection of parents based on neighborhood (Neighborhood Crossover) were also evaluated. From a set of eight instances taken from Routing and Steiner problems literature, the experimental results indicated that besides xing a heuristic that could potentially generate invalid individuals, the new heuristics returned good results in the considered convergence and diversity metrics. More specically, the combined heuristic provided the best results in most cases, showing that the strategy of combining a shortest path with randomness along the reconnections was benecial. The use of Neighborhood Crossover, in turn, was more noticeable on the MRP formulation in which the network instances had larger Pareto-optimal sets. Statistical signicance tests were performed, supporting the evidences showed by punctual and interval estimations.
dc.descriptionCoordenação de Aperfeiçoamento de Pessoal de Nível Superior
dc.descriptionMestre em Ciência da Computação
dc.descriptionNeste trabalho são investigados modelos evolutivos aplicados ao Problema do Roteamento Multicast (PRM), cujo objetivo é calcular árvores multicast a partir de um grafo conectado ponderado, otimizando uma ou mais funções objetivo relacionadas a requisitos de Qualidade de Serviço e Engenharia de Tráfego. O PRM pode ser visto como uma extens ão ao conhecido Problema da Árvore de Steiner, o qual sabe-se estar na classe NP-difícil. Assim, partindo de modelos baseados em Algoritmos Genéticos Clássicos e Multiobjetivo da literatura, propomos três heurísticas a serem utilizadas nos operadores de cruzamento e mutação do modelo evolutivo resultante, sendo baseadas em estratégias mais deterministas (por meio do algoritmo de Dijkstra), mais aleatórias ou uma combinação destas. A aplicação da heurística ocorre numa fase do cruzamento/mutação conhecida como reconex ão de subárvores, a qual guia a geração de novas soluções combinando partes comuns aos pais a novas partes adicionadas pelo algoritmo de reconexão. O PRM foi considerado sob uma série de formulações (uma mono-objetivo, e sete multiobjetivo usando a dominância de Pareto), com o intuito de realizar uma extensa avaliação experimental dos métodos propostos. Foram utilizados três algoritmos evolutivos conhecidos (NSGA-II, SPEA e SPEA2) como mecanismo de busca subjacente, sobre os quais duas variações de seleção de pais (Cruzamento pela Vizinhança) também foram avaliadas. A partir de um conjunto de oito instâncias retiradas da literatura dos problemas de Roteamento e Steiner, os resultados experimentais indicaram que além de corrigir uma heurística que potencialmente gerava indivíduos inválidos, as novas heurísticas forneceram bons resultados nas métricas de convergência e diversidade consideradas. Especi- camente, a heurística combinada proveu os melhores resultados na maioria dos casos, mostrando que a estratégia de combinar um menor caminho com aleatoriedade durante as reconexões foi benéco. Por sua vez, o uso do Crossover pela Vizinhança trouxe benefícios mais nitidamente na formulação com maior número de objetivos, na qual as instâncias apresentaram conjuntos Pareto-ótimos com maior cardinalidade. Testes de signicância estatística foram aplicados, conrmando o que as estimativas pontuais e por intervalo haviam evidenciado na maior parte dos casos.
dc.formatapplication/pdf
dc.formatapplication/pdf
dc.languagepor
dc.publisherUniversidade Federal de Uberlândia
dc.publisherBR
dc.publisherPrograma de Pós-graduação em Ciência da Computação
dc.publisherCiências Exatas e da Terra
dc.publisherUFU
dc.rightsAcesso Aberto
dc.subjectRoteamento multicast
dc.subjectOtimização multiobjetivo
dc.subjectAlgoritmo genético
dc.subjectDominância de pareto
dc.subjectQualidade de serviço
dc.subjectEngenharia de tráfego
dc.subjectRedes de computadores
dc.subjectAlgoritmos genéticos
dc.subjectInteligência artificial
dc.subjectMulticast routing
dc.subjectMultiobjective optimization
dc.subjectGenetic algorithm
dc.subjectPareto dominance
dc.subjectQuality of service
dc.subjectTrac engineering
dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
dc.titleHeurísticas e algoritmos evolutivos para formulações mono e multiobjetivo do problema do roteamento multicast
dc.typeDissertação


Este ítem pertenece a la siguiente institución