姚若侠 薛丹 谢娟英 范虹
摘要：针对0-1背包问题求解，将离散二进制粒子群优化算法、贪心优化策略和模拟退火算法有机结合，提出了一种改进算法：带贪心优化的混合粒子群和模拟退火算法.基于新算法，完成了9组不同维度数据的仿真实验.实验结果表明，BPSOSA-CGOO算法能够以较小的种群规模及迭代次数实现0-1背包问题的有效求解，并在问题维度为20维的测试数据中找到优于已知最优解的解;独立重复实验验证了，无论对于低维度还是高维度背包问题，BPSOSA-CGOO算法均能以较高概率命中最优解，提高了高维度背包问题求解的稳定性和可靠性.
关键词：背包问题;粒子群优化算法;贪心优化策略;模拟退火算法
中图分类号：TP301
文献标志码：A
文章编号：1000-5641（2020）06-0090-09
0引言
0-1背包问题（0-1 Knapsack Problem，0-1 KP）是经典的组合优化问题，也是—个NP（Non-deterministicPolynomial）-难问题.背包问题具有深远的理论意义和重要的实践应用研究价值，自20世纪50年代被Dantzig提出以来，引起了国内外学者极大的研究热情，且已被广泛应用于投资决策、资源分配和货物装载等金融和工业领域.
0-1 KP简要描述如下：共有N种待选定的物品，每种物品只有1个且不可分割，物品j的价值为Pj，重量为hj，只有1个背包且能容纳物品的总重量为C问题：如何选择装入这个背包的物品，使背包中装入物品的总重量不超过C且总价值最大？0-1 KP的数学模型公式为
目前求解0-1 KP的主要算法大致分为精确算法、群智能优化算法、混合算法这3类.精确算法主要包括贪心算法（Greedy Algorithm，GA）、动态规划（Dynamic Programming，DP）算法、分支界定（Branch and Bound，BB）算法群智能优化算法主要包括遗传算法、烟花算法（Fireworks Algorithm，FA）、粒子群优化算法等.混合算法主要包括贪心遗传算法、贪心萤火虫算法、基于直觉模糊熵的粒子群-模拟退火算法、贪心优化粒子群算法等.文献[11]应用贪心算法、动态规划算法、分支界定算法求解0-1 KP，其实验结果表明，贪心算法高效但却不一定能给出最优解;在问题维数较低的情况下，动态规划、分支界定的算法性能较好，但随着问题规模的增大，时间复杂度呈指数级增长，同时动态规划算法的内存消耗也很大，这意味着它们对大规模0-1 KP的解决只是理论层面的.为了以较低的时间和空间消耗来较优地解决高维度背包问题，大量学者将目光转移向了群智能优化算法及其混合算法.文献[8]应用遗传算法等6个算法，求解大量的0-1 KP测试数据，实验结果表明，混合遗传算法和模拟退火算法性能较优.文献[21-22]提出了贪心遗传算法（GGA），并对文献[11]中的贪心策略进行了改进，提出了贪心修正算子（CMO）和贪心优化算子（COO），使得应用遗传算法在求解0-1 KP时不仅可以对不合法的解进行校正，也可以对合法解给出优化，有效提升了种群在进化过程中优质解所占的比率，增强了遗传算法求解0-1 KP的能力，拓展了应用群智能优化算法求解组合优化问题的思路.文献[24]结合粒子群优化算法和模拟退火策略，提出了基于直觉模糊熵的粒子群-模拟退火算法，通过实验验证了算法的有效性，而且，该算法对于较小规模的背包问题能够以100%的概率命中已知解.文献[25]结合粒子群优化算法、贪心修正算子和贪心优化算子，提出了贪心优化粒子群算法，通过实验验证了该算法具有良好的寻优能力，并且可以快速收敛至最优解.以上研究成果显示，混合群智能优化算法对求解0-1 KP具有良好的表現，由此启发本文尝试采用带贪心优化的混合粒子群和模拟退火（BPSOSA-CGOO）算法来求解0-1 KP.
基于对0-1 KP现状的研究和分析，本文结合离散二进制粒子群优化算法（BPSO）可以快速收敛至潜在最优解和对于组合优化问题有广泛适应性的特点、贪心修正算子（GMO）和贪心优化算子（GOO）能够在种群进化过程中提升优质解占有率的特点、模拟退火算法能够概率性地跳出局部极值等特点，提出了带贪心优化的混合粒子群和模拟退火算法（BPSOSA-CGOO），拓展了求解0-1 KP更为稳定和有效的算法集.通过对文献[24]中的背包数据进行测试，BPSOSA-CGOO算法使求解0-1 KP的寻优能力和命中已知最优解的概率得到了有效的提高.下文对BPSOSA-CGOO算法进行详细介绍.
1带贪心优化的混合粒子群和模拟退火算法
本文提出的BPSOSA-CGOO算法，主要在离散二进制粒子群优化算法（BPSO）的基础上进行了以下两个优化.
（1）在种群初始化及更新粒子后，本文调用合并的贪心优化算子对更新后的粒子进行优化，以此保证在种群合法性的基础上价值最大，使得种群在进化过程中优质解的占比增高，进而提升种群的寻优能力.
（1）按照u（pi）由大到小的顺序对粒子已选择的商品进行检查，如果已选择的商品加入背包后，不大于背包总承重，则加入背包，否则，取出该商品.
（2）按照u（pi）由大到小的顺序对粒子未选择的商品进行尝试性地加入背包，如果未选择的商品加入背包后，不大于背包总承重，则加入背包，否则，不加入.
为了更清楚地描述BPSOSA-CGOO算法中CGOO算子的优化过程，本文以1个10维背包问题为例，列举某不合法粒子X经过CGOO算子优化后的结果，结果如下.
设10个物品的价值集P={55，10，47，5，4，50，8，61，85，87），重量集H={95，4，60，32，23，72，80，62，65，46），背包最大容量C=269，粒子X=（1011100010），粒子X优化前，重量为275（>C），价值为196.算法1执行后，粒子X=（1110100010），重量为247（196）.
1.3模拟退火策略
模拟退火操作的基本思想由Metropolis于1953年提出，1983年首次应用于解决组合优化问题.目前，模拟退火操作有许多改进版本，本文选用最基本的模拟退火策略，即在降温的过程中根据马尔科夫链长，重复执行如下迭代过程：①产生新解;②计算价值差;③判断是否接收新解;④接收或舍弃;⑤返回①.
BPSOSA-CGOO算法不仅可以保证粒子在进化过程中都合法，提高种群中优质解的占有率，而且还可以通过模拟退火操作概率性地修改个体极值，有助于种群在进化过程中趋于全局最优.BPSOSA-CGOO算法的程序流程如图2所示.
2仿真实验
实验环境为，Win 10操作系统，Intel Core（TM）i7-8550U CPU处理器，8GB内存，Python3.5编程语言，PyCharm2018.1.4开发环境.实验参数设置为，种群规模=问题维数/2，迭代次数=200，学习因子c1=c2=1，惯性系数ω=0.9，速度的最大值Vmax=6，初始温度T0=1000，马尔科夫链长L=20，降温因子α=0.99，冷冻点f=0.0001.采用文献[24]中的9组不同维度的测试数据，对9组测试数据各执行1次，实验结果见表1，其中进化次数代表收敛至已知最优解的进化次数.
表1实验结果揭示，BPSOSA-CGOO算法对于9组不同维度的测试用例，均能搜索到已知最优解，且测试数据3（表1加粗部分）搜索到的最优解（1042（价值）878（重量））优于文献[24]中的解（1024（价值）871（重量））.
为了进一步分析算法的稳定性和有效性，本文在实验参数设置不变的基础上，对相同的测试数据，分别执行了20次独立重复实验，实验结果见表2.表2中，SSN代表成功实验的次数，AVIN代表成功实验中平均进化代数.假定认为命中已知最优解为一次成功实验，则AVIN的计算公式为其中，Ei为第i次成功实验对应的进化代数.
表2所示的实验结果揭示了，在9组不同测试数据的20次独立重复实验结果中，有7组实验命中最优解的次数都为20次，标准差为0;测试数据5命中最优解的次数为18次，标准差为2.48;测试数据8命中最优解1次，标准差为13.82.这说明：①BPSOSA-CGOO算法对于大多数测试数据能以较高的概率命中最优解，体现了有效性;②标准差是反映数据集离散程度的统计量，表2中的标准差数据表明，BPSOSA-CGOO算法具有较强的稳定性.
为了更加全面地分析BPSOSA-CGOO算法求解0-1背包问题的稳定性，本文基于文献[25]中的算法思想对GOPSO算法进行了Python实现，并对上述9组不同维度的测试用例分别执行了20次独立重复实验.实验环境为本文上述环境;实验参数设置为，种群规模=问题维数/2，迭代次数=200，学习因子c1=c2=1，惯性系数ω=0.9，速度最大值Vmax=6.本文所提的BPSOSA-CGOO算法命中最优解的次数与IFEPSOSA算法和GOPSO算法的对比见图3.
图3表明，GOPSO算法、BPSOSA-CGOO算法除测试数据8以外，均能以较高的次数命中最优解.针对GOPSO和BPSOSA-CGOO算法在测试数据8上表现出的特殊情况，本文做了分析并给出先验推测：这很可能是由种群规模引起的.故本文尝试将种群规模=问题维数/2修改为与文献[24]一致，即种群规模=100，其余参数保持不变，对测试数据8执行20次独立重复实验，执行结果见表3和图4，命中最优解次数与文献[24]中IEFPSOSA算法的对比见图5.
表3所示的实验结果揭示，BPSOSA-CGOO算法的最差解、平均值、标准差均优于GOPSO算法.图4表明，BPSOSA-CGOO算法在20次独立重复实验中找到的实验最优解的数值波动较小，较为稳定.由图5可以看出，BPSOSA-CGOO算法在独立重复实验中命中已知最优解13次，体现了该算法在命中最优解的次数上的优势.
此外，为了充分验证BPSOSA-CGOO算法在高维度背包问题求解上的稳定性，本文对文献[16]中100维的背包算例进行了10次独立重复实验，实验结果见表4.表4所示的实验结果揭示，虽然BPSOSA-CGOO算法的实验最优解稍小于文献[16]中的已知解，但独立重复实验的标准差远远小于文献[16]中的147，实验最差解大于文献[16]中的7753，且随着种群规模和迭代次数的增大，BPSOSA-CGOO算法标准差随之减小，最差解也在增大.这表明，对于高维度背包问题，BPSOSA-CGOO算法能够以较高的稳定性找出较优解.
上述实验数据及结果表明，BPSOSA-CGOO算法不仅可以有效求解0-1背包问题，而且能够在种群规模、迭代次数均较小的条件下，对高维度背包问题以较高概率寻得最优解/较优解，表现出了较强的稳定性和可靠性.
3结束语
本文基于对离散二进制粒子群优化算法的两个优化，提出了带贪心优化的混合粒子群和模拟退火算法——BPSOSA-CGOO算法，采用该算法求解0-1背包问题，完成了9组不同维度背包数据的测试后，得到了以下结论：①BPSOSA-CGOO算法对于9组背包数据均能以较小的种群和进化代数找到已知最优解，且背包数据3找到的解优于已知最优解;②在独立重复实验中，有7组实验以100%的概率命中最优解，其余两组命中最优解的概率分别为90%和65%.
BPSOSA-CGOO算法在本文实验环境下，无论对于高维度还是低维度的测试数据，均能以较高的概率命中最优解，在求解0-1 KP的稳定性、可靠性方面，性能均获得明显提升.此外，谷鹏等根据粒子群优化算法提出了一种改进的粒子群优化算法，并结合扩展的卡尔曼滤波跟踪算法，提高了目标跟踪的精度，该算法虽然能够随机搜索潜在最优解，但是容易陷入局部最优的特点.李鹏等通过将粒子群优化算法与遗传算法相结合，在种群中进行交叉、变异等操作提高了种群多样性，克服了粒子群优化算法容易陷入局部极值的缺点，并将其成功应用于无人机航路规划中，取得了良好的应用效果.郭玉洁等提出了一种双种群协同多目标粒子群优化算法，将其应用于油田开采，以实现油田开采利润最大化为目标，并应用于油田开采优化模型，取得了良好的效果.后續也可以将该算法应用到折扣背包问题、动静态背包问题、机器人路线规划、油田开采模型优化等的实际工作中，使其发挥更大更广泛的实际应用价值.
