改进膜蜂群算法求解0-1背包问题

来源：计算机应用杂志2015年第7期北京时间：

作者：宋潇潇, 王军

单位：西华大学 电气与电子信息学院, 成都 610039

摘要：针对现有算法在求解大规模0-1背包问题时存在的不足,提出一种改进膜蜂群算法(IABCPS)。IABCPS将膜计算(MC)的思想引入人工蜂群(ABC)算法,基于极坐标编码的方式,采用细胞型单层膜结构(OLMS),利用各基本膜中改进人工蜂群算子进行迭代,并结合表层膜实现数据交流;算法通过调整内部参数,实现寻优过程中开发和探索的有效配合。实验结果表明IABCPS在求解小规模背包问题时能准确找到最优解。在求解200个物品的背包问题时,IABCPS相对克隆选择免疫遗传算法(CSIGA)平均结果提高了0.15%,方差降低了97.53%;相对于ABC算法平均结果提高了4.15%,方差降低了99.69%,表现出了良好的寻优能力和稳定性。在与ABCPS求解物品数量为300,500,700,1000的大规模背包问题的比较实验中,IABCPS的平均结果比ABCPS分别高1.25%、3.93%、6.75%和11.21%,且方差与实验次数的商始终维持在个位数,表现出了良好的鲁棒性。

关键词：人工蜂群算法,膜计算,0-1背包问题,极坐标编码,细胞型P系统

基金资助：国家自然科学基金资助项目(61472328, 51477142);四川省教育厅项目(13zb0017);西华大学重点项目(z1120943)。