Use este identificador para citar ou linkar para este item: https://repositorio.ufrn.br/jspui/handle/123456789/24149
Título: Uma abordagem utilizando aprendizagem por reforço hierárquica e computação paralela para o problema dos K-Servos
Autor(es): Costa, Mademerson Leandro da
Palavras-chave: Aprendizagem por reforço hierárquica;Problemas de otimização em espaços métricos;Computação paralela
Data do documento: 9-Jun-2017
Referência: COSTA, Mademerson Leandro da. Uma abordagem utilizando aprendizagem por reforço hierárquica e computação paralela para o problema dos K-Servos. 2017. 95f. Tese (Doutorado em Ciência e Engenharia de Petróleo) - Centro de Ciências Exatas e da Terra, Universidade Federal do Rio Grande do Norte, Natal, 2017.
Abstract: 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.
Resumo: 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.
URI: https://repositorio.ufrn.br/jspui/handle/123456789/24149
Aparece nas coleções:PPGCEP - Doutorado em Ciência e Engenharia do Petróleo

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
AbordagemUtilizandoAprendizagem_Costa_2017.pdf1,84 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.