The Research On The Heuristic Search Algorithms For Solving The Combinatorial Optimization Problems

Combinatorial optimization problems are ubiquitous in the scientific research and engineering practice,such as urban environment planning and pathfinding in the real-time environment..And most of these problems are complex and NP-hard.With the increase of the problems' scale,exact algorithm becomes impossible to solve them.However,the heuristic search algorithm is an efficient algorithm for solving combinatorial optimization problems.Unlike the non-informed search algorithm,it uses additional information to guide the search direction.At the same time,heuristic search algorithm has the characteristics of simple thinking,easy implementation and general use.Therefore,heuristic search algorithm can solve the problem more effectively than the non-informed search algorithm.According to search environment,heuristic search algorithm can be divided into two types: systematic heuristic search algorithm and non-systematic heuristic search algorithm.The systematic heuristic search algorithm requires that the environment is observable,known and deterministic.If the heuristic function satisfies certain characteristics,the systematic heuristic search algorithm can be complete and optimal.However,for some problems which are closer to real life,systematic heuristic search will lose its advantage.In this case,we resort to nonsystematic heuristic search algorithm.There are classical non-systematic heuristic search algorithms such as local search,evolutionary search,variable neighborhood search et al.In this thesis,we mainly study the design of heuristic function,path-finding problem,minimum capacitated dominating set problem and multi-objective minimum weighted vertex cover problem.The first two problems meet the environment of the systematic heuristic algorithm,while the latter two problems adopt non-systematic heuristic algorithm.Here is an overview of our work:(1)Building the pattern database is a way to design heuristic function.The larger the pattern database,the closer the estimated value is to the actual value.Therefore,we propose the direction-optimizing breadth-first search with external memory storage to build a large-scale pattern database.We give the implementation mode of external memory based on the changed list,and give our basic parallel mode.At the same time,we give two criteria for switching search direction.Once one of them is satisfied,we can switch direction.Finally,we propose an optimization based on locality.Our algorithm improves time efficiency by more than three times in Rubik's Cube instances,and creates the largest pattern database.(2)Pathfinding has very important applications in computer games,navigation and robotics.To solve the problem of grid-based routing,we propose an improved A* algorithm based on canonical sorting.In order to improve the preprocessing and reduce the memory occupancy during search,we do not calculate geometric containers for all points.We filter the nodes and only calculate bounding boxes for jumping points and border points.At the same time,in order to avoid large generation,we limit the number of steps for one jump.The experimental results verify the performance of our algorithm in time and space(3)The minimum capacitated dominating set problem is an important variant of dominating set,which also has been widely applied in various fields.We propose a multi-start algorithm with iterated decremental local search.To start with,a solution is produced by the initialization process with different greediness strength.Subsequently,iterated decremental local search is performed to improve the initial solution,and the cardinality of the solution keeps decreasing during the local search.Meanwhile,we use the vertex weighting score function to evaluate the possibility of a vertex inserted into or removed from the dominating set.Further,re-allocation strategy is utilized in the iterated decremental local search to intensify the solution.Finally,we conduct numerous experiments on unit disk graphs,general graphs,real-world large graphs.The computational results indicate that our algorithm performs much better than state-of-the-art algorithms.(4)The multi-objective minimum weighted vertex cover problem aims to minimize the sum of different single type weights simultaneously.In this paper,we propose a multi-objective algorithm integrating iterated neighborhood search with decomposition technique to solve this problem.Initially,we adopt the decomposition method to divide the multi-objective problem into several scalar optimization sub-problems.Meanwhile,to find more possible optimal solutions,we design a mixed score function,which is applied in initializing procedure and neighborhood search.During the neighborhood search,three operators Delete,Swap and Add explore the search space effectively.We perform numerical experiments on many instances,and the results show the effectiveness of our algorithm on several experimental metrics.We compare our experimental results with NSGA-II.It was obviously shown that our algorithm can provide much better results than the comparative algorithm considering several metrics.