Application of Black Hole Algorithm for Solving Knapsack Problems

Document Type : Machine learning-Sadoghi

Author

• Abdolreza Hatamlou

Department of Computer Science, Khoy Branch, Islamic Azad University, Khoy, Iran.

10.22067/cke.2021.63250.0

Abstract

This study investigates the application of the Black Hole algorithm (BH) for solving 0–1 knapsack problems. Knapsack problem is a classic and famous problem for testing and analyzing the behavior of optimization and meta-heuristic algorithms. There is no single algorithm which is suitable for all types of the knapsack problem. So it is an open research area to solve knapsack problem using novel optimization algorithms efficiently. BH algorithm is one of the most recent nature-inspired algorithms that is inspired by the black hole phenomenon. Like other population-based algorithms, the black hole algorithm starts with an initial population of candidate solutions to an optimization problem and an objective function that is calculated for them. At each iteration of the Black hole algorithm, the best candidate is selected to be the black hole, and others called stars. If a star gets too close to the black hole, it will be swallowed by the black hole and is gone forever. Computational experiments with a set of large-scale instances show that the BH algorithm can be an efficient alternative for solving 0–1 knapsack problems. The results show that the algorithm can find high quality solutions in less time compared to similar meta-heuristic approaches. Based on the obtained results it is clear that BH algorithm is a stable algorithm as the standard deviation of finding solutions in different runs is smaller than other test algorithms. 

Keywords

• Knapsack Problems
• Black Hole Algorithm
• Optimization

Main Subjects

• Machine learning

---

References

 

[1] Kellerer, H. and V.A. Strusevich, Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica, vol.57, no.4: pp.769-795, 2010.

[2] A. Hatamlou, E. Ghaniyarlou, Solving knapsack problems using heart algorithm, IJAISC, vol. 5, no. 4, pp.285-293. 2016.

[3] Tavares, J., F.B. Pereira, and E. Costa, Multidimensional knapsack problem: A fitness landscape analysis. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 38, no. 3: pp.604-616. 2008.

[4] Truong, T.K., K. Li, and Y. Xu, Chemical reaction optimization with greedy strategy for the 0–1 knapsack problem. Applied Soft Computing, vol.13, no.4, pp.1774-1780. 2013.

[5] Aho, I., Interactive Knapsacks: Theory and Applications. University of Tampere. 2002:

[6] Martello, S. and P. Toth, Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc. 296. 1990:

[7] Kellerer, H., et al., Knapsack Problems. Springer, 2003.

[8] A Hatamlou, Solving Travelling Salesman Problem Using Heart Algorithm, International Journal of Applied Evolutionary Computation (IJAEC), vol. 8,  no.4, 32-42. 2017.

[9] A Hatamlou, Numerical Optimization Using the Heart Algorithm, International Journal of Applied Evolutionary Computation (IJAEC), vol. 9,  no.2, 33-37. 2018.

[10] M Ruhnavaz, A Hatamlou, Modeling Ghotour-Chai River’s Rainfall-Runoff process by Genetic Programming, Journal of Advances in Computer Research, vol.9, no. 1, 71-84, 2018.

[11] P Mohammadi, A Hatamlou, M Masdari, A comparative study on remote tracking of Parkinsons disease progression using data mining methods, arXiv preprint arXiv:1312.2140, 2013.

[12] A. Hatamlou, A hybrid bio-inspired algorithm and its application, Applied Intelligence, vol. 47, no. 4, pp. 1059-1067, 2017.

[13] A. Hatamlou, Solving travelling salesman problem using black hole algorithm, Soft Computing, vol.22, no. 24, pp. 8167-8175, 2018.

[14] B. Javidy, A. Hatamlou, S Mirjalili, Ions motion algorithm for solving optimization problems, Applied Soft Computing, 32, 72-79. 2015,

[15] A. Bouyer, A. Hatamlou, An efficient hybrid clustering method based on improved cuckoo optimization and modified particle swarm optimization algorithms, Applied Soft Computing, vol.67, pp. 172-182, 2018.

[16] A. Hatamlou, Heart: a novel optimization algorithm for cluster analysis. Prog. Artif. Intell. vol. 2, no. 2-3, pp.167-173, 2014.

[17] Zou, Dexuan, et al. "Solving 0–1 knapsack problem by a novel global harmony search algorithm." Applied Soft Computing 11.2, pp.1556-1564.‏ (2011):

[18] Lin, Feng-Tse. "Solving the knapsack problem with imprecise weight coefficients using genetic algorithms." European Journal of Operational Research 185.1 133-145,‏ (2008):

[19] Ji, Junzhong, et al. "An ant colony optimization algorithm for solving the multidimensional knapsack problems." Intelligent Agent Technology, 2007. IAT'07. IEEE/WIC/ACM International Conference on. IEEE, 2007.‏

[20] Sundar, Shyam, Alok Singh, and André Rossi. "An artificial bee colony algorithm for the 0–1 multidimensional knapsack problem." Contemporary Computing. Springer Berlin Heidelberg, pp. 141-151.‏ 2010.

[21] Pulikanti, Srikanth, and Alok Singh. "An artificial bee colony algorithm for the quadratic knapsack problem." Neural Information Processing. Springer Berlin Heidelberg, 2009.‏

[22] Kong, Min, and Peng Tian. "Apply the particle swarm optimization to the multidimensional knapsack problem." Artificial Intelligence and Soft Computing–ICAISC 2006. Springer Berlin Heidelberg, pp.1140-1149.‏ 2006.

[23] Gherboudj, Amira, Abdesslem Layeb, and Salim Chikhi. "Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm." International Journal of Bio-Inspired Computation 4.4, 229-236.‏ (2012):

 [24].   Hatamlou, Abdolreza. "Black hole: A new heuristic optimization approach for data clustering." Information Sciences 222, 175-184,‏ (2013):

 [25] Wang, L., et al., An improved adaptive binary harmony search algorithm. Information Sciences, 232: pp.58-87, 2013.

 

[26] K. Chen, L. Ma, Artificial glowworm swarm optimization algorithm for 0-1 knapsack problem, Appl. Res. Comput. vol.30, no. 4, pp. 996–998, (2013).

[27] J.Q. Liu, Y.C. He, Gu Qian Q. Solving knapsack problem based on discrete particle swarm optimization, Comput. Eng. Design, vol. 29, no. 13, pp.3189–3191, (2007).

[28] W.L. Xiang, M.Q. An, Y.Z. Li, et al., A novel discrete global-best harmony search algorithm for solving 0-1 knapsack problems, Discret. Dyn. Nat. Soc. (2014) 12, http://dx.doi.org/10.1155/2014/573731, Article ID 573731.

[29] Chen, H., Y. Zhu, and K. Hu, Discrete and continuous optimization based on multi-swarm coevolution. Natural Computing, vol. 9, no. 3. pp.659-682. 2010.