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

Made available in DSpace on 2014-12-17T15:47:55Z (GMT). No. of bitstreams: 1 SilviaMDM_DISSERT.pdf: 1535044 bytes, checksum: 925f2f885f42335d55c35aa64bb4d026 (MD5) Previous issue date: 2011-02-17 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / The Multiobjective Spanning Tree is a NP-hard Combinatorial Optimization problem whose application arises in several areas, especially networks design. In this work, we propose a solution to the biobjective version of the problem through a Transgenetic Algorithm named ATIS-NP. The Computational Transgenetic is a metaheuristic technique from Evolutionary Computation whose inspiration relies in the conception of cooperation (and not competition) as the factor of main influence to evolution. The algorithm outlined is the evolution of a work that has already yielded two other transgenetic algorithms. In this sense, the algorithms previously developed are also presented. This research also comprises an experimental analysis with the aim of obtaining information related to the performance of ATIS-NP when compared to other approaches. Thus, ATIS-NP is compared to the algorithms previously implemented and to other transgenetic already presented for the problem under consideration. The computational experiments also address the comparison to two recent approaches from literature that present good results, a GRASP and a genetic algorithms. The efficiency of the method described is evaluated with basis in metrics of solution quality and computational time spent. Considering the problem is within the context of Multiobjective Optimization, quality indicators are adopted to infer the criteria of solution quality. Statistical tests evaluate the significance of results obtained from computational experiments / A ?rvore Geradora Multiobjetivo ? um problema de Otimiza??o Combinat?ria NP-?rduo. Esse problema possui aplica??o em diversas ?reas, em especial, no projeto de redes. Nesse trabalho, prop?e-se uma solu??o para o problema em sua vers?o biobjetivo por meio de um Algoritmo Transgen?tico, denominado ATIS-NP. A Transgen?tica Computacional ? uma t?cnica metaheur?stica da Computa??o Evolucion?ria cuja inspira??o est? na coopera??o (e n?o na competi??o) como fator de maior influ?ncia para a evolu??o. O algoritmo proposto ? a evolu??o de um trabalho que j? originou dois outros algoritmos transgen?ticos. Nesse sentido, os algoritmos previamente desenvolvidos tamb?m s?o apresentados. Essa pesquisa compreende ainda uma an?lise experimental que visa obter informa??es quanto ao desempenho do ATIS-NP quando comparado a outros algoritmos. Para tanto, o ATIS-NP ? comparado aos dois algoritmos anteriormente implementados, bem como a outro transgen?tico proposto na literatura para o problema tratado. Os experimentos computacionais abrangem ainda a compara??o do algoritmo desenvolvido a duas abordagens recentes da literatura que obt?m excelentes resultados, um GRASP e um gen?tico. A efici?ncia do m?todo apresentado ? avaliada com base em medidas de qualidade de solu??o e tempo computacional despendido. Uma vez que o problema se insere no contexto da Otimiza??o Multiobjetivo, indicadores de qualidade s?o utilizados para inferir o crit?rio de qualidade de solu??es obtidas. Testes estat?sticos avaliam a signific?ncia dos resultados obtidos nos experimentos computacionais

Made available in DSpace on 2014-12-17T15:48:01Z (GMT). No. of bitstreams: 1 PatriciaMLLD_DISSERT.pdf: 2062279 bytes, checksum: edf20f81d921e118846850abb8ec8a1d (MD5) Previous issue date: 2012-03-05 / The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature / O Problema da ?rvore Geradora Multiobjetivo ? NP-?rduo e modela aplica??es em diversas ?reas. Esta pesquisa apresenta uma an?lise experimental de diferentes estrat?gias utilizadas na literatura para desenvolver algoritmos exatos para resolver o problema. Inicialmente, os algoritmos s?o classificados de acordo com as abordagens utilizadas para resolver o problema. Caracter?sticas de duas ou mais abordagens podem ser encontradas em alguns desses algoritmos. As abordagens aqui investigadas s?o: o m?todo duas fases, branch-and-bound, k-best e a abordagem baseada em prefer?ncia. A principal contribui??o deste trabalho est? no fato de que nenhuma pesquisa desenvolvida at? o momento relata uma an?lise sistem?tica experimental de algoritmos exatos para o problema da ?rvore Geradora Multiobjetivo. Portanto, este trabalho pode ser uma base para outras pesquisas que lidam com o mesmo problema. Os experimentos computacionais comparam o desempenho de algoritmos em rela??o ao tempo de processamento, ? efici?ncia com base no n?mero de objetivos e no n?mero de solu??es encontradas em um intervalo de tempo controlado. A an?lise dos algoritmos foi realizada para inst?ncias conhecidas do problema, bem como para inst?ncias obtidas a partir de um gerador bastante utilizado na literatura