Operador de recombinação EHR aplicado ao problema da árvore máxima
Carregando...
Data
2013-10-23
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
Network Design Problems (NDPs) are present in many areas, such as electric power
distribution, communication networks, vehicle routing, phylogenetic trees among others.
Many NDPs are classified as NP-Hard problems. Among the techniques used to solve
them, we highlight the Evolutionary Algorithms (EA). These algorithms simulate the
natural evolution of the species. However, in its standard form EAs have limitations to
solve large scale NDPs, or with very specific characteristics. To solve these problems,
many researchers have studied specific forms of representation of NDPs. Among these
stands we show Node-Depth-Degre Encoding (NDDE). This representation produces only
feasible solutions, regardless of the network characteristics. NDDE has two mutation
operators Preserve Ancestor Operator (PAO) and Ancestor Change Operator (CAO) and
the recombination operator EHR (Evolutionary History Recombination Operator) that
uses historical applications of mutation, and was applied to NDPs more than one tree
and had good results. Thus, this work proposes adapt EHR for NDPs classics represented
by a single tree. In addition, two evolutionary algorithms are developed: the AE-RNPG,
which uses only NDDE, with mutation operators. And the AE-EHR, which makes use of
mutation operators and recombination operator EHR to the One Max Tree Problem. The
results showed that the AE-EHR obtained better solutions than the EA-RNPG for most
instances analyzed.
Descrição
Citação
FARIA, Danilo Alves Martins de. Operador de recombinação EHR aplicado ao problema da árvore máxima. 2013. 86 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2013.