Spelling suggestions: "subject:"metaheuristic?sticas GRASP"" "subject:"metaheuristics?sticas GRASP""
1 |
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
|
2 |
O problema do caixeiro alugador com coleta de bonus: um estudo algoritmico / Prize Collecting Traveling Car Renter Problem: an Algotithm StudyMenezes, Matheus da Silva 21 March 2014 (has links)
Made available in DSpace on 2015-03-03T15:48:41Z (GMT). No. of bitstreams: 1
MatheusSM_TESE.pdf: 3657538 bytes, checksum: 05bf71663b044728a1e70b6db57b834e (MD5)
Previous issue date: 2014-03-21 / This paper introduces a new variant of the Traveling Car Renter Problem, named Prizecollecting
Traveling Car Renter Problem. In this problem, a set of vertices, each associated
with a bonus, and a set of vehicles are given. The objective is to determine a cycle that
visits some vertices collecting, at least, a pre-defined bonus, and minimizing the cost of the
tour that can be traveled with different vehicles. A mathematical formulation is presented
and implemented in a solver to produce results for sixty-two instances. The proposed
problem is also subject of an experimental study based on the algorithmic application of
four metaheuristics representing the best adaptations of the state of the art of the heuristic
programming.We also provide new local search operators which exploit the neighborhoods
of the problem, construction procedures and adjustments, created specifically for the
addressed problem. Comparative computational experiments and performance tests are
performed on a sample of 80 instances, aiming to offer a competitive algorithm to the
problem. We conclude that memetic algorithms, computational transgenetic and a hybrid
evolutive algorithm are competitive in tests performed / Este trabalho apresenta uma nova variante do problema do Caixeiro Alugador ainda n?o
descrita na literatura, denominada de Caixeiro Alugador com Coleta de Pr?mios. Neste
problema s?o disponibilizados um conjunto de v?rtices, cada um com um b?nus associado
e um conjunto de ve?culos. O objetivo do problema ? determinar um ciclo que visite
alguns v?rtices coletando, pelo menos, um b?nus pr?-de nido e minimizando os custos de
viagem atrav?s da rota, que pode ser feita com ve?culos de diferentes tipos. ? apresentada
uma formula??o matem?tica e implementada em um solver produzindo resultados em sessenta
e duas inst?ncias. O problema proposto tamb?m ? objeto de um estudo algor?tmico
experimental baseado na aplica??o de quatro metaheur?sticas de solu??o, representando
adapta??es do melhor do estado da arte em programa??o heur?stica. Nesse trabalho tamb?m apresentamos a constitui??o de novos operadores que exploram as vizinhan?as do
problema, procedimentos construtivos e adapta??es, criados especifi camente para o problema
abordado. Experimentos computacionais comparativos e testes de desempenho s?o
realizados sobre uma amostra de 80 inst?ncias, visando oferecer um algoritmo de solu??o
competitivo para o problema. Conclui-se que algoritmos com abordagem mem?tica, transgen
?tica e evolucion?ria h?brida obtiveram resultados competitivos nos testes efetuados.
Palavras-chave: Caixeiro Alugador com Coleta de Pr?mios. Metaheur?sticas. GRASP/VNS.
Algoritmo Mem?tico. Transgen?tica Computacional. Computa??o Evolucion?ria
|
Page generated in 0.0548 seconds