求解0-1背包问题的贪心优化粒子群算法

周 洋，潘大志

(西华师范大学 数学与信息学院，四川 南充 637009)

0 引 言

背包问题(knapsack problem，KP)是在20世纪50年代由Dantzing提出来的一种组合优化问题，也是一类经典的NP难问题，在预算控制、信息加密、投资决策和货物装载等领域具有重要的应用价值。而如何快速、简洁地求解0-1背包问题成为现阶段一个研究目标。目前，关于KP问题的求解主要有精确算法和近似算法两大类。其中，精确算法包括动态规划法、分支界定法、回溯法等，这些精确算法尽管能够找到问题的精确解，然而相对于物品的数量而言，它的时间复杂度呈指数级增长，因此并不适合求解大规模KP问题。为了改进这一缺陷，许多学者基于生物的群体智能性，开始寻求智能优化算法求解KP问题，目前的近似算法包含遗传算法(GA)、粒子群算法(PSO)、蚁群算法(AC)、贪婪算法(GTA)等，这些智能算法在求解大规模背包问题时表现出明显的优势，但是在一定程度上仍有不足之处，因此，对于KP问题的高效求解算法仍然在不断研究。

粒子群算法(Particle Swarm Optimization，PSO)是由美国社会心理学家James Kennedy和电气工程师Russell Eberhart于1995年共同提出的一种新的进化算法(Evolutionary Algorithm，EA)，它是除了鱼群算法、蚁群算法之外的一种新的群体智能优化算法[1]。粒子群算法起初源于对鸟群捕食行为的研究，是一种基于迭代思想的优化算法，它的规则比遗传算法更简易，参数设置相对较少，实现起来更加方便。近几年，国内外很多学者利用粒子群算法这一优越性，将其他算法与其融合并应用于背包问题等实际领域中，取得了很好的研究成果。陶新民等人将双尺度变异策略加入到粒子群算法中，利用此操作更新粒子的飞行速度，在避免算法陷入局部最优的同时，大大提高了最优解的精度[2]；张其亮等人考虑到解的多样性，在粒子群算法中融入模拟退火(SA)思想，设计了粒子群——模拟退火算法，进一步提高解的质量[3]；贺毅朝等人引入了贪心思想，将其与遗传算法结合，得到一种基于贪心策略的遗传算法(GMOGAs),该算法有效地处理了KP问题中的非正常编码个体，关于大规模KP问题能较快地找到最优解，改善了遗传算法的求解效率[4]。本文受贪心算法的启发，将文献[4]中的贪心修正算子(GMO)和贪心优化算子(GOO)融入到传统粒子群算法中，设计了一种贪心优化粒子群算法(GOPSO)，并通过仿真实验将该算法与GMOGAs、离散二进制粒子群算法(BPSO)、AC在收敛速度、求解效果等方面进行比较。

1 背包问题的数学模型

0-1背包问题的一般描述为：假设有n个物品g1，g2，…，gn和一个背包，第j件物品的重量及其价值分别为wj>0和pj>0(j=1,2,…,n)，背包的最大载重限制为C，选择部分物品放入背包，使得在不超过背包最大载重限制的前提下，所放入物品的总价值最大[5]。为描述n个物品是否放入背包，定义决策变量xj：

(1)

(2)

(3)

2 基本粒子群算法

在基本粒子群算法中，每一个解都是搜索空间中的一只鸟，将其抽象为一个没有任何质量和体积的粒子，并延伸至D维空间，每一个粒子有三个属性：位置、速度和由目标函数决定的适应度。粒子知道自己所在位置和目前为止自己发现的最好位置(pbest)，这个视为粒子自身的飞行经验。除此之外，粒子还知道目前为止整个鸟群中所有粒子发现的最好位置(gbest)，这个视为粒子同伴的经验。粒子通过自身的经验和同伴中最好的经验这二者来共同调整自己的飞行方向和速度，从而寻找全局最优解[6]。

假设在一个D维搜索空间中，有m个粒子组成了一个种群X=(X1，X2，…，Xm)，其中第i个粒子的位置为Xi=(xi1,xi2，…，xiD)，i=1，2，…，m，其速度为Vi=(vi1，vi2，…,viD)，每个粒子的位置代表可行域中的一个可行解，解的优劣由适应度的大小来衡量。每进行一次迭代，粒子便根据这两个“极值”对自身进行一次更新，第i个粒子迄今为止搜索到的最优解为个体最优位置记为：Pi=(Pi1，Pi2，…，PiD)；整个粒子群即同伴中发现的最优解为全局最优位置记为：Pg=(Pg1，Pg2，…，PgD)。

粒子群算法的优化模型如下：

(4)

(5)

基本粒子群算法实现过程如下：

算法1PSOAlgorithm

Step1 初始化一个规模为m的粒子群，随机初始化产生各个粒子的位置和速度；

Step2 由目标函数值计算每个粒子的适应度；

Step3 对于每个粒子而言，将自身的适应度值与其经历过的最好位置Pi的适应度值作比较，若较好，则将其设置为当前的最好位置；

Step4 对于每个粒子而言，将自身适应度值与全局经历的最好位置Pg的适应度值作比较，若较好，则将其设置为当前的全局最优位置；

Step5 根据公式(4)和公式(5)对粒子的速度和位置分别进行动态更新；

Step6 如果满足终止条件(预设的迭代次数或者精度)，则停止搜索，输出解，否则返回Step 2。

3 贪心优化粒子群算法

粒子群算法主要用来处理连续优化问题，而0-1背包问题又是一种典型的组合优化问题，因此，将粒子群算法离散化处理具有重要的理论意义和现实意义。Kennedy和Eberhart在1997年对基本PSO算法进行了改进，提出了一种BPSO算法[8]。这一算法一经提出，便引起了国内外研究学者广泛的关注，马慧民等在此基础上加入了记忆机制，加快了算法的收敛速度[9]。因此，对于0-1背包问题的求解，我们可采用BPSO算法的离散化处理方式，这样便成功解决了编码的问题。同时考虑到背包问题的实质为有约束最优化问题，如果仍然用传统粒子群算法去求解，对于大规模0-1背包问题而言，将会导致算法中出现大量的非正常编码个体，这将不能完全保证解的可行性，且算法求解效率较低。现阶段，对于非正常编码个体的处理方法主要有罚函数法(penalty function method，PFM)和个体修正法(individual optimization method，IOM)[10]。受文献[4]中贪心修正算子(GMO)和贪心优化算子(GOO)的启发，本文将这两种算子融入到传统粒子群算法中，不仅能对非正常编码个体进行修正处理，还能够对所有的个体进一步优化，便于快速找到最优解。

算法2GOPSOAlgorithm

Step1 初始化相关参数，设置种群规模为m，进化代数k=0，最大迭代次数为T，惯性权重为ω，加速因子为c1和c2；

Step2 随机初始化每个粒子的位置和速度：

位置的产生方式为：

(6)

(7)

其中rand()表示[0,1]区间内的随机数，vmin和vmax为速度的最大最小限定值；

Step3 利用GMO和GOO算子对初始种群进行修正与优化处理；

Step4 计算粒子的适应度值并更新个体最优和全局最优位置：

(8)

(9)

(10)

Step5 利用公式(4)和公式(5)更新粒子的速度和位置，对更新后的新种群的再次进行离散化处理，使其变成0-1矩阵，处理方式如下：

(11)

S(x)为sigmoid函数，rand()为[0,1]区间内的随机数。

Step6 利用GMO和GOO算子对更新后的位置进行修正与优化；

Step7 令k=k+1，当k>T时，则停止迭代，否则返回Step 4；

4 实验与仿真

为了验证GOPSO算法的高效性以及更好地说明算法的求解效果，下面选用了两组常用的KP实例，例1数据取自文献[10]，其物品数为50，例2取自文献[4]，其物品数为100。分别独立运行30次，对比BPSO算法、文献[4]中的GMOGAs算法以及AC蚁群算法[11]。仿真实验所选择的测试环境为：处理器为Intel(R) Xeon(R) CPU E3-1240 v5，3.50 GHz，内存为8G，操作系统为Windows10，利用Matlab2014a编程求解，并绘制算法迭代收敛曲线。在GOPSO算法中，设置惯性权重w=0.8，加速因子c1=c2=0.7;在AC算法中，设置信息素重要程度因子α=0.9，启发函数重要程度因子β=1，信息素挥发因子ρ=0.7，信息素总量Q=1。

例1 物品个数N=50，背包载重C=1 000，物品价值集P[1，…，50]=[220,208,198,192,180,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1]，物品重量集W[1，…，50]=[80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30,32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1]。该实例利用动态规划法求解得到最优解为3103，对应的总重量为1000，这里设置种群规模为50，最大迭代次数为50，每个算法独立运行30次，测试结果见表1，算法的迭代收敛曲线如图1。

表1 4种算法求解例1的计算结果

例2 物品个数N=100，背包载重C=1 000，物品价值集P[1，…，100]=[998,997,991,986,978,977,939,936,924,920,911,901,901,885,880,866,866,863,856,842,809,794,792,789,778,767,764,764,763,759,756,747,739,708,707,706,694,693,684,680,676,652,644,640,628,612,607,597,593,570,560,556,556,556,542,538,530,530,520,498,487,466,464,461,459,456,452,443,412,399,391,383,381,378,377,359,353,351,327,317,311,295,289,287,283,269,249,248,235,193,189,189,134,108,93,74,51,48,23,8]；物品重量集W[1，…，100]=[353,180,377,230,87,174,157,390,186,213,56,86,77,215,252,90,360,187,294,379,372,384,93,328,283,99,114,374,383,183,248,164,323,263,266,318,296,196,10,324,128,376,19,280,229,225,217,134,233,35,361,302,166,374,392,319,241,15,384,82,158,322,139,239,110,44,115,23,267,82,30,198,173,70,329,125,220,107,148,159,351,56,17,99,308,396,327,235,213,223,372,376,191,299,304,277,292,391,120,37]；该实例利用动态规划法得出的最优解为40 627，对应的总重量为9 793，设置种群规模为100，最大迭代次数为50，测试结果见表2，算法的迭代收敛图见图2。

表2 4种算法求解例2的计算结果

分析表1、表2以及图1、图2可知，本文提出的GOPSO算法与文献[4]中的GMOGAs算法求解性能基本一致，在最大迭代次数内，均能找到问题的最优解，但是从收敛速度以及平均进化代数来看，GOPSO 算法较GMOGAs算法收敛得更快。明显地，对于大规模0-1背包问题的求解，不论是GOPSO算法还是GMOGAs算法，在总体上关于解的质量以及收敛速度等方面均远远优于BPSO算法和AC算法，这足以说明本文提出的贪心优化粒子群算法是一种比BPSO算法更高效的新方法，更加适合于求解大规模背包问题。

5 结束语

基于贪心的思想，将GMO算子和GOO算子融入到基本粒子群算法中，设计了贪心优化粒子群算法，给出该算法的实现流程，并将该算法应用于0-1背包问题的求解。通过对文献中的两个实例进行仿真实验，测试结果表明：GOPSO算法表现出了良好的寻优能力以及较快的收敛速度，并且成功率较高，大大减少了算法的运行时间，这充分说明了新算法的高效性与可行性。