Using Q-learning Algorithm for Initialization of the GRASP Metaheuristic and Genetic Algorithm

Abstract

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 find good solutions which, however, do not 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 the exploitation -exploration, which consists of choosing between a greedy search and a wider exploration of the solution space. A way to guide such algorithms during the search of better solutions is supplying them with more knowledge through the learning of the environment. This way, this work proposes the use of a technique of Reinforcement Learning -Q-Learning Algorithm -for the constructive phase of GRASP metaheuristic and to generate the initial population of a Genetic Algorithm. The proposed methods will be applied to the symmetrical traveling salesman problem.