Algoritmo Q-learning como estratégia de exploração e/ou explotação para metaheurísticas GRASP e algoritmo genético

Techniques of optimization known as metaheuristics have achieved success in the resolution of many problems classified as NP-Hard. These methods use non deterministic approaches that reach very good solutions which, however, don t guarantee the determination of the global optimum. Beyond the inherent difficulties related to the complexity that characterizes the optimization problems, the metaheuristics still face the dilemma of xploration/exploitation, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the searching of better solutions is supplying them with more knowledge of the problem through the use of a intelligent agent, able to recognize promising regions and also identify when they should diversify the direction of the search. This way, this work proposes the use of Reinforcement Learning technique - Q-learning Algorithm - as exploration/exploitation strategy for the metaheuristics GRASP (Greedy Randomized Adaptive Search Procedure) and Genetic Algorithm. The GRASP metaheuristic uses Q-learning instead of the traditional greedy-random algorithm in the construction phase. This replacement has the purpose of improving the quality of the initial solutions that are used in the local search phase of the GRASP, and also provides for the metaheuristic an adaptive memory mechanism that allows the reuse of good previous decisions and also avoids the repetition of bad decisions. In the Genetic Algorithm, the Q-learning algorithm was used to generate an initial population of high fitness, and after a determined number of generations, where the rate of diversity of the population is less than a certain limit L, it also was applied to supply one of the parents to be used in the genetic crossover operator. Another significant change in the hybrid genetic algorithm is the proposal of a mutually interactive cooperation process between the genetic operators and the Q-learning algorithm. In this interactive/cooperative process, the Q-learning algorithm receives an additional update in the matrix of Q-values based on the current best solution of the Genetic Algorithm. The computational experiments presented in this thesis compares the results obtained with the implementation of traditional versions of GRASP metaheuristic and Genetic Algorithm, with those obtained using the proposed hybrid methods. Both algorithms had been applied successfully to the symmetrical Traveling Salesman Problem, which was modeled as a Markov decision process

Estudo comparativo de abordagens de inversão do fator de qualidade Q

Seismic wave dispersion and attenuation studies have become an important tool for lithology and fluid discrimination in hydrocarbon reservoirs. The processes associated to attenuation are complex and are encapsulated in a single quantitative description called quality factor (Q). The present dissertation has the objective of comparing different approaches of Q determination and is divided in two parts. Firstly, we made performance and robustness tests of three different approaches for Q determination in the frequency domain. They are: peak shift, centroid shift and spectral ratio. All these tests were performed in a three-layered model. In the suite of tests performed here, we varied the thickness, Q and inclination of the layers for propagation pulses with central frequency of 30, 40 and 60 Hz. We found that the centroid shift method is produces robust results for the entire suíte of tests. Secondly, we inverted for Q values using the peak and centroid shift methods using an sequential grid search algorithm. In this case, centroid shift method also produced more robust results than the peak shift method, despite being of slower convergence