Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2017-09-13T18:01:57Z
No. of bitstreams: 2
Dissertação - Roney Lopes Lima - 2017.pdf: 3471034 bytes, checksum: 2dd29fe3cd16f3d5ac0ddabf0ce316b4 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-19T14:01:45Z (GMT) No. of bitstreams: 2
Dissertação - Roney Lopes Lima - 2017.pdf: 3471034 bytes, checksum: 2dd29fe3cd16f3d5ac0ddabf0ce316b4 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-09-19T14:01:45Z (GMT). No. of bitstreams: 2
Dissertação - Roney Lopes Lima - 2017.pdf: 3471034 bytes, checksum: 2dd29fe3cd16f3d5ac0ddabf0ce316b4 (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2017-08-23 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / 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. / A aplicação de Algoritmos Evolutivos na resolução de problemas caracterizados pela
inviabilidade de solução através de métodos determinísticos, fez dessa técnica um objeto
vastamente investigado. Sua aplicação para Problemas de Projeto de Redes (PPRs), tem sido
especialmente estudada. PPRs são caracterizados por modelar problemas reais relacionados a
design de redes aplicados a distribuição de recursos, logística, telecomunicações, roteamento
e até mesmo redes sociais. A solução desses problemas envolve a busca de um grafo como
uma árvore por exemplo que atenda a critérios de minimização de custos, disponibilidade,
escala entre outras restrições que os tornam complexos. A aplicação de Algoritmos Evolutivos
a PPRs demanda a utilização de uma Representação que codifique adequadamente soluções
para esses problemas. A Representação Nó-Profundidade (RNP) tem sido estudada e
apresentado resultados que despertaram a atenção dos pesquisadores nesse tema. Neste
trabalho, propõe-se o desenvolvimento de um novo operador de recombinação para a RNP
chamado NCX, com base no operador CX de recombinação em permutações. Além disso, é
proposto um método para correção de soluções infactíveis devido a profundidade inválida para
a posição no \textit{array}. O método de correção é aplicado tanto para NCX, quanto para
outros dois operadores de recombinação já desenvolvidos para a RNP, o NOX cujo
funcioamento é inspirado no operador OX, e NPBX cujo funcionamento é inspirado no
operador PBX. Os operadores com os seus devidos métodos de correção são validados para as
propriedades tendência e hereditariedade e por fim são aplicados ao Problema da Árvore
Geradora Mínima com Restrição de Diâmetro (BDMSTP) através de Algoritmos Evolutivos
desenvolvidos para esse PPR. Os resultados mostram que os operadores possuem tendência
para árvores estrela e boa hereditariedade das arestas e das profundidades dos vértices. Os
operadores desenvolvidos também mostraram competitividade ao serem aplicados ao
BDMSTP, chegando a superar outras representações em qualidade das soluções.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/7770 |
| Date | 23 August 2017 |
| Creators | Lima , Roney Lopes |
| Contributors | Soares , Telma Woerle de Lima, Soares , Telma Woerle de Lima, Camilo Junior, Celso Gonçalves, Sanches , Danilo Sipoli |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, -961409807440757778 |
Page generated in 0.0137 seconds