Operadores de recombinação baseados em permutação para representações de grafos
Nenhuma Miniatura disponível
Data
2017-08-23
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
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.
Descrição
Citação
LIMA, R. L. Operadores de recombinação baseados em permutação para representações de grafos. 2017. 81 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2017.