Tabu Search Guided by Reinforcement Learning for the Max-Mean Dispersion Problem
Dieudonn\'e Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique
Journal of Industrial & Management Optimization 17 (6) , 3223 (2021) ·
DOI: 10.3934/jimo.2020115
Abstract
$$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 $\backslash$begin\textbraceleft document\textbraceright\$ Q \$\textbackslash end\textbraceleft document\textbraceright$$-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.$$
Publication Details
- Type
- Article
- Journal
- Journal of Industrial & Management Optimization
- Year
- 2021
- Volume
- 17
- Issue
- 6
- Pages
- 3223
- ISSN
- 1547-5816