Q-learning based hyper-heuristic with clustering strategy for combinatorial optimization: A case study on permutation flow-shop scheduling problem

In this paper, a Q-learning based hyper-heuristic with clustering strategy (QHH/CS) is proposed for combinatorial optimization problems (COPs). In QHH/CS, a clustering strategy based on low-dimensional mapping method is devised to map initial population to a low-dimensional space, thus obtaining multiple subpopulations accounting for different search directions. To discover more promising search regions around each subpopulation, we propose a parallel Q-learning search mechanism composed of multiple search components, including multi-subpopulation Q-table, state extraction method, contribution-driven reward function, and deep mining local search actions. Relying on these search components, QHH/CS identifies the variations of the objective values of subpopulations to evaluate the solution features of COPs, whereby valuable information can be learned during the search process of the algorithm. To illustrate the effectiveness of QHH/CS, it is applied to solve the permutation flow-shop scheduling problem. We additionally assess QHH/CS through the well-known vehicle routing problem, which confirms the general search ability of the algorithm for COPs. Moreover, the convergence analysis of the QHH/CS algorithm is performed, providing theoretical guidance for the optimization process of the proposed algorithm. Results of experiments demonstrate that QHH/CS can find high-quality solutions to the solved problems