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

Improved artificial bee colony algorithm based on P system for 0-1 knapsack problem

作　　者：宋潇潇[1] 王军[1] 

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

出　　处：《计算机应用》2015年第7期2088-2092,共5页journal of Computer Applications

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

摘　　要：针对现有算法在求解大规模0-1背包问题时存在的不足,提出一种改进膜蜂群算法(IABCPS)。IABCPS将膜计算(MC)的思想引入人工蜂群(ABC)算法,基于极坐标编码的方式,采用细胞型单层膜结构(OLMS),利用各基本膜中改进人工蜂群算子进行迭代,并结合表层膜实现数据交流;算法通过调整内部参数,实现寻优过程中开发和探索的有效配合。实验结果表明IABCPS在求解小规模背包问题时能准确找到最优解。在求解200个物品的背包问题时,IABCPS相对克隆选择免疫遗传算法(CSIGA)平均结果提高了0.15%,方差降低了97.53%;相对于ABC算法平均结果提高了4.15%,方差降低了99.69%,表现出了良好的寻优能力和稳定性。在与ABCPS求解物品数量为300,500,700,1 000的大规模背包问题的比较实验中,IABCPS的平均结果比ABCPS分别高1.25%、3.93%、6.75%和11.21%,且方差与实验次数的商始终维持在个位数,表现出了良好的鲁棒性。Aiming at the defects of resolving large scale 0-1 knapsack problem with existed algorithm, an Improved Artificial Bee Colony algorithm based on P Systems （IABCPS） was introduced in this paper. The idea of Membrane Computing （MC）, polar coordinate coding and One Level Membrane Structure （OLMS） was used by IABCPS. Evolutionary rules of improved Artificial Bee Colony （ABC） algorithm and transformation or communication rules in P systems were adopted to design its algorithm. The limit of number of trials ＂limit＂ was adjusted to keep the balance of exploitation and exploration. The experimental results show that IABCPS can find the optimum solutions in solving small scale knapsack problems. In solving a knapsack problem with 200 items, compared with Clonal Selection Immune Genetic Algorithm （CSIGA）, ]ABCPS increases the average results by 0.15% and decreases variance by 97.53%; compared with ABC algorithm, IABCPS increases the average results by 4. 15% and decreases variance by 99.69%. The results demonstrate that IABCPS has good ability of optimization and stability. Compared with Artificial Bee Colony algorithm based on P Systems （ABCPS） in solving large scale knapsack problem with 300, 500, 700 and 1 000 items respectively, IABCPS increases the average results by 1.25%, 3.93%, 6.75% and 11.21%, and the ratio of the variance and the number of experiments keeps in single digits. It shows its strong robustness.

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

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