Algoritmos evolutivos aplicados ao problema da árvore de steiner euclidiano
Ano de defesa: | 2019 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | , , |
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
|
Departamento: |
Não Informado pela instituição
|
País: |
Brasil
|
Palavras-chave em Português: | |
Área do conhecimento CNPq: | |
Link de acesso: | http://repositorio.utfpr.edu.br/jspui/handle/1/5298 |
Resumo: | 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. |