Operadores de cruzamento para o problema da árvore de Steiner em grafos

Detalhes bibliográficos
Ano de defesa: 2021
Autor(a) principal: Godoi, Giliard Almeida de lattes
Orientador(a): Sanches, Danilo Sipoli lattes
Banca de defesa: Sanches, Danilo Sipoli lattes, Sampaio, Lucas Dias Hiera lattes, Tinos, Renato 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/30181
Resumo: O Problema da Árvore de Steiner em Grafos (STPG) tem por objetivo determinar uma árvore com o menor custo possível, que conecte um subconjunto de vértices terminais. O caso geral do STPG pertence à classe NP-difícil e diversas estratégias foram desenvolvidas para determinar soluções cada vez melhores. Apesar de abordagens utilizando Algoritmos Genéticos (GA) também terem sido propostas, elas não são competitivas quando comparadas com outras mais tradicionais. Esse pior desempenho pode estar relacionado ao uso de esquemas de codificação e operadores inadequados para as características do problema. Por exemplo, a representação binária e seus respectivos operadores podem codificar soluções infactíveis que se traduzem em subgrafos desconexos. Outros esquemas de codificação lidam diretamente com a representação em grafos das soluções candidatas e são capazes de representar somente soluções factíveis (árvores conexas e livres de ciclos). A representação denominada Edge Sets codifica uma árvore apenas pelo seu subconjunto de arestas e seus operadores de cruzamento são baseados em algoritmos para determinação de árvores geradoras. Outra classe de operadores, que também manipulam diretamente a representação em grafos dos indivíduos, são os operadores baseados em partição (PX, GPX, GAPX e GPX2). Eles foram originalmente propostos para o Problema do Caixeiro Viajante, cujas soluções são ciclos Hamiltonianos. Esses últimos operadores são conhecidos pelas características de transmissão de alelos (hereditariedade), respeitabilidade e tunelamento entre ótimos locais. O presente trabalho apresenta uma adaptação dos operadores baseados em partição para o STPG denominada PXST. Esse operador é então comparado com aqueles da representação por conjunto de arestas. Além disso, duas estratégias de reparo que aprimoram o custo das soluções candidatas foram investigadas. Experimentos com instâncias das classes B e C da biblioteca OR-Library demonstram que o operador PXST é competitivo, em termos de custo da melhor solução encontrada. Além disso, ele foi capaz de encontrar uma solução ótima global para todas as instâncias da classe B, com uma taxa de sucesso de 18% para o pior caso. Para as instâncias da classe C também obteve uma taxa de sucesso superior em muitos casos. Embora o GA com o operador PXST tende a ser mais rápido, isso se deve em parte à rápida estagnação da população de indivíduos.