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

杨 艳，刘生建，周永权

（1.广州大学华软软件学院，广州510990； 2.广西民族大学信息科学与工程学院，南宁530006）（∗通信作者电子邮箱yangyan_08@yeah.net）

0 引言

多维背包问题（Multidimensional Knapsack Problem,MKP）是一类典型的组合优化问题，有着广泛的实际应用价值，如项目决策与规划、资源分配、资金预算、货物装载等，对其求解方法的研究无论是在理论上还是实践中都具有一定的意义［1］。求解MKP主要有精确算法和启发式算法两大类：精确算法的时间复杂性都是呈指数增长的，主要用于求解规模相对较小的问题，对大规模问题依赖智能优化算法解决，常见的算法有粒子群优化算法、烟花算法、狼群算法、布谷鸟搜索算法、蚁群算法等［2-9］；进化算法多采用精英策略，在具有高进化效率的同时，存在易陷入局部最优解的局限性。文献［2-3］提出将连续的粒子群优化算法通过转换函数生成离散粒子群算法，并用于求解MKP，为求解离散问题提供了一种新方法。二进制反向烟花算法求解MKP具有良好的寻优效果，尤其是在背包维度高、物品数量多的问题中具有良好的寻优能力［6］；二进制狼群算法求解MKP时减小了陷入局部极值的概率［7］；二进制布谷鸟算法求解背包问题时提高了算法求解精度和收敛速度［8］；二进制蚁群算法求解背包问题时提高了算法的全局搜索能力［9］。本文受以上算法思想的启发，通过改进狮群算法求解MKP。

受狮群协作捕猎的启发，文献［10］提出一种新的群智能优化算法——狮群算法，并验证其良好的计算鲁棒性和全局搜索能力，但其主要用于连续函数优化问题。本文在基本狮群算法的基础上，引入二进制编码，加入贪心算法增强局部搜索能力，提出一种基于贪心算法的二进制狮群算法并求解多维背包问题，通过经典算例仿真对比实验验证了算法的有效性。

1 多维背包问题描述

多维背包问题（KMP）可以看作多个0-1背包问题，一个m维0-1背包问题可以描述如下：

已知n个价值为，2，…，n）的物品，m个容量大小为，2，…，m）的容器，第i个物品所占第j个容器的容积大小为wij。KMP要解决的就是如何选择物品装入这m个容器，使得装入容器的物品总价值最大。问题的数学模型为：

其中：f(x1，x2，…，xn)为目标函数；n为物品的编号；m为容器的编号；pi为第i个物品的价值；Cj为第j个容器的容积；wi j为第i个物品所占第j个容器的容积大小；xi为0-1决策变量，当物品i为选择装入时xi=1，否则xi=0。

通过引入惩罚系数将带约束的离散化的多维背包问题转化成无约束最优化问题，转化后的无约束优化问题模型如下：其中惩罚系数μ是一个很大的常数，取值为1010，以保证可行解的最差值都要优于不可行解的最优值。

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

2.1 狮群位置数据的离散化

将狮群领地抽象为一个N×m的欧氏空间，N为人工狮的总数量，m为编码长度；第i个人工狮在第t代的位置为为位置X i在第t代时第j维的分量值，且只能取0或1；人工狮感受到的猎物优劣即为目标函数值，通过式（2）求得。

基本的狮群算法主要适用于求解连续空间优化问题，二进制狮群算法求解多维背包问题时需将狮子的位置设为1或0，而狮子个体进行位置更新后产生的位置分量xtij不一定是1或0，使得狮群算法无法对其进行求解。由于狮子下一个位置由位置改变量ΔX i决定，ΔX i=-，ΔX i反映了的各个分量取1的概率。为了使概率值在［0，1］区间，贪心二进制狮群优化（Greedy Binary Lion Swarm Optimization,GBLSO）算法采用式（3）的转换函数对ΔX i进行处理，然后采用式（4）对狮子位置分量置1或0操作［2，4］：

其中：t为当前代数，rand()为［0，1］上均匀分布的随机数。

2.2 狮群位置更新规则

2.2.1 狮王位置更新规则

狮王位置是当前群体最优位置，其下一个位置通过反置移动算子计算。反置移动算子Θ(X i，M，r)表示X i在集合M指定的位置上随机抽出r个位置进行反置运算。狮王通过在可行位置中随机找一个位置进行取反，从而实现位置的更新，位置更新如式（5）：

其中：t为当前代数；gBest t是当前狮群发现的最佳猎物的位置。

2.2.2 母狮位置更新规则

2.2.3 幼狮位置更新规则

幼狮向下一个位置移动的方向由一个随机值rand（）决定：若rand（）＜0.5，幼狮在狮王附近移动进食，下一个位置由当前位置和狮王位置共同决定；若0.5≤rand()＜0.8，幼狮跟随母狮学习捕猎，移动的位置由当前位置和所跟随母狮的历史最优位置决定，而所跟随母狮由幼狮编号与母狮数量求模的方法确定；否则幼狮将被逐出狮群，即幼狮向狮群当前最优位置的相反方向移动。幼狮位置更新如式（7）所示：

2.3 贪心算法修正处理

由于狮子的初始位置是随机产生的，在解空间会产生一部分不满足约束条件的无效解，若直接使用式（2）计算适应度，其结果必然会小于零，从而造成大量的无效试探。为了缩短寻优时间，可对任意一个潜在解使用贪心算法进行修正，使其转换为一个可行解。使用贪心算法修正会增加算法的计算量，但能够使搜索有一定的导向而不再盲目，反而能在总体上缩短处理时间。设第i个潜在解的位置为Xi=(xi1，xi2，…，xij，…，xim)（1≤i≤N，1≤j≤m），贪心算法修正潜在解的实现步骤如下：

步骤1 对任意一个容器j，用式（1）检测输入值Xi表示的物品体积是否超过Cj，若否，则直接转入步骤3。

步骤2 循环处理（总体积＞Cj时）：

1）从袋中取出价值最小的物品xij；

2）实际总体积减去该项物品体积，置xij=0。

步骤3 循环处理（总体积＜Cj时）：

1）从候选物品中选择价值最大的物品xij；

2）若该物品的体积加上袋内物品总体积＞Cj则结束循环；

3）把该物品加入袋中，并更新总体积，置xij=1。

步骤4 返回修正后的X i。

步骤5 检测下一个容器，直到m个容器中的物品全部检测完成。

3 GBLSO算法

GBLSO算法步骤如下：

步骤1 初始化。设定狮群数目N，最大迭代次数T，维度空间m，母狮占狮群比例因子β，随机产生狮子的初始位置X i，贪婪因子Qi。

步骤2 计算适应度值。根据适应度值排序狮王、母狮及幼狮的位置，适应度最佳的位置设为群最优位置，即狮王位置。

步骤3 判断终止条件：若达到终止条件，则输出问题最优解，即狮王的位置；否则，转步骤4。

步骤4 根据式（5）、（6）、（7）更新狮王、母狮及幼狮的位置。

步骤5 根据狮子的位置计算适应度值，并对无效位置进行纠正处理。

步骤6 更新狮子自身历史最优位置及狮群历史最优位置。当有狮子发现最优解时，其他狮子调整自己的贪婪因子为自身因子和最佳因子的均值。

步骤7 每隔一定迭代次数（10次）重新排序狮王、母狮及幼狮的位置。

步骤8 计算适应度值，并判断算法是否达到终止条件，若达到则输出问题最优解，否则转步骤4。

4 仿真实验与分析

本文选取经典的离散二进制粒子群优化（Discrete binary Particle Swarm Optimization，DPSO）算法［11］和二进制蝙蝠算法（Binary Bat Algorithm，BBA）［12］，并按照本文中的修复机制进行改进，和本文算法进行比较。本文算法的实验硬件环境为Intel Xeon E3-1230V2@3.30 GHz和16 GBDDR3内存，操作系统为Win10，使用python3.7，NumPy进行实验仿真。

4.1 常用算例测试

为了验证二进制狮群群算法求解多维背包问题的有效性，本文选用参考文献［11］中的5类10个算例，每个算例的背包维度和物品数量如表1所示。

表1 选用算例测试表Tab.1 Test tableof selected examples

4.2 算法参数设置

实验中种群规模N=50，最大迭代次数T=200。各算法的特定参数设置如表2所示。

表2 算法参数设置表Tab.2 Settingsof parameters of different algorithms

4.3 仿真实验及结果分析

对每个算例独立运行20次，记录20次实验中获优次数、最优解、最差解、平均解和寻优成功迭代次数，如表3所示。

表3 三种算法性能比较Tab.3 Performancecomparison of threealgorithms

从表3的对比数据可以看出，本文算法在大多数算例上都要优于BBA和DPSO。本文算法每次迭代都能获得最优解，且寻优平均迭代数较参考文献算法少；说明本文算法收敛速度快，效率高。

图1是GBLSO、BBA和DPSO三种算法独立运行20次实验的平均寻优曲线。限于篇幅，仅给出三种算法对不同维数的背包问题部分算例的平均寻优曲线图。从图中可以看出，本文算法的平均寻优收敛速度快，能更好地找到全局最优解。

图1 典型测试算例寻优曲线Fig.1 Optimization curves of typical test examples

5 结语

本文在狮群算法的基础上引入贪心算法的思想，利用二进制编码，提出了一种基于贪心算法的二进制狮群算法，并用于求解多维背包问题。通过10个经典多维背包算例的仿真对比实验表明本文算法具有较好的求解稳定性、收敛性和全局搜索能力，同时改进算法也为其他二进制的离散优化问题提供了一种有效的方法。