Made available in DSpace on 2014-12-17T14:54:52Z (GMT). No. of bitstreams: 1 FranciscoCLJ.pdf: 1181019 bytes, checksum: b3894e0c93f85d3cf920c7015daef964 (MD5) Previous issue date: 2009-03-20 / 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 / T?cnicas de otimiza??o conhecidas como metaheur?sticas t?m obtido sucesso na resolu??o de problemas classificados como NP - ?rduos. Estes m?todos utilizam abordagens n?o determin?sticas que geram solu??es pr?ximas do ?timo sem, no entanto, garantir a determina??o do ?timo global. Al?m das dificuldades inerentes ? complexidade que caracteriza os problemas NP-?rduos, as metaheur?sticas enfrentam ainda o dilema de explora??o/explota??o, que consiste em escolher entre intensifica??o da busca em uma regi?o espec?fica e a explora??o mais ampla do espa?o de solu??es. Uma forma de orientar tais algoritmos em busca de melhores solu??es ? supri-los de maior conhecimento do problema atrav?s da utiliza??o de um agente inteligente, capaz de reconhecer regi?es promissoras e/ou identificar em que momento dever? diversificar a dire??o de busca, isto pode ser feito atrav?s da aplica??o de Aprendizagem por Refor?o. Neste contexto, este trabalho prop?e o uso de uma t?cnica de Aprendizagem por Refor?o - especificamente o Algoritmo Q-learning - como uma estrat?gia de explora??o/explota??o para as metaheur?sticas GRASP (Greedy Randomized Adaptive Search Procedure) e Algoritmo Gen?tico. Na implementa??o da metaheur?stica GRASP proposta, utilizou-se o Q-learning em substitui??o ao algoritmo guloso-aleat?rio tradicionalmente usado na fase de constru??o. Tal substitui??o teve como objetivo melhorar a qualidade das solu??es iniciais que ser?o utilizadas na fase de busca local do GRASP, e, ao mesmo tempo, suprir esta metaheur?sticas de um mecanismo de mem?ria adaptativa que permita a reutiliza??o de boas decis?es tomadas em itera??es passadas e que evite a repeti??o de decis?es n?o promissoras. No Algoritmo Gen?tico, o algoritmo Q-learning foi utilizado para gerar uma popula??o inicial de alta aptid?o, e ap?s um determinado n?mero de gera??es, caso a taxa de diversidade da popula??o seja menor do que um determinado limite L, ele ? tamb?m utilizado em uma forma alternativa de operador de cruzamento. Outra modifica??o importante no algoritmo gen?tico h?brido ? a proposta de um processo de intera??o mutuamente cooperativa entre o os operadores gen?ticos e o Algoritmo Q-learning. Neste processo interativo/cooperativo o algoritmo Q-learning recebe uma atualiza??o adicional na matriz dos Q-valores com base na solu??o elite da popula??o corrente. Os experimentos computacionais apresentados neste trabalho consistem em comparar os resultados obtidos com a implementa??o de vers?es tradicionais das metaheur?sticas citadas, com aqueles obtidos utilizando os m?todos h?bridos propostos. Ambos os algoritmos foram aplicados com sucesso ao problema do caixeiro viajante sim?trico, que por sua vez, foi modelado como um processo de decis?o de Markov

[pt] O Brasil é um dos principais produtores e exportadores de celulose e papel no mundo, beneficiando-se de condições climáticas e de solo favoráveis, além de investimentos substanciais em pesquisa. Um desafio significativo nesse setor é o Problema de Planejamento de Colheita Florestal (PPCF), semelhante a um derivado do Problema de Roteamento de Veículos (VRP), com uma frota heterogênea, demanda periódica e ganho de volume de madeira. Este estudo aborda o PPCF utilizando um modelo matemático de Programação Linear Inteira Mista (MILP) e a metaheurística Greedy Randomized Adaptive Search Procedure (GRASP) em cenários simulados e reais para otimizar o sequenciamento dos times de colheita entre as unidades produtivas. O objetivo é reduzir os custos operacionais e aumentar o crescimento do volume ao longo de um horizonte de planejamento de 12 meses, considerando também as restrições de janelas de tempo. Um total de 12 instâncias foram testadas para avaliar o desempenho do GRASP, sendo que a metaheurística superou o resultado do modelo MILP em nove casos. Além disso, três instâncias refletem cenários reais de uma grande empresa brasileira de celulose e papel. Quando comparado aos resultados da equipe de planejamento da empresa, o GRASP alcançou uma redução de até 61,9 por cento nos custos totais. Além disso, o GRASP fornece planos de colheita detalhados em um curto tempo de execução, reduzindo a carga de trabalho da equipe de planejamento e aumentando a flexibilidade na tomada de decisões. / [en] Brazil is one of the world s leading producers and exporters of pulp and paper, benefiting from favorable climatic and soil conditions, coupled with substantial investments in research. A significant challenge in this sector is the Forest Harvesting Planning Problem (FHPP), akin to a derivative of the Vehicle Routing Problem (VRP) featuring a heterogeneous fleet, periodic demand, and wood volume gain. This study addresses FHPP by employing Mixed Integer Linear Programming (MILP) modeling and the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic across real and simulated scenarios to optimize the sequencing of harvesting teams among stands. The objective is to reduce operational costs and enhance volume growth over a 12- month planning horizon, while also considering time windows and scheduling constraints. A total of 12 instances were tested to evaluate GRASP s performance, with the metaheuristic matching or outperforming the MILP model in nine cases. Additionally, three instances reflect real scenarios from a major Brazilian pulp and paper company. When compared against the company s planning team results, GRASP achieved up to a 61.9 percent reduction in total costs. Furthermore, GRASP provides detailed harvesting plans within a short execution time, reducing planning team workload and enhancing decision-making flexibility.