Research Article
Grey Wolf Optimization Applied to the 0/1 Knapsack Problem
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 169 - Issue 5 |
| Published: Jul 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 },
year = { 2017 },
volume = { 169 },
number = { 5 },
pages = { 11-15 },
doi = { 10.5120/ijca2017914734 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2017
%A Eman Yassien
%A Raja Masadeh
%A Abdullah Alzaqebah
%A Ameen Shaheen
%T Grey Wolf Optimization Applied to the 0/1 Knapsack Problem%T
%J International Journal of Computer Applications
%V 169
%N 5
%P 11-15
%R 10.5120/ijca2017914734
%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
- DANTZIG, George B. Discrete-variable extremum problems. Operations research, 1957, 5.2: 266-288.
- PISINGER, David. The quadratic knapsack problem—a survey. Discrete applied mathematics, 2007, 155.5: 623-648.
- 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
- ZOU, Dexuan, et al. Solving 0–1 knapsack problem by a novel global harmony search algorithm. Applied Soft Computing, 2011, 11.2: 1556-1564.
- 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.
- 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.
- TOTH, Paolo. Dynamic programming algorithms for the zero-one knapsack problem. Computing, 1980, 25.1: 29-45.
- KOLESAR, Peter J. A branch and bound algorithm for the knapsack problem. Management science, 1967, 13.9: 723-735.
- POIRRIEZ, Vincent; YANEV, Nicola; ANDONOV, Rumen. A hybrid algorithm for the unbounded knapsack problem. Discrete Optimization, 2009, 6.1: 110-124.
- 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.
- 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.
- HE, Yi-Chao, et al. Exact and approximate algorithms for discounted {0-1} knapsack problem. Information Sciences, 2016, 369: 634-647.
- HOLLAND, John H. Genetic algorithms. Scientific american, 1992, 267.1: 66-72.
- SIMON, Dan. Biogeography-based optimization. IEEE transactions on evolutionary computation, 2008, 12.6: 702-713.
- ALATAS, Bilal. ACROA: artificial chemical reaction optimization algorithm for global optimization. Expert Systems with Applications, 2011, 38.10: 13170-13180.
- WEBSTER, Barry; BERNHARD, Philip J. A local search optimization algorithm based on natural principles of gravitation. 2003.
- 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.
- 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.
- 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.
- MIRJALILI, Seyedali; MIRJALILI, Seyed Mohammad; LEWIS, Andrew. Grey wolf optimizer. Advances in Engineering Software, 2014, 69: 46-61.
- YANG, Jinhui, et al. An ant colony optimization method for generalized TSP problem. Progress in Natural Science, 2008, 18.11: 1417-1422.
- 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.
- 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.
- 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.
- 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.
- 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
Keywords