Research On Improved Particle Swarm Optimization Algorithm And Chicken Swarm Algorithm For Solving 0-1 Knapsack Problem

With the rapid development of the global economy,people pay more and more attention to the efficiency of dealing with some complex problems,and try to establish mathematical models to solve them optimally.Knapsack Problem(KP),as a classical combinatorial optimization problem in operations research,has been applied in many fields.The 0-1 Knapsack Problem(0-1KP)is the most basic sub-problem in Knapsack Problem,which effectively describes the original design state and the original idea of the equation.Therefore,all types of KP can be transformed and deformed by 0-1KP,which make the optimization and efficient solution of 0-1KP becoming one of the important research directions at present.However,0-1KP is essentially a constrained optimization problem,so it is easy to have high probability of abnormal encoded individuals and prematurity.Based on the characteristics of 0-1KP,this dissertation takes the basic Particle Swarm Optimization(PSO)and the Chicken Swarm Optimization(CSO)as the starting point,and deals with the three main problems of abnormal encoded individuals,iterative efficiency and parameter evaluation.The main contents are as follows:Firstly.The existing greedy algorithm can't complete repair of all individuals,so we introduced two kinds of greedy operators GMO and GOO to deal with the abnormal encoded individuals of the operation process in algorithm.The GMO and GOO can not only modify the abnormal encoded individuals,but also further optimize it.Thus,they can significantly improve the precision and efficiency of the algorithm.Secondly.Considering the poor local search ability and precocity of the basic Particle Swarm Optimization(PSO)Algorithm,we put forward the Greedy Optimization Particle Swarm Optimization(GOPSO).When solving 0-1KP,the inertia weight with linear decline is designed to increase the diversity of the population by affecting the flight speed of particles,and add GMO and GOO operators to reduce the probability of occurrence of abnormal encoded individuals and improve the efficiency of the algorithm.We used the improved algorithm to solve the 0-1KP example.The experiment shows that the GOPSO algorithm is better in convergence accuracy than the traditional Particle Swarm Optimization.Thirdly.Since the basic Chicken Swarm Optimization(CSO)Algorithm can only be applied to continuous space at the present stage,the Discrete Chicken SwarmOptimization(DCSO)is designed to solve 0-1KP,which further expand its application field.At the same time,the weightings of Gaussian and Cauchy mutation were used to adjust the probability of variation adaptively,and the values of parameters were adjusted and analyzed in combination with the statistical evaluation strategy.By examples of different scales,the DCSO algorithm can not only inherit the strong global search capability of the basic chicken swarm algorithm,but enhance the ability to jump out of the local optimal solution,which avoid the phenomenon of prematurity and significantly improve the quality of the solution.Finally.Through examples of different scales,the two improved algorithms proposed in this dissertation are compared horizontally,and what the two improved algorithms respectively applicable are illustrated by statistics.