期刊
INFORMATION SCIENCES
卷 512, 期 -, 页码 533-548出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2019.09.059
关键词
Minimum weight independent dominating set problem; Local search; Reinforcement-learning-based repair procedure; Scoring function
资金
- Fundamental Research Funds for the Central Universities [2412018QD022, 2412018ZD017]
- NSFC [61806050,61972063,61976050]
The minimum weight independent dominating set problem (MWIDS) is a famous NP-hard combinatorial optimization problem. We herein propose a local search algorithm with reinforcement-learning-based repair procedure (LSRR). The proposed algorithm combines local search with repair procedure based on the mind of reinforcement learning. This algorithm iterates through three procedures: the greedy procedure to improve the initial solution, the local search procedure to further improve the solution, and the repair procedure to destroy the initial solution and then reconstruct a new solution. In addition, because of the particularity of the weight functions in all benchmarks, we propose three novel scoring functions. Experiments are performed on two types of graphs including random graphs and random geometric graphs. Experimental results display that LSRR outperforms the previous MWIDS algorithms significantly. (C) 2019 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据