SOLVING 0 - 1 KNAPSACK PROBLEM BASED ON HYBRID GREEDY FIREWORKS ALGORITHM

Aiming at the classical knapsack problem in combinatorial optimization, in order to improve the local search ability and global search ability of the basic fireworks algorithm, an improved fireworks algorithm is proposed by combining the basic fireworks algorithm, greedy optimization strategy and simulated annealing algorithm. In order to ensure the diversity of the initial population, the Tent mapping is proposed to initialize the population ; greedy repair operator and greedy optimization operator are introduced to correct the intermediate solution ; at the same time, the simulated annealing mechanism is introduced to make the poor solution have a certain probability to be accepted to improve the ability of the algorithm to jump out of the local optimum. By solving the typical test function, it is found that the improved fireworks algorithm can accurately solve the theoretical optimal solution of the Griewank function. Compared with the basic fireworks algorithm, simulated annealing algorithm and particle swarm optimization algorithm, the improved fireworks algorithm can find the optimal value of Sphere function with higher accuracy. By solving six groups of knapsack problems with different dimensions, it is found that the improved fireworks algorithm can hit the optimal solution with 100 % probability for most test data, and hit the optimal solution with more than 70 % probability for its test data, and the standard deviation of hit times is less than 13. The experimental results show that the improved fireworks algorithm has higher solving accuracy and faster solving speed, and can effectively solve the 0-1 knapsack problem.