Operadores de recombinação baseados em permutação para representações de grafos

• Ano de defesa: 2017
• Autor(a) principal: Lima , Roney Lopes
• Orientador(a): Soares , Telma Woerle de Lima
• Banca de defesa: Soares , Telma Woerle de Lima , Camilo Junior, Celso Gonçalves, Sanches , Danilo Sipoli
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Goiás
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação (INF)
• Departamento: Instituto de Informática - INF (RG)
• País: Brasil
• Palavras-chave em Português: Nó profundidade; Operadores de recombinação; Permutação; Projeto de rede; Árvore geradora mínima com restrição de diâmetro
• Palavras-chave em Inglês: Node depth; Recombination operators; Permutation; Network design; Bounded diameter minimmum spanning tree
• Área do conhecimento CNPq: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/7770

The application of Evolutionary Algorithms in the solution of problems characterized by the unviability through deterministic methods, has made this technique a vast object investigated. Its application to Network Design Problems (NDPs), has been specially studied. NDPs are characterized by modeling real world problems related to network design applied to resource distribution, logistics, telecommunications, routing and even social networks. The solution to these problems involves searching for a graph such as trees that meets criteria for cost minimization, availability, scaling among other constraints that make them complex. The application of Evolutionary Agorithms to NDPs requires a Representation that codes solutions properly towards to these problems. The Node-Depth Encoding (NDE) has been studied and presented results that have aroused the attention of researchers in this topic. In this work, we propose the development of a new recombination operator for NDE called NCX, based on the permutation recombination operator CX. In addition, a method is proposed for correction of infeasible solutions due to an invalid depth for a position in the array. The correction method is applied to both NCX, NOX and NPBX. The operators with their methods of correction are validated for the bias and heritability properties and finally are applied to the Bounded Diameter Minimmum Spanning Tree (BDMSTP) through Evolutionary Algorithms developed for this NDP. The results show that the operators have bias towards to star like trees and good heritability of the edges and depths of the vertices. The developed operators also showed competitiveness when applied to the BDMSTP, even surpassing other representations in the quality of the solutions.