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

An Improved Binary Fishing Algorithm for 0-1 Knapsack Problem

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

In solving 0-1 knapsack problem,the classical swarm intelligence algorithm has some shortcomings,such as weak global search ability,low solution accuracy and slow convergence speed.In view of this situation,the binary coding is introduced into the fishing algorithm,and the binary fishing algorithm is proposed.On this basis,combined with the characteristics of the algorithm itself,the approach search method is added to improve the cooperation effect among fishermen.Drawing on the idea of greedy algorithm and roulette,the greedy roulette strategy is designed,and the initial value of the algorithm is improved by combining the random proportion parameter.At the same time,the adaptive radius coefficient is introduced to solve the problem of step parameter setting,and then an improved binary fishing algorithm is proposed.In the experiment and comparison section,150-1 knapsack problems are solved and tested.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 performance is better.For high-dimensional knapsack problems of 100 dimensions and above,the improved algorithm has obvious advantages in solving accuracy,stability,convergence speed and running time.Therefore,it is effective and feasible to apply the modified binary fishing algorithm to solve the 0-1 knapsack problem.