Identificação de componentes recombinantes no generalized partition crossover

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSanches, Danilo Sipoli-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6377657274398145-
Autor(es): dc.contributorSanches, Danilo Sipoli-
Autor(es): dc.contributorhttp://lattes.cnpq.br/6377657274398145-
Autor(es): dc.contributorSampaio, Lucas Dias Hiera-
Autor(es): dc.contributorhttp://lattes.cnpq.br/2330964607178017-
Autor(es): dc.contributorTinós, Renato-
Autor(es): dc.contributorhttp://lattes.cnpq.br/1273134370963830-
Autor(es): dc.creatorCarvalho, Ozeas Quevedo de-
Data de aceite: dc.date.accessioned2022-02-21T22:13:58Z-
Data de disponibilização: dc.date.available2022-02-21T22:13:58Z-
Data de envio: dc.date.issued2020-11-02-
Data de envio: dc.date.issued2020-11-02-
Data de envio: dc.date.issued2019-08-13-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/5442-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/670612-
Descrição: dc.descriptionThe Traveling Salesman Problem (TSP) is one of the best-known optimization problems and consists of finding the shortest Hamiltonian circuit for a set of vertices. Partition Crossover (PX) is an important recombination operator developed for the TSP. It generates offspring by the recombination of connected components found after removing shared edges from the graph formed by the union of parent solutions. The operator then determines which components can be recombined to generate offspring. However, not every connected component can be recombined. To identify recombining components, the operator applies a test comparing the simplified graphs of parent solutions within the component, called inner graphs. An inner graph simplifies one solution paths within a component. If solutions inner graphs are equal, the component is a recombining component. However, one can demonstrate that there are recombining components not identified by the operator. Based on the study of the relation between simplified graphs and perfect matchings, a concept from Graph Theory, this work proposes two additional tests. Experiments show that PX can find more recombining components applying the proposed tests, hence improving operator performance.-
Descrição: dc.descriptionO Problema do Caixeiro Viajante (PCV) é um dos mais conhecidos problemas de otimização e consiste em encontrar o menor circuito Hamiltoniano para um conjunto de vértices. O Partition Crossover (PX) é um importante operador de recombinação desenvolvido para o PCV. O operador gera descendentes pela recombinação dos componentes conectados encontrados após a remoção de arestas duplas do grafo formado pela união das soluções pais. Para tanto, o operador determina quais componentes podem ser recombinados para formar soluções filhas, chamados de componentes recombinantes. Para identificar componentes recombinantes, o operador aplica um teste que compara os grafos simplificados das soluções pais dentro do componente, chamados de grafos internos. Um grafo interno simplifica os caminhos de uma solução dentro de um componente. Se os grafos internos das soluções forem iguais, o componente é recombinante. No entanto, é possível demonstrar que existem componentes recombinantes que não são identificados pelo operador. A partir do estudo da relação entre grafos simplificados e emparelhamentos perfeitos, um conceito da Teoria dos Grafos, este trabalho propõe dois testes adicionais. Experimentos demonstram que o PX pode encontrar mais componentes recombinantes com o emprego dos testes propostos, melhorando assim o desempenho do operador.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherCornelio Procopio-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherPrograma de Pós-Graduação em Informática-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Palavras-chave: dc.subjectOtimização combinatória-
Palavras-chave: dc.subjectAlgoritmos Genéticos-
Palavras-chave: dc.subjectRecombinação (Genética)-
Palavras-chave: dc.subjectCombinatorial optimization-
Palavras-chave: dc.subjectGenetic algorithms-
Palavras-chave: dc.subjectGenetic recombination-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Palavras-chave: dc.subjectCiência da Computação-
Título: dc.titleIdentificação de componentes recombinantes no generalized partition crossover-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.