Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Sanches, Danilo Sipoli | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/6377657274398145 | - |
Autor(es): dc.contributor | Sanches, Danilo Sipoli | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/6377657274398145 | - |
Autor(es): dc.contributor | Sampaio, Lucas Dias Hiera | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/2330964607178017 | - |
Autor(es): dc.contributor | Tinós, Renato | - |
Autor(es): dc.contributor | http://lattes.cnpq.br/1273134370963830 | - |
Autor(es): dc.creator | Carvalho, Ozeas Quevedo de | - |
Data de aceite: dc.date.accessioned | 2022-02-21T22:13:58Z | - |
Data de disponibilização: dc.date.available | 2022-02-21T22:13:58Z | - |
Data de envio: dc.date.issued | 2020-11-02 | - |
Data de envio: dc.date.issued | 2020-11-02 | - |
Data de envio: dc.date.issued | 2019-08-13 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/5442 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/670612 | - |
Descrição: dc.description | The 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.description | O 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Cornelio Procopio | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Programa de Pós-Graduação em Informática | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Otimização combinatória | - |
Palavras-chave: dc.subject | Algoritmos Genéticos | - |
Palavras-chave: dc.subject | Recombinação (Genética) | - |
Palavras-chave: dc.subject | Combinatorial optimization | - |
Palavras-chave: dc.subject | Genetic algorithms | - |
Palavras-chave: dc.subject | Genetic recombination | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Palavras-chave: dc.subject | Ciência da Computação | - |
Título: dc.title | Identificação de componentes recombinantes no generalized partition crossover | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: