Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-10-18T20:55:13Z No. of bitstreams: 1 MademersonLeandroDaCosta_TESE.pdf: 1891375 bytes, checksum: 6977d7d34bb28c61fa6a511b98c8df53 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-10-24T22:28:38Z (GMT) No. of bitstreams: 1 MademersonLeandroDaCosta_TESE.pdf: 1891375 bytes, checksum: 6977d7d34bb28c61fa6a511b98c8df53 (MD5) / Made available in DSpace on 2017-10-24T22:28:39Z (GMT). No. of bitstreams: 1 MademersonLeandroDaCosta_TESE.pdf: 1891375 bytes, checksum: 6977d7d34bb28c61fa6a511b98c8df53 (MD5) Previous issue date: 2017-06-09 / Um sistema de tarefas em espa?os m?tricos ? um modelo abstrato para uma classe de problemas de otimiza??o online, incluindo o problema de pagina??o de mem?ria, listas de acesso, problemas na ind?stria do petr?leo como o gerenciamento de sondas de produ??o terrestre (workover rigs) e de log?stica na produ??o de petr?leo offshore, o problema dos K-Servos, dentre outros. A utiliza??o da aprendizagem por refor?o na solu??o destes problemas, embora tenha se mostrado eficiente, est? restrita a uma classe simples de problemas, devido ? maldi??o da dimensionalidade inerente ao m?todo. Neste trabalho, apresenta-se uma solu??o que utiliza a aprendizagem por refor?o, baseada em t?cnicas de decomposi??o hier?rquica e computa??o paralela para solu??o de problemas de otimiza??o em espa?os m?tricos, com o objetivo de estender a aplicabilidade do m?todo a problemas complexos na ind?stria petrol?fera, contornando a restri??o da sua utiliza??o a problemas te?ricos de menor porte. A dimens?o da estrutura de armazenamento utilizada pela aprendizagem por refor?o para se obter a pol?tica ?tima cresce em fun??o do n?mero de estados e de a??es, sendo diretamente proporcional ao n?mero n de n?s e k de servos, fazendo com que o crescimento da complexidade do problema se d? de maneira exponencial (?????(??)). Para contorn?-lo, o problema foi modelado com um processo de decis?o em m?ltiplas etapas onde inicialmente utilizamos o algoritmo k-means como m?todo de agrupamento visando decompor o problema em subproblemas de menor dimens?o. Em seguida foi aplicado o algoritmo Q-learning nos subgrupos buscando-se atingir a melhor pol?tica de deslocamento dos servos. Nesta etapa, foram utilizadas t?cnicas de computa??o paralela para que os processos de aprendizado e armazenamento nos subgrupos fossem executados de forma paralela. Desta forma, a dimens?o do problema e o tempo total de execu??o do algoritmo foram reduzidos, viabilizando a aplica??o do m?todo proposto ?s grandes inst?ncias. A abordagem proposta apresentou melhores resultados quando comparada com a aprendizagem por refor?o cl?ssica e o m?todo guloso. Al?m de ter atingido ganhos de speedup e efici?ncia na avalia??o das m?tricas de desempenho paralelo. / A metrical task system is an abstract model for a class of online optimization problems, including paging, access lists, industry oil problems such as the management of workover rigs and logistics in the production of offshore oil, the problem of K-Servos, among others. The use of reinforcement learning to solving these problems, although proved to be efective, is restricted to a simple class of problems due to the curse of dimensionality inherent to the method. This work presents a solution that uses reinforcement learning based on hierarchical decomposition techniques and parallel computing to solve optimization problems in metric spaces. The use of these techniques allowed to extend the applicability of the method to more complex problems, bypassing the restriction of its use to smaller problems. As the size of the storage structure used by reinforcement learning to obtain the optimal policy grows as a function of the number of states and actions, which in turn is proportional to the number n of nodes and k of servers, it is noticed that their growth is given exponentially (?????(??)). To circumvent this, the problem was modeled with a multi-step decision process where we initially used the k-means algorithm as a grouping method to decompose the problem into smaller subproblems. Then, the Q-learning algorithm was applied in the subgroups, aiming at achieving the best server displacement policy. In this step, the learning and storage processes in the subgroups were executed in parallel. In this way, the problem dimension and the total execution time of the algorithm were reduced, making possible the application of the proposed method to the large instances. The proposed approach presented better results when compared to the classical reinforcement learning and the greedy method. In addition to achieving speedup and efficiency gains in the evaluation of parallel performance metrics. Keywords? Metrical Task Systems, The K-Server Problem, Curse of Dimensionality, Hierarchical Reinforcement Learning, Q-Learning Algorithm, Parallel Computing.