一种求解多背包问题的改进的人工鱼群算法  

An Improved Artificial Fish School Algorithm for Multi-Knapsack Problem

作　　者：覃磊[1,2] 周康[1] 易校尉[1] 

机构地区：[1]武汉轻工大学数学与计算机学院,武汉430023 [2]华中科技大学自动化学院,武汉430074

出　　处：《科技通报》2016年第6期166-171,共6页Bulletin of Science and Technology

基　　金：湖北省教育厅科学研究计划项目(B2016071)

摘　　要：多背包问题是优化领域中典型的NP难题,传统算法由于计算复杂性高或收敛速度慢等缺点,结果往往不能令人满意。针对上述问题提出了一种求解多背包问题的改进的人工鱼群算法(IAF-SA)。首先将多背包放入方式整数编码,其次对不可行人工鱼编码、不充分人工鱼编码采用"随机修复"策略进行修复,并对人工鱼群算法(AFSA)中觅食、聚群和追尾等行为和产生的人工鱼编码进行改进和修复,最后结合实验对IAFSA算法分析和检验。实验结果表明,求解多背包问题的IAFSA算法相对其它算法不仅具有更快收敛速度和更强鲁棒性,而且以较大的概率收敛于原问题的最优解。Multi-knapsack problem is a typical NP problem in optimization field, because the computing complexity of the traditional algorithms is high or they have slow convergence speed, the results are often not satisfactory. An improved artificial fish school algorithm （IAFSA） was proposed for multi-knapsack problem. Firstly, the integer coding was used in the input ways of multiple backpacks, secondly, IAFSA adopted the strategy of random repair to repair infeasible artificial fish coding and inadequate artificial fish coding, and the preying, swarming and following, etc and subsequent artificial fish coding were improved and repaired, finally, IAFSA was verified by numerical examples. Experimental results show that IAFSA not only has faster convergence speed and stronger robustness than other algorithms, but also converges to the optimal solution of the original problem with greater probability.

关 键 词：多背包问题 人工鱼群算法 约束条件 随机修复 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]