Please use this identifier to cite or link to this item: http://monografias.ufrn.br/handle/123456789/4319
Title: Hibridização de algoritmos exatos e meta-heurísticas para o problema da árvore geradora quadrática em adjacência de arestas biobjetivo
Authors: Marques, Thiago Soares
Keywords: Árvore Geradora Quadrática em Adjacência de Arestas Biobjetivo. Meta-heurísticas. Algoritmos Exatos. Hibridização. Otimização Multiobjetivo;Biobjective Adjacency-Only Quadratic Minimum Spanning Tree. Metaheuristics. Exact Algorithms. Hybridization. Multiobjective Optimization
Issue Date: Jun-2017
Publisher: Universidade Federal do Rio Grande do Norte
Citation: MARQUES, Thiago Soares. Hibridização de algoritmos exatos e meta-heurísticas para o problema da árvore geradora quadrática em adjacência de arestas biobjetivo. 2017. 84 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação), Universidade Federal do Rio Grande do Norte, Natal, 2017.
Portuguese Abstract: O problema da Árvore Geradora Mínima (AGM) consiste em, dado um grafo finito não direcionado G = (V, E) com |V| = n e |E| = m, ponderado em arestas, encontrar um subgrafo gerador acíclico e conexo de modo que a soma dos pesos das arestas seja mínima. Esse é um problema clássico de otimização combinatória que pode ser resolvido de maneira ótima em tempo polinomial. O problema da Árvore Geradora Mínima Quadrática (AGMQ) é uma generalização da AGM na qual custos quadráticos associados à interação de cada par de arestas estão presentes. Os custos lineares e quadráticos são somados de modo a compor o custo total da árvore geradora resultante. Uma vez que apenas interações de arestas adjacentes são consideradas, o problema é denominado Árvore Geradora Mínima Quadrática em Adjacência de Arestas (AGMQA). Ambos AGMQ e AGMQA são problemas NP-Difíceis que procuram modelar problemas reais envolvendo projeto de redes de transporte e distribuição. Por exemplo, no transporte de petróleo e seus derivados. O transporte acontece através de dutos, os quais possuem interfaces de conexão entre eles. Assim, o custo de transportar petróleo e seus derivados de um duto para outro, pode depender da natureza das suas interfaces. Embora na versão mono-objetivo os custos lineares e quadráticos são somados, em aplicações reais tais custos podem ser conflitantes, o que torna mais interessante considerá-los independentemente. Neste sentido, a otimização multiobjetivo parece proporcionar um modelo mais realista para os problemas da AGMQ e AGMQA, dando origem ao problema da AGQA Biobjetivo (AGQA-bi). Na formulação sob a perspectiva biobjetivo é considerado o fato de que os custos lineares e quadráticos podem assumir situações conflitantes. Em geral, pode-se resolver AGQA-bi a partir de estratégias exatas e (meta) heurísticas, todavia ambas as abordagens possuem desvantagens. O exato pode tomar um tempo computacional não admissível, enquanto que as heurísticas nem sempre encontrarão a solução ótima do problema. Assim, um terceiro enfoque é combinar esses métodos a fim de minimizar as desvantagens de cada abordagem, sendo este o estudo realizado neste trabalho.
Abstract: The Minimum Spanning Tree Problem (MST) consists of, given a finite non-directed graph G = (V, E) with |V| = n and |E| = m, weighted by edges, find an acyclic and connected spanning subgraph so that the sum of the weights of the edges is minimal. This is a classic problem of combinatorial optimization that can be solved optimally in polynomial time. The Quadratic Minimum Spanning Tree Problem (QMST) is a generalization of MST in which quadratic costs associated with the interaction of each pair of edges are present. The linear and quadratic costs are summed to make up the total cost of the resulting spanning tree. Since only adjacent edge interactions are considered, the problem is called the Adjacency-Only Quadratic Minimum Spanning Tree (AQMST). Both QMST and AQMST are NP-Hard problems that attempt to model real problems involving the design of transport and distribution networks. For example, in the transportation of petroleum and its derivatives. Transportation takes place through pipes, which have connection interfaces between them. Thus, the cost of transporting oil and its derivatives from one pipeline to another may depend on the nature of their interfaces. Although in the mono-objective version, linear and quadratic costs are summed up, but in real applications such costs can be conflicting, which makes it more interesting to consider them independently. In this sense, multiobjective optimization seems to provide a more realistic model for the problems of QMST and AQMST, giving rise to the Biobjective Adjacency-Only Quadratic Spanning Tree Problem (bi-AQST). In the formulation by the biobjective perspective it is considered the fact that linear and quadratic costs can assume conflicting situations. In general, bi-AQST can be solved from exact strategies and (meta) heuristics, but both approaches have drawbacks. The exact one can take an inadmissible computational time, whereas the heuristics will not always find the optimal solution of the problem. Thus, a third approach is to combine these methods in order to minimize the disadvantages of each approach, this being the study carried out in this work.
URI: http://monografias.ufrn.br/jspui/handle/123456789/4319
Other Identifiers: 2016007211
Appears in Collections:Ciência da Computação

Files in This Item:
File Description SizeFormat 
HibridizaçaoAlgoritmos_Marques_2017.pdfMonografia891.01 kBAdobe PDFThumbnail
View/Open


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