Open AccessTabu search guided by reinforcement learning for the max-mean dispersion problem
Author(s) -
Dieudonné Nijimbere,
Shengchuan Zhao,
Xunhao Gu,
Moses Olabhele Esangbedo,
Nyiribakwe Dominique
Publication year - 2021
Publication title -
journal of industrial and management optimization
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.325
H-Index - 32
eISSN - 1553-166X
pISSN - 1547-5816
DOI - 10.3934/jimo.2020115
Subject(s) - tabu search , reinforcement learning , metaheuristic , benchmark (surveying) , computer science , guided local search , local search (optimization) , algorithm , mathematical optimization , artificial intelligence , mathematics , geodesy , geography
We present an effective hybrid metaheuristic of integrating reinforcement learning with a tabu-search (RLTS) algorithm for solving the max–mean dispersion problem. The innovative element is to design using a knowledge strategy from the \begin{document}$ Q $\end{document} -learning mechanism to locate promising regions when the tabu search is stuck in a local optimum. Computational experiments on extensive benchmarks show that the RLTS performs much better than state-of-the-art algorithms in the literature. From a total of 100 benchmark instances, in 60 of them, which ranged from 500 to 1, 000, our proposed algorithm matched the currently best lower bounds for all instances. For the remaining 40 instances, the algorithm matched or outperformed. Furthermore, additional support was applied to present the effectiveness of the combined RL technique. The analysis sheds light on the effectiveness of the proposed RLTS algorithm.