Solving Combinatorial Optimization Problems Based On Heuristic Algorithms

With the development and progress of science and technology,combinatorial optimization had become more and more important in many fields such as commerce,economy,human resources,transportation,communication and image processing.At the same time,because the combination optimization problem in practical application also had the characteristics of high dimension and hard to solve,the precise algorithm often needs a lot of time in calculation,which can not meet the actual needs of production.Therefore,the imprecise algorithm represented by heuristic algorithm had been widely studied.Heuristic algorithm had the advantages of simple structure,easy implementation and fast computing speed,and had achieved great success in solving large-scale combinatorial optimization problems.Therefore,we studied heuristic algorithms such as Genetic Algorithm(GA),Binary Particle Swarm Optimization(BPSO),Hybrid Binary Differential Evolution(HBDE),Group Theory-based Optimization Algorithm(GTOA),Ring Theory-based Evolutionary Algorithm(RTEA)and Harris Hawk Optimization(HHO)to solve the3-incremental knapsack problem(3-IKP),the knapsack problem with a single continuous variable(KPC)and the uncapacitated facility location problem(UFLP)had good research significance.The main research contents of this paper are as follows:1.Based on the in-depth study of the definition of 3-IKP and the existing mathematical model 3IKPM1,a new mathematical model 3IKPM2 was established.On the basis of two repair and optimization algorithms IKPM1-ROA and IKPM2-ROA for potential solutions based on greedy strategy,the new methods of solving 3-IKP based on the two mathematical models by using heuristic algorithms are presented.Finally,by comparing the calculation results of GA,BPSO,HBDE,GTOA,RTEA and the approximate algorithm H1,the effectiveness of the proposed model and methods are proved.2.The two-stage evolution equation of HHO was reconstructed based on bit operations,and an improved discrete Harris Hawk optimization algorithm Dis HHO was proposed.In order to solve the KPC problem efficiently,an adaptive one-way mutation operation was proposed,and the repair and optimization algorithm M2-GROA was used to eliminate abnormal coding individuals in the evolution process.Finally,the efficiency of Dis HHO was verified by solving the public KPC examples.3.On the basis of summarizing the characteristics of T transfer function,a new T transfer function T5 was proposed.By using T5 to discretize DE,a new binary differential evolution algorithm T5-NBDE was proposed.By comparing the results of T5-NBDE and state-of-the-art algorithm for UFLP,the effectiveness of T5 and T5-NBDE were verified.