背包问题又称子集合问题, 其最早由Merkel 和Hellman于1978年提出, 属于经典的NP-hard难解问题, 无论在理论研究方面还是实际应用方面均有很大的价值, 已被应用于下料问题, 预测控制, 资本投资和贷款组合优化决策问题等许多领域^[1]. 背包问题描述简单, 但实际求解过程复杂, 其求解方法可分为两大类: 传统求解和群智能算法. 早期传统方法如穷举法、分支界定法、回溯法和动态规划法等枚举了所有可能解^[2–5], 因此其解的数量相当大, 可能达到指数爆炸, 而群智能算法适于求解大规模问题, 为传统方法无法解决的优化问题提供了技术保障, 如差分进化算法^[6], 粒子群算法^[7]和遗传算法^[8]等. 但随着问题规模的增大, 逃逸局部极小值, 提高求解精度成为人们普遍关注的问题.

烟花算法是2010年由Tan和Zhu提出的一种新型群体智能算法^[9], 其属于随机搜索算法, 具有较强的并行性和鲁棒性, 近年来逐渐受到研究者的广泛关注. 目前, 烟花算法及其改进算法已被应用于多个领域, 例如, 文献[10]利用烟花算法在图像识别中进行了优化的距离度量; 文献[11]使用烟花算法进行了配电网优化方案设计; 文献[12]将烟花算法应用于非负矩阵分解问题; 文献[13]提出多目标烟花算法, 并用其进行了施肥比例的设计; 文献[14]提出动态变化半径的烟花算法, 并将其应用于负荷在线优化分配中; 文献[15]提出自适应烟花算法, 并应用于重型装备装载问题. 但是, 随着问题复杂性的增加, 该算法还会出现陷入局部极值的弊端. 因此, 对该算法进一步研究是很必要的, 并对解决实际问题具有重要的现实意义.

为了提高烟花算法的寻优性能, 本文将Kent混沌映射和Sigmoid函数引入到基本烟花算法中, 从而给出了一种改进烟花算法, 并将其应用到求解0-1背包问题. 通过实验仿真验证了所给算法是有效的.

1 烟花算法 1.1 基本烟花算法

烟花算法是由烟花的爆炸过程得到启示而提出的一种新型群体智能算法^[9]. 该算法在每一代都选择出性能较好的烟花作为父代, 来产生子代火花用以搜索最优解. 每一个烟花 ${x_i}$ , 其产生火花的数量 ${S_i}$ 以及爆炸半径 ${A_i}$ 分别定义如下:

${S_i} = Mii \times \frac{{{f_{\max }} - f({x_i}) + \varepsilon }}{{\displaystyle\sum\limits_{j = 1}^M {({f_{\max }} - f({x_j})) + \varepsilon } }}$

(1)

${A_i} = Aii \times \frac{{f({x_i}) - {f_{\min }} + \varepsilon }}{{\displaystyle\sum\limits_{j = 1}^M {(f({x_j}) - {f_{\min }}) + \varepsilon } }}$

(2)

其中, $Mii$ 和 $Aii$ 是常数, 分别用来调整产生的爆炸火花和爆炸半径大小; M为种群规模; ${f_{\max }}$ 和 ${f_{\min }}$ 分别表示目标函数的最大值和最小值; $\varepsilon $ 是用以避免结果为零的极小量.

为了使产生的火花粒子不过多或过少, 需对 ${S_i}$ 的大小范围进行如下限制:

${S_i} = \left\{ \begin{gathered} {S_{\min }},\quad \;{S_i} < {S_{\min }} \\ {S_{\max }},\quad {S_i} > {S_{\max }} \\ \;{S_i},\quad \;\;{\rm{otherwise}} \\ \end{gathered} \right.$

(3)

假设搜索空间的维数为D, 随机选择烟花 ${x_i}$ 的 $z(z < D)$ 个维度, 对每一个维度的 $x_i^k$ 进行位置偏移, 构成 $x_j^k(1 \leqslant j \leqslant {S_i},1 \leqslant k \leqslant z)$ . 生成火花 $x_j^k$ 的方法有两种, 大部分火花是通过对 $x_i^k$ 加上一个位移 ${h_k} = {A_i} \cdot rand( - 1,1)$ 而得到的, 即:

$x_j^k = x_i^k + {h_k}$

(4)

为了提高种群的多样性, 少数的烟花将需进行高斯变异, 即将一个高斯偏移乘到 $x_i^k$ 上, 即:

$x_j^k = x_i^k \cdot Gaussian(1,1)$

(5)

在上述过程中, 产生的火花可能会超出可行域的边界范围, 从而当火花 ${x_i}$ 在 $k$ 维上超出边界时, 可由(6)式映射到其它位置.

$x_j^k = x_{\min }^k + \left| {x_j^k} \right|od (x_{\max }^k - x_{\min }^k)$

(6)

在每一次迭代中, 所有的个体(包括烟花, 爆炸火花和高斯变异火花)中的最优个体, 总是被选为烟花进入下一代, 并根据轮盘赌的方法选择其他M–1个个体作为下一代迭代计算的烟花.

1.2 改进的烟花算法

在基本烟花算法中, 初始化种群由随机函数产生, 而利用随机初始化方法给出的一组解可能会出现与最优值较为接近, 也可能相差甚远, 即给出的解往往无法覆盖整个解空间, 解得不到充分挖掘, 从而致使算法全局搜索能力较弱. 另外, 基本烟花算法的爆炸半径采用式(2)进行计算, 使得对于最优烟花带入式(2)后得到的火花半径趋于0, 即原样复制了最优烟花, 没有进行任何搜索, 从而降低了搜索速度, 降低了在其周围找到最优解的可能性. 针对基本烟花算法自身所存在的这些缺陷, 本文在算法初始化过程中, 采用具有遍历性和随机性的Kent混沌映射来替代随机初始化过程, 同时引入Sigmoid函数对烟花半径进行改进, 使得爆炸半径能及时地对搜索方向进行引导和限制. 改进方法具体如下:

1.2.1 解初始化的改进

种群初始解的质量在一定程度上影响最终解的质量, 初始解在解空间分布越均匀, 覆盖面就越广泛, 从而在最优解邻域搜索的可能性就越大. 而混沌的无规则性可使初始解在解空间分布更加均匀, 所以, 这里采用混沌初始化代替原来的随机初始化过程, 使得初始化过程可以搜索到整个解空间, 从而可提高最优解被搜索到的概率. 目前, 在改进群智能算法时, 一般引入的是Logistic映射策略进行混沌初始化, 但是, 该映射的混沌特性并不十分优良, 其分岔图如图1所示. 而Kent映射克服了Logistic映射的缺点^[16], 图2给出了Kent映射的分岔图.

从图1可看出, 当 $3.42 < \mu \le 3.52$ 时, 发生了第二周期分岔, 从周期二轨道变成周期四轨道, 当 $3.52 < \mu \le 3.58$ 时, 发生了第三周期分岔, 从周期四轨道变成周期八轨道, 而当 $3.58 < \mu \le 4$ 时, 轨道周期达到无穷长, 系统才开始工作于混沌状态. 而从图2的Kent映射分岔图中可以看出, Kent映射始终处于混沌状态. 从而可看出Kent映射的混沌特性更明显.

另外, Lyapunov指数通常是衡量系统动力学特性的一个重要定量指标, 它表征了系统在相空间中相邻轨道间收敛或发散的平均指数率, 指数越大, 说明混沌特性越明显, 混沌程度越高, 其分布越均匀^[16]. Kent映射的Lyapunov指数是0.696, 而Logistic映射的Lyapunov指数是0.691, 因此, 这里采用Kent混沌映射对烟花粒子进行初始化, 具体由如下函数来产生:

${h_{j + 1}} = \left\{ \begin{gathered} \frac{{{h_j}}}{b},\quad \,\,\;\,0 < {h_j} \leqslant b \\ \frac{{1 - {h_j}}}{{1 - b}},\;\;b < {h_j} \leqslant 1 \\ \end{gathered} \right.$

(7)

其中, ${h_j}$ 为混沌变量, ${h_j} \in [0,1]$ , $j = 1,2, \cdots ,n$ ; $b$ 为参数, 当 $b = 0.4$ 时, ${h_j}$ 为 $(0,1)$ 上的均匀分布,且 ${x_{ij}}$ 可由下式产生.

${x_{ij}} = {x_{\min }} + {h_j} \cdot ({x_{\max }} - {x_{\min }})$

(8)

其中, ${x_{ij}}$ 为第 $i$ 个烟花在第 $j$ 维的具体位置; $[{x_{\min }},{x_{\max }}]$ 为 ${x_{ij}}$ 的取值范围. 因为 ${h_j}$ 为 $(0,1)$ 上的均匀分布, 所以由(8)式可以使 ${x_{ij}}$ 广泛分布于区间 $[{x_{\min }},{x_{\max }}]$ 中, 有利于烟花进行下一步搜索, 这在很大程度上避免了算法陷入局部最优值, 从而节省了搜索时间, 能很快找到最优解, 因此有利于提高整个算法的求解精度, 加快了算法收敛速度.

1.2.2 爆炸半径的改进

为了使得算法爆炸半径能及时地对搜索方向进行引导和限制, 那么就需要算法在迭代初期, 爆炸半径取值较大来加强全局探索能力; 在迭代后期, 爆炸半径取值较小来加强局部搜索能力, 这样就可以使得算法求解精度与搜索速度达到一种平衡来改进其寻优性能.

在人工神经网络中, 神经元激活函数经常采用Sigmoid函数和Tanh函数来过渡线性与非线性, 其往往都可以作为激励函数^[17], 它们的曲线图如图3所示. 但是, 从图中可以看出, Sigmoid函数在线性与非线性行为之间表现出更好的平衡性, 过渡更加平滑. 并且由参考文献[17]可知, Sigmoid函数连续、可导、有界、光滑和严格单调, 可将变量映射到 $[0,1]$ 范围内, 并且在区间内逐渐变小. 因此, 在这里引入Sigmoid函数可得到平滑渐变的爆炸半径, 从而在迭代初期, 爆炸半径取值较大, 算法的全局探索能力强, 同时有利于烟花弹较快集中在全局最优点附近; 在迭代后期, 爆炸半径取值较小, 使得算法在最优点附近能进行充分的局部搜索, 提高求解的精度, 这样就可以使得求解精度与搜索速度达到一种平衡, 并且在迭代前后期平滑过渡, 而不显得突兀. 这里构造的递减因子具体如下.

${a_{k + 1}} = \frac{1}{{1 + {e^{2\ln 100 \cdot \frac{k}{M} - \ln 1000}}}} \cdot \frac{{M - k + 1}}{M} \cdot a$

(9)

其中, $k$ 为当前的迭代次数, M为最大的迭代次数, $a$ 为调节系数.

2 利用改进的烟花算法求解0-1背包问题 2.1 0-1背包问题

0-1背包问题可描述为^[1]: 给定一个背包和 $m$ 种不同的物品, 其中背包的容积、物品的体积和价值一定, 一种物品只能有装入或者不装入背包中两种状态, 要求解一种物品装入方案使装入背包中的物品总价值最大. 假设背包容积为 $C$ , 有 $m$ 个物品待选择, 其中第 $i$ 个物品的体积为 ${w_i}$ , 价值为 ${p_i}$ , ${x_i} = 1$ 为物品被装入背包中, ${x_i} = 0$ 为物品不装入背包中, 其中 $i = 1,2, \cdots ,m$ . 这样问题就可表述为:

$\begin{array}{l} \max f(x) = \displaystyle\sum\limits_{i = 1}^m {{p_i}{x_i}} \\ {\rm{s.t.}}\left\{ \begin{array}{l} \displaystyle\sum\limits_{i = 1}^m {{w_i}{x_i} \le C} \\ {x_i} = \left\{ \begin{array}{l} 1,\text{物品}i\text{装入背包}\\ 0,\text{物品}i\text{不装入背包} \end{array} \right. \end{array} \right. \end{array}$

(10)

现需考虑在不超过背包容积 $C$ 的前提下, 怎样使装入背包中的物品总价值最大, 那么对该问题的求解就可以采用下面的烟花算法.

2.2 建立算法与问题的对应关系

要利用改进的烟花算法求解0-1背包问题, 首先要明确算法与0-1背包问题间的相互对应关系, 其具体如表1所示.

2.3 求解步骤

Step 1. 解的表示和初始化: 设种群规模为 $M$ , 对初始烟花利用(7)和(8)式进行混沌搜索, 对于第 ${X_i} =$ $({x_{i1}},{x_{i2}}, \cdots ,{x_{iD}})$ 个烟花, 其当前的位置向量为 ${X_i} = \left({x_{i1}},\right.$ $\left.{x_{i2}}, \cdots ,{x_{iD}}\right)$ ,其中 $i = 1,2, \cdots ,M$ , $j = 1,2, \cdots ,D$ , D为所求问题的物品数量.

Step 2. 迭代过程: 初始 $iter = 1$ , 计算烟花粒子的适应度, 即背包内物品的价值, 通过函数限制背包内物体的总体积.

Step 3. 编码: 采用二进制编码, 当背包内物体的体积超过限制时, 将其适应度设置为0, 当烟花粒子的适应度大于其最佳适应度时, 用其替代原来的粒子适应度, 并记录下来, 同样当存在粒子的最佳适应度大于种群最佳适应度时, 用其替代原来种群的最佳适应度.

Step 4. 爆炸火花的产生: 利用式(9)计算烟花半径, 利用式(4)产生爆炸火花数, 由式(6)进行越界检查, 对超出边界的火花重新映射到边界内.

Step 5. 高斯变异火花的产生: 由式(5)产生高斯变异火花, 利用式(6)进行越界检查, 同样对超出边界的火花重新映射到边界内.

Step 6. 离散化函数值: 由于烟花位置只有0, 1两种状态, 以0.5为分界点对函数值进行离散化, 其中小于0.5的粒子取为0, 大于0.5的粒子取为1.

Step 7. 子代选择: 将种群中烟花个体的最优个体选为烟花进入下一代, 并根据轮盘赌的方法选择其它 $M - 1$ 个个体作为下一代的父体烟花, 返回Step 2, $iter = $ $iter + 1$ , 直至背包内的物品体积达到背包限制, 或所选物品价值达到某一可接受值, 算法结束, 输出最优函数值.

3 仿真实验

为了说明所给的IFWA的可行性, 以下对典型测试函数和0-1背包问题进行求解, 并与基本烟花算法(BFWA)^[9], 文献[18]给出的改进爆炸半径的烟花算法(RFWA), 文献[19]给出的加入惯性权重的烟花算法(WFWA), 差分进化算法(DE)^[6], 粒子群算法(PSO)^[7]和遗传算法(GA)^[8]的求解结果进行比较. 在仿真实验中, IFWA的参数设置是依据文献[9]及多次试验所获得的经验值来确定的, 其中种群大小 $M = 20$ , 总的迭代次数 $N = 1000$ , 半径系数 $Aii = 1500$ , 火花系数 $Mii = 300$ , 高斯变异火花数 $Ma = {M/3}$ , 搜索空间维数 $D = 20$ , 爆炸火花最大值 ${S_{i\max }} = 27$ , 最小值 ${S_{i\min }} = 1$ , 极小量 $\varepsilon = {10^{ - 250}}$ , 调节系数 $a = 10$ ; 对比算法参数值设置见文献[6–9,18,19].

3.1 典型测试函数

(1) Sphere函数: $f(x) = \displaystyle\sum\limits_{i = 1}^N {x_i^2} $

(2) Rosenbrock函数:

$f(x) = \sum\limits_{i = 1}^N {[100 \cdot {{({x_{i + 1}} - x_i^2)}^2} + {{({x_i} - 1)}^2}]} $

这两个函数的理论最小值均为0. 现对两函数均在20维的情况下, 利用IFWA, RFWA^[18], WFWA^[19], BFWA^[9], DE^[6], PSO^[7]和GA^[8]分别进行一次求解, 得到寻优过程曲线如图4和图5所示.

在仿真过程中发现, 正如前面理论分析所言, 本文所提IFWA的优化性能明显改善. 这是由于IFWA用Kent混沌映射来替代随机初始化过程后, 使得初始解分布更加均匀. 同时, 引入Sigmoid函数得到平滑渐变的爆炸半径后, 使得算法的求解精度与搜索速度达到一种平衡. 从图4和图5均可以看出, IFWA的寻优性能远远强于RFWA, WFWA, BFWA, DE, PSO和GA. 并且从图4可以看出, 对Sphere函数而言, 虽然RFWA和WFWA在求解精度上有了一定的提高, 可是, 两个算法在迭代920次时还未稳定, 而IFWA不仅求解精度大幅度改善, 而且IFWA在不到50次迭代时就已经收敛, 搜索速度较快. 从图5可以看出, 对Rosenbrock函数而言, RFWA和WFWA收敛速度较慢, 在迭代次数接近980次时又出现不稳定现象, 而IFWA在迭代不到100次时已收敛, 收敛速度较快, 求解精度也大幅度提高.

进一步利用IFWA, RFWA^[18], WFWA^[19], BFWA^[9], DE^[6], PSO^[7]和GA^[8]分别进行50次求解, 将得到的最优解, 平均解和方差分别罗列在表2中. 从表2可看出, 相对于DE, PSO, GA, BFWA, RFWA和WFWA, 所提IFWA的混沌初始化改进有效地搜索到了最优解, 且对于爆炸半径的改进也避免了最优解的浪费, 故在50次求解中利用IFWA得到的最优解和平均解都较小, 更接近于理论最优值, 并且方差较小, 即具有更强的稳定性. 对于文献[18]所提改进半径烟花算法和文献[19]引入惯性权重的烟花算法的最优解虽然优于基本烟花算法, 但与本文所提IFWA仍有较大差距.

3.2 0-1背包问题

这里选用文献[20]中所给的0-1背包问题, 它们的规模由小到大, 具体数据见算例1和算例2.

算例1: 物品数量m=50, 背包容量C=1000, 物品价值p=[220, 208, 195, 192, 180, 180, 165, 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, 25, 30, 45, 30, 60, 50, 20, 65, 20, 25, 30, 10, 20, 25, 15, 10, 10, 10, 4, 4, 2, 1].

算例2: 物品数量m=100, 背包容量C=2010, 物品价值p=[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].

利用IFWA, RFWA^[18], WFWA^[19], BFWA^[9], DE^[6], PSO^[7]和GA^[8]算法分别对上述两个算例进行一次求解,得到相应寻优曲线如图6和图7所示.

在仿真过程中发现, 所提IFWA在对初始解进行了混沌初始化和爆炸半径进行了渐变改进后, 算法的局部搜索能力与全局搜索能力达到了平衡, 能迅速跳出局部最优, 加快了算法的求解精度与收敛速度. 从图6和图7均可以看出, IFWA的寻优能力均明显优于RFWA, WFWA, BFWA, DE, PSO和GA. 并且从图6和图7可以看出, 当算例1的物品数量为50和例2的物品数量为100时, IFWA均在迭代20次左右时就已经收敛, 收敛速度较快, 求解精度得到明显提高.

进一步利用IFWA, RFWA^[18], WFWA^[19], BFWA^[9], DE^[6], PSO^[7]和GA^[8]分别对两个算例进行50次求解,得到的最优解, 最差解, 平均解和方差如表3所示.从表3可看出, 所给IFWA的寻优结果相对于其它所提的算法明显更优, 且方差较小, 说明算法具有较好的稳定性. 尤其随着物品数量的增大, 问题复杂度的加大, 相对于其它所提到的对比优化算法, 所给IFWA仍然具有较高的求解精度和稳定性, 说明改进算法是有效的.

综上, 通过以上对测试函数和0-1背包问题的仿真结果可看出, 相对于BFWA^[9], RFWA^[18], WFWA^[19], DE^[6], PSO^[7]和GA^[8], 所给的IFWA由于采用了混沌初始化和渐变的爆炸半径, 因此在搜索能力上明显更优, 能够更好地搜索到全局最优解, 且稳定性较好. 从而说明所给IFWA算法是有效的, 达到了预期的目的, 为求解0-1背包问题提供了新的途径.

4 结论

为了克服基本烟花算法的缺点, 利用Kent混沌映射对算法的解初始化进行了改进, 同时引入Sigmoid函数得到渐变的烟花爆炸半径后, 使得得到的改进烟花算法的求解精度与搜索速度达到某种平衡, 提高了算法的寻优性能. 通过仿真实验验证了所给改进烟花算法是有效的.