求解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.