Algoritmos evolutivos aplicados ao problema da árvore de steiner euclidiano

Detalhes bibliográficos
Ano de defesa: 2019
Autor(a) principal: Oliveira, Andrey Vinicius Rocha de lattes
Orientador(a): Sanches, Danilo Sipoli lattes
Banca de defesa: Sanches, Danilo Sipoli lattes, Palacios, Rodrigo Henrique Cunha lattes, Soares, Telma Woerle De Lima lattes
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.