CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem

by Said Labed, Amira Gherboudj, Salim Chikhi
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 34 - Number 2
Year of Publication: 2011
Authors: Said Labed, Amira Gherboudj, Salim Chikhi
10.5120/4070-5586

Said Labed, Amira Gherboudj, Salim Chikhi . A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem. International Journal of Computer Applications. 34, 2 ( November 2011), 11-16. DOI=10.5120/4070-5586

@article{ 10.5120/4070-5586,
author = { Said Labed, Amira Gherboudj, Salim Chikhi },
title = { A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem },
journal = { International Journal of Computer Applications },
issue_date = { November 2011 },
volume = { 34 },
number = { 2 },
month = { November },
year = { 2011 },
issn = { 0975-8887 },
pages = { 11-16 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume34/number2/4070-5586/ },
doi = { 10.5120/4070-5586 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:20:02.921536+05:30
%A Said Labed
%A Amira Gherboudj
%A Salim Chikhi
%T A Modified Hybrid Particle Swarm Optimization Algorithm for Multidimensional Knapsack Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 34
%N 2
%P 11-16
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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)
  2. 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)
  3. 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
  4. J. Kennedy, R.C. Eberhart. Particle Swarm Optimization. In: Proc. IEEE Int. Conf. On Neural Networks, WA, Australia, pp. 1942–1948 (1995)
  5. 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)
  6. 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)
  7. 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.
  8. Pisinger, D.: Where are the hard knapsack problems? Computers and Operations Research, Vol.32, N°. 9, pp. 2271-2284, 2005.
  9. 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)
  10. P.C. Chu, J.E. Beasley. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics, 4: 63–86 (1998).
  11. 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)
  12. Drexl A. A simulated annealing approach to the multiconstraint zero–one knapsack problem. Computing 1988; 40:1–8.
  13. 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).
  14. 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)
  15. 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).
  16. 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)
  17. J H. Holland. Adaptation in natural and artificial system. Ann Arbor, The university of Michigan Press, (1975).
  18. OR-Library, J.E. Beasley, http: // www. people.brunel.ac.uk/mastjjb/jeb/orlib/mknapinfo.html
Index Terms

Computer Science
Information Sciences

Keywords

Particle Swarm Optimization Crossover Operation Continuous/Discrete Optimization Problems Multidimensional Knapsack Problem

Powered by PhDFocusTM