Journal
INFORMATION SCIENCES
Volume 512, Issue -, Pages 533-548Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2019.09.059
Keywords
Minimum weight independent dominating set problem; Local search; Reinforcement-learning-based repair procedure; Scoring function
Categories
Funding
- Fundamental Research Funds for the Central Universities [2412018QD022, 2412018ZD017]
- NSFC [61806050,61972063,61976050]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available