Leaders and Followers Algorithm for the Binary Knapsack Problem

Helen Yuliana Angmalisang; Harrychoon Angmalisang; Nita Anggriani

doi:10.57152/malcom.v5i4.2164

Authors

Helen Yuliana Angmalisang Universitas Negeri Manado https://orcid.org/0009-0004-3572-249X
Harrychoon Angmalisang Universitas Negeri Manado
Nita Anggriani Universitas Negeri Manado

DOI:

https://doi.org/10.57152/malcom.v5i4.2164

Keywords:

Knapsack Problem, Leaders and Followers Algorithm, Metaheuristic Algorithm, Optimization

Abstract

The Leaders and Followers (LaF) algorithm, as a relatively recent metaheuristic compared to other well-established algorithms, has demonstrated strong performance in solving continuous constrained optimization problems, the balanced transportation problem, and the traveling salesman problem. The distinctive feature of the LaF algorithm lies in its dual-population structure, where two groups operate with different roles, namely exploration and exploitation, to balance search diversity and convergence. This design effectively prevents premature convergence. In this study, the LaF algorithm is applied to address the binary knapsack problem. The proposed algorithm was evaluated using a well-established benchmark dataset for this problem. The results indicate that the LaF algorithm exhibits stable performance in solving binary knapsack problems with moderately sized capacities and outperforms several other metaheuristic algorithms

Downloads

Download data is not yet available.

Author Biography

Helen Yuliana Angmalisang, Universitas Negeri Manado

Helen is now currently an assistant professor in Mathematics Department at Universitas Negeri Manado and PhD student in Computer and Mathematical Sciences at University of Adelaide, Australia. She does research in optimization, evolutionary and metaheuristic algorithms.

References

Y. Gonzalez-Fernandez and S. Chen, “Leaders and followers-A new metaheuristic to avoid the bias of accumulated information,” in 2015 IEEE Congress on Evolutionary Computation, CEC 2015 - Proceedings, Institute of Electrical and Electronics Engineers Inc., Sep. 2015, pp. 776–783. doi: 10.1109/CEC.2015.7256970.

H. Y. Angmalisang, H. Angmalisang, and S. J. A. Sumarauw, “Leaders and Followers Algorithm for Balanced Transportation Problem,” Computer Engineering and Applications, vol. 12, no. 2, 2023.

H. Y. Angmalisang, H. Angmalisang, and S. J. A. Sumarauw, “Leaders and Followers Algorithm for Balanced Transportation Problem,” Computer Engineering and Applications, vol. 12, no. 2, 2023, Accessed: Oct. 01, 2023. [Online]. Available: https://comengapp.unsri.ac.id/index.php/comengapp/article/view/436/265

H. Angmalisang and S. Anam, “Leaders and Followers Algorithm For Traveling Salesman Problem,” BAREKENG: Jurnal Ilmu Matematika dan Terapan, vol. 18, no. 1, pp. 449–456, Mar. 2024, doi: 10.30598/barekengvol18iss1pp0449-0456.

N. Morimoto, “Power allocation optimization as the multiple knapsack problem with assignment restrictions,” in 2017 8th International Conference on the Network of the Future (NOF), 2017, pp. 40–45. doi: 10.1109/NOF.2017.8251218.

N. Ferdosian, M. Othman, K. Y. Lun, and B. M. Ali, “Optimal solution to the fractional knapsack problem for LTE overload-state scheduling,” in 2016 IEEE 3rd International Symposium on Telecommunication Technologies (ISTT), 2016, pp. 97–102. doi: 10.1109/ISTT.2016.7918092.

F. Vaezi, S. J. Sadjadi, and A. Makui, “A Robust Knapsack Based Constrained Portfolio Optimization,” International Journal of Engineering, vol. 33, no. 5, pp. 841–851, 2020, doi: 10.5829/ije.2020.33.05b.16.

V. Traneva, P. Petrov, and S. Tranev, “An Elliptic Intuitionistic Fuzzy Portfolio Selection Problem based on Knapsack Problem,” in Communication Papers of the 18th Conference on Computer Science and Intelligence Systems, PTI, Oct. 2023, pp. 335–342. doi: 10.15439/2023f4882.

Y. Laalaoui and R. M’Hallah, “A binary multiple knapsack model for single machine scheduling with machine unavailability,” Comput Oper Res, vol. 72, pp. 71–82, Aug. 2016, doi: 10.1016/J.COR.2016.02.005.

M. Samavati, D. Essam, M. Nehring, and R. Sarker, “A methodology for the large-scale multi-period precedence-constrained knapsack problem: an application in the mining industry,” Int J Prod Econ, vol. 193, pp. 12–20, Nov. 2017, doi: 10.1016/J.IJPE.2017.06.025.

J. and M. G. Pferschy Ulrich and Schauer, “A Quadratic Knapsack Model for Optimizing the Media Mix of a Promotional Campaign,” in Operations Research and Enterprise Systems, F. and V. B. Pinson Eric and Valente, Ed., Cham: Springer International Publishing, 2015, pp. 251–264.

X. Hao et al., “Dynamic Knapsack Optimization Towards Efficient Multi-Channel Sequential Advertising,” in Proceedings of the 37th International Conference on Machine Learning, H. D. III and A. Singh, Eds., in Proceedings of Machine Learning Research, vol. 119. PMLR, Apr. 2020, pp. 4060–4070. [Online]. Available: https://proceedings.mlr.press/v119/hao20b.html

N. Ferdosian, M. Othman, B. M. Ali, and K. Y. Lun, “Greedy–knapsack algorithm for optimal downlink resource allocation in LTE networks,” Wireless Networks, vol. 22, no. 5, pp. 1427–1440, 2016, doi: 10.1007/s11276-015-1042-9.

G. B. Dantzig, “Discrete-Variable Extremum Problems,” Oper Res, vol. 5, no. 2, pp. 266–288, Apr. 1957, doi: 10.1287/opre.5.2.266.

C. Cacchiani, M. Iori, A. Locatelli, and S. Martello, “Knapsack problems-An Overview of Recent Advances. Part I: Single Knapsack Problems,” 2022. [Online]. Available: https://www.elsevier.com/open-access/userlicense/1.0/

N. Acevedo, C. Rey, C. Contreras-Bolton, and V. Parada, “Automatic design of specialized algorithms for the binary knapsack problem,” Expert Syst Appl, vol. 141, p. 112908, 2020, doi: https://doi.org/10.1016/j.eswa.2019.112908.

M. Abdel-Basset, R. Mohamed, I. M. Hezam, K. M. Sallam, A. M. Alshamrani, and I. A. Hameed, “A novel binary Kepler optimization algorithm for 0–1 knapsack problems: Methods and applications,” Alexandria Engineering Journal, vol. 82, pp. 358–376, Nov. 2023, doi: 10.1016/j.aej.2023.09.072.

J. He, B. Mitavskiy, and Y. Zhou, “A theoretical assessment of solution quality in evolutionary algorithms for the knapsack problem,” in 2014 IEEE Congress on Evolutionary Computation (CEC), 2014, pp. 141–148. doi: 10.1109/CEC.2014.6900442.

I. M. Ali, D. Essam, and K. Kasmarik, “An Efficient Differential Evolution Algorithm for Solving 0–1 Knapsack Problems,” in 2018 IEEE Congress on Evolutionary Computation (CEC), 2018, pp. 1–8. doi: 10.1109/CEC.2018.8477916.

V. Jain and J. S. Prasad, “Applying greedy genetic algorithm on 0/1 multiple knapsack problem,” International Journal of Advanced Technology and Engineering Exploration, vol. 5, no. 45, pp. 292–296, Aug. 2018, doi: 10.19101/ijatee.2018.545018.

Wei-Zhong Sun, Min Zhang, Jie-Sheng Wang, Sha-Sha Guo, Min Wang, and Wen-Kuo Hao, “Binary Particle Swarm Optimization Algorithm Based on Z-shaped Probability Transfer Function to Solve 0-1 Knapsack Problem,” IAENG Int J Comput Sci, vol. 48, no. 2, pp. 294–303, 2021, Accessed: Apr. 13, 2024. [Online]. Available: http://www.iaeng.org/IJCS/issues_v48/issue_2/IJCS_48_2_09.pdf

K. K. Bhattacharjee and S. P. Sarmah, “Shuffled frog leaping algorithm and its application to 0/1 knapsack problem,” Applied Soft Computing Journal, vol. 19, pp. 252–263, 2014, doi: 10.1016/j.asoc.2014.02.010.

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. 01, pp. 160–167, 2020, doi: 10.37398/jsr.2020.640136.

D. David, E. V. H. S, R. Ronny, and T. Widayanti, “Modification of Attractiveness and Movement of the Firefly Algorithm for Resolution to Knapsack Problems,” in 2022 4th International Conference on Cybernetics and Intelligent System (ICORIS), 2022, pp. 1–5. doi: 10.1109/ICORIS56080.2022.10031553.

R. S. Pavithr and Gursaran, “Quantum Inspired Social Evolution (QSE) algorithm for 0-1 knapsack problem,” Swarm Evol Comput, vol. 29, pp. 33–46, Aug. 2016, doi: 10.1016/J.SWEVO.2016.02.006.

G. Yildizdan and E. Ba?, “A Novel Binary Artificial Jellyfish Search Algorithm for Solving 0–1 Knapsack Problems,” Neural Process Lett, vol. 55, no. 7, pp. 8605–8671, 2023, doi: 10.1007/s11063-023-11171-x.

M. Abdel-Basset, R. Mohamed, and S. Mirjalili, “A Binary Equilibrium Optimization Algorithm for 0–1 Knapsack Problems,” Comput Ind Eng, vol. 151, p. 106946, 2021, doi: https://doi.org/10.1016/j.cie.2020.106946.

A. J. Umbarkar and P. D. Sheth, “Crossover Operators In Genetic Algorithms: A Review,” ICTACT Journal on Soft Computing, vol. 06, no. 01, pp. 1083–1092, Oct. 2015, doi: 10.21917/ijsc.2015.0150.

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. 01, pp. 160–167, 2020, doi: 10.37398/jsr.2020.640136.

A. E. Ezugwu, V. Pillay, D. Hirasen, K. Sivanarain, and M. Govender, “A Comparative Study of Meta-Heuristic Optimization Algorithms for 0 - 1 Knapsack Problem: Some Initial Results,” IEEE Access, vol. 7, pp. 43979–44001, 2019, doi: 10.1109/ACCESS.2019.2908489