Font Size: a A A

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

Posted on:2021-01-18Degree:MasterType:Thesis
Country:ChinaCandidate:Y ZhouFull Text:PDF
GTID:2428330611487311Subject:Basic mathematics
Abstract/Summary:PDF Full Text Request
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.
Keywords/Search Tags:0-1 Knapsack Problem, Greedy operator, Particle Swarm Optimization Algorithm, Chicken Swarm Algorithm, Abnormal encoded individuals
PDF Full Text Request
Related items
 1 Improvement And Application Of Chicken Swarm Optimization Algorithm 2 Application Research Of Particle Swarm Optimization Algorithm 3 The Research Of Multiple Target Knapsack Problem On Tabu PSO 4 Some Improvements And Applications Of Particle Swarm Optimization Algorithm 5 Research Of Swarm Intelligence Algorithm Based Particle Swarm Optimization And Chicken Swarm Optimization 6 Analysis And Application Of Particle Swarm Optimization 7 Research On Particle Swarm Optimization Algorithm Based On ITO Stochastic Process And Its Application 8 Heuristic Optimization Algorithms And Their Applications In Several Typical Optimization Problems 9 Study Of Knapsack Problem Based On Probability Particle Swarm Optimization Algorithm 10 Double Evaluation Of Particle Swarm Algorithm