Made available in DSpace on 2014-12-17T15:47:03Z (GMT). No. of bitstreams: 1
SilviaMDMM_TESE.pdf: 3010194 bytes, checksum: 43610ec3f0a30c2e5ef7fb5c0b2dc5b0 (MD5)
Previous issue date: 2013-12-16 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum
Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic
structure of costs. This quadratic structure models interaction effects between pairs of edges.
Linear and quadratic costs are added up to constitute the total cost of the spanning
tree, which must be minimized. When these interactions are restricted to adjacent edges,
the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST).
AQMST and QMST are NP-hard problems that model several problems of transport and
distribution networks design. In general, AQMST arises as a more suitable model for real
problems. Although, in literature, linear and quadratic costs are added, in real applications,
they may be conflicting. In this case, it may be interesting to consider these costs
separately. In this sense, Multiobjective Optimization provides a more realistic model for
QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers
regarding these problems under a biobjective point of view. Thus, the objective of this
Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent
Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation,
other NP-hard problems directly related to bi-AQST are discussed: the QMST
and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed
to the target problem of this investigation. The heuristic algorithms developed are:
Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II
and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms
are compared to each other through performance analysis regarding computational
experiments with instances adapted from the QMST literature. With regard to exact algorithms,
the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is
evaluated. Quality indicators are used to assess such information. Appropriate statistical
tools are used to measure the performance of exact and heuristic algorithms. Considering
the set of instances adopted as well as the criteria of execution time and quality of the
generated approximation set, the experiments showed that the Tabu Search with ejection
chain approach obtained the best results and the transgenetic algorithm ranked second.
The PLS algorithm obtained good quality solutions, but at a very high computational
time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II
algorithms got the last positions / O problema da ?rvore Geradora M?nima Quadr?tica (AGMQ) ? uma vers?o do problema
da ?rvore Geradora M?nima na qual se considera, al?m dos custos lineares tradicionais,
uma estrutura de custos quadr?tica. Tal estrutura quadr?tica modela efeitos de intera??o
entre pares de arestas. Os custos lineares e quadr?ticos s?o somados para compor o custo
total da ?rvore geradora, que deve ser minimizado. Quando as intera??es s?o restritas ?s
arestas adjacentes, o problema ? denominado ?rvore Geradora M?nima Quadr?tica em
Adjac?ncia de Arestas (AGMQA). A AGMQA e a AGMQ s?o problemas NP-dif?ceis que
modelam diversos problemas de projeto de redes de transporte e distribui??o. Em geral, a
AGMQA emerge como um modelo mais apropriado para a modelagem de problemas reais.
Embora, na literatura, os custos lineares e quadr?ticos sejam somados, em aplica??es
reais, os custos linear e quadr?tico podem ser conflitantes. Neste caso, seria mais interessante
considerar os custos separadamente. Neste sentido, a Otimiza??o Multiobjetivo
prov? uma modelagem mais realista para os problemas da AGMQ e da AGMQA. Uma
revis?o do estado da arte, at? o momento, n?o foi capaz de encontrar qualquer trabalho
que investigue esses problemas sob um ponto de vista biobjetivo. O objetivo desta Tese
?, pois, o desenvolvimento de algoritmos exatos e heur?sticos para o Problema Biobjetivo
da ?rvore Geradora Quadr?tica em Adjac?ncia de Arestas (AGQA-bi). Para tanto,
como fundamenta??o te?rica, discutem-se outros problemas NP-dif?ceis diretamente relacionados
? AGQA-bi, a saber: AGMQ e AGMQA. Algoritmos exatos backtracking e
branch-and-bound s?o propostos para o problema-alvo desta investiga??o. Os algoritmos
heur?sticos desenvolvidos s?o: busca local Pareto Local Search, Busca Tabu com ejection
chain, Algoritmo Transgen?tico, NSGA-II e uma hibridiza??o das duas ?ltimas propostas
mencionadas denominada NSTA. Os algoritmos propostos s?o comparados entre si por
meio da an?lise de seus desempenhos em experimentos computacionais com casos de teste
adaptados da literatura da AGMQ. No que se refere aos algoritmos exatos, a an?lise considera,
em especial, o tempo de execu??o. No caso dos algoritmos heur?sticos, al?m do tempo
de execu??o, a qualidade do conjunto de aproxima??o gerado ? avaliada. Indicadores de
qualidade s?o empregados para aferir tal informa??o. Ferramentas estat?sticas apropriadas
s?o usadas na an?lise de desempenho dos algoritmos exatos e heur?sticos. Para o conjunto
de inst?ncias utilizado e considerando os crit?rios de qualidade dos conjuntos de aproxima??o
gerados e tempo de execu??o dos algoritmos, os experimentos mostraram que o
algoritmo de Busca Tabu com ejection chain obteve melhores resultados e que o algoritmo
transgen?tico ficou em segundo lugar. A busca local PLS obteve solu??es de qualidade,
mas a um tempo computacional muito alto se comparado ?s outras (meta)heur?sticas.
Nesse sentido, ocupa a terceira coloca??o. Por fim, ficaram os algoritmos NSTA e NSGAII
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufrn.br:123456789/17955 |
| Date | 16 December 2013 |
| Creators | Maia, Silvia Maria Diniz Monteiro |
| Contributors | CPF:81652011749, http://lattes.cnpq.br/2888641121265608, Coelho, Andr? Lu?s Vasconcelos, CPF:51077124368, http://lattes.cnpq.br/8377890158420707, Cabral, Luc?dio dos Anjos Formiga, CPF:37383388372, http://lattes.cnpq.br/6699185881827288, Goldbarg, Marco C?sar, CPF:25841025953, http://lattes.cnpq.br/1371199678541174, Gouv?a, Elizabeth Ferreira |
| Publisher | Universidade Federal do Rio Grande do Norte, Programa de P?s-Gradua??o em Sistemas e Computa??o, UFRN, BR, Ci?ncia da Computa??o |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFRN, instname:Universidade Federal do Rio Grande do Norte, instacron:UFRN |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0029 seconds