Spelling suggestions: "subject:"metaheuristic?sticas"" "subject:"metaheuristics?sticas""
1 |
O problema do caixeiro viajante com passageiros e lota??o / The traveling salesman with passengers and high occupancy problemBastos, Ranms?s Emanuel Martins 17 February 2017 (has links)
Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-06-02T19:19:17Z
No. of bitstreams: 1
RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-06-05T19:52:50Z (GMT) No. of bitstreams: 1
RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5) / Made available in DSpace on 2017-06-05T19:52:51Z (GMT). No. of bitstreams: 1
RanmsesEmanuelMartinsBastos_DISSERT.pdf: 3544164 bytes, checksum: 0be0a21709a7526cbbea13cf73f55d8e (MD5)
Previous issue date: 2017-02-17 / O Problema do Caixeiro Viajante com Passageiros e Lota??o ? uma vers?o do PCV cl?ssico
onde o caixeiro ? o motorista de um ve?culo que compartilha os custos de viagem com
passageiros. Al?m de dividir os custos do percurso, o caixeiro pode se valer, tamb?m, dos
descontos das high-occupancy vehicle lanes, que s?o faixas de tr?nsito que isentam ve?culos
lotados do pagamento de ped?gio. A adi??o de passageiros ao PCV, um problema restrito ao
roteamento, cria um vi?s colaborativo que ? intensificado pela considera??o das faixas
especiais. Tal cen?rio confere ao problema estudado um aspecto ecol?gico, uma vez que seu
estudo tem consequ?ncias diretas sobre o uso eficiente do espa?o urbano e a diminui??o da
emiss?o de gases poluentes, contribuindo sobremaneira para o incremento da qualidade de vida.
A pesquisa compreendeu desde a correla??o entre esse novo problema e outros constantes na
literatura at? a concep??o de um conjunto de seiscentas inst?ncias artificiais e a cria??o de
diversos m?todos de solu??o. Para a determina??o de ?timos, ? proposto um modelo
matem?tico que suportou as solu??es por Programa??o Matem?tica e por Restri??es.
Adicionalmente, ? apresentado um algoritmo branch-and-bound especificamente desenvolvido
para o problema. Visando a busca por solu??es de qualidade em curto espa?o de tempo, s?o
expostos cinco algoritmos experimentais com base nas abordagens heur?sticas Simulated
Annealing, Variable Neighborhood Search, Coloniza??o de Abelhas e Algoritmos Gen?ticos.
Diversos procedimentos auxiliares para constru??o de solu??es e execu??o de buscas locais s?o
tamb?m expostos. Um experimento computacional ? realizado para compara??o entre os
m?todos de solu??o. Uma amostra de cem casos teste ? utilizada para o processo estat?stico de
ajuste de par?metros dos algoritmos heur?sticos, enquanto o restante das inst?ncias ?
extensivamente abordado pelos m?todos. S?o determinados os ?timos para cento e cinquenta e
cinco casos com tamanhos 10 e 20 cidades. Dentre os m?todos experimentais, cabe destacar a
superioridade do algoritmo heur?stico que une as meta-heur?sticas Simulated Annealing e
Variable Neighborhood Search. / The Traveling Salesman with Passengers and High Occupancy Problem is a version of the
classic TSP where the salesman is the driver of a vehicle who shares travels? expenses with
passengers. Besides shared expenses, the driver also benefits from discounts of the highoccupancy
vehicle lanes, i.e. traffic lanes in which high occupancy vehicles are exempted from
tolls. The addition of passengers to the TSP, a routing-only problem, creates a sharing view
which is intensified by the consideration of special lanes. This scenario grants to the problem
an ecological feature, since its study have direct consequences for the efficient use of urban
space and the greenhouse gas emissions reduction, greatly contributing for quality of life
improvement. This work addresses the study of this novel combinatorial optimization problem,
going from the relationship it draws with other ones in the literature until the conception of a
six hundred set of artificial test cases and the creation of many solution methods. To find
optimal solutions, a mathematical model is proposed. This model supported the search for exact
solutions by Mathematical and Constraint Programming. Additionally, is presented a branchand-
bound algorithm specifically developed for the problem. Aiming the search for good
quality solutions in short time period, five experimental algorithms based on the heuristics
approaches Simulated Annealing, Variable Neighborhood Search, Bees Colony and Genetic
Algorithms are introduced. Several auxiliary procedures for solutions generations and local
search execution are revealed as well. A computational experiment is fulfilled to comparison
between the solution methods. A sample of a hundred test cases is used for the heuristics
algorithms? parameter tuning statistical process, while the rest of them are extensively
addressed by the methods. The optimal solution for a hundred and fifty five test cases with sizes
of 10 and 20 cities are determined. Among the experimental methods, one has to highlight the
advantage of the heuristic algorithm that unites the metaheuristics Simulated Annealing and
Variable Neighborhood Search.
|
2 |
Arquitetura multiagente baseada em nuvem de part?culas para hibridiza??o de metaheur?sticasSouza, Givanaldo Rocha de 25 October 2013 (has links)
Made available in DSpace on 2014-12-17T15:47:03Z (GMT). No. of bitstreams: 1
GivanaldoRS_TESE.pdf: 2106802 bytes, checksum: 88486cf095bfcefea309b73b76e7de67 (MD5)
Previous issue date: 2013-10-25 / This thesis proposes an architecture of a new multiagent system framework for hybridization
of metaheuristics inspired on the general Particle Swarm Optimization framework (PSO). The
main contribution is to propose an effective approach to solve hard combinatory optimization
problems. The choice of PSO as inspiration was given because it is inherently multiagent, allowing
explore the features of multiagent systems, such as learning and cooperation techniques.
In the proposed architecture, particles are autonomous agents with memory and methods for
learning and making decisions, using search strategies to move in the solution space. The concepts
of position and velocity originally defined in PSO are redefined for this approach. The
proposed architecture was applied to the Traveling Salesman Problem and to the Quadratic Assignment
Problem, and computational experiments were performed for testing its effectiveness.
The experimental results were promising, with satisfactory performance, whereas the potential
of the proposed architecture has not been fully explored. For further researches, the proposed
approach will be also applied to multiobjective combinatorial optimization problems, which are
closer to real-world problems. In the context of applied research, we intend to work with both
students at the undergraduate level and a technical level in the implementation of the proposed
architecture in real-world problems / A presente tese prop?e uma arquitetura multiagente para hibridiza??o de metaheur?sticas, inspirada
na t?cnica de Otimiza??o por Nuvem de Part?culas, e tem como principal contribui??o a
proposta de uma abordagem efetiva para resolu??o de problemas de otimiza??o combinat?ria. A
escolha da Otimiza??o por Nuvem de Part?culas como inspira??o deu-se pelo fato desta t?cnica
ser inerentemente multiagente, permitindo explorar os recursos dos sistemas multiagente, tais
como as t?cnicas de aprendizado e coopera??o. Na arquitetura proposta, as part?culas s?o agentes
aut?nomos com mem?ria e m?todos de decis?o e de aprendizagem, utilizando estrat?gias de
busca para se moverem no espa?o de solu??es. Os conceitos de posi??o e velocidade, originalmente
definidos na Otimiza??o por Nuvem de Part?culas, s?o redefinidos para esta abordagem.
A arquitetura proposta foi aplicada ao Problema do Caixeiro Viajante e ao Problema Quadr?tico
de Aloca??o, realizando experimentos computacionais que comprovaram sua efetividade. Os
resultados dos experimentos foram bastante promissores, apresentando desempenho satisfat?rio,
considerando que o potencial da arquitetura proposta ainda n?o foi totalmente explorado. Em
pesquisas futuras, a abordagem proposta ser? aplicada a problemas de otimiza??o combinat?ria
multiobjetivo, os quais s?o mais pr?ximos aos problemas do mundo real. No ?mbito da pesquisa
aplicada, pretende-se trabalhar tanto com alunos em n?vel de gradua??o como em n?vel t?cnico
a aplica??o da arquitetura proposta em problemas pr?ticos do mundo real
|
3 |
Aplica??o do algoritmo de otimiza??o por col?nia de formigas sobre o problema do passeio do rob? seletivoOliveira J?nior, Edmilson Frank Machado 27 February 2012 (has links)
Made available in DSpace on 2014-12-17T15:48:01Z (GMT). No. of bitstreams: 1
EdmilsonFMOJ_DISSERT.pdf: 4310075 bytes, checksum: c753f90b3f1afd654108edecd6a3fc70 (MD5)
Previous issue date: 2012-02-27 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior / This work seeks to propose and evaluate a change to the Ant Colony Optimization based on the results of experiments performed on the problem of Selective Ride Robot (PRS, a new problem, also proposed in this paper. Four metaheuristics are implemented,
GRASP, VNS and two versions of Ant Colony Optimization, and their results are analyzed by running the algorithms over 32 instances created during this work. The metaheuristics also have their results compared to an exact approach. The results show that the algorithm implemented using the GRASP metaheuristic show good results. The version of the multicolony ant colony algorithm, proposed and evaluated in this work, shows the best results / Este trabalho tem o objetivo de propor e avaliar uma variante para o algoritmo de col?nia de formigas baseando-se no resultado de experimentos executados sobre o problema do Passeio do Rob? Seletivo (PRS, um novo problema, tamb?m proposto neste
trabalho. S?o implementadas quatro metaheur?sticas, GRASP, VNS, e duas vers?es do Otimiza??o por Col?nia de Formigas, e analisados seus resultados executando-os sobre 32 inst?ncias criadas no trabalho. As metaheur?sticas tamb?m tem seu resultado comparado
com o de um algoritmo exato. Os resultados mostram que o algoritmo implementado utilizando a metaheur?stica GRASP apresenta bons resultados. A vers?o multi-col?nias do
algoritmo de col?nia de formigas, proposta e avaliada no trabalho, apresenta os melhores resultados
|
4 |
Melhoria na converg?ncia do algoritmo Q-Learning na aplica??o de sistemas tutores inteligentesPaiva, ?verton de Oliveira 16 August 2016 (has links)
Submitted by Jos? Henrique Henrique (jose.neves@ufvjm.edu.br) on 2017-06-22T22:29:53Z
No. of bitstreams: 2
everton_oliveira_paiva.pdf: 3688473 bytes, checksum: 00c67bcc4d4564b69bb64a0b596743fc (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Rodrigo Martins Cruz (rodrigo.cruz@ufvjm.edu.br) on 2017-06-23T13:21:09Z (GMT) No. of bitstreams: 2
everton_oliveira_paiva.pdf: 3688473 bytes, checksum: 00c67bcc4d4564b69bb64a0b596743fc (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-06-23T13:21:09Z (GMT). No. of bitstreams: 2
everton_oliveira_paiva.pdf: 3688473 bytes, checksum: 00c67bcc4d4564b69bb64a0b596743fc (MD5)
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Previous issue date: 2016 / O uso sistemas computacionais como complemento ou substitui??o da sala de aula ? cada vez
mais comum na educa??o e os Sistemas Tutores Inteligentes (STIs) s?o uma dessas alternativas.
Portanto ? fundamental desenvolver STIs capazes tanto de ensinar quanto aprender informa??es
relevantes sobre o aluno atrav?s de t?cnicas de intelig?ncia artificial. Esse aprendizado acontece
por meio da intera??o direta entre o STI e o aluno que ? geralmente demorada. Esta disserta??o
apresenta a inser??o da metaheur?sticas Lista Tabu e GRASP com o objetivo de acelerar esse
aprendizado. Para avaliar o desempenho dessa modifica??o, foi desenvolvido um simulador de
STI. Nesse sistema, foram realizadas simula??es computacionais para comparar o desempenho
da tradicional pol?tica de explora??o aleat?ria e as metaheur?sticas propostas Lista Tabu e
GRASP. Os resultados obtidos atrav?s dessas simula??es e os testes estat?sticos aplicados
indicam fortemente que a introdu??o de meta-heur?sticas adequadas melhoram o desempenho
do algoritmo de aprendizado em STIs. / Disserta??o (Mestrado Profissional) ? Programa de P?s-Gradua??o em Educa??o, Universidade Federal dos Vales do Jequitinhonha e Mucuri, 2016. / Using computer systems as a complement or replacement for the classroom experience is an
increasingly common practice in education and Intelligent Tutoring Systems (ITS) are one of
these alternatives. Therefore, it is crucial to develop ITS that are capable of both teaching and
learning relevant information about the student through artificial intelligence techniques. This
learning process occurs by means of direct, and generally slow, interaction between the ITS and
the student. This dissertation presents the insertion of meta-heuristic Tabu search and GRASP
with the purpose of accelera ting learning. An ITS simulator was developed to evaluate the
performance of this change. Computer simulations were conducted in order to compare the
performance of traditional randomized search methods with the meta-heuristic Tabu search.
Results obtained from these simulations and statistical tests strongly indicate that the
introduction of meta-heuristics in exploration policy improves the performance of the learning
algorithm in ITS.
|
5 |
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.
|
6 |
Uma implementa??o paralela h?brida para o problema do caixeiro viajante usando algoritmos gen?ticos, GRASP e aprendizagem por refor?oSantos, Jo?o Paulo Queiroz dos 06 March 2009 (has links)
Made available in DSpace on 2014-12-17T14:55:11Z (GMT). No. of bitstreams: 1
JoaoPQS.pdf: 1464588 bytes, checksum: ad1e7b6af306b0ce9b1ccb1fb510c4ab (MD5)
Previous issue date: 2009-03-06 / The metaheuristics techiniques are known to solve optimization problems classified as NP-complete and are successful in obtaining good quality solutions. They use non-deterministic approaches to generate solutions that are close to the optimal, without the guarantee of finding the global optimum. Motivated by the difficulties in the resolution of these problems, this work proposes the development of parallel hybrid methods using the reinforcement learning, the metaheuristics GRASP and Genetic Algorithms. With the use of these techniques, we aim to contribute to improved efficiency in obtaining efficient solutions. In this case, instead of using the Q-learning algorithm by reinforcement learning, just as a technique for generating the initial solutions of metaheuristics, we use it in a cooperative and competitive approach with the Genetic Algorithm and GRASP, in an parallel implementation. In this context, was possible to verify that the implementations in this study showed satisfactory results, in both strategies, that is, in cooperation and competition between them and the cooperation and competition between groups. In some instances were found the global optimum, in others theses implementations reach close to it. In this sense was an analyze of the performance for this proposed approach was done and it shows a good performance on the requeriments that prove the efficiency and speedup (gain in speed with the parallel processing) of the implementations performed / As metaheur?sticas s?o t?cnicas conhecidas para a resolu??o de problemas de otimiza??o, classificados como NP-Completos e v?m obtendo sucesso em solu??es aproximadas de boa qualidade. Elas fazem uso de abordagens n?o determin?sticas que geram solu??es que se aproximam do ?timo, mas no entanto, sem a garantia de que se encontre o ?timo global. Motivado pelas dificuldades em torno da resolu??o destes problemas, este trabalho prop?s o desenvolvimento de m?todos paralelos h?bridos utilizando a aprendizagem por refor?o e as metaheur?sticas GRASP e Algoritmos Gen?ticos. Com a utiliza??o dessas t?cnicas em conjunto, objetivou-se ent?o, contribuir na obten??o de solu??es mais eficientes. Neste caso, ao inv?s de utilizar o algoritmo Q-learning da aprendizagem por refor?o, apenas como t?cnica de gera??o das solu??es iniciais das metaheur?sticas, este tamb?m aplicado de forma cooperativa e competitiva com o Algoritmo Gen?tico e o GRASP, em uma implementa??o paralela. Neste contexto, foi poss?vel verificar que as implementa??es realizadas neste trabalho apresentaram resultados satisfat?rios, tanto na parte de coopera??o e competi??o entre os algoritmos Q-learning, GRASP a Algoritmos Gen?ticos, quanto na parte de coopera??o e competi??o entre grupos destes tr?s algoritmos. Em algumas inst?ncias foi encontrado o ?timo global; quando n?o encontrado, conseguiu-se chegar bem pr?ximo de seu valor. Neste sentido foi realizada uma an?lise do desempenho da abordagem proposta e verificou-se um bom comportamento em rela??o aos quesitos que comprovam a efici?ncia e o speedup (ganho de velocidade com o processamento paralelo) das implementa??es realizadas
|
7 |
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
|
8 |
Um estudo algor?tmico de problemas log?sticos na ind?stria de petr?leo e g?s natural / An algorithmic study of logistic problems on petroleum and natural gas industryDuarte, Herbert de Melo 16 November 2006 (has links)
Made available in DSpace on 2014-12-17T15:48:08Z (GMT). No. of bitstreams: 1
HerbertMD.pdf: 1096047 bytes, checksum: 6cf0c7d90914e2c3fd03f494b71cfa3a (MD5)
Previous issue date: 2006-11-16 / This work consists on the study of two important problems arising from the operations of petroleum and natural gas industries. The first problem the pipe dimensioning problem on constrained gas distribution networks consists in finding the least cost combination of diameters from a discrete set of commercially available ones for the pipes of a given gas network, such that it respects minimum pressure requirements at each demand node and upstream pipe conditions. On its turn, the second problem the piston pump unit routing problem comes from the need of defining the piston pump unit routes for visiting a number of non-emergent wells in on-shore fields, i.e., wells which don t have enough pressure to make the oil emerge to surface. The periodic version of this problem takes into account the wells re-filling equation to provide a more accurate planning in the long term. Besides the mathematical formulation of both problems, an exact algorithm and a taboo search were developed for the solution of the first problem and a theoretical limit and a ProtoGene transgenetic algorithm were developed for the solution of the second problem. The main concepts of the metaheuristics are presented along with the details of their application to the cited problems. The obtained results for both applications are promising when compared to theoretical limits and alternate solutions, either relative to the quality of the solutions or to associated running time / Este trabalho consiste do estudo de dois importantes problemas oriundos das opera??es das ind?strias de petr?leo e g?s natural. O primeiro problema do dimensionamento de dutos em uma rede urbana de distribui??o de g?s natural consiste em encontrar a combina??o de di?metros de menor custo, a partir de um conjunto de op??es comercialmente dispon?veis, para os dutos de uma dada rede de distribui??o de g?s, de forma a respeitar requisitos de press?o m?nima em cada n? de demanda e condi??es de upstream. Por sua vez, o segundo problema do roteamento da unidade m?vel do pistoneio decorre da necessidade de se definir as rotas de visita??o da dita unidade m?vel do pistoneio aos diversos po?os n?o surgentes do campo de explora??o, ou seja, po?os que n?o possuem press?o suficiente para fazer o ?leo emergir ? superf?cie. A vers?o peri?dica do problema leva em considera??o a equa??o de re-enchimento dos po?os, de forma a possibilitar um planejamento mais acurado num horizonte de tempo maior. Al?m da formula??o matem?tica dos dois problemas, para a solu??o do primeiro foram desenvolvidos um algoritmo exato e uma busca tabu e para o segundo, um limite superior e um algoritmo transgen?tico ProtoGene. Os principais conceitos das metaheur?sticas s?o apresentados, juntamente com os detalhes da aplica??o destas aos problemas citados. Os resultados obtidos para ambas as aplica??es s?o promissores quando comparados com limites te?ricos e solu??es alternativas, tanto relativamente ? qualidade das solu??es como ao tempo computacional envolvido
|
9 |
Algoritmos cient?ficosFelipe, Denis 14 February 2014 (has links)
Made available in DSpace on 2014-12-17T15:48:10Z (GMT). No. of bitstreams: 1
DenisF_DISSERT.pdf: 776997 bytes, checksum: c0d801fdcf21ff4f335f115d3918ed93 (MD5)
Previous issue date: 2014-02-14 / The Scientific Algorithms are a new metaheuristics inspired in the scientific research process. The new method introduces the idea of theme to search the solution space of hard problems. The inspiration for this class of algorithms comes from the act of researching that comprises thinking, knowledge sharing and disclosing new ideas. The ideas of the new method are illustrated in the Traveling Salesman Problem. A computational experiment applies the proposed approach to a new variant of the Traveling Salesman Problem named Car Renter Salesman Problem. The results are compared to state-of-the-art algorithms for the latter problem / Os algoritmos cient?ficos s?o uma nova metaheur?stica inspirada no processo da pesquisa cient?fica. O novo m?todo introduz a ideia de tema para buscar o espa?o de solu??es de problemas dif?ceis. A inspira??o para esta classe de algoritmos vem do ato de pesquisar, que compreende pensar, compartilhar conhecimento e descobrir novas ideias. As ideias do novo m?todo s?o ilustradas no Problema do Caixeiro Viajante. Um experimento computacional aplica a abordagem proposta a uma nova variante do Problema do Caixeiro Viajante intitulada Problema do Caixeiro Alugador. Os resultados s?o comparados aos algoritmos do estado da arte para o ?ltimo problema
|
10 |
Uma col?nia de formigas para o caminho mais curto multiobjetivoBezerra, Leonardo Cesar Teon?cio 07 February 2011 (has links)
Made available in DSpace on 2015-03-03T15:47:46Z (GMT). No. of bitstreams: 1
LeonardoCTB_DISSERT.pdf: 2119704 bytes, checksum: 5bdd21de8bfa668bba821593cdd5289f (MD5)
Previous issue date: 2011-02-07 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / Multi-objective combinatorial optimization problems have peculiar characteristics that
require optimization methods to adapt for this context. Since many of these problems are
NP-Hard, the use of metaheuristics has grown over the last years. Particularly, many
different approaches using Ant Colony Optimization (ACO) have been proposed. In this
work, an ACO is proposed for the Multi-objective Shortest Path Problem, and is compared
to two other optimizers found in the literature. A set of 18 instances from two
distinct types of graphs are used, as well as a specific multiobjective performance assessment
methodology. Initial experiments showed that the proposed algorithm is able
to generate better approximation sets than the other optimizers for all instances. In the
second part of this work, an experimental analysis is conducted, using several different
multiobjective ACO proposals recently published and the same instances used in the first
part. Results show each type of instance benefits a particular type of instance benefits a
particular algorithmic approach. A new metaphor for the development of multiobjective
ACOs is, then, proposed. Usually, ants share the same characteristics and only few works
address multi-species approaches. This works proposes an approach where multi-species
ants compete for food resources. Each specie has its own search strategy and different
species do not access pheromone information of each other. As in nature, the successful
ant populations are allowed to grow, whereas unsuccessful ones shrink. The approach introduced
here shows to be able to inherit the behavior of strategies that are successful
for different types of problems. Results of computational experiments are reported and
show that the proposed approach is able to produce significantly better approximation
sets than other methods / Problemas de otimiza??o combinat?ria multiobjetivo apresentam caracter?sticas peculiares
que exigem que t?cnicas de otimiza??o se adaptem a esse contexto. Como muitos
desses problemas s?o NP-?rduos, o uso de metaheur?sticas tem crescido nos ?ltimos anos.
Particularmente, muitas abordagens que utilizam a Otimiza??o por Col?nias de Formigas
t?m sido propostas. Neste trabalho, prop?e-se um algoritmo baseado em col?nias de formigas
para o Problema do Caminho mais Curto Multiobjetivo, e compara-se o algoritmo
proposto com dois otimizadores encontrados na literatura. Um conjunto de 18 inst?ncias
oriundas de dois tipos de grafos ? utilizado, al?m de uma metodologia espec?fica para a
avalia??o de otimizadores multiobjetivo. Os experimentos iniciais mostram que o algoritmo
proposto consegue gerar conjuntos de aproxima??o melhores que os demais otimizadores
para todas as inst?ncias. Na segunda parte do trabalho, uma an?lise experimental de diferentes
abordagens publicadas para col?nias de formigas multiobjetivo ? realizada, usando
as mesmas inst?ncias. Os experimentos mostram que cada tipo de inst?ncia privilegia uma
abordagem algor?tmica diferente. Uma nova met?fora para o desenvolvimento deste tipo
de metaheur?stica ? ent?o proposta. Geralmente, formigas possuem caracter?sticas comuns
e poucos artigos abordam o uso de m?ltiplas esp?cies. Neste trabalho, uma abordagem
com m?ltiplas esp?cies competindo por fontes de comida ? proposta. Cada esp?cie possui
sua pr?pria estrat?gia de busca e diferentes esp?cies n?o tem acesso ? informa??o dada
pelo ferom?nio das outras. Como na natureza, as popula??es de formigas bem sucedidas
tem a chance de crescer, enquanto as demais se reduzem. A abordagem apresentada aqui
mostra-se capaz de herdar o comportamento de estrat?gias bem-sucedidas em diferentes
tipos de inst?ncias. Resultados de experimentos computacionais s?o relatados e mostram
que a abordagem proposta produz conjuntos de aproxima??o significativamente melhores
que os outros m?todos
|
Page generated in 0.0455 seconds