Return to search

Algoritmos experimentais para o problema biobjetivo da ?rvore geradora quadr?tica em adjac?ncia de arestas / The biobjective adjacent only quadratic spanning tree problem

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2016-07-22T15:02:53Z
No. of bitstreams: 1
LucasDanielMonteiroDosSantosPinheiro_DISSERT.pdf: 1789796 bytes, checksum: 996c49626073bcec8708e85866e1f00e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2016-07-26T23:43:20Z (GMT) No. of bitstreams: 1
LucasDanielMonteiroDosSantosPinheiro_DISSERT.pdf: 1789796 bytes, checksum: 996c49626073bcec8708e85866e1f00e (MD5) / Made available in DSpace on 2016-07-26T23:43:20Z (GMT). No. of bitstreams: 1
LucasDanielMonteiroDosSantosPinheiro_DISSERT.pdf: 1789796 bytes, checksum: 996c49626073bcec8708e85866e1f00e (MD5)
Previous issue date: 2016-02-03 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico (CNPq) / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / O problema da ?rvore Geradora M?nima Quadr?tica (AGMQ) ? uma generaliza??o doproblema da ?rvore Geradora M?nima onde, al?m dos custos lineares das arestas, custosquadr?ticos associados a cada par de arestas s?o considerados. Os custos quadr?ticos s?odevidos ? custos de intera??o entre as arestas. No caso das intera??es ocorrerem somenteentre arestas adjacentes, o problema ? denominado ?rvore Geradora M?nima Quadr?ticaem Adjac?ncia de Arestas (AGMQA). Tanto a AGMQ quanto a AGMQA s?o NP-dif?ceise modelam diversos problemas reais envolvendo projeto de redes de infraestrutura. Oscustos lineares e quadr?ticos s?o somados nas vers?es mono-objetivo destes problemas.Frequentemente, aplica??es reais lidam com objetivos conflitantes. Nestes casos a considera??o dos custos lineares e quadr?ticos separadamente ? mais adequada e a otimiza??omultiobjetivo prov? modelos mais realistas. Algoritmos exatos e heur?sticos s?o investigados neste trabalho para a vers?o biobjetivo da AGMQA. As seguintes t?cnicas s?opropostas: backtracking, branch-and-bound, busca local, Greedy RandomizedAdaptive Search Procedure, Simulated Annealing, NSGAII, Algoritmo Transgen?tico, Otimiza??o por Nuvem de Part?culas e uma hibridiza??o entre a t?cnica do MOEA-D eo Algoritmo Transgen?tico. S?o utilizados indicadores de qualidade Pareto concordantespara comparar os algoritmos em um conjunto de inst?ncias de bases de dado da literatura. / The Quadratic Minimum Spanning Tree (QMST) problem is a generalization of the Minimum
Spanning Tree problem in which, beyond linear costs associated to each edge,
quadratic costs associated to each pair of edges must be considered. The quadratic costs
are due to interaction costs between the edges. When interactions occur between adjacent
edges only, the problem is named Adjacent Only Quadratic Minimum Spanning
Tree (AQMST). Both QMST and AQMST are NP-hard and model a number of real
world applications involving infrastructure networks design. Linear and quadratic costs
are summed in the mono-objective versions of the problems. However, real world applications
often deal with conflicting objectives. In those cases, considering linear and quadratic
costs separately is more appropriate and multi-objective optimization provides a more
realistic modelling. Exact and heuristic algorithms are investigated in this work for the
Bi-objective Adjacent Only Quadratic Spanning Tree Problem. The following techniques
are proposed: backtracking, branch-and-bound, Pareto Local Search, Greedy Randomized
Adaptive Search Procedure, Simulated Annealing, NSGA-II, Transgenetic Algorithm,
Particle Swarm Optimization and a hybridization of the Transgenetic Algorithm with
the MOEA-D technique. Pareto compliant quality indicators are used to compare the
algorithms on a set of benchmark instances proposed in literature.

Identiferoai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/21031
Date03 February 2016
CreatorsPinheiro, Lucas Daniel Monteiro dos Santos
Contributors81652011749, http://lattes.cnpq.br/2888641121265608, Goldbarg, Marco Cesar, 25841025953, http://lattes.cnpq.br/1371199678541174, Gon?alves, Richard Aderbal, 28850139829, http://lattes.cnpq.br/4210531173050798, Maia, Silvia Maria Diniz Monteiro, Gouvea, Elizabeth Ferreira
PublisherUniversidade Federal do Rio Grande do Norte, PROGRAMA DE P?S-GRADUA??O EM SISTEMAS E COMPUTA??O, UFRN, Brasil
Source SetsIBICT Brazilian ETDs
LanguagePortuguese
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis
Sourcereponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN
Rightsinfo:eu-repo/semantics/openAccess

Page generated in 0.0018 seconds