|
|
基于S型传递函数的二进制乌鸦搜索算法求解0-1背包问题
|
Abstract:
基于传递函数，我们提出了一种新的二进制乌鸦搜索算法(BCSA)来求解0-1背包问题(0-1KP)，它不仅保留了原有乌鸦搜索算法良好的探索能力，而且具有良好的开发能力。充分利用修复优化方法处理不可行解，在提升算法搜索能力的同时，也加快了算法的收敛速度。为验证BCSA求解0-1KP的性能，将其计算结果与七种不同算法的计算结果进行了比较，发现BCSA的求解精度高、算法稳定性良好，非常适合用来处理大规模0-1KP实例。
Based on the transfer function, we propose a new Binary Crow Search Algorithm (BCSA) for solving the 0-1 Knapsack Problem (0-1KP). It not only retains the good exploration ability of the original crow search algorithm, but also has good development ability. Making full use of repair optimization methods to handle infeasible solutions improves the search ability of the algorithm while also accelerating its convergence speed. In order to verify the performance of BCSA in solving 0-1KP, its calculation results were compared with those of seven different algorithms. It was found that BCSA has high resolution and good algorithm stability, and is very suitable for processing large-scale 0-1KP instances.
| [1] | 王熙照, 贺毅朝. 求解背包问题的演化算法[J]. 软件学报, 2017, 28(1): 1-16. |
| [2] | 贺毅朝, 李泽文, 李焕哲, 等. 离散灰狼优化算法求解有界背包问题[J]. 计算机工程与设计, 2019, 40(4): 1008-1015. |
| [3] | Peng, H., Wu, Z.J., Shao, P. and Deng, C.S. (2016) Dichotomous Binary Differential Evolution for Knapsack Problems. Mathematical Problems in Engineering, 2016, Article ID: 5732489. https://doi.org/10.1155/2016/5732489 |
| [4] | Müller, S., Al-Shatri, H., Wichtlhuber, M., Hausheer, D. and Klein, A. (2015) Computation Offloading in Wireless Multi-Hop Networks: Energy Minimization via Multi-Dimensional Knapsack Problem. 2015 IEEE 26th Annual International Sym-posium on Personal, Indoor, and Mobile Radio Communications (PIMRC), Hong Kong, 30 August-2 September 2015, 1717-1722. https://doi.org/10.1109/PIMRC.2015.7343576 |
| [5] | Song, H.J., Liang, C.G. and Can, G.G. (1999) Solving the 0/1-Knapsack Problem on Quantum Computer. Chinese Journal of Computers, 12, 1314-1316. |
| [6] | Askarzadeh, A. (2016) A Novel Metaheuristic Method for Solving Constrained Engineering Optimiza-tion Problems: Crow Search Algorithm. Computers & Structures, 169, 1-12. https://doi.org/10.1016/j.compstruc.2016.03.001 |
| [7] | 刘雪静, 贺毅朝, 路凤佳, 等. 基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题[J]. 计算机应用, 2018, 38(2): 433-442. |
| [8] | Kaur, S., Awasthi, L.K., Sangal, A.L. and Dhiman, G. (2020) Tunicate Swarm Algorithm: A New Bio-Inspired Based Metaheuristic Paradigm for Global Op-timization. Engineering Applications of Artificial Intelligence, 90, Article ID: 103541. https://doi.org/10.1016/j.engappai.2020.103541 |
| [9] | Heidari, A.A., Mirjalili, S., Faris, H., et al. (2019) Harris Hawks Optimization: Algorithm and Applications. Future Generation Computer Systems, 97, 849-872. https://doi.org/10.1016/j.future.2019.02.028 |
| [10] | Mirjalili, S. and Lewis, A. (2016) The Whale Optimization Algo-rithm. Advances in Engineering Software, 95, 51-67.
https://doi.org/10.1016/j.advengsoft.2016.01.008 |
| [11] | Shayanfar, H. and Gharehchopogh, F.S. (2018) Farmland Fertility: A New Metaheuristic Algorithm for Solving Continuous Optimization Problems. Applied Soft Computing, 71, 728-746. https://doi.org/10.1016/j.asoc.2018.07.033 |
| [12] | Kennedy, J. and Eberhart, R. (1995) Particle Swarm Op-timization. Proceedings of ICNN’95—International Conference on Neural Networks, Perth, 27 November-1 December 1995, 1942-1948. https://doi.org/10.1109/ICNN.1995.488968 |
| [13] | Rao, R.V., Savsani, V.J. and Vakharia, D.P. (2011) Teaching-Learning-Based Optimization: A Novel Method for Constrained Mechanical Design Optimization Problems. Computer-Aided Design, 43, 303-315.
https://doi.org/10.1016/j.cad.2010.12.015 |
| [14] | Hashim, F.A., Hussain, K., Houssein, E.H., Mabrouk, M.S. and Al-Atabany, W. (2021) Archimedes Optimization Algorithm: A New Metaheuristic Algorithm for Solving Optimization Problems. Applied Intelligence, 51, 1531-1551.
https://doi.org/10.1007/s10489-020-01893-z |
