Call for Paper - November 2020 Edition
IJCA solicits original research papers for the November 2020 Edition. Last date of manuscript submission is October 20, 2020. Read More

Grey Wolf Optimization Applied to the 0/1 Knapsack Problem

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

Eman Yassien, Raja Masadeh, Abdullah Alzaqebah and Ameen Shaheen. Grey Wolf Optimization Applied to the 0/1 Knapsack Problem. International Journal of Computer Applications 169(5):11-15, July 2017. BibTeX

@article{10.5120/ijca2017914734,
	author = {Eman Yassien and Raja Masadeh and Abdullah Alzaqebah and Ameen Shaheen},
	title = {Grey Wolf Optimization Applied to the 0/1 Knapsack Problem},
	journal = {International Journal of Computer Applications},
	issue_date = {July 2017},
	volume = {169},
	number = {5},
	month = {Jul},
	year = {2017},
	issn = {0975-8887},
	pages = {11-15},
	numpages = {5},
	url = {http://www.ijcaonline.org/archives/volume169/number5/27980-2017914734},
	doi = {10.5120/ijca2017914734},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, 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.

Keywords

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