The Algorithms For Solving Several Combinatorial Optimization Problems Based On Local Search Strategies

Combinatorial optimization problem is an important branch of Computer Science and Operations Research.In the combinatorial optimization problems,the goal is to find an(a)optimal grouping,arrangement,selection or ordering of the discrete objects through the study of mathematical methods.Combinatorial optimization problems have important applications in information technology,transportation,communication network and economic management areas.There are exact algorithms and heuristic algorithms for solving combinatorial optimization problems.Exact algorithms can accurately find the optimal solution of the problem.However,with the problem scale increasing,the required calculation and storage space of finding the optimal solution is growing exponentially,which leads to the so-called “combination explosion” phenomenon.It is almost impossible to find the optimal solution using the exact algorithms under the existing computing capacity.In this situation,some heuristic algorithms arise,such as local search algorithms,relaxation algorithms et al.For the hard problems,local search algorithms can find an optimal or a sub-optimal solution in a reasonable time.Local search algorithms have the advantages of simpleness,efficiency and easiness of parallel.Local search algorithm is easy to implement.For the optimization problems,the local search algorithms can solve them if the neighbor structure of the solution space is defined.Many studies have shown the efficiency of local search algorithms,especially for the large-scale instances of NP-hard problem,local search algorithms have great potential.Because most local search algorithms integrate random strategies,we could run them with different random seeds to implement parallelism.In this paper,we study the local search algorithms,and design efficient local search algorithms according to the characteristics of the specific problems.Specifically,we choose minimum weighted vertex cover problem,minimum capacitated dominating set problem and minimum connected dominating set problem as the research objects and design efficient local search algorithms.The main research work and contributions are as follows.(1)We design a diversion local search algorithm based on dynamic score strategy and weighted configuration checking strategy(DLSWCC)for minimum weighted vertex cover problem.In DLSWCC algorithm,the dynamic scoring strategy dynamically modifies the edge weights of the edges when the search is trapped in local optima,which changes the scores of the vertices and makes the search jump out of local optima for the right direction.The weighted configuration checking strategy is used for avoiding the circle problem by considering the environment information(configuration)of the vertices.We develop the vertex selection strategy using the dynamic scoring strategy and the weighted configuration checking strategy to determine which vertex to be added into or removed from the candidate solution.We test DLSWCC algorithm on a large number of benchmark instances,and the experimental results show that DLSWCC algorithm is superior to state-of-the-art algorithms.(2)We provide a local search algorithm based on vertex penalizing and two-mode dominated vertex selecting strategy(LS_PD)for minimum capacitated dominating set problem.In LS_PD algorithm,the vertex penalty of each undominated vertex will be increased when the search is trapped in local optima.Penalty values' change will affect the scores of the vertices and avoid the algorithm reaching the local optima.After adding one vertex into the candidate solution,the dominated vertices will be selected randomly with probability and greedily with probability 1-.The intensification strategy is used to improve the utilization rate of each vertex capacity,so as to improve the performance of the algorithm.We test LS_PD on uniform and variable capacity of the general and UDG graphs.The experimental results show that LS_PD algorithm performs better on both the general and UDG graphs.(3)We present GRASP algorithm based on candidate vertex set and solution connected elements set for minimum connected dominating set problem.In the construction process of GRASP algorithm,the vertices in the candidate vertex set are selected to be added into the candidate solution,which will not destroy the connectivity of the solution.In the process of search,if the vertices in the solution connected elements set are added into the candidate solution,the unconnected solution will be connected.Besides,we use greedy function to define the score of each vertex and tabu strategy to avoid the search revisiting the searching space repeatedly.We compare GRASP with state-of-the-art heuristic algorithms and exact algorithms.The experimental results show that GRASP performs better on LPRNMR and random instances except for a few sparse instancs of MLSTP.