Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-20T11:31:40Z
No. of bitstreams: 2
Dissertação - Danilo Alves Martins de Faria - 2013.pdf: 1188393 bytes, checksum: c56b169690f22bbbeaa2ee6fa46ade1c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-11-20T14:17:45Z (GMT) No. of bitstreams: 2
Dissertação - Danilo Alves Martins de Faria - 2013.pdf: 1188393 bytes, checksum: c56b169690f22bbbeaa2ee6fa46ade1c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-11-20T14:17:45Z (GMT). No. of bitstreams: 2
Dissertação - Danilo Alves Martins de Faria - 2013.pdf: 1188393 bytes, checksum: c56b169690f22bbbeaa2ee6fa46ade1c (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2013-10-23 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / 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. / Problemas de Projeto de Redes (PPRs) estão presentes em diversas áreas, tais como reconfiguração
de sistemas de distribuição de energia elétrica, projetos de redes de comunicação,
roteamento de veículos, reconstrução de árvores filogenéticas entre outros. Vários
PPRs pertencem à classe de problemas NP-Difíceis. Dentre as técnicas utilizadas para
resolvê-los, destacam-se os Algoritmos Evolutivos (AE), cujo processo de resolução de
um problema simula a evolução natural das espécies. Entretanto, os AEs em sua forma
padrão também possuem limitações quanto a PPRs de larga escala, ou com características
muito específicas. Para solucionar esses problemas, diversas pesquisas têm estudado
formas específicas de estruturas de dados dos PPRs. Dentre essas destaca-se a representação
Nó-Profundidade-Grau (RNPG). Essa representação produz apenas soluções factíveis,
independente da característica da rede. A RNPG possui dois operadores de mutação
Preserve Ancestor Operator (PAO) e Change Ancestor Operator (CAO) e o operador de
recombinação EHR (Evolutionary History Recombination Operator), que utiliza o histórico
de aplicações dos operadores de mutação, o qual tem sido aplicado a PPRs com
mais de uma árvore com bons resultados. Este trabalho propõem a adequação do EHR
para PPRs clássicos de uma única árvore. Além disso, são desenvolvidos dois algoritmos
evolutivos: o AE-RNPG, que utiliza a RNPG somente com os operadores de mutação; e
o AE-EHR, que faz uso tanto dos operadores de mutação quanto do operador de recombinação
EHR para o problema da Árvore máxima. Os resultados obtidos mostram que
o AE-EHR obtém melhores soluções do que o AE-RNPG para a maioria das instâncias
analisadas.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3655 |
| Date | 23 October 2013 |
| Creators | Faria, Danilo Alves Martins de |
| Contributors | Soares, Telma Woerle de Lima, Soares, Telma Woerle de Lima, Soares, Anderson da Silva, Delbem, Alexandre Cláudio Botazzo |
| 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, 8930092515683771531, 2075167498588264571 |
Page generated in 0.0023 seconds