Improved Implementation Of Firefly Algorithm And Its Application In Solving Knapsack Problem

Some practical problems in production and life can be modeled as knapsack problems,such as decision investment,resource allocation,budget control,etc.Among them,the 0-1 knapsack problem is the most basic type of knapsack problem.Many knapsack problems can be converted into 0-1 knapsack problems.The key to solving the 0-1 knapsack problem is to maximize the sum of the values of the items finally loaded into the backpack when the constraints are met.Since the knapsack problem is a discretization problem,the first problem to be solved when using the group intelligence algorithm is to select the coding method to discretize the algorithm.A large number of infeasible solutions are generated when the group intelligence algorithm is calculated.If the infeasible solution is directly discarded,the population diversity will be destroyed.Therefore,the repair algorithm is needed to make the infeasible solution feasible and ensure the diversity of the population.This dissertation proposes two improved algorithms to solve the 0-1 knapsack problem.The first is the adaptive firefly algorithm.The adaptive weight is given to the position of the firefly,and the weight is weakened in the early stage of the algorithm to weaken the firefly's own position,increase the global search ability,and increase the weight in the later stage of the algorithm,in order to make the algorithm have stronger local search ability.According to the weight,the algorithm can quickly and effectively approach the theoretical optimal value.Finally,after each generation is updated,the individual performs the mutation operation according to the mutation probability.The second is an improved firefly algorithm based on simulated annealing.The firefly algorithm is used to update the position of the individual,and the simulated annealing operation selects the updated individual to ensure the diversity of the population to a certain extent.According to the crowding degree of the population,the mutation probability is set.When the population is crowded,the mutation probability is increased and the global diversity is enhanced.When the population is dispersed,the mutation probability is reduced to protect the optimal individual from damage.The two improved algorithms are tested in multiple sets,which shows that the algorithm can be used to solve the 0-1 knapsack problem and Bounded Knapsack Problem.Finally,the coding method and repair algorithm are re-selected,and the two algorithms are used to solve the bounded knapsack problem,and 30 sets of simulation experiments are used to illustrate and compare.