We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
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

Grey Wolf Optimization Applied to the 0/1 Knapsack Problem

by Eman Yassien, Raja Masadeh, Abdullah Alzaqebah, Ameen Shaheen
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 169 - Number 5
Year of Publication: 2017
Authors: Eman Yassien, Raja Masadeh, Abdullah Alzaqebah, Ameen Shaheen
10.5120/ijca2017914734

Eman Yassien, Raja Masadeh, Abdullah Alzaqebah, Ameen Shaheen . Grey Wolf Optimization Applied to the 0/1 Knapsack Problem. International Journal of Computer Applications. 169, 5 ( Jul 2017), 11-15. DOI=10.5120/ijca2017914734

@article{ 10.5120/ijca2017914734,
author = { Eman Yassien, Raja Masadeh, Abdullah Alzaqebah, Ameen Shaheen },
title = { Grey Wolf Optimization Applied to the 0/1 Knapsack Problem },
journal = { International Journal of Computer Applications },
issue_date = { Jul 2017 },
volume = { 169 },
number = { 5 },
month = { Jul },
year = { 2017 },
issn = { 0975-8887 },
pages = { 11-15 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume169/number5/27980-2017914734/ },
doi = { 10.5120/ijca2017914734 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:16:32.672678+05:30
%A Eman Yassien
%A Raja Masadeh
%A Abdullah Alzaqebah
%A Ameen Shaheen
%T Grey Wolf Optimization Applied to the 0/1 Knapsack Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 169
%N 5
%P 11-15
%D 2017
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The knapsack problem (01KP ) in networks is investigated in this paper. A novel algorithm is proposed in order to find the best solution that maximizes the total carried value without exceeding a known capacity using Grey Wolf Optimization (GWO) and K-means clustering algorithms. GWO is a recently established meta-heuristics for optimization, inspired by grey wolf's species. K-means clustering algorithm is used to group each 5-12 agents with each other at one cluster according to GWO constraint. The evaluated performance is satisfying. The simulation results show great compatibility between experimental and theoretical results.

References
  1. DANTZIG, George B. Discrete-variable extremum problems. Operations research, 1957, 5.2: 266-288.‏
  2. PISINGER, David. The quadratic knapsack problem—a survey. Discrete applied mathematics, 2007, 155.5: 623-648.‏
  3. Bhattacharjee, K. K., & Sarmah, S. P. (2015, March). A binary cuckoo search algorithm for knapsack problems. In Industrial Engineering and Operations Management (IEOM), 2015 International Conference on (pp. 1-5). IEEE
  4. ZOU, Dexuan, et al. Solving 0–1 knapsack problem by a novel global harmony search algorithm. Applied Soft Computing, 2011, 11.2: 1556-1564.‏
  5. CHANGDAR, Chiranjit; MAHAPATRA, G. S.; PAL, Rajat Kumar. An Ant colony optimization approach for binary knapsack problem under fuzziness. Applied Mathematics and Computation, 2013, 223: 243-253.‏
  6. AZAD, Md Abul Kalam; ROCHA, Ana Maria AC; FERNANDES, Edite MGP. A simplified binary artificial fish swarm algorithm for 0–1 quadratic knapsack problems. Journal of Computational and Applied Mathematics, 2014, 259: 897-904.‏
  7. TOTH, Paolo. Dynamic programming algorithms for the zero-one knapsack problem. Computing, 1980, 25.1: 29-45.‏‏
  8. KOLESAR, Peter J. A branch and bound algorithm for the knapsack problem. Management science, 1967, 13.9: 723-735.‏
  9. POIRRIEZ, Vincent; YANEV, Nicola; ANDONOV, Rumen. A hybrid algorithm for the unbounded knapsack problem. Discrete Optimization, 2009, 6.1: 110-124.‏
  10. CHEN, Yuning; HAO, Jin-Kao. A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem. European Journal of Operational Research, 2014, 239.2: 313-322.‏
  11. RONG, Aiying; FIGUEIRA, José Rui; KLAMROTH, Kathrin. Dynamic programming based algorithms for the discounted {0–1} knapsack problem. Applied Mathematics and Computation, 2012, 218.12: 6921-6933.‏‏
  12. HE, Yi-Chao, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem. Information Sciences, 2016, 369: 634-647.‏
  13. HOLLAND, John H. Genetic algorithms. Scientific american, 1992, 267.1: 66-72.‏
  14. SIMON, Dan. Biogeography-based optimization. IEEE transactions on evolutionary computation, 2008, 12.6: 702-713.‏
  15. ALATAS, Bilal. ACROA: artificial chemical reaction optimization algorithm for global optimization. Expert Systems with Applications, 2011, 38.10: 13170-13180.‏
  16. WEBSTER, Barry; BERNHARD, Philip J. A local search optimization algorithm based on natural principles of gravitation. 2003.‏
  17. DORIGO, Marco, et al. (ed.). Ant Colony Optimization and Swarm Intelligence: 6th International Conference, ANTS 2008, Brussels, Belgium, September 22-24, 2008, Proceedings. Springer, 2008.‏
  18. ABBASS, Hussein A. MBO: Marriage in honey bees optimization-A haplometrosis polygynous swarming approach. In: Evolutionary Computation, 2001. Proceedings of the 2001 Congress on. IEEE, 2001. p. 207-214.‏
  19. YANG, Xin-She. A new metaheuristic bat-inspired algorithm. In: Nature inspired cooperative strategies for optimization (NICSO 2010). Springer Berlin Heidelberg, 2010. p. 65-74.‏
  20. MIRJALILI, Seyedali; MIRJALILI, Seyed Mohammad; LEWIS, Andrew. Grey wolf optimizer. Advances in Engineering Software, 2014, 69: 46-61.‏
  21. YANG, Jinhui, et al. An ant colony optimization method for generalized TSP problem. Progress in Natural Science, 2008, 18.11: 1417-1422.‏
  22. LI, Zhuangkuo; LI, Ning. A novel multi-mutation binary particle swarm optimization for 0/1 knapsack problem. In: Control and Decision Conference, 2009. CCDC'09. Chinese. IEEE, 2009. p. 3042-3047.‏
  23. LIM, Ting Yee; AL-BETAR, Mohammed Azmi; KHADER, Ahamad Tajudin. Taming the 0/1 knapsack problem with monogamous pairs genetic algorithm. Expert Systems with Applications, 2016, 54: 241-250.‏ ‏
  24. TRUONG, Tung Khac; LI, Kenli; XU, Yuming. Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem. Applied Soft Computing, 2013, 13.4: 1774-1780.‏
  25. SHAHEEN, Ameen; SLEIT, Azzam. Comparing between different approaches to solve the 0/1 Knapsack problem. International Journal of Computer Science and Network Security (IJCSNS), 2016, 16.7: 1.‏
  26. Masadeh R., Sharieh A. , Sleitn, A.. "Grey wolf optimization applied to the maximum flow problem", International Journal of ADVANCED AND APPLIED SCIENCES 4(7):95-100 · June 2017.
Index Terms

Computer Science
Information Sciences

Keywords

Grey Wolf Optimization (GWO) Knapsack problem Meta-heuristic Optimization.

Powered by PhDFocusTM