How to improve “construct, merge, solve and adapt"? Use reinforcement learning!
提出一种强化学习增强的CMSA算法（RL-CMSA），在线训练学习机制替代贪心函数，在远距离字符串和最小支配集问题上平均性能提升1.28%和0.69%。
Abstract In this work, we propose a new variant of construct, merge, solve, and adapt (CMSA), which is a recently introduced hybrid metaheuristic for combinatorial optimization. Our newly proposed variant, named reinforcement learning CMSA (RL-CMSA), makes use of a reinforcement learning (RL) mechanism trained online with data gathered during the search process. In addition to generally outperforming standard CMSA, this new variant proves to be more flexible as it does not require a greedy function for the evaluation of solution components at each solution construction step. We present RL-CMSA as a general framework for enhancing CMSA by leveraging a simple RL learning process. Moreover, we study a range of specific designs for the employed learning mechanism. The advantages of the introduced CMSA variant are demonstrated in the context of the far from most string and minimum dominating set problems, showing the improvement in performance and simplicity with respect to standard CMSA. In particular, the best performing RL-CMSA variant proposed is statistically significantly better than the standard algorithm for both problems, obtaining 1.28% and 0.69% better results on average respectively.