Operador de recombinação EHR aplicado ao problema da árvore máxima
dc.contributor.advisor1 | Soares, Telma Woerle de Lima | |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/6296363436468330 | por |
dc.contributor.referee1 | Soares, Telma Woerle de Lima | |
dc.contributor.referee2 | Soares, Anderson da Silva | |
dc.contributor.referee3 | Delbem, Alexandre Cláudio Botazzo | |
dc.creator | Faria, Danilo Alves Martins de | |
dc.creator.Lattes | http://lattes.cnpq.br/6389001801524739 | por |
dc.date.accessioned | 2014-11-20T14:17:45Z | |
dc.date.issued | 2013-10-23 | |
dc.description.abstract | 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. | por |
dc.description.provenance | 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) | eng |
dc.description.provenance | 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) | eng |
dc.description.provenance | 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 | eng |
dc.description.resumo | 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. | por |
dc.description.sponsorship | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES | por |
dc.format | application/pdf | * |
dc.identifier.citation | 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. | por |
dc.identifier.uri | http://repositorio.bc.ufg.br/tede/handle/tede/3655 | |
dc.language | por | por |
dc.publisher | Universidade Federal de Goiás | por |
dc.publisher.country | Brasil | por |
dc.publisher.department | Instituto de Informática - INF (RG) | por |
dc.publisher.initials | UFG | por |
dc.publisher.program | Programa de Pós-graduação em Ciência da Computação (INF) | por |
dc.rights | Acesso Aberto | por |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
dc.subject | Nó-profundidade-grau | por |
dc.subject | Algoritmos evolutivos | por |
dc.subject | Projeto de rede | por |
dc.subject | Problema da árvore máxima | por |
dc.subject | Node-deep-degree encoding | eng |
dc.subject | Evolutionary algorithms | eng |
dc.subject | Network design | eng |
dc.subject | One-max tree problem | eng |
dc.subject.cnpq | CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO | por |
dc.thumbnail.url | http://repositorio.bc.ufg.br/tede/retrieve/12660/Disserta%c3%a7%c3%a3o%20-%20Danilo%20Alves%20Martins%20de%20Faria%20-%202013.pdf.jpg | * |
dc.title | Operador de recombinação EHR aplicado ao problema da árvore máxima | por |
dc.type | Dissertação | por |
Arquivos
Pacote Original
1 - 1 de 1
Carregando...
- Nome:
- Dissertação - Danilo Alves Martins de Faria - 2013.pdf
- Tamanho:
- 1.13 MB
- Formato:
- Adobe Portable Document Format
- Descrição:
Licença do Pacote
1 - 1 de 1
Nenhuma Miniatura disponível
- Nome:
- license.txt
- Tamanho:
- 2.11 KB
- Formato:
- Item-specific license agreed upon to submission
- Descrição: