Local Search Algorithm For Solving The Minimum Weight Independent Dominating Set Problem

The minimum weight independent dominating set problem(MWIDS)is an important branch of the independent dominating set problem.It adds weight constraints to the independent dominating set problem and also increases the difficulty of the problem.The MWIDS problem has been proven to be a NP hard combination optimization problem,which has been widely used in industrial production and real life,such as wireless sensor networks,wireless sensor/ actor networks,social networks,etc.This paper proposes a local search algorithm with reinforcement learning based repair procedure LSRR.The algorithm combines local search with a reinforcement learning-based repair process.Based on the characteristics of the MWIDS problem and the particularity of the benchmarks,the algorithm first designed novel dynamic scoring functions that take full account of the difference between vertex weighting and edge weighting in order to perform efficient vertex selection and improve algorithm performance.Next,the algorithm iterates through three stages: combining the greedy stage of the dynamic scoring functions to improve the initial solution,combining the local search stage of the dynamic function to further improve the solution,and repair procedure to destroy the local optimal solution and then reconstructing a new candidate solution.The algorithm assigns a reward value to each vertex.After applying the local search algorithm,the algorithm will change the reward value based on the feedback information obtained.The repair process combines reinforcement learning ideas and frequency technology to destroy and reconstruct the candidate solution.This strategy will help the algorithm to break the cycle problem,avoid falling into the sub-optimal solution space,and enable the algorithm to search more areas for better solutions.In the comparison and analysis of experimental results,this paper compares LSRR with the state-of-the-art MWIDS algorithms.The benchmarks include two types of graphs,random graphs and random geometric graphs.Experimental results show that the algorithm designed in this paper can quickly and efficiently solve MWIDS problems,and the results are obviously better than the comparison MWIDS algorithms.