Spelling suggestions: "subject:"algoritmos exatas"" "subject:"algoritmos exatidão""
1 |
Algoritmos experimentais para o problema biobjetivo da ?rvore geradora quadr?tica em adjac?ncia de arestas / The biobjective adjacent only quadratic spanning tree problemPinheiro, Lucas Daniel Monteiro dos Santos 03 February 2016 (has links)
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.
|
2 |
O problema biobjetivo da ?rvore geradora quadr?tica em adjac?ncia de arestasMaia, Silvia Maria Diniz Monteiro 16 December 2013 (has links)
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
|
3 |
Uma an?lise experimental de algoritmos exatos aplicados ao problema da ?rvore geradora multiobjetivo / An experimental analysis of exact algorithms applied to the multiobjective spanning tree problemDrumond, Patricia Medyna Lauritzen de Lucena 05 March 2012 (has links)
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
|
Page generated in 0.0355 seconds