贪心二进制狮群优化算法求解多维背包问题  

Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem

作　　者：杨艳[1] 刘生建[1] 周永权 YANG Yan;LIU Shengjian;ZHOU Yongquan(South China Institute of Software Engineering.GU,Guangzhou Guangdong 510990,China;School of Information Science and Engineering,Guangxi University for Nationalities,Nanning Guangxi 530006,China)

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

出　　处：《计算机应用》2020年第5期1291-1294,共4页journal of Computer Applications

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

摘　　要：针对经典的多约束组合优化问题——多维背包问题(MKP),提出了一种贪心二进制狮群优化(GBLSO)算法。首先,采用二进制代码转换公式将狮群个体位置离散化,得到二进制的狮群算法;其次,引入反置移动算子对狮王位置进行更新,同时对母狮和幼狮位置重新定义;然后,充分利用贪心算法进行解的可行化处理,增强搜索能力并进一步提高收敛速度;最后,对10个MKP典型算例进行仿真实验,并把GBLSO算法与离散二进制粒子群(DPSO)算法和二进制蝙蝠算法(BBA)进行对比。实验结果表明,GBLSO算法是一种有效的求解MKP的新方法,在求解MKP时具有相对良好的收敛效率、较高的寻优精度和很好的鲁棒性。The Multidimensional Knapsack Problem(MKP)is a kind of typical multi-constraint combinatorial optimization problems.In order to solve this problem,a Greedy Binary Lion Swarm Optimization(GBLSO)algorithm was proposed.Firstly,with the help of binary code transform formula,the locations of lion individuals were discretized to obtain the binary lion swarm algorithm.Secondly,the inverse moving operator was introduced to update the location of lion king and redefine the locations of the lionesses and lion cubs.Thirdly,the greedy algorithm was fully utilized to make the solution feasible,so as to enhance the local search ability and speed up the convergence.Finally,Simulations on 10 typical MKP examples were carried out to compare GBLSO algorithm with Discrete binary Particle Swarm Optimization(DPSO)algorithm and Binary Bat Algorithm(BBA).The experimental results show that GBLSO algorithm is an effective new method for solving MKP and has good convergence efficiency,high optimization accuracy and good robustness in solving MKP.

关 键 词：智能算法 贪心算法 贪心二进制狮群优化算法 多维背包问题 组合优化 

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