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

doi:10.11772/j.issn.1001-9081.2015.07.2088

计算机应用 ›› 2015, Vol. 35 ›› Issue (7): 2088-2092.DOI: 10.11772/j.issn.1001-9081.2015.07.2088

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

宋潇潇, 王军

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

收稿日期:2015-01-26 修回日期:2015-04-05 出版日期:2015-07-10 发布日期:2015-07-17
通讯作者: 宋潇潇(1981-),男,江苏南京人,讲师,博士,主要研究方向:优化算法、智能控制,sxx_pippen@163.com
作者简介:王军(1966-),女,四川绵阳人,教授,博士,主要研究方向:优化算法、交流传动、电力电子装置与系统。
基金资助:
国家自然科学基金资助项目(61472328, 51477142);四川省教育厅项目(13zb0017);西华大学重点项目(z1120943)。

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

SONG Xiaoxiao, WANG Jun

School of Electrical Engineering and Electronic Information, Xihua University, Chengdu Sichuan 610039, China

Received:2015-01-26 Revised:2015-04-05 Online:2015-07-10 Published:2015-07-17

摘要/Abstract

摘要：

针对现有算法在求解大规模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系统

Abstract:

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), IABCPS 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 1000 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.

Key words: Artificial Bee Colony (ABC) algorithm, Membrane Computing (MC), 0-1 knapsack problem, polar coordinate coding, cell-like P system

中图分类号:

TP301.6
TP18

宋潇潇, 王军. 改进膜蜂群算法求解0-1背包问题[J]. 计算机应用, 2015, 35(7): 2088-2092.

SONG Xiaoxiao, WANG Jun. Improved artificial bee colony algorithm based on P system for 0-1 knapsack problem[J]. Journal of Computer Applications, 2015, 35(7): 2088-2092.

参考文献

[1] WILBAUT C, SALHI S, HANAFI S. An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem [J]. European Journal of Operational Research, 2009, 199(2): 339-348.
[2] AGHEZZAF B, NAIMI M. The two-stage recombination operator and its application to the multiobjective 0/1 knapsack problem: a comparative study [J]. Computers & Operations Research, 2009, 36(12): 3247-3262.
[3] HILL R R, CHO Y K, MOORE J T. Problem reduction heuristic for the 0-1 multidimensional knapsack problem [J]. Computers & Operations Research, 2012, 39(1): 19-26.
[4] GIBSON M R, OHLMANN J W, FRY M J. An Agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition [J]. Computers & Operations Research, 2010, 37(3): 598-609.
[5] YOON Y, KIM Y, MOON B. A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem [J]. European Journal of Operational Research, 2012, 218(2): 366-376.
[6] LI Y, LI X. A continuous solution to linear 0-1 programming [J]. Journal of Dalian University of Technology, 2009, 49(2): 299-302.(李艳艳,李兴斯.求解线性0-1规划的一种连续化方法[J].大连理工大学学报,2009,49(2):299-302.)
[7] LIN F. Solving the knapsack problem with imprecise weight coefficients using genetic algorithms [J]. European Journal of Operational Research, 2008, 185(1): 133-145.
[8] MA F, XIE L, ZHENG Z. Attribute gene-reserved genetic algorithm for solving knapsack problem [J]. Journal of Tianjin University, 2010, 43(11): 1020-1024.(马丰宁,谢龙,郑重.求解背包问题的基因属性保留遗传算法[J].天津大学学报,2010,43(11):1020-1024.)
[9] YAN Y, WANG D, WANG D, et al. MultiAgent-based evolutionary algorithm for dynamic knapsack problem [J]. Journal of Northeastern University: Natural Science, 2009, 30(7): 948-951.(闫杨,汪定伟,王大志,等.求解动态背包问题的多智能体进化算法[J].东北大学学报:自然科学版,2009,30(7):948-951.)
[10] BANSAL J C, DEEP K. A modified binary particle swarm optimization for knapsack problems [J]. Applied Mathematics and Computation, 2012, 218(22): 11042-11061.
[11] ZHOU S, PAN W, LUO B, et al. A novel quantum genetic algorithm based on particle swarm optimization method and its application [J]. Acta Electronica Sinica, 2006, 34(5): 897-901.(周殊,潘炜,罗斌,等.一种基于粒子群优化方法的改进量子遗传算法及应用[J].电子学报,2006,34(5):897-901.)
[12] ZHANG W, LU T. The research of genetic ant colony algorithm and its application [J]. Procedia Engineering, 2012, 37: 101-106.
[13] REN Z, FENF Z, ZHANG A. Fusing ant colony optimization with Lagrangian relaxation for the multiple-choice multidimensional knapsack problem [J]. Information Sciences, 2012, 182(1): 15-29.
[14] SONG X, SUN D, XIE J. Improved artificial fish swarm algorithm based on polar coordinate coding [J]. System Engineering and Electronics, 2010, 32(10): 2248-2251.(宋潇潇,孙棣华,解佳.基于极坐标编码的改进人工鱼群算法[J].系统工程与电子技术,2010,32(10):2248-2251.)
[15] PĂUN G. Computing with membranes [J]. Journal of Computer and System Sciences, 2000, 61(1): 108-143.
[16] KARABOGA D. An idea based on honey bee swarm for numerical optimization, technical report TR06 [R]. Kayseri: Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.
[17] KARABOGA D, NASTURK B. A powerful and efficient algorithm for numerical function optimization: Artificial Bee Colony (ABC) algorithm [J]. Journal of Global Optimization, 2007, 39(3): 459-471.
[18] KARABOGA D, BASTURK B. On The performance of Artificial Bee Colony (ABC) algorithm [J]. Applied Soft Computing, 2008, 8(1): 687-697.
[19] KARABOGA D, AKAY B. A comparative study of artificial bee colony algorithm [J]. Applied Mathematics and Computation, 2009, 214(1): 108-132.
[20] NISHIDA T Y. An application of P-system: a new algorithm for NP-complete optimization problems [C]// Proceedings of the 8th World Multi-Conference on Systems, Cybernetics and Informatics. Orlando: International Institute of Informations and Systemics, 2004: 109-112.
[21] HUANG L, HE X, WANG N, et al. P systems based multi-objective optimization algorithm [J]. Progress in Natural Science, 2007, 17(4): 458-465.
[22] CHENG J, ZHANG G, ZENG X. A novel membrane algorithm based on differential evolution for numerical optimization [J]. International Journal of Unconventional Computing, 2011, 7(3): 159-183.
[23] ZHANG G, GHEORGHE M, WU C. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem [J]. Fundamenta Informaticae, 2008, 87(1): 93-116.
[24] ZHANG G, GHEORGHE M, LI Y. A membrane algorithm with quantum-inspired subalgorithms and its application to image processing [J]. Natural Computing, 2012, 11(4): 701-717.
[25] ZHANG G, CHENG J, GHEORGHE M, et al. A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems [J]. Applied Soft Computing, 2013, 13(3): 1528-1542.
[26] ZHANG G, ZHOU F, HUANG X. A novel membrane algorithm based on particle swarm optimization for optimization for solving broadcasting problems [J]. Journal of Universal Computer Science, 2012, 18(13): 1821-1841.
[27] TU M, WANG J, SONG X, et al. An artificial fish swarm algorithm based on P systems [J]. ICIC Express Letters, Part B: Applications, 2013, 4(3): 747-753.
[28] WU H, QIAN S, XU Z. Immune genetic algorithm based on clonal selection and its application to 0/1 knapsack problem [J]. Journal of Computer Applications, 2013, 33(3): 845-848.(武慧虹,钱淑渠,徐志丹.克隆选择免疫遗传算法对高维0/1背包问题应用[J].计算机应用,2013,33(3):845-848.)
[29] SONG X, WANG J. A membrane-inspired evolutionary algorithm based on artificial bee colony algorithm [C]// BIC-TA 2014: Proceedings of the 9th International Conference on Bio-Inspired Computing-Theories and Applications. Berlin: Springer, 2014: 395-410.

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

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[2]	李文霞, 刘林忠, 代存杰, 李玉. 基于多种群组合策略的人工蜂群算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3113-3119.
[3]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.
[4]	汤星峰, 徐卿钦, 马世纬. 基于路径探索的车载自组网贪婪路由算法[J]. 计算机应用, 2020, 40(6): 1738-1744.
[5]	张架鹏, 倪志伟, 倪丽萍, 朱旭辉, 伍章俊. 基于改进离散人工蜂群算法的同类机调度优化[J]. 计算机应用, 2020, 40(3): 689-697.
[6]	张志强, 鲁晓锋, 孙钦东, 王侃. 增强开发能力的改进人工蜂群算法[J]. 计算机应用, 2019, 39(4): 949-955.
[7]	张维存, 高蕊, 张曼. 作业车间环境下的采购生产配送联合调度模型[J]. 计算机应用, 2019, 39(11): 3383-3390.
[8]	方春林, 刘晓娟, 辛营营, 罗欢. 基于人工蜂群算法的轨道交通列车行车间隔优化[J]. 计算机应用, 2018, 38(9): 2725-2729.
[9]	梁冰, 徐华. 基于改进人工蜂群的核模糊聚类算法[J]. 计算机应用, 2017, 37(9): 2600-2604.
[10]	翟光明, 李国和, 吴卫江, 洪云峰, 周晓明, 汪静. 基于Spark的人工蜂群改进算法[J]. 计算机应用, 2017, 37(7): 1906-1910.
[11]	林凯, 陈国初, 张鑫. 多交互式人工蜂群算法及其收敛性分析[J]. 计算机应用, 2017, 37(3): 760-765.
[12]	宋栓军, 杨佩莉, 石雯丽. 基于人工蜂群算法的柔性工艺与车间调度集成优化[J]. 计算机应用, 2017, 37(2): 523-529.
[13]	陈皓, 张洁, 杨清萍, 董娅娅, 肖利雪, 冀敏杰. 基于混合搜索的多种群人工蜂群算法[J]. 计算机应用, 2017, 37(10): 2773-2779.
[14]	宋月振, 裴腾达, 裴炳南. 基于中心解的改进人工蜂群算法[J]. 计算机应用, 2016, 36(4): 1022-1026.
[15]	倪志伟, 李蓉蓉, 方清华, 庞闪闪. 基于离散人工蜂群算法的云任务调度优化[J]. 计算机应用, 2016, 36(1): 107-112.