Fireworks Algorithm For Solving 0-1 Knapsack Problem

Knapsack problem is a typical NP-hard problem in operations research,and many problems in life can be classified as such.Therefore,the solution to this problem is of great significance both in theory and in practice.At present,with the increase of the scale of the problem,the research on such problems has higher requirements,and the classic optimization method is even more powerless.Fortunately,with the development of swarm intelligent optimization algorithm,it has opened up new ideas for solving such problems.As an effective method to solve high-dimensional and complex optimization problems,swarm intelligence optimization algorithm is a new algorithm derived from simulating the interaction and information exchange between individuals in biological groups.Fireworks algorithm is realized by simulating the explosion process of fireworks in the air.The algorithm has less parameters and simple execution process,especially in solving high-dimensional complex optimization problems,so it has been widely concerned.Of course,this algorithm can also be used to solve the knapsack problem.The main works of this thesis are as follows:1.A fireworks algorithm based on Logistic chaotic mapping and Sigmoid function is proposed and applied to solve the classical 0-1 knapsack problems.For basic fireworks algorithm,first of all,the initialization process of fireworks adopts a random search method which is conducive to global exploration,but it is often difficult to carry out detailed local development.Therefore,the widely used Logistic chaotic map is used to initialize the fireworks,so that the distribution of the initial fireworks is more uniform and the search ability is stronger;secondly,the explosion radius of fireworks is not conducive to the balance between search speed and solution accuracy,therefore,Sigmoid function is introduced to construct the decreasing explosion radius,so that the explosion radius keeps a larger value for a longer time in the early iteration period,and full global exploration is carried out.In the later iteration period,the explosion radius keeps a smaller value for a longer time,and detailed local development is carried out to balance the search speed and solution precision;finally,the standard test function is tested and compared with other algorithms.The experimental results show that the improved algorithm has better performance.And the improved algorithm is applied to solve the classical 0-1 knapsack problems.The experimental results show that the improved algorithm is effective in solving practical optimization problems.2.Basic fireworks algorithm is improved by using Kent mapping,cosine function and crossover mutation idea,and applied to solve discounted 0-1 knapsack problem.Firstly,in order to solve the random search problem of basic fireworks algorithm,Kent mapping rules isomorphic to Logistic chaotic map are adopted to improve the search accuracy.Secondly,the sectional explosion radius is designed by using cosine function to keep the radius decreasing in the first 1/2 iteration process and increasing appropriately in the second 1/2 iteration process to avoid the fireworks falling into the local optimum.In this way,the calculation method of explosion radius can be used to guide the explosion direction purposefully,thus avoiding blindness and saving search time.Then,the Gauss mutation process is improved to optimize the mutation process by using the idea of cross mutation,which further improves the optimization performance of the algorithm.Finally,the standard test function and discounted 0-1 knapsack problems are solved.The simulation results show that the proposed algorithm outperforms other swarm intelligence algorithms and achieves the purpose of improving the performance of the algorithm.