A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem
|
10.5120/4070-5586 |
Said Labed, Amira Gherboudj and Salim Chikhi. Article: A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem. International Journal of Computer Applications 34(2):11-16, November 2011. Full text available. BibTeX
@article{key:article,
author = {Said Labed and Amira Gherboudj and Salim Chikhi},
title = {Article: A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem},
journal = {International Journal of Computer Applications},
year = {2011},
volume = {34},
number = {2},
pages = {11-16},
month = {November},
note = {Full text available}
}
Abstract
In this paper, a modified hybrid Particle Swarm Optimization (MHPSO) algorithm that combines some principles of Particle Swarm Optimization (PSO) and Crossover operation of the Genetic Algorithm (GA) is presented. Our contribution has a twofold aim: first, is to propose a new hybrid PSO algorithm. Second is to prove the effectiveness of the proposed algorithm in dealing with NP-hard and combinatorial optimization problems. In order to test and validate our algorithm, we have used it for solving the Multidimensional Knapsack Problem (MKP) which is a NP-hard combinatorial optimization problem. The experimental results based on some benchmarks from OR-Library, show a good and promise solution quality obtained by the proposed algorithm.
Reference
- A. Gherboudj, S. Chikhi. BPSO Algorithms for Knapsack Problem. A. Özcan, J. Zizka, and D. Nagamalai (Eds.): WiMo/CoNeCo 2011, CCIS 162, pp. 217–227, 2011. Springer (2011)
- J. Olamaei, T. Niknam, G. Gharehpetian. Application of particle swarm optimization for distribution feeder reconfiguration considering distributed generators. Appl. Math. Comput., 201(1-2):575-586. (2008)
- Carlos Cotta, Jose Ma Troya: A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Problem. Artificial Neural Nets and Genetic Algorithms 3, New York (1998) 250-254
- J. Kennedy, R.C. Eberhart. Particle Swarm Optimization. In: Proc. IEEE Int. Conf. On Neural Networks, WA, Australia, pp. 1942–1948 (1995)
- Shi. Y, R. Eberhart. Parameter Selection in Particle Swarm Optimization. Proceedings of the 7th Annual Conference on Evolutionary Programming, pp. 591-600, LNCS 1447, Springer (1998)
- J. Kennedy, R.C. Eberhart. A discrete binary version of the particle swarm algorithm. Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, pp. 4104-4109, NJ: Piscatawary (1997)
- Khanesar. M-A, Teshnehlab. M and Shoorehdeli. M-A. A Novel Binary Particle Swarm Optimization. In proceedings of the 15th Mediterranean Conference on Control & Automation, July 27 – 29, 2007, Athens – Greece.
- Pisinger, D.: Where are the hard knapsack problems? Computers and Operations Research, Vol.32, N°. 9, pp. 2271-2284, 2005.
- Y. Zhou, Z. Kuang, J. Wang. A Chaotic Neural Network Combined Heuristic Strategy for Multidimensional Knapsack Problem. In: Proc. L. Kang et al. (Eds.): ISICA 2008, LNCS 5370, pp. 715–722, 2008. Springer (2008)
- P.C. Chu, J.E. Beasley. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4: 63–86 (1998).
- C-L. Alonso,F. Caro, J-L. Montana. An Evolutionary Strategy for the Multidimensional 0-1 Knapsack Problem Based on Genetic Computation of Surrogate Multipliers. In: Proc. J. Mira and J.R. Alvarez (Eds.): IWINAC 2005, LNCS 3562, pp. 63–73, 2005.Springer (2005)
- Drexl A. A simulated annealing approach to the multiconstraint zero–one knapsack problem. Computing 1988; 40:1–8.
- Stefka Fidanova. Ant Colony Optimization for Multiple Knapsack Problem and Model Bias Z. Li et al. (Eds.): NAA 2004, LNCS 3401, pp. 280–287, Springer (2005).
- H. Li, Y-C.Jiao, L. Zhang, Z-W. Gu. Genetic Algorithm Based on the Orthogonal Design for Multidimensional Knapsack Problems. In: Proc. L. Jiao et al. (Eds.): ICNC 2006, Part I, LNCS 4221, pp. 696–705, 2006.Springer (2006)
- E. Angelelli, R. Mansini, M.G. Speranza. Kernel search: A general heuristic for the multi-dimensional knapsack problem. Computers & Operations Research 37 (2010) 2017–2026. Elsevier (2010).
- M. Kong, P. Tian. Apply the Particle Swarm Optimization to the Multidimensional Knapsack Problem. In: Proc. L. Rutkowski et al. (Eds.): ICAISC 2006, LNAI 4029, pp. 1140–1149, 2006. Springer (2006)
- J H. Holland. Adaptation in natural and artificial system. Ann Arbor, The university of Michigan Press, (1975).
- OR-Library, J.E. Beasley, http: // www. people.brunel.ac.uk/mastjjb/jeb/orlib/mknapinfo.html