Research On The Model And Solution Algorithm Of Discounted 0-1 Knapsack Problem

The discounted {0-1} knapsack problem(D{0-1}KP)was proposed based on the{0-1} knapsack problem({0-1}KP)to characterize the discounts in commercial activities.When the evolutionary algorithm solves the D{0-1}KP,the individual coding is prone to the phenomenon that the abnormal coding probability is too high,and the algorithm is prone to premature.Based on the algorithm and model of the D{0-1}KP,three main problems that greedy optimization and repair strategy,iterative efficiency and abnormal individual coding probability were solved.The main contents are as follows:1.A new greedy repaired and optimization algorithm(NGROA)was proposed for the existing greedy repaired optimization algorithm(GROA),which only selects the greatest value density item in the same set.NGROA considers the greatest value item in the same item when multiple items are selected at the same set,which is consistent with the objective function,thereby improving the accuracy of the solution.Based on the new greedy repair optimization algorithm strategy and genetic algorithm,a new algorithm(NFir EGA)is proposed.Through the example calculation,it is verified that the new greedy repaired and optimization algorithm has a significant improvement in the accuracy of the solution.2.Considering that the traditional genetic algorithm solves the D{0-1}KP,the cross operation and mutation operation are less efficient.Combined with the core algorithm,the core accelerated genetic algorithm(CEGA)is proposed.The core acceleration genetic algorithm improves the efficiency of the algorithm by reducing the range of cross mutation operators and cross operators.The core accelerated genetic algorithm is used to solve the discounted 0-1 knapsack problem.The results show that the core accelerated genetic algorithm is superior to the traditional genetic algorithm in terms of convergence speed.3.By changing the individual coding correspondence method of the discounted0-1 knapsack problem,a new coding expression is proposed,so that the individual coding is always normal during the solving process,thereby the simplified discounted{0-1} knapsack problem(SD{0-1}KP).Based on the SD{0-1}KP model and the genetic algorithm,the first genetic algorithm(FG)for solving the SD{0-1}KP is proposed.Combined with the penalty function,a second genetic algorithm(SG)is proposed.Through the example calculation,the results show that the simplified discount 0-1 knapsack problem cannot only completely cover the field of discount{0-1} knapsack problem,but the two proposed two kinds of algorithms are all suitable for solving the simplified discounted {0-1} knapsack problem.