Registro fonte: Identificação de componentes recombinantes no generalized partition crossover

Identificação de componentes recombinantes no generalized partition crossover

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 co...

ver descrição completa

Autor principal:	Carvalho, Ozeas Quevedo de
Formato:	Dissertação
Idioma:	Português
Publicado em:	Universidade Tecnológica Federal do Paraná 2020
Assuntos:	Otimização combinatória Algoritmos Genéticos Recombinação (Genética) Combinatorial optimization Genetic algorithms Genetic recombination CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/5442
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-5442
recordtype	dspace
spelling	riut-1-54422020-11-04T06:01:05Z Identificação de componentes recombinantes no generalized partition crossover Carvalho, Ozeas Quevedo de Sanches, Danilo Sipoli http://lattes.cnpq.br/6377657274398145 Sanches, Danilo Sipoli http://lattes.cnpq.br/6377657274398145 Sampaio, Lucas Dias Hiera http://lattes.cnpq.br/2330964607178017 Tinós, Renato http://lattes.cnpq.br/1273134370963830 Otimização combinatória Algoritmos Genéticos Recombinação (Genética) Combinatorial optimization Genetic algorithms Genetic recombination CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação 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. 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. 2020-11-03T19:04:21Z 2020-11-03T19:04:21Z 2019-08-13 masterThesis CARVALHO, Ozeas Quevedo de. Identificação de componentes recombinantes no generalized partition crossover. 2019. Dissertação (Mestrado em Informática) - Universidade Tecnológica Federal do Paraná, Cornélio Procópio, 2019. http://repositorio.utfpr.edu.br/jspui/handle/1/5442 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Cornelio Procopio Brasil Programa de Pós-Graduação em Informática UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Otimização combinatória Algoritmos Genéticos Recombinação (Genética) Combinatorial optimization Genetic algorithms Genetic recombination CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação
spellingShingle	Otimização combinatória Algoritmos Genéticos Recombinação (Genética) Combinatorial optimization Genetic algorithms Genetic recombination CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Ciência da Computação Carvalho, Ozeas Quevedo de Identificação de componentes recombinantes no generalized partition crossover
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.
format	Dissertação
author	Carvalho, Ozeas Quevedo de
author_sort	Carvalho, Ozeas Quevedo de
title	Identificação de componentes recombinantes no generalized partition crossover
title_short	Identificação de componentes recombinantes no generalized partition crossover
title_full	Identificação de componentes recombinantes no generalized partition crossover
title_fullStr	Identificação de componentes recombinantes no generalized partition crossover
title_full_unstemmed	Identificação de componentes recombinantes no generalized partition crossover
title_sort	identificação de componentes recombinantes no generalized partition crossover
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2020
citation	CARVALHO, Ozeas Quevedo de. Identificação de componentes recombinantes no generalized partition crossover. 2019. Dissertação (Mestrado em Informática) - Universidade Tecnológica Federal do Paraná, Cornélio Procópio, 2019.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/5442
_version_	1805320668094398464
score	10,814766

Identificação de componentes recombinantes no generalized partition crossover

Registros relacionados