多维背包问题(Multidimensional knapsack problem, MKP)[1]是典型的NP-hard问题, 其求解目标是在满足多个资源限制的条件下, 从对象总体中选出能使总价值最大的一个对象子集. MKP具有较广泛的工程应用背景, 可以用来描述货物装载问题[2]、下料问题[3]以及资源配置问题[4].早期求解MKP的方法主要为精确算法, 如动态规划[5]和分支界定法[2]等, 主要针对小规模问题, 难以求解大规模MKP, 但这类算法能够得到问题的最优解.对于大规模MKP, 通常采用智能算法求解.目前, 这类算法包括遗传算法[6]、粒子群算法[7]、蚁群算法[8]、果蝇优化算法(Fruit fly optimization algorithm, FOA)[9]、差分进化算法[10]、和声搜索算法[11]、狼群算法[12]和分布估计算法[13]等, 这些智能算法在解决大规模MKP方面具有较好的表现.
FOA[14]是一种基于果蝇觅食行为的新型智能优化算法.不同于其他智能算法(如遗传算法、粒子群算法以及蚁群算法等), FOA的优化过程简单、参数少、易于实现, 同时也具备较强的搜索能力.目前, FOA已成功应用于电力负荷预测[15-16]、集合覆盖问题[17]、生产调度问题[18-19]、PID参数寻优[20]、图像分割[21]、项目调度问题[22]、传感器网络[23]、负荷频率控制[24]、复杂函数优化问题[25-26]、多工位装配序列规划问题[27]、物流仓储[28]和背包问题[29]等的求解.
由于MKP具有NP-hard和约束性强等特点, 无法确定最优解与当前解的差别.单级果蝇优化算法仅能在群体中心位置附近产生果蝇, 且解的质量很大程度上由步距决定[9, 30], 而二级FOA在一级果蝇的基础上再次进行搜索, 并将二级果蝇划分为用于开发的果蝇和用于探索的果蝇, 扩大了搜索范围, 可避免算法陷入局部最优.为此, 提出一种二级协作果蝇优化算法(Two-level cooperative fruit fly optimization algorithm, TCFOA), 设计一级果蝇和二级果蝇的产生策略, 提出果蝇间的交流协作策略, 设计一种基于全局性价比的修复机制.大量实验表明, TCFOA在求解MKP方面具有较强的搜索优势和能力.
1 多维背包问题MKP可描述为
(1) |
(2) |
其中: n为物品的数量; m为资源种类数; pi为第i个物品的价值; rij为第i个物品消耗第j个资源的量; bj为第j个资源的总量; ω为选中物品的总价值; xi表示一个二进制变量, xi=1表示第i个物品被选中, xi=0表示第i个物品没有被选中.多维背包问题的最优解即在多个有限资源的约束下, 从n个物品中选择一组物品, 使得物品的总价值ω最大.
2 二级协作果蝇优化算法 2.1 果蝇优化算法描述FOA是一种模拟果蝇觅食行为的群智能优化算法, 其主要依据果蝇敏锐的嗅觉系统对食物味道超强的感知能力.它首先模拟果蝇的嗅觉搜索过程, 使果蝇在解空间内搜索更优解, 在所有果蝇完成嗅觉搜索后, 再通过视觉搜索更新种群中心位置.
FOA的具体过程如下.
Step1:初始化种群中心位置.
Step2:嗅觉搜索, 在种群中心位置附近随机产生N个解.
Step3:计算每个解的适应度函数值.
Step4:视觉搜索, 寻找最优适应度函数值的解, 更新种群中心位置.
Step5:判断是否满足终止条件, 若是, 则输出最优解, 否则跳转至Step2.
2.2 求解MKP的TCFOA利用多种新策略构建TCFOA.下面描述TCFOA的具体步骤.
2.2.1 初始群体中心位置对于MKP, 通常采用二进制编码, 问题的解由n位的进制串[x1, x2, …, xn]表示, 其中xi=1表示第i个物品被选中, xi=0表示第i个物品没有被选中.
对于物品i, 定义全局性价比
(3) |
其中: ti表示第i个物品对于每种资源的占用比例之和与该物品价值之比, ti越大, 表明物品的全局性价比越高, 单位价值对于整体资源的占用率越低; 反之, ti越小, 表明物品单位价值对于整体资源的占用率越高.
初始群体中心位置的产生过程如下.
Step1:对所有物品计算全局性价比, 并按照其全局性价比降序排序.
Step2:从第1个物品开始依次确定每个物品能否被选中, 对于第i个物品, 如果加入该物品后所有资源限制条件均能满足, 则选择该物品; 否则, 忽略该物品.
Step3:如果所有物品均检查完毕, 则结束.
2.2.2 一级果蝇与二级果蝇一级果蝇由离散化后的FOA嗅觉搜索过程产生[9], 具体步骤如下.
Step1:利用初始种群中心位置按文献[9]的嗅觉搜索过程产生fly1个一级果蝇.
Step2:对于每个一级果蝇, 随机选择L个基因, 将选中的基因由0变成1或由1变成0后, 进行修复补偿.
现有文献[9, 31]大多采用单级果蝇, 并未考虑二级果蝇和两级结构.单级FOA只在一个群体中心位置附近进行搜索, 解的质量较大程度上取决于步距[9].由于二级果蝇在一级果蝇的基础上再次进行了搜索, 使得TCFOA能在群体中心位置及其周围多个不同位置附近搜索, 这样扩大了搜索范围, 提高了获得更高质量解的可能性; 同时为了平衡FOA的开发能力和探索能力, 避免算法陷入局部最优, 将二级果蝇划分为两类, 一类果蝇负责开发, 另一类果蝇实现探索.
针对每个一级果蝇, 设其二级果蝇总数为fly2, 其二级果蝇的搜索过程如下.
Step1:设置开发步距Lt, 探索步距Le, 开发探索比ratio.
Step2:确定开发果蝇数量flyt=fly2×ratio, 探索果蝇数量flye=fly2×(1-ratio).
Step3:以一级果蝇为中心位置, 按照文献[9]的方式, 产生flyt个二级开发果蝇和flye个二级探索果蝇.
Step4:对于每个二级开发果蝇和二级探索果蝇, 分别随机选择Lt个和Le个基因, 将选中的基因由1变成0或者由0变成1.
Step5:对所有二级果蝇进行修复补偿.其中Le, Lt=1, 2, …, n, ratio∈[0, 1].
2.2.3 交流策略为了有效利用除最好果蝇外的其他果蝇的信息, TCFOA引入多种交流策略, 包含一级果蝇交流和二级果蝇交流.首先进行二级果蝇交流, 挑选出总价值最高的二级果蝇作为新的一级果蝇后, 再进行一级果蝇交流.
针对每个一级果蝇的所有二级果蝇, 相应的交流过程如下.
Step1:设定交流概率P1, P1∈[0, 1].
Step2:对所有二级果蝇根据总价值降序排序, 选择排在前θ %的二级果蝇.
Step3:除最优二级果蝇外, 针对每个排名前θ %的二级果蝇, 比较该果蝇与最优二级果蝇的每个基因.若两个果蝇对应位置上的基因不相等, 则产生一个区间[0, 1]上的随机数ζ; 若ζ>P1, 且该果蝇的基因用最优二级果蝇的同一位置上的基因替代后依然能够满足资源限制条件, 则直接替代.
Step4:选取具有最高总价值的二级果蝇作为对应的一级果蝇.
其中100>θ>0, 最优二级果蝇为总价值最高的果蝇.
由于排名靠前的二级果蝇质量相对较高, 将这些果蝇与最优二级果蝇交流, 有助于获得更高质量的二级果蝇, 从而提高了一级果蝇质量, 故θ≤50, 具体取值需通过实验确定.通过大量实验, 本文设置θ=50.
在所有二级果蝇执行完交流策略后, 一级果蝇为相应二级果蝇中的最优解, 一级果蝇再进行交流, 以进一步提高解的质量.一级果蝇的交流策略与二级果蝇交流策略基本步骤大致相同, 不同的是, 所有的一级果蝇都向最优一级果蝇学习, 且交流概率为P2.
2.2.4 修复补偿策略FOA产生的解中, 部分解违背MKP的资源约束, 而有些解在增加部分物品的情况下依然能够满足所有资源约束条件.为了保证所有解满足资源约束条件的同时, 尽可能多地放入物品, 提高解的质量, 需对上述两类解进行修复补偿.
修复补偿的具体过程如下:首先, 针对违背资源约束条件的解, 对解中所有被选中的物品, 根据2.2.1节降序排序结果, 从全局性价比最低的物品开始, 逐个取出解中的物品, 直至所有资源约束条件满足; 其次, 对那些可以添加物品的解, 根据2.2.1节降序排序结果, 对所有未包含在解中的物品, 从全局性价比最高的物品开始, 逐个检测每个物品, 根据资源约束条件是否满足确定物品能否添加到解中.
上述修复策略与文献[32]的方法一样, 也参照了MKP本身的结构特点, 同时还不需要像伪效用比修复过程[9]那样, 求解新的对偶问题, 降低了算法的复杂度, 避免面对大规模问题时计算量的显著增大; 同时, 有些物品对于某个资源消耗量非常大, 但对其他资源消耗量非常小, 只考虑一个资源限制条件的修复方法无法全面地衡量物品的性价比, 而上述策略利用衡量一个物品对于所有资源约束条件的全局性价比进行修复补偿, 有效避免了上述情况的发生.
2.2.5 视觉搜索TCFOA中视觉搜索分为两个过程: 1)对于每个一级果蝇, 在其所有二级果蝇执行完嗅觉搜索和交流过程后, 将二级果蝇中的最优解作为新的一级果蝇; 2)在所有的一级果蝇间的交流过程执行完毕后, 寻找出总价值最高的一级果蝇作为下一次迭代的种群中心位置. TCFOA的视觉搜索过程如图 1所示, 其中一级果蝇表示其二级果蝇执行视觉搜索后产生的新的一级果蝇, 种群中心位置代表本次迭代产生的最优解, 同时作为下一次迭代的种群中心位置.
TCFOA的流程如图 2所示. TCFOA利用一级和二级果蝇在群体中心位置和多个其他位置进行搜索, 若以基因从0变成1或者从1变成0, 以及修复补偿时取物品或添加物品作为基本操作, 算法的时间复杂性为O(G×fly1×fly2×n), 其中G为最大迭代次数.
为了测试TCFOA的性能, 采用两组标准测试集对算法进行测试, 测试集1来自OR Library(http://people.brunel.ac.uk/~mastjjb/jeb/info.html), 命名规则为m-n-xx, 其中xx表示问题的编号.测试集2 (http://hces.bus.olemiss.edu/tools.html), 包含了11组中大规模的问题, 命名规则为Mk_gkxx. TCFOA算法在Visual C++6.0集成环境中编写, 运行环境为Windows10操作系统, Intel Core i5-5200U处理器(2.20 GHz).实验中每个问题均独立运行20次, 如非特殊说明, 每次测试允许的最大迭代次数为2 000.
3.1 参数设置TCFOA的参数共有8个, 分别为一级果蝇数量fly1、二级果蝇数量fly2、开发步距Lt、探索步距Le、开发探索比ratio、一级果蝇的搜索步距L和两个交流概率.相比前5个参数, 后3个参数的设置相对容易, 例如, 一级果蝇的搜索步距可以单独通过实验测试确定, 故本文仅针对前5个参数进行实验设计(Design of experiment, DOE)[33].
以Mk_gk06为例子, 5个参数均取4个水平值, 建立L16 (45)的正交实验表, 每种参数组合算法均独立运行20次, 将计算产生结果的平均价值(AVG)作为评价指标, 如表 1所示.
利用数据分析软件Minitab得到各个参数的排秩和主效应图, 排秩由高到低依次为开发步距Lt、探索步距Le、一级果蝇数量fly1、开发探索比ratio以及二级果蝇数量fly2的主效应如图 3所示.由分析可得, 开发步距Lt为最重要的参数, 一个合适的开发步距有助于增加算法的开发能力, 增大获得最优解的成功率.同时, 探索步距Lt的合理设定也能使算法的搜索能力有效提高, 减小陷入局部最优的概率.对于fly1, fly2和ratio, 设定一个相对适中的值即可.
根据DOE实验的结果, 对测试集1以及测试集2中的MK_gk01~MK_gk06, 设置一级果蝇数量为80, 二级果蝇数量为1 100, 开发步距为4, 探索步距为8, 开发探索比为0.6, 交流概率P1=P2=0.5, 一级果蝇搜索步距为4.对于MK_gk07~MK_gk11这几个规模较大的问题, 重新调整一级果蝇和二级果蝇的数量, 设置一级果蝇数量为50, 二级果蝇数量为500, 最大迭代次数调整为7 040, 其余参数保持不变, 这样所得到的结果优于利用上一组参数值所获得的解.
3.2 结果比较与分析为了验证TCFOA算法二级结构的有效性, 将其与文献[9]中的bFOA算法进行比较. bFOA为单级果蝇算法, 该算法利用概率向量生成解, 用差分进化公式更新概率向量, 并采用两种不同的修复策略对不同规模的问题进行修复. bFOA1和bFOA2的区别仅为所使用的修复策略不同, bFOA1更适用于中小规模问题, 而bFOA2在解决大规模问题时有更好的表现[9]. 表 2给出了TCFOA与bFOA1和bFOA2的比较结果, 分别统计了测试结果的最优偏差MIN.DEV, 平均偏差AVG.DEV和偏差方差VAR.DEV.
由表 2可以看出, 在最优解上, TCFOA与bFOA1持平, 但在平均值和方差上表现优于bFOA1, 且TCFOA在最优解、平均值和方差上均远优于bFOA2.相比于bFOA的单级结构, TCFOA的二级结构能够有效提升解的质量.
为了验证算法解决MKP的能力, 将其与3种算法进行比较.其中算法1是HEDA[13], 该算法利用概率向量产生解, 并采用伪效用比修复机制和基于问题本身结构特点的修复机制对解进行修复, 是较为经典的解决MKP的算法之一, 常用于算法的测试和比较[8-9].算法2为HHS[11], 该算法结合了和声搜索和果蝇优化算法, 同时引用了两种修复策略, 是最新提出的一种能够有效解决MKP的算法.算法3为AL-MKP, 该算法构建了低维MKP核问题[8], 并利用ACO求解.
表 3和表 4分别给出了TCFOA与HEDA以及TCF-OA和HHS的对比结果, 其中表 3采用BEST、AVG和STD三个指标分别描述最好解、平均解和标准差, 表 5给出了TCFOA与AL-MKP的测试比较结果, 同时给出了最优解的首达时间T.
由表 2和表 3可知, 对于测试集1中的被测问题, TCFOA均能够得到最优解, 同时能够保证平均解非常接近最优解, TCFOA解的质量和稳定性远高于HEDA和HHS.如表 5所示, 对于测试集2, 在最优解方面, TCFOA仅关于MK_gk03和MK_gk05的结果不如AL_MKP, 而关于其他问题的最好解均大于或等于AL_MKP的相应结果, 尤其是关于大规模问题MK_gk10和MK_gk11, TCFOA的优势更大.在平均值方面, TCFOA关于7个问题的结果占优, 在标准偏差方面, TCFOA关于7个问题的结果也优于AL_MKP, 这表明TCFOA有非常好的稳定性和鲁棒性; 在最优解的首达时间上, 对于中小规模问题, TCFOA不如AL_MKP, 但是对于大规模问题, TCFOA远远优于AL_MKP, 这表明TCFOA对于处理大规模问题具有较强的优势.总之, TCFOA能够有效解决MKP, 且具有较强的搜索优势.
4 结论为了解决MKP, 本文提出了一种新型二级协作果蝇优化算法, 设计了果蝇开发和探索平衡方法、一级果蝇和二级果蝇的产生机制、果蝇交流策略以及基于全局性价比的解的修复补偿机制, 并利用两级结构改善搜索结果.基于两个不同测试集的测试结果表明, TCFOA能够有效解决MKP, 对于不同规模的问题均有较高的优化质量.
进一步的工作是针对MKP构造动态分配果蝇开发和探索数量的机制, 进而得到更加有效的果蝇优化算法, 并研究FOA对于其他组合优化问题的应用, 如并行机调度问题等.
[1] |
Chu P C, Beasley J E. A genetic algorithm for the multidimensional knapsack problem[J]. J of Heuristics, 1998, 4(1): 63-86. DOI:10.1023/A:1009642405419 |
[2] |
Wei S. A branch and bound method for the multiconstraint zero-one knapsack problem[J]. J of the Operational Research Society, 1979, 30(4): 369-378. |
[3] |
Gilmore P C, Gomory R E. The theory and computation of knapsack functions[J]. Operations Research, 1966, 14(6): 1045-1074. DOI:10.1287/opre.14.6.1045 |
[4] |
Vanderster D C, Dimopoulos N J, Parra-Hernandez R, et al. Resource allocation on computational grids using a utility model and the knapsack problem[J]. Future Generation Computer Systems, 2009, 25(1): 35-50. DOI:10.1016/j.future.2008.07.006 |
[5] |
Toth P. Dynamic programming algorithms for the zero-one knapsack problem[J]. Computing, 1980, 25(1): 29-45. |
[6] |
Ünal A N, Kayakutlu G. A partheno-genetic algorithm for dynamic 0-1 multidimensional knapsack problem[J]. RAIRO-Operations Research, 2015, 50(1): 47-66. |
[7] |
Chih M, Lin C, Chern M, et al. Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem[J]. Applied Mathematical Modelling, 2014, 38(4): 1338-1350. DOI:10.1016/j.apm.2013.08.009 |
[8] |
任志刚, 赵松云, 黄姗姗, 等. 求解多维背包问题的蚁群-拉格朗日松弛混合优化算法[J]. 控制与决策, 2016, 31(7): 1178-1184. (Ren Z Z, Zhao S Y, Huang S S, et al. Ant colony-lagrangian relaxation optimization algorithm for solving multidimensional backpack problem[J]. Control and Decision, 2016, 31(7): 1178-1184.) |
[9] |
Wang L, Zheng X, Wang S. A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem[J]. Knowledge-Based Systems, 2013, 48(2): 17-23. |
[10] |
Tasgetiren M F, Pan Q K, Kizilay D, et al. A differential evolution algorithm with variable neighborhood search for multidimensional knapsack problem[M]. Sendai: Institute of Electrical and Electronics Engineers Inc, 2015: 2797-2804.
|
[11] |
Zhang B, Pan Q, Zhang X, et al. An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems[J]. Applied Soft Computing, 2015, 29(C): 288-297. |
[12] |
吴虎胜, 张凤鸣, 战仁军, 等. 利用改进的二进制狼群算法求解多维背包问题[J]. 系统工程与电子技术, 2015, 37(5): 1084-1091. (Wu H S, Zhang F M, Zhan R J, et al. Using the improved binary wolves algorithm to solve the multidimensional backpack problem[J]. Systems Engineering and Electronics, 2015, 37(5): 1084-1091.) |
[13] |
Wang L, Wang S, Xu Y. An effective hybrid EDA-based algorithm for solving multidimensional knapsack problem[J]. Expert Systems with Applications, 2012, 39(5): 5593-5599. DOI:10.1016/j.eswa.2011.11.058 |
[14] |
Dai H, Zhao G, Lu J, et al. Comment and improvement on "A new fruit fly optimization algorithm: Taking the financial distress model as an example"[J]. Knowledge-Based Systems, 2014, 59: 159-160. DOI:10.1016/j.knosys.2014.01.010 |
[15] |
Hu R, Wen S, Zeng Z, et al. A short-term power load forecasting model based on the generalized regression neural network with decreasing step fruit fly optimization algorithm[J]. Neurocomputing, 2017, 221(C): 24-31. |
[16] |
Li H Z, Guo S, Li C J, et al. A hybrid annual power load forecasting model based on generalized regression neural network with fruit fly optimization algorithm[J]. Knowledge-Based Systems, 2013, 37(2): 378-387. |
[17] |
Crawford B, Soto R, Torres-Rojas C, et al. A binary fruit fly optimization algorithm to solve the set covering problem[C]. Int Conf on Computational Science and Its Applications. Bainf: Springer, 2015: 411-420. https://link.springer.com/chapter/10.1007%2F978-3-319-21410-8_32
|
[18] |
郑晓龙, 王凌, 王圣尧. 求解置换流水线调度问题的混合离散果蝇算法[J]. 控制理论与应用, 2014, 13(2): 159-164. (Zheng X L, Wang L, Wang S R. A hybrid discrete drosophila algorithm for solving displacement pipeline scheduling problem[J]. Control Theory & Applications, 2014, 13(2): 159-164.) |
[19] |
Li J Q, Pan Q K, Mao K. A hybrid fruit fly optimization algorithm for the realistic hybrid flowshop rescheduling problem in steelmaking systems[J]. IEEE Trans on Automation Science & Engineering, 2016, 13(2): 932-949. |
[20] |
Song J, Pan H. PID control parameters optimize based on an immune fruit fly optimization algorithm[C]. Chinese Control and Decision Conf. Yinchuan, 2016: 6383-6388.
|
[21] |
孙立新, 张栩之, 邓先瑞, 等. 自适应果蝇算法优化模糊均值聚类算法图像分割[J]. 控制工程, 2016, 23(4): 494-499. (Sun L X, Zhang X Z, Deng X R, et al. Adaptive fruit fly algorithm optimization fuzzy mean clustering algorithm image segmentation[J]. Control Engineering, 2016, 23(4): 494-499.) |
[22] |
郑晓龙, 王凌. 随机资源约束项目调度问题基于序的果蝇算法[J]. 控制理论与应用, 2015, 32(4): 540-545. (Zheng X L, Wang L. Stochastic resource constrained project scheduling problem based on the order of fruit fly algorithm[J]. Control Theory & Applications, 2015, 32(4): 540-545.) |
[23] |
Dey A, Sarkar T, Ali S. Fruit fly algorithm based clustering protocol in wireless sensor networks[C]. Int Conf on Electrical and Computer Engineering. Dhaka: IEEE, 2017: 295-298. https://www.researchgate.net/publication/313807351_Fruit_Fly_algorithm_based_clustering_protocol_in_wireless_sensor_networks
|
[24] |
Huang C, Li Y. Linear active disturbance rejection control approach for load frequency control problem using diminishing step fruit fly algorithm[M]. Xiamen: Springer Singapore, 2016: 9-18.
|
[25] |
王林, 吕盛祥, 曾宇容. 果蝇优化算法研究综述[J]. 控制与决策, 2017, 32(7): 1153-1162. (Wang L, Lv S X, Zeng Y R. A review of fruit fly optimization algorithm[J]. Control and Decision, 2017, 32(7): 1153-1162.) |
[26] |
Pan Q K, Sang H Y, Duan J H, et al. An improved fruit fly optimization algorithm for continuous function optimization problems[J]. Knowledge-Based Systems, 2014, 62(5): 69-83. |
[27] |
袁文兵, 常亮, 徐周波, 等. 基于果蝇优化算法的多工位装配序列规划[J]. 计算机科学, 2017, 44(4): 246-251. (Yuan W B, Chang L, Xu Z B, et al. Multi-station assembly sequence planning based on drosophila optimization algorithm[J]. Computer Science, 2017, 44(4): 246-251.) |
[28] |
Pan W T, Zhu W Z, Ma F X, et al. Modified fruit fly optimization algorithm of logistics storage selection[J]. Int J of Advanced Manufacturing Technology, 2017, 93(6): 1-12. |
[29] |
Qian H, Zhang Q Y, Lei D M, et al. A cooperated fruit fly optimization algorithm for knapsack problem[C]. Chinese Automation Congress. Ji'nan: IEEE, 2018: 591-595.
|
[30] |
王凌, 郑晓龙. 果蝇优化算法研究进展[J]. 控制理论与应用, 2017, 34(5): 557-563. (Wang L, Zheng X L. Research progress of fruit fly optimization algorithm[J]. Control Theory & Applications, 2017, 34(5): 557-563.) |
[31] |
Wang L, Liu R, Liu S. An effective and efficient fruit fly optimization algorithm with level probability policy and its applications[J]. Knowledge-Based Systems, 2016, 97(C): 158-174. |
[32] |
王凌, 王圣尧, 方晨. 一种求解多维背包问题的混合分布估计算法[J]. 控制与决策, 2011, 26(8): 1121-1125. (Wang L, Wang S R, Fang C. Hybrid distribution estimation algorithm for solving multidimensional backpack problem[J]. Control and Decision, 2011, 26(8): 1121-1125.) |
[33] |
Montgomery D C. Design and analysis of experiments[J]. J of the American Statistical Association, 2000, 16(2): 241-242. |