Study Of Local Search Algorithms For Classic Combinatorial Optimization Problems

The combinatorial optimization problem(COP)is a kind of optimization problem that finds the optimal solution in a set of finite feasible solutions.It widely appears in many important fields such as logistics,telecommunications,transportation,and military affairs.Although the application backgrounds of various combinatorial optimization problems are different,most combinatorial optimization problems can be abstracted into mixed integer programming problems after being mathematically modeled,which essentially belong to the same type of problems.How to efficiently solve combinatorial optimization problems has always been an important topic in academic research.Traditional methods for solving combinatorial optimization problems can obtain theoretical optimal solutions under certain conditions,but they are often weak in the face of the "combinatorial explosion" caused by large-scale combinatorial optimization problems.This thesis uses local search as the basic framework to design efficient strategies and algorithms for multiple combinatorial optimization problems in different domains.At the problem-solving level,this thesis focuses on solving four typical and related combinatorial optimization problems: Vertex Bisection Minimization Problem(VBMP),Minimum Load Coloring Problem(MLCP),Discounted 0-1 Knapsack Problem(DKP)and Hardware and Software Partitioning Problem(HW/SW).At the algorithm design level,to address the challenges faced by local search algorithms in solving the aforementioned problems,this thesis proposes the following algorithms: the local search algorithm that integrates bucket sorting strategy and high-quality neighborhood structure,the local search algorithm that integrates the reduction rule and dynamic selection strategy,the local search algorithm that integrates multiple scoring functions and diverse perturbation strategies,the local search algorithm based on a similarity model algorithm framework.Specifically,the main work of this thesis is as follows:(1)Two local search algorithms that integrate bucket sorting strategy and highquality neighborhood structure are proposed to solve the vertex bisection minimization problem.The Basic Variable Neighborhood Search(BVNS)algorithm is a classic heuristic algorithm for solving the VBMP problem.Building upon the BVNS algorithm,this thesis addresses the inefficiency in evaluating the quality of neighboring solutions by optimizing it using the bucket sorting strategy.The BVNSbucket algorithm significantly reduces the time required to find the optimal solution for the VBMP problem.To further enhance the performance of the BVNSbucket algorithm for solving large-scale instances,this thesis introduces the top-swap strategy and information perturbation strategy.These strategies aim to improve the performance of the BVNSbucket algorithm for large-scale instances by constructing high-quality neighborhood structures and generating highquality initial solutions.Experimental results demonstrate that the BVNSbucket2 algorithm achieves competitive performance in solving large-scale instances compared to other well-performing heuristic algorithms for the VBMP problem.(2)A local search algorithm that integrates the reduction rule and dynamic selection strategy is proposed to solve the minimum load coloring problem.The state-of-the-art heuristic algorithm for solving the MLCP problem,Reinforcement Learning based Tabu Search(RLTS),suffers from high computational time when dealing with large-scale instances due to the enormous search space.To address this issue,this thesis introduces the one-degree vertex rule and the two-stage best from multiple selection strategy from the perspectives of reducing the instance size and dynamically selecting neighboring solutions,respectively.These strategies aim to help the RLTS algorithm adapt flexibly and efficiently to different-sized search spaces.Compared to other well-performing heuristic algorithms for the MLCP problem,the Improved Reinforcement Learning based Tabu Search(IRLTS)algorithm achieves competitive performance.Additionally,this thesis provides theoretical evidence of the effectiveness of the one-degree vertex rule and validates the effectiveness of the two-stage best from multiple selection strategy through ablation experiments.(3)A local search algorithm that integrates multiple scoring functions and diverse perturbation strategies is proposed to solve the discounted 0-1 knapsack problem.Addressing the low efficiency of heuristic algorithms for solving the DKP problem,this thesis designs three efficient scoring functions and diverse perturbation strategies based on the characteristics of the DKP problem.The multiple scoring functions are used to improve the search efficiency of the local search algorithm,while the diverse perturbation strategies focus on addressing the issue of low-quality new initial solutions obtained after algorithm perturbation.Experimental results demonstrate that the Knapsack Local Search(KPLS)algorithm,which integrates the above two strategies,achieves competitive performance compared to multiple well-performing heuristic algorithms for solving the DKP problem.Additionally,this thesis validates the effectiveness of the diverse perturbation strategies through ablation experiments and analyzes the impact of key parameters on the KPLS algorithm.(4)A local search algorithm based on a similar model algorithm framework is proposed to solve the hardware and software partitioning problem.By leveraging the similarity between the mathematical models of the HW/SW problem and the Minimum Weight Dominating Set(MWDS)problem,this thesis introduces and improves the local search algorithm framework of the MWDS problem to solve the HW/SW problem.Based on this framework,two vertex selection rules based on scoring functions and tabu tenure strategy,as well as an initial construction method that utilizes the average communication cost information of vertices,are proposed.These components form the HW/SW Local Search(HSLS)algorithm,which efficiently solves the HW/SW problem.Experimental results demonstrate that the HSLS algorithm achieves competitive performance compared to four well-performing heuristic algorithms for the HW/SW problem.Additionally,this thesis organizes experiments to analyze the impact of key parameters on the HSLS algorithm and validate the effectiveness of the proposed strategies.In summary,from the perspective of problem-solving,the multiple local search algorithms proposed in this thesis have achieved good performance for their respective problems,making them efficient heuristic algorithms for solving these problems.From the perspective of algorithm design,the multiple local search algorithms proposed in this thesis,as well as the various optimization strategies proposed to address the shortcomings of local search algorithms,have certain reference and inspiration value for the design of heuristic algorithms for other combinatorial optimization problems.