Improved Swarm Intelligence Algorithms And The Application In The Knapsack Problem

With the fast development of economy and science technology, traditional optimization methods are facing more and more difficulties such as the system complexity, non-linear, hugeness and fast reactivity system. At this time, the gregarious simple biology which expresses complex wisdom gives us some enlightenment. Though every unit acts very simple, the whole colony appears great wisdom with their own organically harmony and self-organization ability, so they can also complete very complex task. The phenomenon attracts many researchers to study the mechanism which hide in the phenomenon. They simulate disciplinarian from the colony and use these disciplinarian to guide and solve actual problem which is difficult to solve by traditional method.At present, solving practical problem by simulating the act of colony biology in optimization has becoming the new focus. Such as Marco Dorigo, an Italian researcher, who offered the Ant Colony Optimization (ACO) in 1991; James Kennedy and Russell Eberhart offered Particle Swarm Optimization (PSO) based on the simulating of birds colonys' and fish colonys' preying action in 1995. These methods received recognition in international optimization computing field rapidly because the methods are easy to realize, especially solving complex combination optimization problems, and it was also applied successfully in engineering design and production optimization.The dissertation discussed the comprehensive and typical methods of swarm intelligence optimization—ACO and PSO. Basic princile of ACO and PSO algorithms are systematically introduced and existing results of NP-hard problems are analyzed. Furthermore, in this dissertation we gave an improved ACO algorithem and a new hybrid PSO algorithm for the NP-hard problem—The knapsack problem. The correlative theoretical investigation was illustrated by numerical examples. It proved the algorithms was effective and ascendant.The innovative viewpoints of this dissertation are as follows:1. In order to avoid prematurity of the ACO algorithm which lead to getting the local-best solution, we gave the method for the local optimum unit to variation which based on the fundermental principle of ACO; At the same time, considering of the important of the pheromone in ACO, based on the pheromone's mutation operator, we propose an improved ACO which introduced intrusion operator. The two operators were called inner mutation operator and outer mutation operator. According to the mixed mutation, we gave a new improved algorithm and designed operation steps.2. The dissertation gave a new improved PSO algorithm which introduced crossover operator and mutation operator of GA. We can get the new fitness value from crossovering of the current fitness value, the individual fitness value and the global fitness value, the next step is the mutation operater. In the course of crossover, we use Davis's method of sequence crossover, besides this we adopt reverse mutation in the mutation step. On the basis of this, we obtained a new hybrid PSO algorithm and operation steps.3. The improved two swarm intelligence algorithms are used to solvethe typical NP-hard problem-----the knapsack problem. We got better resultthrough the practical numerical examples, it proved to be effective and ascendant in solving this problem. This paper introduced the optimal value theorem about the knapsack problem by Dantzig to the improved PSO, from that, we got the boundary of the fitness value, and gave us the better condition to eliminate non-optimal solution. Since the knapsack problem is representative and occupies an important position, the new algorithms which the dissertation proposed has considerable theoretical significance and practical meaning.