Algoritomos transgenéticos aplicados ao problema da árvore geradora biobjetivo

AUTOR(ES)

Silvia Maria Diniz Monteiro

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

17/02/2011

RESUMO

A Árvore Geradora Multiobjetivo é um problema de Otimização Combinatória NP-árduo. Esse problema possui aplicação em diversas áreas, em especial, no projeto de redes. Nesse trabalho, propõe-se uma solução para o problema em sua versão biobjetivo por meio de um Algoritmo Transgenético, denominado ATIS-NP. A Transgenética Computacional é uma técnica metaheurística da Computação Evolucionária cuja inspiração está na cooperação (e não na competição) como fator de maior influência para a evolução. O algoritmo proposto é a evolução de um trabalho que já originou dois outros algoritmos transgenéticos. Nesse sentido, os algoritmos previamente desenvolvidos também são apresentados. Essa pesquisa compreende ainda uma análise experimental que visa obter informações quanto ao desempenho do ATIS-NP quando comparado a outros algoritmos. Para tanto, o ATIS-NP é comparado aos dois algoritmos anteriormente implementados, bem como a outro transgenético proposto na literatura para o problema tratado. Os experimentos computacionais abrangem ainda a comparação do algoritmo desenvolvido a duas abordagens recentes da literatura que obtêm excelentes resultados, um GRASP e um genético. A eficiência do método apresentado é avaliada com base em medidas de qualidade de solução e tempo computacional despendido. Uma vez que o problema se insere no contexto da Otimização Multiobjetivo, indicadores de qualidade são utilizados para inferir o critério de qualidade de soluções obtidas. Testes estatísticos avaliam a significância dos resultados obtidos nos experimentos computacionais

ASSUNTO(S)

computação evolucionária programação multiobjetivo Árvore geradora multiobjetivo sistemas de computacao experimental algorithms transgenetic algorithms evolutionary computation multiobjective programming multiobjective spanning tree algoritmos experimentais algoritmos transgenéticos

Documentos Relacionados

• Métodos heurísticos aplicados ao problema da árvore de Steiner rectilinear
• Algoritmos para o problema da árvore geradora mínima probalística
• DESENVOLVIMENTO DE METAHEURÍSTICAS PARA O PROBLEMA DA ÁRVORE GERADORA MÍNIMA GENERALIZADO
• Sistema imunológico artificial para resolver o problema da árvore geradora mínima com parâmetros fuzzy
• Abordagem de refinamento iterativo para o problema da árvore geradora com número mínimo de vértices Branch