A New Hybrid Particle Swarm Optimization for Solving the Knapsack Problem

Abstract:

A Knapsack Problem is a typical NP complete problem. For solving Knapsack problem, A new improved Particle Swarm Optimization algorithm was proposed in this paper, the new algorithm combine Dantzigs theory of Knapsack Problem and crossover and mutation operation of Genetic Algorithm. According their fitness values, individuals are improved firstly by crossover, Daviss sequence crossover method and reverse mutation method are used respectively in the course of crossover and mutation. Numerical examples illustrate the validity and efficiency of the new hybrid Particle Swarm Optimization.

• Periodical: Applied Mechanics and Materials (Volume 328)
• Pages: 266-270
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.328.266
• Online since: June 2013
• Authors: Hong Wang
• Keywords: Crossover, Knapsack Problem, Mutation, Particle Swarm Optimization (PSO)

References

[1] David Pisinger: Computers and Operations Research 32, pp.2271-2284. (2005).

[2] Shiyong Li, in: Ant Colony Optimization and Its Applications. Harbin Institute of Technology Press. (2004).

[3] Peram T, Veeramachaneni K, Mohan C K: Proc. of Swarm Intelligence Symposium. (2003).

[4] Parsopoulos K E, Vrahatis M N: Lecture Series on Computational Sciences.868~873. (2004).

[5] Liang J J, Qin A K, Suganthan P N: Comprehensive learning particle swarm optimizer for global optimization of multimodal functions .IEEE Transactions on Evolutionary Computation. Vol. 10 (2006), p.281~296.

DOI: 10.1109/tevc.2005.857610

[6] Clerc M: Discrete partice swarm optimization illustrated by the traveling salesman problem. 2000.http: // www.ma-uriceclerc.net.

[7] Qidi Wu, Lei Wang, In: Intelligent Particle Swarm Optimization and Its Applications. Jiangsu Education Publishing House. (2005).

[8] Shang Gao: China Engineering Science, Vol. 8, No.11. (2006).

[9] Dantzig G B: Operations Research. (1957).

[10] Liang Ma, Longde Wang: Computer Application, Vol. 21, No.8. (2001).