基于混合贪婪烟花算法求解0-1背包问题_李秋月.pdf

基于混合贪婪烟花算法求解 0-1 背包问题*李秋月（中国矿业大学（北京），北京100083）Solving 0-1 Knapsack Problem Based on Hybrid Greedy Fireworks Algorithm摘要：针对组合优化中的经典背包问题，为提高基本烟花算法寻找最优解的局部搜索能力和全局搜索能力，将基本烟花算法、贪婪优化策略和模拟退火算法结合，提出一种改进烟花算法。为保证初始种群的多样性，提出采用Tent映射初始化种群；引入贪心修复算子和贪心优化算子修正中间解；同时引入模拟退火机制使得较差解能有一定概率被接受提高算法跳出局部最优的能力。通过对典型测试函数的求解，发现改进烟花算法能精确求解出Griewank函数的理论最优解；对比基本烟花算法、模拟退火算法和粒子群算法，改进烟花算法能以更高精度寻找Sphere函数最优值。通过对4组不同维度的背包问题的求解，发现改进烟花算法能对于大多数测试数据以较大的概率命中最优解。实验结果说明，改进烟花算法具有较高的求解精度和较快的求解速度，能有效求解0-1背包问题。关键词：0-1背包问题；烟花算法；混沌映射；模拟退火算法Abstract:Aiming at the classical knapsack problem in combinatorial optimization,in order to improve the local searchability and global search ability of the basic fireworks algorithm,an improved fireworks algorithm is proposed by combiningthe basic fireworks algorithm,greedy optimization strategy and simulated annealing algorithm.In order to ensure the diversi-ty of the initial population,the Tent mapping is proposed to initialize the population.Greedy repair operator and greedy op-timization operator are introduced to correct the intermediate solution.Compared with the basic fireworks algorithm,simulat-ed annealing algorithm and particle swarm optimization algorithm,the improved fireworks algorithm can find the optimal val-ue of Sphere function with higher accuracy.By solving four groups of knapsack problems with different dimensions,it isfound that the improved fireworks algorithm can hit the optimal solution with large probability for most test data.Keywords:0-1 knapsack problem,fireworks algorithm,chaos mapping,simulated annealing algorithm*中国矿业大学（北京）大学生创业创新项目（202107004）背包问题（Knapsack problem）是一个经典的NP难问题1，其最终目的是包装最有价值的物品而不超载。背包问题出现在各种领域的实际决策过程中，例如选择投资和投资组合2、选择资产支持资产证券化3、生成密钥和其他背包密码系统。因此研究背包问题的求解具有极大的现实意义。求解背包问题的方法主要分为传统方法和智能算法。传统方法包括动态规划法4、回溯法5和分支定界法6等。对于较低维的背包问题，传统方法能以较大的精度寻找最优解，但对于高维的背包问题，传统方法求解复杂度较高。而智能算法是一种非精确求解算法，适用于求解大规模问题，如模拟退火算法7、遗传算法8、粒子群算法9、烟花算法10等。为了均衡背包问题的求解时间和求解精度，人们将目光投向混合智能优化算法。文献11利用混合遗传算法求解背包问题，并引入了贪婪修复算子（OP-R）和贪婪优化算子（OP-O）；文献12结合粒子群算法和贪心策略，提出混合粒子群改进算法，通过实验验证该算法在较高规模问题上有较好的寻优能力和收敛性；文献13提出了贪心萤火虫算法，改善了基本萤火虫算法的全局搜索能力提高后期搜索精度；文献14将粒子群算法与模拟退火算法结合，产生了更好的局部最优解和全局最优解。本文将Fireworks Algorithm与Simulated Annealing Al-gorithm结合，提出Fireworks Algorithm-Simulated AnnealingAlgorithm（FWA-SA）。在烟花算法框架内加入模拟退火操作，提高算法跳出局部最优的能力。不同规模实验对比表明，FWA-SA在一定程度上能有效避免算法早熟，具有较强的全局寻优能力。1问题描述0-1背包问题可描述为：在背包容量有限的情况下，基于每个物品的价值和重量制定最优装包方案，使得背包内物品价值尽量大同时不超过背包体积重量限制。每个物品i重量为ci，价值为pi，背包容量为C。物品有两种状态，装入背包和不装入背包。装载时要保持背包内物品总重量不超过背包容量，同时使背包内物品总价值尽可能大。2混合贪婪烟花算法求解0-1背包问题2.1解的表示和初始化0-1背包问题是一种离散组合优化问题，其解可用二进制编码表示。烟花算法受夜空中烟花爆炸启发而提出，每一个烟花代表可行域内一个初始解。基本烟花算法初始解由随机函数产生，可能会出现离最优解充分近或者充分远的情况，会使算法全局搜索能力下降。混沌序列具有随机性、遍历性和初值敏感性，能有效弥补随机初始化方法的缺陷。文献15提出Tent映射在遍历性、均匀性和迭代速度方面比Logistis混沌映射有更大优势。本文采用改进后的Tent映射生成初始解，以便算法初期在空间内进行更好的搜索。2.2 FWA-SA算法基于以上分析，烟花算法在迭代前期群体更新较快，局部搜索能力较差；在烟花算法和模拟退火算法的基础上，提出本文的混合算法FWA-SA，结合对0-1背包问题的分析，算法以烟花算法为框架，嵌入模拟退火操作，并引入贪心修复算子对选入背包的物品进行修复。FWA-SA算法的具体流程如图1所示。2.2.1爆炸数目和爆炸半径烟花算法以烟花爆炸产生子代火花表示在可行域内进行搜索，每一个烟花xi，其产生的火花数目Si和爆炸半径Ai分别定义如下：Si=Sfmax-f（xi）+Ni=1（fmax-f（xi）+（1）基于混合贪婪烟花算法求解0-1背包问题94工业控制计算机2023年第36卷第1期图1FWA-SA算法流程Ai=Af（xi）-fmin+Ni=1（f（xi）-fmin）+（2）为了保证产生的火花数量适宜，需要对Si的大小进行如下限制：Si=round（aEn），SiaEnround（bEn），SibEnround（Si），else（3）假设搜索空间的纬度为D，对第k个纬度的第i个烟花位置进行位移操作，构成火花的公式如下：xki=xki+dk（4）2.2.2高斯变异与映射规则为提高种群多样性，选取部分烟花进行高斯变异，变异公式如下：xki=xkig（5）为了保证产生火花都在可行域范围内，需要对可能跳出可行域火花采用特定规则将其拉回可行域内，其公式如下：xki=xkmin+xkimod（xkmax-xkmin）（6）2.2.3模拟退火操作模拟退火算法的思想来源于固体退火原理。根据Mon-tepolis准则接受比当前解好的解和以一定概率接受比当前解差的解7。引入模拟退火机制使得迭代初期能有较大的概率跳出当前最优解，迭代后期能更好地收敛到最优区域，提高了烟花算法的全局搜索能力。3仿真实验3.1算法参数设计为 验 证FWA-SA算 法 的 有 效 性，选 取 基 本 烟 花 算 法（FWA）、模拟退火算法（SA）和粒子群算法（PSO）进行对比。算法参数设置如表1所示：3.2测试结果分析基于以上算法参数设置和函数选择，采用Matlab2020b编辑 算 法 和 运 行 仿 真。CPU：Intel Core i5-7200U CPU 2.50 GHz 2.70 GHz，操作系统Windows 10专业版，内存12 GB。为减少实验误差，每个算法在每个测试函数上独立运行10次，优化寻优结果如表2所示：表2测试函数求解比较由表2可以看出，FWA-SA算法在测试函数寻优的最优值和平均值最接近理论最优值且寻优方差最小，故FWA-SA算法比FWA算法、SA算法和PSO算法稳定性好。从图2和图3可以看出，FWA-SA的寻优性强于FWA、SA和PSO。对于Sphere函数，FWA算法相比于SA、PSO有更好的收敛值，而FWA-SA算法在15次左右就已收敛，收敛速度较快。由图2及表2可知，FWA-SA算法可以精确收敛到Griewank函数的理论最优值，并且收敛速度较快，相较于FWA、SA和PSO求解精度大大提高。图2Griewank函数求解过程3.3 0-1背包问题选用和文献14-16中所给的部分数据，分别执行10次独立重复试验，实验结果如表3所示：由表3可以看出，3组数据均能找到最优值，第4组数据找到的最优解优于相较于BFWA、WFWA、RFWA，最差解亦优于BFWA、WFWA、RFWA16。这说明：FWA-SA算法具有较强的有效性和较高的稳定性，对于0-1背包问题有较强的寻优能力。表1算法参数设置图3Sphere函数求解过程表30-1背包问题求解结果95（上接第93页）本文提出的方法在红外掩埋目标检测的任务上比传统的语义分割方法获得了更好的效果，但仍存在不小的提升空间，值得继续研究。参考文献1高仕博，程咏梅，赵永强，等.基于多时相红外图像探测浅层地下目标J.红外与毫米波学报，2009，28（1）：25-302LONG J,SHELHAMER E,DARRELL T.Fully convolutionalnetworks for semantic segmentation C/Proceedings of theIEEE conference on computer vision and pattern recognition,2015:3431-34403VASWANI A,SHAZEER N,PARMAR N,et al.Attention is allyou need C Proceedings of the 31st International Confer-ence on Neural Information Processing Systems,2017,6000-60104KHAN S,NASEER M,HAYAT M,et al.Transformers in Vision:A SurveyJ.ACM Computing Survegs,2022,54(10):1-415HE K,ZHANG X,REN S,et al.Deep residual learning forimage recognitionC/Proceedings of the IEEE conference oncomputer vision and pattern recognition,2016:770-7786ZHENG S,LU J,ZHAO H,et al.Rethinking semantic seg-m