International Journal of Modern Education and Computer Science (IJMECS)
IJMECS Vol. 16, No. 5, 8 Oct. 2024
Cover page and Table of Contents: PDF (size: 531KB)
Optimizing Knapsack Problem with Improved SHLO Variations
PDF (531KB), PP.50-64
Views: 0 Downloads: 0
Author(s)
Index Terms
Knapsack problem, Human learning optimization, Metaheuristic, Optimization problem
Abstract
The Simple Human Learning Optimization (SHLO) algorithm, drawing inspiration from human learning mechanisms, is a robust metaheuristic. This study introduces three tailored variations of the SHLO algorithm for optimizing the 0/1 Knapsack Problem. While these variants utilize the same SHLO operators for learning, their distinctiveness lies in how they generate new solutions, specifically in the selection of learning operators and bits for updating. To assess their efficacy, comprehensive tests were conducted using four benchmark datasets for the 0/1 Knapsack Problem. The results, encompassing 42 instances from three datasets, reveal that both SHLO and its proposed variations yield optimal solutions for small instances of the problem. Notably, for datasets 2 and 3, the performance of SHLO variations 2 and 3 outpaces that of the Harmony Search Algorithm and the Flower Pollination Algorithm. In particular, Variation 3 demonstrates superior performance compared to SHLO and variations 1 and 2 concerning optimal solution quality, success rate, convergence speed, and execution time. This makes Variation 3 notably more efficient than other approaches for both small and large instances of the 0/1 Knapsack Problem. Impressively, Variation 3 exhibits a remarkable 14x speed improvement over SHLO for large datasets.
Cite This Paper
Amol C. Adamuthe, Harshad Kumbhar, "Optimizing Knapsack Problem with Improved SHLO Variations", International Journal of Modern Education and Computer Science(IJMECS), Vol.16, No.5, pp. 50-64, 2024. DOI:10.5815/ijmecs.2024.05.04
Reference
[1]J. C. Bansal and K. Deep. A modified binary particle swarm optimization for knapsack problems. Applied Mathematics and Computation, Vol. 218, No. 22, pp. 11042-11061, 2012.
[2]Y.S.V. Boas and C.F. de Barros. SRVB Cryptosystems four approaches for Knapsack-based cryptosystems.
[3]S. Choi, S. Park, and H. M. Kim. The application of the 0-1 knapsack problem to the load-shedding problem in microgrid operation. In International Conference on Circuits, Control, Communication, Electricity, Electronics, Energy, System, Signal and Simulation, pp. 227-234, 2011.
[4]A. Liu, J. Wang, G. Han, S. Wang, and J. Wen. Improved simulated annealing algorithm solving for 0/1 knapsack problem. In Sixth International Conference on Intelligent Systems Design and Applications, Vol. 2, pp. 1159-1164, 2006.
[5]A. Sundarkar, and A. C. Adamuthe. Solving 01 Knapsack Problem with variations of Flower Pollination Algorithm. Journal of Scientific Research, Vol. 65, No. 3, 2021.
[6]A. Rezoug, M. Bader-El-Den and D. Boughaci. Guided genetic algorithm for the multidimensional knapsack problem. Memetic Computing, Vol. 10. pp. 29-42, 2018.
[7]C. Changdar, G. S. Mahapatra and R. K. Pal. An improved genetic algorithm based approach to solve constrained knapsack problem in fuzzy environment. Expert Systems with Applications, Vol. 42, No. 4, pp. 2276-86, 2015.
[8]H. Shi. Solution to 0/1 knapsack problem based on improved ant colony algorithm. In 2006 IEEE International Conference on Information Acquisition, pp. 1062-1066, 2006.
[9]P. Zhao, P. Zhao and X. Zhang. A new ant colony optimization for the knapsack problem. In 2006 7th International Conference on Computer-Aided Industrial Design and Conceptual Design, pp. 1-3, 2006.
[10]B. Ye, J. Sun, W. B. Xu. Solving the hard knapsack problems with a binary particle swarm approach. In Computational Intelligence and Bioinformatics: International Conference on Intelligent Computing, pp. 155-163, 2006.
[11]Y. C. He, L. Zhou, C. P. Shen. A greedy particle swarm optimization for solving knapsack problem. In 2007 International Conference on Machine Learning and Cybernetics, Vol. 2, pp. 995-998, 2007.
[12]A. C. Adamuthe, V. N. Sale and S. U. Mane. Solving single and multi-objective 01 knapsack problem using harmony search algorithm. Journal of scientific research, Vol. 64, No. 1, 2020.
[13]D. Zou, L. Gao, S. Li and J. Wu. Solving 0–1 knapsack problem by a novel global harmony search algorithm. Applied Soft Computing, Vol. 11, No. 2, pp. 1556-64, 2011.
[14]A. Bettinelli, V. Cacchiani and E. Malaguti. A branch-and-bound algorithm for the knapsack problem with conflict graph. INFORMS Journal on Computing, Vol. 29, No. 3, pp. 457-73, 2017.
[15]U. Pferschy and J. Schauer. The Knapsack Problem with Conflict Graphs. J. Graph Algorithms Appl., Vol. 13, No. 2, pp. 233-49, 2009.
[16]D. Pisinger. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research, Vol. 114, No. 3, pp. 528-41, 1999.
[17]L. Wang, H. Ni, R. Yang, M. Fei and W. Ye. A simple human learning optimization algorithm. In Computational Intelligence, Networked Systems and Their Applications. International Conference of Life System Modeling and Simulation and International Conference on Intelligent Computing for Sustainable Energy and Environment, pp. 56-65, 2014.
[18]P. Zhang, J. Du, L. Wang, M. Fei, T. Yang and P. M. Pardalos. A human learning optimization algorithm with reasoning learning. Applied Soft Computing, Vol. 122, pp. 108816, 2022.
[19]J. Du, L. Wang, M. Fei, M. I. Menhas. A human learning optimization algorithm with competitive and cooperative learning. Complex & Intelligent Systems, Vol. 9, No. 1, pp. 797-823, 2023.
[20]L. Wang, H. Ni, R. Yang, P. M. Pardalos, X. Du and M. Fei. An adaptive simplified human learning optimization algorithm. Information Sciences, Vol. 320, pp. 126-39, 2015.
[21]L. Wang, R. Yang, H. Ni, W. Ye, M. Fei and P. M. Pardalos. A human learning optimization algorithm and its application to multi-dimensional knapsack problems. Applied Soft Computing, Vol. 34, pp. 736-43, 2015.
[22]https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html (Accessed on 10/05/2023)
[23]Bhattacharjee, Kaushik Kumar, and Sarada Prasad Sarmah. Shuffled frog leaping algorithm and its application to 0/1 knapsack problem. Applied soft computing, Vol. 19, pp. 252-263, 2014.
[24]https://pages.mtu.edu/~kreher/cages/Data.html (Accessed on 10/05/2023)