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

A binary lion swarm algorithm for solving 0-1 knapsack problem

作　　者：刘生建[1] 杨艳[1] 周永权 LIU Sheng-jian;YANG Yan;ZHOU Yong-quan(Department of Game,South China Institute of Software Engineering,Guangzhou University,Guangzhou 510990;College of Information and Computer Science,Guangxi University for Nationalities,Nanning 530006,China)

机构地区：[1]广州大学华软软件学院游戏系,广东广州510990 [2]广西民族大学信息科学与工程学院,广西南宁530006

出　　处：《计算机工程与科学》2019年第11期2079-2087,共9页Computer Engineering & Science

基　　金：广东高校省级重点平台和重大科研项目(2016KTSCX189);广东省普通高校重点科研平台和科研项目(2018KQNCX392);广州大学华软软件学院科研项目(ky201823)

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]