背包问题是由Merkel和Hellman在1978年提出的^[1], 它是一个典型的组合优化问题, 属于NP-hard难题, 随着问题规模越来越大, 复杂度增强. 在实际应用中, 许多工业和金融等问题都可以用背包问题来描述, 如预算控制、资源分配、项目选择、资本投资、金融组合、材料切割和物件装箱等^[2]. 近年来, 背包问题已成为众多学者研究的一个热点问题, 寻找新的方法来求解背包问题具有重要的理论和实际意义^[3]. 目前, 求解背包问题的方法主要有两种: 最优算法和启发式算法. 最优算法包括穷举法、动态规划法、递归算法、回溯法和分支界限法等^[4–7]. 启发式算法包括差分进化算法^[8], 粒子群算法^[9]和遗传算法^[10]等. 前者的思想比较简单, 不需要其它专业知识, 一般适用于求解规模较小的问题; 后者一般适用于求解规模较大的问题, 可是对其求解的精度还需继续探讨.

猴群算法是一种新兴的群智能优化算法^[11], 该算法的突出特点在于求解高维的优化问题时, 无需考虑函数是否可导或可微, 只需要计算当前位置的伪梯度, 就可以确定算法的搜索方向, 并且该算法的结构简单, 参数少和易实现. 因此, 猴群算法在提出不久便得到了众多学者的广泛关注, 在各个领域内得到了快速地发展, 例如在大跨径连续刚构桥传感器优化布置问题^[12]、入侵检测系统存在高漏报率的问题^[13]、加气站项目进度的问题^[14]、混合动力优化^[15,16]、模糊规则的分类器^[17]等领域. 而文献[12–17]中均是基本猴群算法的应用, 可以看出在某种程度上解决了一些问题. 但是, 在上述问题的应用中, 随着测点数目或者规则等的增加, 基本猴群算法暴露出易陷入局部最优, 导致存在求解精度不高的弊端. 因此, 对该算法进一步研究是很必要的, 并将其的应用进行扩展, 来解决实际生活中的诸多应用问题具有重要的实际意义.

为了提高猴群算法的寻优性能, 本文将诱导因子引入基本猴群算法的爬过程中, 给出了一种诱导因子猴群算法, 并将其应用到求解0-1背包问题. 最后, 通过仿真实验验证了该方法的可行性.

1 0-1背包问题

0-1背包问题是一种常见的组合优化问题. 一般可简单叙述为: 设物品的数量为D, 第i个物品的体积(重量)和价格分别为w_i和p_i, 一个背包的能承受的最大容量为V, 选择一些物品, 放入背包中. 如何选择物品, 在满足背包约束条件下, 使背包中物品的总价值最大, 这个问题被称为0-1背包问题, 其数学模型建立如下:

$\max \;f = RX = \sum\limits_{i = 1}^D {{R_i}{x_i}} $

(1)

${\rm{s}}{\rm{.t}}{\rm{.}}\quad WX = \sum\limits_{i = 1}^D {{w_i}{x_i} \le V} $

(2)

其中, $R = ({R_1},{R_2}, \cdots ,{R_D})$ 表示物品的价值向量, $W = ({w_1},{w_2},\cdots,{w_D})$ 表示物品对应的体积(重量)向量, $X = \left( {{x_1},{x_2},\cdots,{x_n}} \right)$ 表示解向量. 式(1)表示目标函数; 式(2)中x_i为决策变量, x_i=0表示第i个物品未装入包中, x_i=1表示第i个物品装入包中.

2 猴群算法 2.1 基本猴群算法

基本猴群算法是由Zhao和Tang两位学者首次在期刊Journal of Uncertain Systems上提出的^[11]. 该算法主要包括解的表示和初始化、爬过程、望过程和跳过程, 其具体的操作过程如下:

Step1. 解的表示和初始化: 设 ${X_i} = \left( {{x_{i1}},{x_{i2}},\cdots,} \right.$ $\left. {{x_{ij}},\cdots,{x_{iD}}} \right)(1 \le i \le M,1 \le j \le D)$ 是目标函数的一个可行解, 表示第i只猴子当前的位置, 由式(3)生成.

${X_i} = {\rm{(}}{x_{\max }} - {x_{\min }}{\rm{)}} \cdot rand{\rm{(}}1,D{\rm{)}} + {x_{\min }}$

(3)

其中, M表示种群规模, D为维数, x_ij表示第i只猴子在第j维的位置, 变量的区间为 $[{x_{\min }},{x_{\max }}]$ , $rand\left( {1,D} \right)$ 是由[0, 1]之间的均匀分布的随机数组成的D维向量.

Step2. 执行爬过程: 爬过程是每只猴子在当前的范围内通过逐步爬行迭代, 寻找优化问题的目标函数值的过程, 具体过程如下:

1) 随机生成向量 $\Delta {X_i} = \left( {\Delta {x_{i1}},\Delta {x_{i2}},\cdots,\Delta {x_{ij}},\cdots,}\right.$ $\left. {\Delta {x_{iD}}} \right)$ , 其中, $\Delta {x_{ij}}$ 由式(4)生成. 参数 $a\left( {a > 0} \right)$ 为猴群每次爬的步长.

$\Delta {x_{ij}} = \left\{ {\begin{array}{*{20}{c}}{a,\quad {\text{以概率}}0.5}\\{ - a,\;\;{\text{以概率}}0.5}\end{array}} \right.$

(4)

2) 计算 ${f_{ij}}'\left( {{X_i}} \right) = \displaystyle\frac{{f\left( {{X_i} + \Delta {X_i}} \right) - f\left( {{X_i} - \Delta {X_i}} \right)}}{{2\Delta {X_i}}}$ , 其中, ${f_i}'\left( {{X_i}} \right) = \left( {{f_{i1}}'\left( {{X_i}} \right),{f_{i2}}'\left( {{X_i}} \right), \cdots ,{f_{iD}}'\left( {{X_i}} \right)} \right)$ 是目标函数所在位置的伪梯度.

3) 令 ${Y_i} = {X_i} + a \cdot sign\left( {{f_{ij}}'\left( {{X_i}} \right)} \right)$ , 其中, sign为符号函数.

4) 如果向量 ${Y_i} = \left( {{y_{i1}},{y_{i2}}, \cdots ,{y_{ij}}, \cdots ,{y_{iD}}} \right)$ 在 $[{x_{\min }},{x_{\max }}]$ 范围内, 并且 $f\left( {{Y_i}} \right) < f\left( {{X_i}} \right)$ , 更新X_i为Y_i: 否则, X_i不变.

5) 重复1)–4), 直到达到预定的执行次数Nc.

Step3. 执行望过程: 在爬过程之后, 每只猴子都到达了各自所在的山峰的顶端, 并向四周眺望, 观察视野范围内是否存在比当前位置更高的山峰.若存在, 就从当前位置跳到更高的位置. 具体过程如下:

1) 在视野范围内 $\left[ {{x_{ij}} - b,{x_{ij}} + b} \right]$ , 随机产生实数y_ij, 令 ${Y_i} = \left( {{y_{i1}},{y_{i2}}, \cdots ,{y_{ij}}, \cdots ,{y_{iD}}} \right)$ , 那么 $Y = \left( {{Y_1},{Y_2}, \cdots ,{Y_j}, \cdots ,{Y_D}} \right)$ . 其中, b为视野长度, 它决定了猴子从当前位置眺望的最远距离.

2) 如果向量 ${Y_i} = \left( {{y_{i1}},{y_{i2}}, \cdots ,{y_{ij}}, \cdots ,{y_{iD}}} \right)$ 在 $[{x_{\min }},{x_{\max }}]$ 的范围内, 并且 $f\left( {{Y_i}} \right) < f\left( {{X_i}} \right)$ , 更新X_i为Y_i; 否则, 重复1), 直至找到可行的Y_i.

3) 以Y作为初始位置, 执行爬过程.

Step4. 执行跳过程: 它的主要目的是由当前区域转移到新的区域进行搜索. 选择所有猴子的重心位置作为支点, 每只猴子从当前位置朝着支点的方向跳到新的区域进行搜索, 具体过程如下:

1) 在跳区间[c, d]内随机生成一个实数θ.

2) 令:

${Y_i} = {x_{ij}} + \theta \left( {{p_j} - {x_{ij}}} \right)$

(5)

其中, ${p_j} = \frac{1}{M}\sum\limits_{i = 1}^M {{x_{ij}}} $ , 其中 $p = \left( {{p_1},{p_2}, \cdots ,{p_D}} \right)$ 被称为支点.

3) 如果向量 ${Y_i} = \left( {{y_{i1}},{y_{i2}}, \cdots ,{y_{ij}}, \cdots ,{y_{iD}}} \right)$ 在 $[{x_{\min }},{x_{\max }}]$ 范围内, 并且 $f\left( {{Y_i}} \right) < f\left( {{X_i}} \right)$ , 更新X_i为Y_i; 否则, 重复1)和2), 直至找到可行的Y_i.

Step5. 终止条件: 重复Step2–Step4, 直到达到预先设定的迭代次数N, 算法终止, 输出结果.

2.2 诱导因子猴群算法

在基本猴群算法中, 爬过程是非常重要的, 它是控制算法的搜索精度. 可是, 在基本猴群算法中, 猴群位置在爬过程中的更新, 是没有规律的, 往往具有很大的随机性, 使得算法很难找到局部范围内的最优个体, 从而不容易找到全局最优个体, 这样就降低了算法的求解精度.

为了克服算法的这个缺陷, 本文在爬过程中引入诱导过程, 提出了一种诱导因子猴群算法. 具体为: 在猴子爬行过程中, 给定猴子向上爬行的指示, 诱导它们向最优位置的方向爬行, 这样可以避免绕路, 尽快找到局部范围内的最优个体, 从而迅速找到全局最优个体, 来提高算法的寻优能力, 达到提高算法的精度, 其具体操作如下.

在爬过程中, 随机生成爬向量 $\Delta {X_i} =(\Delta {x_{i1}},$ $ \Delta {x_{i2}}, \cdots ,\Delta {x_{ij}}, \cdots ,\Delta {x_{iD}})(1 \le i \le M,1 \le j \le D)$ , 其中, 分量 $\Delta {x_{ij}}$ 由下述过程生成.

随机生成一个M×D阶矩阵 $\beta = \left( {{\beta _{i1}},}\right.$ $\left. {{\beta _{i2}}, \cdots ,{\beta _{ij}}, \cdots ,{\beta _{iD}}} \right)(1 \le i \le M,1 \le j \le D)$ , 其中, 分量β_ij是在区间[0, 1]上随机生成的一个实数. 当 ${\beta _{ij}} > {e^{1 - \frac{{Nc}}{{Nc + 1 - kc}}}}$ 时, $\Delta {x_{ij}} = 0$ ; 否则, $\Delta {x_{ij}} = a$ . 这样, 分量 $\Delta {x_{ij}}$ 就可由下式(6)来表示.

$\Delta {x_{ij}} = \left\{ {\begin{array}{*{20}{c}}{0,\quad \quad {\beta _{ij}} > {e^{1 - \frac{{Nc}}{{Nc + 1 - kc}}}}}\\{a,\quad \quad {\beta _{ij}} \le {e^{1 - \frac{{Nc}}{{Nc + 1 - kc}}}}}\end{array}} \right.$

(6)

这样, 在猴子爬行的过程中, 就可以通过爬向量 $\Delta {X_i}$ 中0的个数来诱导猴子的爬行, 来提高算法的寻优能力, 进而达到提高算法的求解精度. 其中, M为种群规模, D为维数, N_c为爬过程中爬的次数, k_c为每次爬行的迭代次数, 参数 $a\left( {a > 0} \right)$ 为猴子的爬步长.

在爬过程中引入诱导过程时, 为了达到提高算法寻优能力的目的, 那么就需要选择一个合适的诱导次数. 如果诱导次数过低, 提高算法寻优能力就不太明显. 如果诱导次数过高, 算法往往会出现陷入局部最优, 达不到提高算法寻优能力的目的. 因此, 本文经过多次仿真后, 找到当诱导次数 $guide = 5$ 时, 既可以提高局部寻优能力, 又可以避免因过高的局部寻优能力而降低了全局寻优能力, 从而提高了算法的寻优性能.

3 利用诱导因子猴群算法求解0-1背包问题

利用诱导因子猴群算法求解0-1背包问题时, 就是以式(1)作为目标函数, 寻找式(1)的最大值. 在求解中, 它们的对应关系为: 每只猴子的位置, 相当于式(1)的一组可行解; 猴群规模对应可行解的个数; 维数对应物品的数量. 实施步骤如下.

Step1. 参数值设定, 如种群规模M=20, 最大迭代次数 $nMax = 500$ 等.

Step2. 随机生成一个二进制向量 ${X_i} = \left( {{x_{i1}},} \right.$ $\left. {{x_{i2}}, \cdots ,{x_{ij}}, \cdots ,{x_{iD}}} \right)$ 作为初始位置(其中, 第i位为1表示第i件物件被选中, 若为0, 则表示第i件物件未被选中). 并计算所有猴子的目标函数值 $f({X_i})$ , 找出较优位置.

Step3. 执行爬过程, 计算, ${Y_i} = {X_i} + a \cdot sign\left( {{f_{ij}}'\left( {{X_i}} \right)} \right)$ , 产生新的二进制向量 ${Y_i} = \left( {{y_{i1}},{y_{i2}}, \cdots ,{y_{ij}}, \cdots ,{y_{iD}}} \right)$ , 若 $f({Y_i}) > f({X_i})$ , 则更新第i只猴子当前的位置, 即 ${X_i} = {Y_i}$ . 直到预定的执行次数Nc. 然后, 为了能够优先选取物品中单位体积价值较高的装入背包, 在这里设计一个诱导因子, 具体过程如下.

① 求出每件物品的单位体积的价值量, 第i件物品为:

${k_i} = \frac{{{p_i}}}{{{w_i}}}$

(7)

② 求出每件物品所占背包的比例, 第i件物品为:

${t_i} = \frac{{{w_i}}}{V}$

(8)

③ 据此设计诱导因子为:

${q_i} = {k_i} + \frac{\alpha }{{{t_i}}}$

(9)

${m_i} = \frac{{{q_i} - {q_{\min }}}}{{{q_{\max }} - {q_{\min }}}}$

(10)

其中, α为常量, 用来调整k_i和 $\frac{1}{{{t_i}}}$ 的关系.

④ 随机选取两个值c₁和c₂, 其中, ${c_1}\,,{c_2} \in \{ 1,2, \cdots ,D\} $ . 如果 ${m_{{c_1}}} > {m_{{c_2}}}$ 并且 ${y_{i{c_1}}} \ne {y_{i{c_2}}}$ , 则更新猴子的位置的变量为 $\left\{ {\begin{array}{*{20}{c}} {y{'_{i{c_1}}} = 1}\\ {y{'_{i{c_2}}} = 0} \end{array}} \right.$ , 否则更新为 $\left\{ {\begin{array}{*{20}{c}} {y{'_{i{c_2}}} = 1}\\ {y{'_{i{c_1}}} = 0} \end{array}} \right.$ . 计算 $f({Y_i})$ , 若 $f({Y_i}) > f({X_i})$ , 则更新第i只猴子的位置. 直到一定的诱导次数guide.

Step4. 执行望过程, 在视野范围 $\left[ {{x_{ij}} - b,{x_{ij}} + b} \right]$ 内生成新的二进制向量 ${Y_i} = \left( {{y_{i1}},{y_{i2}}, \cdots ,{y_{ij}}, \cdots ,{y_{iD}}} \right)$ , 并计算 $f({Y_i})$ , 若 $f({Y_i}) > f({X_i})$ , 则更新第i只猴子当前的位置, 即 ${X_i} = {Y_i}$ .

Step5. 执行跳过程, 计算, ${Y_i} = {x_{ij}} + \theta \left( {{p_j} - {x_{ij}}} \right)$ , 产生新的二进制向量 ${Y_i} = \left( {{y_{i1}},{y_{i2}}, \cdots ,{y_{ij}}, \cdots ,{y_{iD}}} \right)$ , 计算计算 $f({Y_i})$ , 若 $f({Y_i}) > f({X_i})$ , 则更新第i只猴子当前的位置, 即 ${X_i} = {Y_i}$ .

Step6. 重复Step3–Step5, 直到达到预定的最大迭代次数nMax, 算法结束, 输出最优个体和最优值.

4 实例仿真及其分析

为了验证所给算法的可行性, 下边给出两个算例, 它们的规模由小变大, 具体数据见以下相关算例数据. 比较差分进化算法(Differential Evolution Algorithm, DEA)^[8]、粒子群算法(Particle Swarm Optimization, PSO)^[9]、遗传算法(Genetic Algorithm, GA)^[10]、基本猴群算法(Basic Monkey Algorithm, BMA)^[11]以及本文所给诱导因子猴群算法(Inducing Factor Monkey Algorithm, IFMA)求解问题的效果.

算例1. 物品数量n=50, 背包容量V=1000, 物品价值R=[220, 208, 198, 192, 180, 180, 65, 162, 160, 158, 155, 130, 125, 122, 120, 118, 115, 110, 105, 101, 100, 100, 98, 96, 95, 90, 88, 82, 80, 77, 75, 73, 72, 70, 69, 66, 65, 63, 60, 58, 56, 50, 30, 20, 15, 10, 8, 5, 3, 1], 物品重量W=[80, 82, 85, 70, 72, 70, 66, 50, 55, 25, 50, 55, 40, 48, 50, 32, 22, 60, 30, 32, 40, 38, 35, 32, 25, 28, 30, 22, 50, 30, 45, 30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2, 1].

算例2. 物品数量n=100, 背包容量V=2010, 物品价值R=[68, 101, 125, 159, 65, 146, 28, 92, 143, 37, 5, 154, 183, 117, 96, 127, 139, 113, 100, 95, 12, 134, 65, 112, 69, 45, 158, 60, 142, 179, 36, 43, 107, 143, 49, 6, 130, 151, 102, 149, 24, 155, 41, 177, 109, 40, 124, 139, 83, 142, 116, 59, 131, 107, 187, 146, 73, 30, 174, 13, 91, 37, 168, 175, 53, 151, 125, 31, 192, 138, 88, 184, 110, 159, 189, 147, 31, 169, 192, 56, 160, 138, 84, 42, 151, 37, 21, 22, 200, 85, 135, 200, 139, 189, 68, 94, 84, 22, 18, 115], 物品重量W=[42, 35, 70, 79, 63, 6, 82, 62, 96, 28, 92, 3, 93, 22, 19, 48, 72, 70, 68, 36, 4, 23, 74, 42, 54, 48, 63, 38, 24, 30, 17, 91, 89, 41, 65, 47, 91, 71, 7, 94, 30, 85, 57, 67, 32, 45, 27, 38, 19, 30, 34, 40, 5, 78, 74, 22, 25, 71, 78, 98, 87, 62, 56, 56, 32, 51, 42, 67, 8, 8, 58, 54, 46, 10, 22, 23, 7, 14, 1, 63, 11, 25, 49, 96, 3, 92, 75, 97, 49, 69, 82, 54, 19, 1, 28, 29, 49, 8, 11, 14].

在仿真中, 用本文所给IFMA求解上述问题时, 算法的参数设定为: 种群规模M=20, 最大迭代次数nMax=500, 爬步长a=1, 爬的迭代次数N_c=20, 诱导次数guide=5, 视野长度b=0.5, 望的迭代次数N_w=3, 跳区间 $\left[ {c,d} \right] = \left[ { - 1,1} \right]$ , 常量α=1.2.

利用上述五种算法分别对算例1和算例2进行一次求解, 得到算例1的最优值和最优个体罗列在表1, 寻优过程如图1所示, 算例2的最优值和最优个体罗列在表2, 优化过程曲线如图2所示.

接着, 进一步利用这5种算法分别对算例1和算例2进行50次求解, 得出它们的最优值、最差值、平均值和方差分别罗列在如表3和表4.

通过以上仿真结果中的图1, 图2和表1至表4可以看出, 文中在BMA算法中的爬过程中引入诱导过程后, 很好地诱导了猴子向着指定的方向爬行, 从而避免了算法走弯路, 提高了算法的局部寻优能力和全局寻优能力. 而且随着物品数量的增大, 复杂度的增强, 相对于DEA, PSO, GA和BMA算法, 所给IFMA算法的求解精度仍然较高, 且方差较小. 从而说明所给IFMA算法具有较高的可行性和稳定性, 达到了预期的效果, 为求解0-1背包问题提供了新的途径.

5 结束语

在利用猴群算法求解0-1背包问题时, 在爬过程中, 引入诱导因子后, 可以诱导猴子向着指定的方向爬行, 从而避免绕路, 使得所给IFMA能够找到全局最优解. 通过仿真实验表明, 利用所给的IFMA求解0-1背包问题达到了预期的结果, 提高了求解精度.