Please use this identifier to cite or link to this item: https://repositorio.ufersa.edu.br/handle/tede/675
Type: Dissertação
Title: Desenvolvimento de um framework para utilização do GR-Learning em problemas de otimização combinatória
Authors: Silva, Alexsandro Trindade Sales da
First Advisor: Lima Júnior, Francisco Chagas de
First Co-advisor: Liberalino, Carlos Heitor Pereira
First member of the board: Aloise, Dario José
Second member of the board: Medeiros Neto, Francisco Dantas de
Third member of the board: Medeiros, João Paulo de Souza
Resume: A utilização de metaheurísticas para resolução de problemas de otimização combinatória per-tencentes à classe NP-Difícil vem se tornando cada vez mais comum, e segundo Temponi (2007 apud RIBEIRO, 1996) uma metaheurística deve ser modelada de acordo com o proble-ma que ela foi projetada para resolver. Isto na maioria vezes requer muitas alterações quando se tem que aplicar uma mesma metaheurística a diversos tipos de problemas de otimização combinatória. Neste trabalho foi proposto um framework para utilização de uma metaheurísti-ca híbrida proposta por Almeida (2014) que utilizou a metaheurística GRASP Reativo junta-mente com uma técnica de aprendizagem por reforço (denominada GR-Learning). Especifi-camente, o algoritmo Q-learning, que foi utilizado para aprender com o passar das iterações qual valor para o parâmetro α (alfa) utilizar durante a fase de construção da GRASP. O GR-Learning foi utilizado para resolver o problema dos p-Centros aplicado a Segurança Pública na Cidade de Mossoró/RN. Para validar a eficácia do framework proposto o mesmo foi utili-zado para resolver dois problemas clássicos de otimização combinatória: O Problema de Lo-calização de Hubs (do inglês Hub Location Problem - HLP) e o Problema de Corte e Estoque – PCE (do inglês Cutting Stock Problem - CSP). Para validação dos resultados obtidos foram utilizadas instâncias com resultados já conhecidos na literatura e adicionalmente foi criada uma instância com dados do setor aeroviário Brasileiro. Os resultados obtidos mostraram que o framework proposto foi bastante competitivo quando comparado a outros resultados de di-versos algoritmos já conhecidos na literatura, pois obteve o valor ótimo em quase todas as instâncias do HLP como também novos valores (melhores que os obtidos com outros algorit-mos já conhecido na literatura) para algumas instâncias do CSP
Abstract: The use of metaheuristics for solving combinatorial optimization problems belong to NP-Hard class is becoming increasingly common, and second Temponi (2007 apud RIBEIRO, 1996) a metaheurist should be modeled according to the problem she was designed to solve. This most often requires many changes when you have to apply the same metaheuristic to various types of combinatorial optimization problems. In this work we propose a framework for use of a hybrid metaheuristic proposed by Almeida (2014) who used the GRASP Reactive along with a reinforcement learning technique (called GR-learning). Specifically, the Q-learning algorithm that was used to learn over which the iterations value for the parameter α (alpha) used during the construction phase of GRASP. The GR-Learning was used to solve the problem of p-centers applied to Public Security in the city of Mossoró/RN. To validate the effectiveness of the framework proposed it was used to solve two classical problems of combinatorial optimi-zation: The Hub Location Problem (HLP), and the Cutting Stock Problem (CSP). To validate the results obtained we used instances with results known in the literature and in addition has created an instance with data from the Brazilian airline industry. The results showed that the proposed framework was quite competitive when compared to other results of different algo-rithms known in the literature as got great value in almost all instances of HLP as well as new values (better than those obtained with other algorithms known in the literature) for some ins-tances of CSP
Keywords: Framework
Metaheurística
GRASP
Aprendizado por reforço
Framework
Metaheuristic
GRASP
Reinforcement learning
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: Brasil
Publisher: Universidade Federal Rural do Semi-Árido
Institution Initials: UFERSA
Program Name: Programa de Pós-Graduação em Ciência da Computação
Citation: SILVA, Alexsandro Trindade Sales da. Desenvolvimento de um framework para utilização do GR-Learning em problemas de otimização combinatória. 2016. 100 f. Dissertação (Mestrado) - Curso de Pós-graduação em Ciência da Computação, Universidade Federal Rural do Semi-Árido, Mossoró, 2016.
Access Type: Acesso Aberto
URI: https://repositorio.ufersa.edu.br/handle/tede/675
Issue Date: 20-Jul-2016
License Term: CC-BY-SA
Appears in Collections:Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
AlexsandroTSS_DISSERT.pdf2.74 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.