Research On Solving Knapsack Problem Based On Heuristic Algorithms

Knapsack problem is a NP hard combinatorial optimization problem,which has important value in engineering technology,economic management,transportation,natural science and other fields.Because the classical algorithm has some shortcomings in solving the knapsack problem,such as high time complexity,poor convergence performance,and it is difficult to obtain accurate solution within a limited time,the heuristic algorithm has been developed.Evolutionary algorithm is an important branch of meta-heuristic algorithm,which has the advantages of simple parameters,strong versatility,easy to implement and so on.The algorithm has good performance in solving nonlinear and non-convex problems,and has been successfully applied to industrial design,economic forecasting,production scheduling,artificial intelligence and other fields.Among them,GTOA,TGA and MVO are three novel evolutionary algorithms proposed in recent years,and have achieved success in numerical optimization,complex engineering problems and machine learning.Therefore,it is of good research significance to use the above three evolutionary algorithms to solve the three knapsack problems of KPS,KPC and D {0-1} KP.The main research of this paper is given below:1.A new model KPSM2 that is convenient to use evolutionary algorithm to solve KPS problem is firstly proposed,and then a general framework for solving KPS problem using evolutionary algorithm is given.In the framework,a random algorithm RGSA to generate the potential solution of KPS and a repair optimization algorithm g ROA to deal with the infeasible solution of KPS are proposed.Finally,a heuristic algorithm RA-GTOA based on the combination of GTOA and random algorithm is given,and the performance of the algorithm is verified by solving KPS instances.2.A discrete team game algorithm DTGA,which can directly solve combinatorial optimization problems,is proposed by reconstructing three TGA operators based on modular operation.In order to solve the KPC problem,the repair and optimization algorithm M2-GROA is used to eliminate the infeasible solutions.Based on DTGA,a binary team game algorithm MOBTGA based on one-way mutation strategy is proposed.By solving the KPC standard test example,the superiority of one-way mutation strategy and the efficiency of MOBTGA algorithm are verified.3.Based on modular operation,two new models of MVO are proposed,and then the local search strategy and elite strategy which can improve the convergence performance of the algorithm are introduced.Finally,a discrete hybrid multi-verse optimization algorithm DHMVO is proposed.In order to solve the D {0-1} KP problem,the repair and optimization algorithm NROA is used to eliminate the infeasible solution,and a quaternary hybrid multi-verse algorithm QHMVO for solving D {0-1} KP problem is proposed on the basis of DHMVO.The performance of the algorithm is verified by comparing with other 9 algorithms.