Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Doutor em Ciências (D.Sc.)
Aplicações de Algoritmos Paralelos e Híbridos para o Problema de Árvore de Steiner Euclidiana no Rn
Marcelo Lisboa Rocha
Outubro/2008
Programa: |
Engenharia Elétrica |
Neste trabalho será apresentada uma aplicação proposta de algoritmos paralelos e híbridos para problemas de otimização de grande porte, mais especificamente ao Problema de Árvore de Steiner Euclidiano (PASE) no Rn. Como método híbrido, foi proposta uma heurística GRASP mais o procedimento de Path-relinking, com várias implementações paralelas do mesmo. Também foi realizada uma implementação paralela de um time assíncrono para o problema em questão. Os métodos propostos neste trabalho ao problema em questão possuem desempenho superior ao dos melhores métodos existentes na literatura, conforme mostram os testes e resultados computacionais obtidos.