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

Greedy binary lion swarm optimization algorithm for solving multidimensional knapsack problem

针对经典的多约束组合优化问题——多维背包问题(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.