Please use this identifier to cite or link to this item: http://monografias.ufrn.br/handle/123456789/7679
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorMaia, Sílvia Maria Diniz Monteiro-
dc.contributor.authorIsabel, Fernanda Menezes Paes-
dc.date.accessioned2018-12-07T19:50:17Z-
dc.date.available2018-12-07T19:50:17Z-
dc.date.issued2018-11-30-
dc.identifier20170153995pt_BR
dc.identifier.citationISABEL, 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.pt_BR
dc.identifier.urihttp://monografias.ufrn.br/jspui/handle/123456789/7679-
dc.description.abstractO 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.pt_BR
dc.languageenpt_BR
dc.publisherUniversidade Federal do Rio Grande do Nortept_BR
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 Brazil*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/br/*
dc.subjectQMSTpt_BR
dc.subjectmetaheuristicpt_BR
dc.subjecttransgenetic algorithmpt_BR
dc.titleA transgenetic algorithm for the quadratic minimum spanning tree problempt_BR
dc.title.alternativeUm algoritmo transgenético para o problema da árvore geradora mínima quadráticapt_BR
dc.typebachelorThesispt_BR
dc.contributor.referees1Goldbarg, Elizabeth Ferreira Gouvêa-
dc.contributor.referees2Goldbarg, Marco César-
dc.description.resumoThe 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.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentCiência da Computaçãopt_BR
dc.publisher.initialsUFRNpt_BR
dc.subject.cnpq1.03.01.03-8 Análise de Algoritmos e Complexidade de Computaçãopt_BR
Appears in Collections:Ciência da Computação

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


This item is licensed under a Creative Commons License Creative Commons