Please use this identifier to cite or link to this item: http://monografias.ufrn.br/jspui/handle/123456789/7679
Title: A transgenetic algorithm for the quadratic minimum spanning tree problem
Other Titles: Um algoritmo transgenético para o problema da árvore geradora mínima quadrática
Authors: Isabel, Fernanda Menezes Paes
Keywords: QMST;metaheuristic;transgenetic algorithm
Issue Date: 30-Nov-2018
Publisher: Universidade Federal do Rio Grande do Norte
Citation: ISABEL, Fernanda Menezes Paes. A Transgenetic Algorithm for the Quadratic Minimum Spanning Tree Problem. 2018. 49 f. Trabalho de Conclusão de Curso (Ciência da Computação) - Departamento de Informática e Matemática Aplicada, Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2018.
Portuguese Abstract: The Quadratic Minimum Spanning Tree Problem is a variation of the classic Minimum Spanning Tree Problem which considers the costs of pairs of edges as well as the costs of edges. This problem is NP-hard and therefore there isn’t a known polynomial time solu- tion for it. Since it was first described, several metaheuristic approaches have been applied to this problem, trying to find close-to-optimal solutions. Out of those, the tabu search technique has shown the most promising results, having been successfully applied to this problem many times. This work proposes a new metaheuristic approach to this prob- lem, a transgenetic algorithm. The transgenetic algorithm is an evolutionary algorithm that has shown good results for other optimization problems. The proposed transgenetic algorithm was implemented, as well as a tabu search from the literature for comparison purposes. Computational experiments were performed on those algorithms and the results are described and analyzed in this work.
Abstract: O problema da árvore geradora mímina quadrática é uma variação do problema clássico da árvore geradora mínima que considera o custo de pares de arestas além do custo de arestas. Esse problema é NP-difícil e portanto não é conhecida uma solução exata em tempo polinomial para ele. Desde que foi descrito pela primeira vez, várias aborgadens meta- heurísticas foram aplicadas a esse problema, tentando encontrar soluções quase ótimas. Destas, a técnica de busca tabu foi a que apresentou resultados mais promissores, já tendo sido aplicada com sucesso a esse problema muitas vezes. Este trabalho propões uma nova abordagem meta-heurística para esse problema, um algoritmo transgenético. O algoritmo transgenético é um algoritmo evolucionário que já mostrou bons resultados para outros problemas de otimização. O algoritmo transgenético proposto foi implementado, assim como uma busca tabu da literatura para comparação. Experimentos computacionais foram realizados e os resultados são descritos e analisados neste trabalho.
URI: http://monografias.ufrn.br/jspui/handle/123456789/7679
Other Identifiers: 20170153995
Appears in Collections:Ciência da Computação

Files in This Item:
File Description SizeFormat 
ATransgeneticAlgorithm_Isabel_2018.pdfATransgeneticAlgorithm_Isabel_2018638.48 kBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons