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.

References

• 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