Please use this identifier to cite or link to this item: https://repositorio.ufrn.br/jspui/handle/123456789/18112
Title: Algoritmo treansgenético na solução do problema do Caixeiro Viajante
Authors: Bagi, Ligia Bariani
Keywords: Mercados;Algoritmo;PCC;Vetores;Transgenético;Traveling purchaser problem;Transgenetic;Algorithm;Evolution
Issue Date: 9-Feb-2007
Publisher: Universidade Federal do Rio Grande do Norte
Citation: BAGI, Ligia Bariani. Algoritmo treansgenético na solução do problema do Caixeiro Viajante. 2007. 169 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Rio Grande do Norte, Natal, 2007.
Portuguese Abstract: O Problema do Caixeiro Comprador é uma variante do Problema do Caixeiro Viajante, onde existe um conjunto de mercados e um conjunto de produtos. Cada produto está disponível em um subconjunto de mercados e o preço da unidade varia de acordo com o mercado. O objetivo é comprar todos os produtos, partindo e retornando para o depósito, de maneira que a soma do custo da rota e dos produtos seja mínimo. Um Algoritmo Transgenético, algoritmo evolucionário com base na endosimbiose, é utilizado para resolver a versão Capacitada e Não Capacitada desse problema. A evolução no algoritmo transgenético é simulada com a interação e troca de informações entre população de indivíduos de diferentes espécies. Os resultados computacionais mostram que a abordagem é satisfatória para o PCC , tanto na qualidade da solução, quanto no tempo de execução. Dezessete e nove novas melhores soluções são encontradas para o PCC Capacitado e para o PCC Não Capacitado, respectivamente
Abstract: The Traveling Purchaser Problem is a variant of the Traveling Salesman Problem, where there is a set of markets and a set of products. Each product is available on a subset of markets and its unit cost depends on the market where it is available. The objective is to buy all the products, departing and returning to a domicile, at the least possible cost defined as the summation of the weights of the edges in the tour and the cost paid to acquire the products. A Transgenetic Algorithm, an evolutionary algorithm with basis on endosymbiosis, is applied to the Capacited and Uncapacited versions of this problem. Evolution in Transgenetic Algorithms is simulated with the interaction and information sharing between populations of individuals from distinct species. The computational results show that this is a very effective approach for the TPP regarding solution quality and runtime. Seventeen and nine new best results are presented for instances of the capacited and uncapacited versions, respectively
URI: http://repositorio.ufrn.br:8080/jspui/handle/123456789/18112
Appears in Collections:PPGSC - Mestrado em Sistemas e Computação

Files in This Item:
File Description SizeFormat 
LigiaBB.pdf1.01 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.