Operadores de recombinação baseados em permutação para representações de grafos

Página do item simplificado
dc.contributor.advisor1Soares , Telma Woerle de Lima
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/6296363436468330eng
dc.contributor.referee1Soares , Telma Woerle de Lima
dc.contributor.referee1Latteshttp://lattes.cnpq.br/6296363436468330eng
dc.contributor.referee2Camilo Junior, Celso Gonçalves
dc.contributor.referee3Sanches , Danilo Sipoli
dc.creatorLima , Roney Lopes
dc.creator.Latteshttp://lattes.cnpq.br/3406246380949411eng
dc.date.accessioned2017-09-19T14:01:45Z
dc.date.issued2017-08-23
dc.description.abstractThe 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.eng
dc.description.provenanceSubmitted 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)eng
dc.description.provenanceApproved 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)eng
dc.description.provenanceMade 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-23eng
dc.description.resumoA 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.eng
dc.description.sponsorshipFundação de Amparo à Pesquisa do Estado de Goiás - FAPEGeng
dc.formatapplication/pdf*
dc.identifier.citationLIMA, 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.eng
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/7770
dc.languageporeng
dc.publisherUniversidade Federal de Goiáseng
dc.publisher.countryBrasileng
dc.publisher.departmentInstituto de Informática - INF (RG)eng
dc.publisher.initialsUFGeng
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)eng
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectNó profundidadepor
dc.subjectOperadores de recombinaçãopor
dc.subjectPermutaçãopor
dc.subjectProjeto de redepor
dc.subjectÁrvore geradora mínima com restrição de diâmetropor
dc.subjectNode deptheng
dc.subjectRecombination operatorseng
dc.subjectPermutationeng
dc.subjectNetwork designeng
dc.subjectBounded diameter minimmum spanning treeeng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOeng
dc.titleOperadores de recombinação baseados em permutação para representações de grafoseng
dc.title.alternativePermutation based recombination operators for graph representationseng
dc.typeDissertaçãoeng

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Roney Lopes Lima - 2017.pdf
Tamanho:
3.31 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 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:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)