求解0-1背包问题的二进制狮群算法

计算机工程与科学

求解0-1背包问题的二进制狮群算法

刘生建1，杨艳1，周永权2

(1.广州大学华软软件学院游戏系，广东广州 510990;2.广西民族大学信息科学与工程学院，广西南宁 530006)

收稿日期:2018-11-14 修回日期:2019-03-04 出版日期:2019-11-25 发布日期:2019-11-25
基金资助:
广东高校省级重点平台和重大科研项目(2016KTSCX189)；广东省普通高校重点科研平台和科研项目(2018KQNCX392);广州大学华软软件学院科研项目(ky201823)

A binary lion swarm algorithm for

solving 0-1 knapsack problem

LIU Sheng-jian1,YANG Yan1,ZHOU Yong-quan2

(1.Department of Game,South China Institute of Software Engineering,Guangzhou University,Guangzhou 510990;

2.College of Information and Computer Science,Guangxi University for Nationalities,Nanning 530006,China)

Received:2018-11-14 Revised:2019-03-04 Online:2019-11-25 Published:2019-11-25

摘要/Abstract

摘要：

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点，提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义，引入反置运算、移动算子和学习算子建立全新的位置转移方式和局部搜索规则；加入贪心策略进行解的可行化处理和充分利用，增强局部搜索能力，进一步提高收敛速度。对9个典型的0-1背包算例进行仿真实验，实验结果表明，该算法不仅可以有效求解 0-1背包问题，而且还能够以较快的速度搜索到精度较高的次优解甚至全局最优解，具有较好的稳定性；同时，对高维背包问题的求解与参考算法相比，在寻优时间和精度上更具优势。

关键词: 狮群算法, 0-1 背包问题, 组合约束优化, NP难题

Abstract:

Aiming at the shortcoming that the traditional binary swarm intelligent algorithm easily falls into local optimum and has slow convergence speed when solving the 0-1 knapsack problem,a new binary lion warm optimization algorithm (BLSO) is proposed to solve the discrete space problem.The BLSO algorithm redefines the positions of the lion, lioness and cubs, and introduces the inverse operator, move operator and learning operator to construct a brand-new location transfer method and the local search rule.The greedy strategy is added to make the solution feasible and fully utilized, so as to enhance the local search ability and speed up the convergence. The simulation experiments of nine typical 0-1 knapsack cases show that the proposed algorithm can not only solve the 0-1 knapsack problem effectively, but also search for suboptimal solutions with higher precision and even global optimal solutions quickly. The solutions have strong stability. When solving high-dimensional 0-1 knapsack problems, the proposed algorithm is superior to the reference algorithm in terms of optimization time and precision.

Key words:

Key words: Lion Swarm Optimization (LSO), 0-1 knapsack problem, combined constraint optimization, NP hard problem

刘生建1，杨艳1，周永权2. 求解0-1背包问题的二进制狮群算法[J]. 计算机工程与科学.

LIU Sheng-jian1,YANG Yan1,ZHOU Yong-quan2.

A binary lion swarm algorithm for

solving 0-1 knapsack problem

[J]. Computer Engineering & Science.

参考文献［13］

［1］	Fayard D,Plateau G.Resolution of the 0-1 knapsack problem comparison of methods ［J］.Mathematical Programming,1975,8(1):272-307.
［2］	Liu Sheng-jian，Yang Yan，Zhou Yong-quan． A swarm intelligence algorithm—Lion swarm optimization ［J］．Pattern Recognition and Artificial Intelligence,2018,31(5):431-441．(in Chinese)
［3］	Hu Xiao-bing,Huang Xi-yue.Solving 0-1 knapsack problem based on ant colony optimization algorithm ［J］.Journal of Systems Engineering,2005,20(5):520-523.(in Chinese)
［4］	Qin Ling,Bai Yun,Zhang Chun-fang,et al.Ant colony algorithm for 0-1 knapsack problem［J］.Computer Engineering,2006,32(6):212-214.(in Chinese)
［5］	Wang Li,Shao Ding-hong,Lu Jin-gui.The genetic algorithm of solving 0/1 knapsack problem［J］.Computer Simulation,2006,23(3):154-156.(in Chinese)
［6］	Wu Hai-zhou,Zhou Yong-quan,Luo Qi-fang.Hybrid symbiotic organisms search algorithm for solving 0-1 knapsack problem［J］.International Journal of Bio-inspired Computation,2018,12(1):23-53.
［7］	Zhou Yong-quan, Bao Zong-fan,Luo Qi-fang,et al.A complex-valued encoding wind driven optimization for the 0-1 knapsack problem［J］.Applied Intelligence,
20	17,46(3):684-702.
［8］	Zhou Yong-quan,Chen Xin,Zhou Guo.An improved monkey algorithm for a 0-1 knapsack problem［J］.Applied Soft Computing,2016,38:817-830.
［9］	Zhou Yong-quan,Li Liang-liang,Ma Ming-zhi.A complex-valued encoding bat algorithm for solving 0-1 knapsack problem［J］.Neural Processing Letters,
20	16,44(2):407-430.
［10］	Mirjalili S, Mirjalili S M,Yang X S.Binary bat algorithm［J］.Neural Computing and Applications,
20	13,25(3-4):663-681.
［11］	Wu Hu-sheng,Zhang Feng-ming,Zhan Ren-jun,et al.A binary wolf pack algorithm for solving 0-1 knapsack problem ［J］.Systems Engineering and Electronics,2014,36 (8):1660-1667.(in Chinese)
［12］	Li Zhi-yong,Ma Liang,Zhang Hui-zhen． Adaptive cellular particle swarm algorithm for solving 0/1 knapsack problem ［J］.Computer Engineering,2014,40(10):198-203.(in Chinese)
［13］	Wan Xiao-qiong,Zhang Hui-zhen.Hybrid bat algorithm for solving 0-1 knapsack problem［J］.Application Research of Computers,2019,36（9）:2579-2583.(in Chinese)
［14］	Dorigo M,Maniezzo V,Colomi A.Ant system:Optimization by a colony of coorperating agents［J］.IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.
［15］	Kennedy J，Eberhart R C.A discrete binary version of the particle swarm algorithm ［C］∥Proc of the World Conference on Systemics,Cybernetics and Informatics,1997:4104-4109.
	附中文参考文献：
［2］	刘生建,杨艳,周永权．一种群体智能算法——狮群算法［J］.模式识别与人工智能,2018,31(5):431-441．
［3］	胡小兵,黄席樾.基于蚁群优化算法的 0-1 背包问题求解［J］.系统工程学报,2005,20(5):520-523.
［4］	秦玲,白云,章春芳，等.解0-1背包问题的蚁群算法［J］.计算机工程,2006,32(6):212-214.
［5］	王莉,绍定宏,陆金桂.基于遗传算法的 0/1背包问题求解［J］.计算机仿真,2006,23(3):154-156.
［11］	吴虎胜,张凤鸣,战仁军,等.求解 0-1 背包问题的二进制狼群算法［J］.系统工程与电子技术,2014,36(8):1660-1667.
［12］	李枝勇,马良,张惠珍.求解 0/1 背包问题的自适应元胞粒子群算法［J］.计算机工程,2014,40(10):198-203.
［13］	万晓琼,张惠珍.求解 0-1 背包问题的混合蝙蝠算法［J］.计算机应用研究，2019,36(9):2579-2583.