基于混合贪婪烟花算法求解0-1背包问题*李秋月（中国矿业大学（北京），北京100083）Solving0-1KnapsackProblemBasedonHybridGreedyFireworksAlgorithm摘要：针对组合优化中的经典背包问题，为提高基本烟花算法寻找最优解的局部搜索能力和全局搜索能力，将基本烟花算法、贪婪优化策略和模拟退火算法结合，提出一种改进烟花算法。为保证初始种群的多样性，提出采用Tent映射初始化种群；引入贪心修复算子和贪心优化算子修正中间解；同时引入模拟退火机制使得较差解能有一定概率被接受提高算法跳出局部最优的能力。通过对典型测试函数的求解，发现改进烟花算法能精确求解出Griewank函数的理论最优解；对比基本烟花算法、模拟退火算法和粒子群算法，改进烟花算法能以更高精度寻找Sphere函数最优值。通过对4组不同维度的背包问题的求解，发现改进烟花算法能对于大多数测试数据以较大的概率命中最优解。实验结果说明，改进烟花算法具有较高的求解精度和较快的求解速度，能有效求解0-1背包问题。关键词：0-1背包问题；烟花算法；混沌映射；模拟退火算法Abstract:Aimingattheclassicalknapsackproblemincombinatorialoptimization,inordertoimprovethelocalsearchabilityandglobalsearchabilityofthebasicfireworksalgorithm,animprovedfireworksalgorithmisproposedbycombiningthebasicfireworksalgorithm,greedyoptimizationstrategyandsimulatedannealingalgorithm.Inordertoensurethediversi-tyoftheinitialpopulation,theTentmappingisproposedtoinitializethepopulation.Greedyrepairoperatorandgreedyop-timizationoperatorareintroducedtocorrecttheintermediatesolution.Comparedwiththebasicfireworksalgorithm,simulat-edannealingalgorithmandparticleswarmoptimizationalgorithm,theimprovedfireworksalgorithmcanfindtheoptimalval-ueofSpherefunctionwithhigheraccuracy.Bysolvingfourgroupsofknapsackproblemswithdifferentdimensions,itisfoundthattheimprovedfireworksalgorithmcanhittheoptimalsolutionwithlargeprobabilityformosttestdata.Keywords:0-1knapsackproblem,fireworksalgorithm,chaosmapping,simulatedannealingalgorithm*中国矿业大学（北京）大学生创业创新项目（202107004）背包问题（Knapsackproblem）是一个经典的NP难问题［1］，其最终目的是包装最有价值的物品而不超载。背包问题出现在各种领域的实际决策过程中，例...
