求解大规模0-1背包问题的改进人工鱼群算法  

An Improved Artificial Fish Swarm Algorithm for Solving Large Scale 0-1 Knapsack Problem

作　　者：宋潇潇[1] 

机构地区：[1]西华大学电气信息学院,四川成都610039

出　　处：《西华大学学报（自然科学版）》2013年第4期5-9,22,共6页Journal of Xihua University:Natural Science Edition

基　　金：西华大学重点项目(Z1120943)

摘　　要：针对现有算法在求解大规模0-1背包问题时存在求解精度不够和稳定性不足的情况,将贪婪算法引入到人工鱼群算法中,提出一种基于贪婪的极坐标编码人工鱼群算法。该算法引入贪婪思想对母体的初始值以及非法解修正方式进行改进;根据大规模0-1背包问题的特点对算法中的母体结构和迭代方式进行调整,并引入最优保留机制增强算法搜索的方向性。通过对物品为500、700和1 000的背包问题的实验结果表明,该算法具有良好的寻优能力和鲁棒性。Aming at the poor solution precision and stability of resolving large scale 0-1 knapsack problem with existed algorithms,this paper introduces greedy algorithm into artificial fish swarm algorithm and proposes a greedy based polar coordinate coding artificial fish swarm algorithm（GP-AFSA）.The algorithm uses the idea of greedy to improve the initial value of matrix and revision of illegal results.According to the characteristics of large scale 0-1 knapsack problem,the structure of matrix and iteration method is adjusted.The strategy of preserving is introduced to increase the search direction.Thought the experiments with 500,700 and 1 000 items,the results show that GP-AFSA has good ability of optimization and strong robustness.

关 键 词：0-1背包问题 人工鱼群算法 贪婪算法 GP-AFSA 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]