[1]陈建荣.求解 0-1 背包问题的改进二进制捕鱼算法[J].计算机技术与发展,2023,33(05):187-193.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 028]
　CHEN Jian-rong.An Improved Binary Fishing Algorithm for 0-1 Knapsack Problem[J].,2023,33(05):187-193.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 028]
点击复制

求解 0-1 背包问题的改进二进制捕鱼算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
33
期数:
2023年05期
页码:
187-193
栏目:
人工智能
出版日期:
2023-05-10

文章信息/Info

Title:
An Improved Binary Fishing Algorithm for 0-1 Knapsack Problem
文章编号:
1673-629X(2023)05--0187-07
作者:
陈建荣
右江民族医学院 公共卫生与管理学院,广西 百色 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.

相似文献/References:

[1]王建辉,郑光勇,徐雨明.混合人工化学反应优化算法求解 0-1 背包问题[J].计算机技术与发展,2020,30(07):71.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
　WANG Jian-hui,ZHENG Guang-yong,XU Yu-ming.Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem[J].,2020,30(05):71.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
[2]聂 鑫,殷若兰,刘海峰.软硬件协同的遗传算法设计[J].计算机技术与发展,2021,31(11):114.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 019]
　NIE Xin,YIN Ruo-lan,LIU Hai-feng.Design of Genetic Algorithm Based on Software and Hardware Cooperation[J].,2021,31(05):114.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 019]
[3]孙佳宁,马海龙,张立臣,等.求解 0-1 背包问题的融合贪心策略的回溯算法[J].计算机技术与发展,2022,32(02):190.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 031]
　SUN Jia-ning,MA Hai-long,ZHANG Li-chen,et al.Backtracking Algorithm of Fusion Greedy Strategy for Solving 0-1 Knapsack Problem[J].,2022,32(05):190.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 031]

更新日期/Last Update: 2023-05-10