求解 0-1 背包问题的改进二进制捕鱼算法

来源：计算机技术与发展杂志2023年第05期北京时间：

作者：陈建荣

单位：右江民族医学院 公共卫生与管理学院,广西 百色 533000 Author(s): CHEN Jian-rong School of Public Health and Management,Youjiang Medical University for Nationalities,Baise 533000,China 关键词: 捕鱼算法;0-1 背包问题;贪心算法;群智能;二进制 Keywords: fishing algorithm;0-1 knapsack problem;greedy algorithm;swarm intelligence;binary 分类号: TP301. 6 DOI: 10. 3969 / j. issn. 1673-629X. 2023. 05. 028 摘要: 经典群智能算法在求解 0-1 背包问题时普遍存在全局搜索能力不强、求解精度不高、收敛速度慢等缺点。 针对这一情况,将二进制编码引入捕鱼算法中,提出二进制捕鱼算法。 在此基础上,结合算法本身的特点,添加靠近搜索方法,改善渔夫之间的协作效果;借鉴贪心算法和轮盘赌的思想,设计贪心轮盘赌策略,并结合随机比例参数来改善算法初值;同时引入自适应半径系数来解决步长参数设置的问题,进而提出了一种改进二进制捕鱼算法。 实验与对比部分对 15 个 0 -1背包问题进行求解测试,结果表明,对于常用算例而言,与其它群智能算法相比,改进二进制捕鱼算法能找到全部问题的最优解,且在总体性能上看较优;对于 100 维及以上的高维背包问题而言,改进算法在求解精度、稳定性、收敛速度、运行耗时等方面均具有明显优势。 因此,将改进二进制捕鱼算法应用于求解 0-1 背包问题是有效的和可行的。 Abstract: In solving 0-1 knapsack problem,the classical swarm intelligence algorithm has some shortcomings,such as weak global searchability,low solution accuracy and slow convergence speed.?In view of this situation, the binary coding is introduced into the fishingalgorithm,and the binary fishing algorithm is proposed. On this basis, combined with the characteristics of the algorithm itself, theapproach search method is added to improve the cooperation effect among fishermen. Drawing on the idea of greedy algorithm androulette,the greedy roulette strategy is designed,　and the initial value of the algorithm is improved by combining the random proportionparameter. At the same time,the adaptive radius coefficient is introduced to solve the problem of step parameter setting, and then animproved binary fishing algorithm is proposed. In the experiment and comparison section,15 0 - 1 knapsack problems are solved andtested. The results show that for common examples, compared with other swarm intelligence algorithms, the improved binary fishing algorithm can find the optimal solutions to all problems,and the overall perform－ance is better. For high-dimensional knapsack problems of100 dimensions and above,the improved algorithm has obvious advantages in solving accuracy, stability,convergence speed and runningtime. Therefore,it is effective and feasible to apply the modified binary fishing algorithm to solve the 0-1 knapsack problem.

摘要：经典群智能算法在求解 0-1 背包问题时普遍存在全局搜索能力不强、求解精度不高、收敛速度慢等缺点。 针对这一情况,将二进制编码引入捕鱼算法中,提出二进制捕鱼算法。 在此基础上,结合算法本身的特点,添加靠近搜索方法,改善渔夫之间的协作效果;借鉴贪心算法和轮盘赌的思想,设计贪心轮盘赌策略,并结合随机比例参数来改善算法初值;同时引入自适应半径系数来解决步长参数设置的问题,进而提出了一种改进二进制捕鱼算法。 实验与对比部分对 15 个 0 -1背包问题进行求解测试,结果表明,对于常用算例而言,与其它群智能算法相比,改进二进制捕鱼算法能找到全部问题的最优解,且在总体性能上看较优;对于 100 维及以上的高维背包问题而言,改进算法在求解精度、稳定性、收敛速度、运行耗时等方面均具有明显优势。 因此,将改进二进制捕鱼算法应用于求解 0-1 背包问题是有效的和可行的。

关键词：捕鱼算法;0-1 背包问题;贪心算法;群智能;二进制