Spelling suggestions: "subject:"?rvores geradoras multiobjective"" "subject:"?rvores gerador multiobjective""
1 |
Algoritomos transgen?ticos aplicados ao problema da ?rvore geradora biobjetivoMonteiro, Silvia Maria Diniz 17 February 2011 (has links)
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
|
2 |
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.0845 seconds