Desenvolvimento de um framework para utilização do GR-Learning em problemas de otimização combinatória

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