﻿ 求解0-1背包问题的烟花算法
 计算机系统应用  2019, Vol. 28 Issue (2): 164-170 PDF

1. 西安理工大学 理学院, 西安 710054;
2. 西安交通大学 数学与统计学院, 西安 710049;
3. 西安理工大学 自动化与信息工程学院, 西安 710048;
4. 西安卫星测控中心 宇航动力学国家重点实验室, 西安 710043

Fireworks Algorithm for Solving 0-1 Knapsack Problems
XU Xiao-Ping1, PANG Run-Juan1, WANG Feng2, QIAN Fu-Cai3,4
1. Faculty of Sciences, Xi’an University of Technology, Xi’an 710054, China;
2. School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an 710049, China;
3. Faculty of Automation and Information Engineering, Xi’an University of Technology, Xi’an 710048, China;
4. State Key Laboratory of Astronautic Dynamics, Xi'an Satellite Control Center, Xi’an 710043, China
Foundation item: National Natural Science Foundation of China (61773016); Fundamental Research Program of Natural Science of Shaaxi Province (2014JM8325); Scientific Research Project of Education Bureau of Shaaxi Province (14JK1538); Science and Technology Innovation Program of Xi’an University of Technology (2016CX013)
Abstract: To overcome the shortcomings of the existing method in solving the 0-1 knapsack problems, an improved fireworks algorithm is proposed. After a mathematical model of the 0-1 knapsack problem is given, an improved fireworks algorithm is proposed to solve it. The main idea of the improved algorithm is as follows. The initialization of the basic fireworks algorithm is solved by using Kent chaotic map to make the initial position more uniform. The Sigmoid function is also introduced to get the gradual explosion radius to make the solution accurate and the search speed reach a certain balance. The resolving results of the typical test function and the 0-1 knapsack problem show that the improved fireworks algorithm has higher precision and more stable performance.
Key words: 0-1 knapsack problem     optimization     fireworks algorithm     chaotic mapping     gradual explosion radius

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

 ${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)

 ${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)

 $x_j^k = x_i^k + {h_k}$ (4)

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

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

1.2 改进的烟花算法

1.2.1 解初始化的改进

 ${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)

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

 图 1 Logistic映射分岔图

 图 2 Kent映射分岔图

1.2.2 爆炸半径的改进

 ${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)

 图 3 两个激励函数曲线图

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)

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

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 仿真实验

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}]}$

 图 4 对Sphere函数的优化曲线

 图 5 对Rosenbrock函数的优化曲线

3.2 0-1背包问题

 图 6 算例1寻优曲线图

 图 7 算例2寻优曲线图

4 结论

 [1] Merkle R, Hellman M. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 1978, 24(5): 525-530. DOI:10.1109/TIT.1978.1055927 [2] Caprara A, Pisinger D, Toth P. Exact solution of the quadratic knapsack problem. Informs Journal on Computing, 1999, 11(1): 125-139. [3] 李鸣山, 郑海虹. 0–1背包问题的多重分枝-限界算法. 武汉测绘科技大学学报, 1995, 20(1): 84-85. [4] 王梦竹. 求解0–1背包问题算法研究. 软件导刊, 2013, 12(8): 59-61. [5] 王乐, 王世卿, 张静乐. 基于Matlab的0–1背包问题的动态规划方法求解. 计算机技术与发展, 2006, 16(4): 88-89, 92. DOI:10.3969/j.issn.1673-629X.2006.04.031 [6] 荆源. 背包问题的差分进化算法. 才智, 2011, 12(7): 92-93. [7] 赵传信, 季一木. 粒子群优化算法在0/1背包问题的应用. 微机发展, 2005, 15(10): 23-25. DOI:10.3969/j.issn.1673-629X.2005.10.009 [8] 乐天. 遗传算法求解0/1背包问题的综述. 浙江海洋学院学报(自然科学版), 2013, 32(1): 71-74. DOI:10.3969/j.issn.1008-830X.2013.01.014 [9] Tan Y, Zhu YC. Fireworks algorithms for optimization. Proceeding of International Conference on Swarm Intelligence (ICSI2010). Beijing, China. 2010. 355–364. [10] Zhang SQ, Tan Y. A unified distance measure scheme for orientation coding in identification. 2013 International Conference on Information Science and Technology. Yangzhou, China. 2013. 979–985. [11] Imran AM, Kowsalya M. A new power system reconfiguration scheme for power loss minimization and voltage profile enhancement using fireworks algorithm. International Journal of Electrical Power & Energy Systems, 2014, 62: 312-322. [12] Janecek A, Tan Y. Swarm intelligence for non-negative matrix factorization. International Journal of Swarm Intelligence Research, 2011, 2(4): 12-34. DOI:10.4018/IJSIR [13] Zheng YJ, Song Q, Chen SY. Multiobjective fireworks optimization for variable-rate fertilization in oil crop production. Applied Soft Computing, 2013, 13(11): 4253-4263. DOI:10.1016/j.asoc.2013.07.004 [14] 曾德良, 邓志光, 陈彦桥. 改进烟花算法在火电厂负荷优化分配中的应用. 应用科学学报, 2018, 36(3): 542-552. DOI:10.3969/j.issn.0255-8297.2018.03.014 [15] 陈璇, 樊永生, 余红英, 等. 自适应烟花算法在重型装备装载中的应用. 科学技术与工程, 2016, 16(25): 296-300. DOI:10.3969/j.issn.1671-1815.2016.25.051 [16] 孙宪坤, 陈涛, 韩华, 等. 基于Kent混沌测量矩阵的压缩感知图像重构算法. 计算机应用与软件, 2017, 34(4): 213-220. DOI:10.3969/j.issn.1000-386x.2017.04.036 [17] 吴湘锋, 李志军, 向林波. 可编程双极性Sigmoid函数及其导数发生器. 电子测量与仪器学报, 2015, 29(8): 1137-1143. [18] 杜振鑫. 烟花算法中爆炸半径的改进研究. 计算机时代, 2013(1): 28-29. DOI:10.3969/j.issn.1006-8228.2013.01.011 [19] 尚亚菲, 刘雪英, 贾敏南. 引入惯性权重的烟花算法. 内蒙古工业大学学报, 2016, 35(3): 168-177. DOI:10.3969/j.issn.1001-5167.2016.03.002 [20] 王秋芬, 梁道雷. 一种求解0–1背包问题的启发式遗传算法. 计算机应用与软件, 2013, 30(2): 33-37, 57. DOI:10.3969/j.issn.1000-386x.2013.02.009