Parameter Tuning Strategy Based On Reinforcement Learning For Heuristic And Meta-heuristic Search

With the rapid development of information technology, the optimization problem has penetrated deeply into people’s life. Researchers have been exploring a variety of efficient optimization algorithms to solve various optimization problems in academic problem and daily life. As more and more areas continue to be expanded, the optimization problems seems to be difficult, methods for solving optimization problems have evolved from the development of traditional optimization methods into today’s heuristics and meta-heuristics algorithm.This thesis is mainly based on related algorithms and parameter tuning in algorithms, providing parameter tuning with reinforcement learning, mainly about:Firstly, the current research of heuristics algorithms is in a period of rapid development, the associated algorithm has also been used in the military field, the international economic and other fields. This thesis analyzes operating efficiency and performance problems of different algorithms. Meta-heuristic algorithms, including tabu search algorithm, iterative local search algorithm, simulated annealing algorithm, etc.,can solve some combination and optimization problem, but these algorithms are not useful for solving NP-hard problem or engineering problem, it can not get satisfying results. To solve this problem, we propose a hybrid heuristic algorithm. Combining iterative local search algorithm and tabu search algorithm, we aim to improve the performance of algorithm.Secondly, there are different kinds of parameters in algorithms, to make sure that the algorithm operating well, we need to give a value or a specific range of values to parameters of the algorithm. There is no fixed pattern to explain how to set parameters.And setting values of the parameters play an important role in the performance of the algorithm. Therefore, this thesis introduces the parameter tuning mechanism in the proposed algorithm. As far as I am aware, similar parameter control strategies have not been reported before for local search heuristics. Basing on reinforcement learning theory and the existing reinforcement techniques, this thesis propose to use parameters tuning strategy to change the value of important parameters in the algorithm, so as to improve the quality of the algorithm.Thirdly, the proposed strategy is going to be extensively evaluated on two hard and challenging combinatorial problems including UBQP and Max-Cut. According to theanalysis of the problem and results, we evaluate the functionality and effectiveness of the algorithm under the proposed strategy.