Algoritmos evolutivos aplicados ao problema da árvore de steiner euclidiano

• Ano de defesa: 2019
• Autor(a) principal: Oliveira, Andrey Vinicius Rocha de
• Orientador(a): Sanches, Danilo Sipoli
• Banca de defesa: Sanches, Danilo Sipoli , Palacios, Rodrigo Henrique Cunha , Soares, Telma Woerle De Lima
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Tecnológica Federal do Paraná; Cornelio Procopio
• Programa de Pós-Graduação: Programa de Pós-Graduação em Informática
• País: Brasil
• Palavras-chave em Português: Algoritmos computacionais; Árvores (Teoria dos grafos); Algoritmos genéticos; Computer algorithms; Trees (Graph theory); Genetic algorithms
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.utfpr.edu.br/jspui/handle/1/5298

Este trabalho apresenta a aplicação de algoritmos evolutivos híbridos para o problema da árvore de Steiner euclidiano. Esse e um problema de otimização cujo objetivo é obter uma árvore de comprimento mínimo para interconectar um conjunto de pontos fixos. Para que esse objetivo seja alcançado e permitido adicionar novos pontos, denominados pontos Steiner. Com a finalidade de obter soluções de boa qualidade em tempo computacional viável, duas heurísticas são utilizadas, uma utiliza o algoritmo evolução diferencial em que são testadas estratégias de mutação e a outra faz uso de um algoritmo genético, em que se investiga os efeitos de operadores de cruzamento e mutação relativamente gulosos, sobreposição de gerações e estratégias evolutivas. Os experimentos são realizados com os problemas da biblioteca OR-Library e apresentam resultados próximos aos melhores métodos presentes na literatura.