Heurísticas e algoritmos evolutivos para formulações mono e multiobjetivo do problema do roteamento multicast
AUTOR(ES)
Marcos Luiz de Paula Bueno
DATA DE PUBLICAÇÃO
2010
RESUMO
Neste 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.
ASSUNTO(S)
roteamento multicast otimização multiobjetivo algoritmo genético dominância de pareto qualidade de serviço engenharia de tráfego ciencia da computacao redes de computadores algoritmos genéticos inteligência artificial multicast routing multiobjective optimization genetic algorithm pareto dominance quality of service trac engineering
ACESSO AO ARTIGO
http://www.bdtd.ufu.br//tde_busca/arquivo.php?codArquivo=3241Documentos Relacionados
- Algoritmos genÃticos para um problema de objetivos mÃltiplos: roteamento multicast
- Heurísticas mono e multiobjetivo para o problema de cobertura e conectividade de redes de sensores sem fio planas
- Novos algoritmos para resolução do problema de roteamento.
- Heuristicas para o problema de estoque e roteamento de veiculos
- Algoritmos para a resolução do problema de estoque e roteamento de veiculos