求解0/1背包问题的自适应元胞粒子群算法

李枝勇,马 良,张惠珍

(上海理工大学管理学院,上海200093)

求解0/1背包问题的自适应元胞粒子群算法

李枝勇,马 良,张惠珍

(上海理工大学管理学院,上海200093)

对0/1背包问题进行研究,提出一种自适应元胞粒子群算法。在算法设计过程中,重新定义粒子位置和速度的更新方程,引入自适应因子,为有效粒子的主动进化和无效粒子的主动退化提供依据,新的编码方式使得新产生的粒子能够以更大的概率和更快的速度成为有效粒子,将元胞及其邻居引入到算法中保持种群的多样性,利用元胞的演化规则进行局部优化,避免算法陷入局部极值。对多组不同规模的背包问题进行仿真实验,结果表明,该算法不仅可以有效求解0/1背包问题,而且能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性。

粒子群优化;0/1背包问题;自适应因子;元胞自动机;组合约束优化;NP难题

1 概述

0/1背包问题是运筹学中的一个典型优化难题[1],已被应用于诸多领域,如预算控制、项目选择、装载问题、材料切割和投资问题等,并且还经常作为其他问题的子问题加以研究。

就计算复杂性而言,背包问题属于NP难题,随着问题规模的增大,求解时间随指数增长,在最坏的情况下,时间复杂度为O(2n)。因此,设计新的高效算法来求解背包问题具有重要的理论和实际意义[2-3]。从已有的研究成果来看,求解背包问题的方法主要有精确算法和启发式算法两大类。其中,精确算法包括分支界定法、动态规划法、递归法和回溯法等。启发式算法主要包括贪心算法、遗传算法、蚁群算法、蜂群算法、模拟退火算法、禁忌搜索算法、粒子群算法及以上几种算法的改进算法等。精确算法虽然可以得到精确解,但是当物品数目较大时,精确算法并没有可行性。启发式算法虽然不一定得到精确解,但可以得到次优解,时间复杂度也比较低。

粒子群优化[4](Particle Swarm Optimization, PSO)算法源于对鸟类捕食的行为研究,是Kennedy和Eberhart于1995年提出的仿生智能计算方法,具有概念简单、控制参数少、容易实现等优点。目前,粒子群算法的研究成果大多是在对各类连续空间优化问题的研究上所取得的,对离散优化问题的研究相对较少,因此,开拓离散的PSO算法的应用研究是一项很有价值的工作。有部分学者已经将PSO算法用来解决背包问题,并取得了很好的效果[5-8],如文献[5]定义了等值交换、异值变换以及变换序列等概念,并针对性地设计了一种适合求解0/1背包问题的特殊微粒群算法,具有一定的可行性,但是该算法用概率来引导变换序列的变换这一过程具有较强的随机性,虽然可以增加算法的多样性,但是可能会降低算法的收敛速度。本文在对粒子位置和速度更新公式进行重新定义的基础上,利用决策分析的相关知识定义了每个物品被选择的机率,并结合元胞自动机理论,丰富种群的多样性,提出一种自适应元胞粒子群算法(Adaptive Cellular Particle Swarm Optimization,ACPSO)来解决0/1背包问题。

2 基本粒子群算法

在PSO系统中,每个备选解被看作一个“粒子”,每个粒子根据自身的最佳“经验”和种群的最佳“经验”,在问题空间中向更好的位置飞行,这样反复搜索,直到发现最优解。PSO算法的数学表示如下:

设种群粒子数为 n,搜索的空间维数为 d。第i个粒子位置表示为向量Xi=(xi1,xi2,…,xid),速度为向量Vi=(vi1,vi2,…,vid),第i个粒子目前搜索到的最优位置为向量Pi=(Pi1,Pi2,…,Pid),整个种群目前搜索到的最优位置为向量 Pj=(Pj1,Pj2,…, Pjd),每个粒子的速度和位置分别按式(1)和式(2)进行迭代更新:

其中,c1和c2为正常数,称为加速因子;R1和R2为均匀分布在[0,1]之间的随机数;w称为惯性因子,较大时适于对解空间进行较大范围探查,反之亦然; t表示某一次迭代。粒子群初始速度和位置随机产生,然后按式(1)和式(2)进行迭代,直到算法满足迭代终止条件。

3 自适应元胞粒子群算法

3.1 速度和位置更新公式的重新定义

0/1背包问题可被描述为:给定n个物品和一个背包,物品i的价值为pi、重量为wi,(i=1,2,…,n)背包能容纳的最大物品重量为C,现要求从这n个物品中选出若干件放入背包,使得放入物品的总重量不超过C,且总价值达到最大:

根据背包问题可行解的性质,解是由0和1组成的集合向量,所以第i个粒子的初始位置可以表示为向量Xi=round(rand(i,d))。同理,第i个粒子的初始速度可以表示为向量 Vi=round(rand(i, d))。至此,在求解之前必须给出各个粒子的速度和位置的更新公式的重新定义,定义如下:

Pi-Xi(t)和Pj-Xi(t)运算操作定义为:

这样定义了粒子群速度和位置更新公式的相关操作规则。通过这种定义可以将粒子群扩展到背包问题的求解上。ACPSO实现只要将式(5)～式(9)带入式(1)和式(2)即可。

3.2 自适应因子

定义1 如果某个粒子所对应的解满足式(4),则称该粒子为有效粒子,否则称为无效粒子。

为了引导每个粒子能够主动地适应环境,本文引入自适应因子来推动有效粒子的主动进化和无效粒子的主动退化。针对0/1背包问题,自适应因子是由d个0～1之间的小数组成的数字串(m1,m2,…,m3),mi表示物品i被选中放入背包的机率。这个机率由下面2个因素决定:

(1)物品i的单位重量价值avi,令avi=pi/wi;

(2)物品i的重量和背包容量的比率关系wci,令wci=C/wi;

不难发现,avi和wci越大越好,可由下式得到自适应因子:

由以上可以看出,mi和物品i放入背包的机率呈正比关系。

根据自适应因子,可以对当前每个有效粒子进行主动进化:首先将m的各个元素由大到小进行排序,然后按照该顺序对每个粒子进行如下操作,当该粒子位置的某个分量所对应物品被选择的概率mi＞rand()或者该分量为0,则将该分量设置为1,从而产生一个备选粒子,如果此时该备选粒子为有效粒子,就将该物品放进背包里面,否则扔掉。

如果一个粒子为无效粒子,则对该粒子进行退化处理:如果该粒子的某个分量所对应的物品被选择的机率mi＜rand()且该分量取值为1,则将该分量退化成0。然后,再次判断该粒子是否为有效粒子,如果不是,则继续重复前面的操作,直到满足为止。

3.3 编码方式

很多文献在产生粒子的初始位置时都简单地定义当产生的随机数小于0.5时便取0,否则取1。然而,在经过大量的实验数据验证后发现:用MATLAB中函数rand()产生的随机数,超过半数的均要大于0.5。这说明当某个背包问题的最优解中1较少,则会以很大的概率出现初始种群全部是无效粒子的情况,又因为本文所提出的算法要求参与评价的粒子必须全都是有效粒子,为了避免算法在进入循环迭代之前的初始化过程中出现由于无效粒子的存在,使得算法一直处在将无效粒子退化成有效粒子的循环往复的过程而使算法停滞不前的情况,这里给出一种新的有关粒子初始化的编码方式,方法如下:如果rand()＜r,则x=1,否则,x=0。其中, r为一个常数,这里称作为被选率。

3.4 背包问题的元胞粒子群算法

元胞自动机是一个时间离散化、状态离散化的网格动力模型,已成为以离散性为特点描述复杂行为的具有广阔发展前景的方法。元胞在元胞空间里,按照演化规则有很多种变化,有助于保持种群的多样性。

定义2 设物品选择的集合 C=(c1,c2,…, ci,…,cn),其中,ci∈{0,1},ci=1表示选中物品i, ci=1表示未选中物品i。C中ci任意取值的排列组合的集合为元胞空间,可表示为L={CellX=(c1, c2,…,ci,…cn)},每个组合CellX为元胞。

定义3 moore邻居类型:

其中,diff(CellY-CellX)≤γ为2个组合排序的差异,如无差异为0,有差异时,最小为1;γ为差异度,这里γ取1。

定义4 扩展moore邻居类型:

其中,diff(CellY-CellX)≤λ为2个组合排序的差异,如无差异为0,有差异时,最小为2。λ为差异度,这里λ取2。

定义5 元胞演化规则

根据元胞邻居的定义计算其邻居的目标解,比较元胞和其邻居的差异,选择最好的目标解。

背包问题的自适应元胞粒子群算法的基本步骤如下:

Step 1 初始化粒子群中粒子的位置和速度,相关参数的设置以及自适应因子的计算;

Step 2 设粒子自身最佳位置pbest为当前位置,设初始群体最佳粒子的位置为gbest;

Step 3 判断算法是否满足结束条件,如果满足,转Step8,否则执行Step4;

Step 4 根据式(1)和式(2)来更新粒子的位置和速度;

Step 5 粒子主动进化,更新gbest和pbest,如果粒子的gbest和pbest相等,则将该粒子的位置重新初始化,其他参数不变;

Step 6 按元胞邻居的定义,在邻居范围内演化,记录最好的解,再次更新gbest和pbest;

Step 7 迭代次数加1,转Step3;

Step 8 输出结果,算法结束。

在算法运行的过程中,粒子初始化、粒子位置更新和粒子的主动进化过程中都伴随有对该粒子所对应解是否符合约束规则的判断以及当粒子不符合约束规则时对该粒子进行主动退化的过程。

这里,定义去掉Step6这一过程后的算法为自适应粒子群算法,方便起见,记作算法1;在Step6进行moore邻居类型演化的算法为自适应元胞粒子群算法,方便起见,记作算法2;在Step6进行moore扩展邻居类型演化的算法为自适应扩展元胞粒子群算法,方便起见,记作算法3。

4 仿真实验

为了比较上述3种算法解决实际问题的能力,从中找出一种较好的算法作为本文提出的算法,本文选用各种文献中普遍使用的9组测试算例,其中涉及到不同规模的0/1背包问题。实验所用硬件为Core(TM)2 Duo CPU为 2.93 GHz,内存为1.93 GB,软件为Windows XP和Matlab。

4.1 测试算例

测试用到的9组算例如下:

算例1 物件个数d=10,最大重量限制C= 269,各个物件重量w=[95,4,60,32,23,72,80,62, 65,46],各个物件价值p=[55,10,47,5,4,50,8,61, 85,87],最优值为295[9]。

算例2 物件个数d=20,最大重量限制=878,各个物件重量w=[92,4,43,83,84,68,92,82,6, 44,32,18,56,83,25,96,70,48,14,58],各个物件价值p=[44,46,90,72,91,40,75,35,8,54,78,40,77, 15,61,17,75,29,75,63],最优值1 024[9]。

算例3 物件个数d=20,最大重量限制C= 878,各个物件重w=[44,46,90,72,91,40,75,35, 8,54,78,40,77,15,61,17,75,29,75,63],各个物件值p=[92,4,43,83,84,68,92,82,6,44,32,18,56, 83,25,96,70,48,14,58],最优值1 042。不难发现,算例3是将算例2的物件重量矩阵和物件价值矩阵对调了一下,但是有些文献却没有发现这一不同[10]。

算例4 物件个数d=50,最大重量限制C= 959,各个物件重量w=[95,39,69,63,49,104,56, 58,47,23,17,129,91,28,77,125,73,5,103,63,76, 23,47,79,119,125,26,119,79,56,50,75,12,26,31, 43,41,38,29,21,14,9,3,17,8,8,9,7,4,5],各个物件价值p=[293,291,290,280,278,274,269,265, 248,247,245,245,241,234,229,228,222,216,214, 191,191,187,171,170,164,152,142,132,131,126, 122,116,112,111,110,106,77,76,74,73,69,67,42, 41,35,33,30,29,28,26],最优值为4 882[11]。

算例5 物件个数d=100,最大重量限制C=3 820,各个物件重量w=[54,95,36,18,4,71,83,16, 27,84,88,45,94,64,14,80,4,23,75,36,90,20,77, 32,58,6,14,86,84,59,71,21,30,22,96,49,81,48, 37,28,6,84,19,55,88,38,51,52,79,55,70,53,64, 99,61,86,1,64,32,60,42,45,34,22,49,37,33,1, 78,43,85,24,96,32,99,57,23,8,10,74,59,89,95, 40,46,65,6,89,84,83,6,19,45,59,26,13,8,26,5, 9],各个物件价值p=[297,295,293,292,291,289, 284,284,283,283,281,280,279,277,276,275,273, 264,260,257,250,236,236,235,235,233,232,232, 228,218,217,214,211,208,205,204,203,201,196, 194,193,193,192,191,190,187,187,184,184,184, 181,179,176,173,172,171,160,128,123,114,113, 107,105,101,100,100,99,98,97,94,94,93,91,80, 74,73,72,63,63,62,61,60,56,53,52,50,48,46,40, 40,35,28,22,22,18,15,12,11,6,5],最优值为15 170[11]。

算例6 物件个数d=100,最大重量限制C= 6 718,各个物件重量w=[54,183,106,82,30,58, 71,166,117,190,90,191,205,128,110,89,63,6, 140,86,30,91,156,31,70,199,142,98,178,16,140, 31,24,197,101,73,169,73,92,159,71,102,144, 151,27,131,209,164,177,177,129,146,17,53,164, 146,43,170,180,171,130,183,5,113,207,57,13, 163,20,63,12,24,9,42,6,109,170,108,46,69,43, 175,81,5,34,146,148,114,160,174,156,82,47, 126,102,83,58,34,21,14],各个物件价值p=[597, 596,593,586,581,568,567,560,549,548,547,529, 529,527,520,491,482,478,475,475,466,462,459, 458,454,451,449,443,442,421,410,409,395,394, 390,377,375,366,361,347,334,322,315,313,311, 309,296,295,294,289,285,279,277,276,272,248, 246,245,238,237,232,231,230,225,192,184,183, 176,174,171,169,165,165,154,153,150,149,147, 143,140,138,134,132,127,124,123,114,111,104, 89,74,63,62,58,55,48,27,22,12,6],当前最优值为26 559[12]。

算例7 物件个数d=100,最大重量限制C= 999.60,各个物件重量w=[94,81,8,62,21,83,85, 45,48,81,4,64,59,97,96,14,21,59,34,68,36,2,3, 65,26,48,25,17,11,97,43,23,24,48,56,73,54,15, 98,99,47,93,78,68,24,52,8,89,100,7,9,46,8,40, 77,46,76,78,7,32,92,11,93,75,6,60,64,15,99, 30,99,61,17,3,31,34,76,68,79,91,95,25,73,43, 89,9,12,31,71,24,19,70,76,14,50,85,40,78,12, 6],各个物件价值p=[94,60,88,18,39,57,4,74, 86,77,59,45,74,99,46,68,99,83,23,85,80,41,58, 11,35,73,100,2,79,58,70,40,6,9,26,2,7,92,40, 45,65,50,80,53,37,84,14,14,72,41,46,76,13,78, 77,77,49,29,63,61,32,2,6,47,31,46,35,85,39, 64,52,24,25,26,50,81,89,61,44,95,40,27,83,81, 85,32,60,91,44,54,31,48,50,94,32,83,24,40,43, 11],当前最优值为2 656,本文最优值为2 660[13]。

算例8 算例8和算例7的区别仅仅在于最大重量限制和当前最优值不一样,算例8的最大重量限制C=2 499,当前最优值为4 142,其他相关数据均一样。本文最优值为4 143[13]。

算例9 算例9和算例7的区别仅仅在于最大重量限制和当前最优值不一样,算例9的最大重量限制C=3 998.4,当前最优值为4 985,其他相关数据均一样。本文最优值为4 986[13]。

4.2 参数设置

惯性权重因子w=0.8,学习因子c1=c2=2,种群规模50,最大迭代次数500,被选率为0.5(算例7除外,为0.009)。

4.3 测试结果及分析

3个算法各自独立运行30轮,寻优目标均为当前最新文献给出的最好值(算例7、算例8和算例9除外,这3个算例的寻优目标分别为2 660,4 143和4 986,均优于当前文献给出的最好值),各个算法在每轮寻优的过程中算法停止的条件有 2个,具体如下:一旦找到当前最好值,该轮算法程序运行结束,随即转入下一轮程序的运行;当算法程序运行过程中,如果一直没有找到当前最好值,则达到最大迭代次数时,该轮算法程序运行结束.该实验统计的指标有: 30轮独立实验中的实验最好值、实验平均值和实验最差值;30轮独立实验消耗总时间(单位: s);30轮独立实验中寻找当前最好值的成功次数;30轮独立实验中寻找当前最好值的成功迭代次数中的最小迭代次数、平均迭代次数和最大迭代次数。实验结果见表1。其中“-”表示由于30次独立实验中没有找到当前最好值,指标无法统计。另外需要指出的是在统计指标为“最小迭代”中有数据为0,指得是在没有进入循环前的初始化中已经找到当前最好值。

表1 实验结果比较

从表1中可以看出,虽然算法1运行的时间最短,而且寻找算例4和算例6的当前最好值的成功次数要多于算法2和算法3,寻找算例7的当前最好值的成功次数要多于算法3,但是在寻找算例2和算例3的当前最好值的成功次数要明显少于算法2和算法3;算法3的缺点很明显,主要体现在2个方面:一方面是其运行的时间要远远大于其他两个算法;另一方面针对算例6,算法3的实验最好值要劣于其他2个算法。所以,综合运行时间和解决问题能力2个方面考虑,算法2是本文所要提出的用于求解0/1背包问题的自适应元胞粒子群算法。

4.4 算法比较

为了进一步验证本文提出的求解0/1背包问题的自适应元胞粒子群算法的性能,将该算法与其他算法进行比较。鉴于文章篇幅的原因,这里只给出算例7、算例8和算例9的比较结果,比较的算法是文献[13]提出的算法及原文用来比较的其他算法。算法独自运行30次,统计比较其中的最好值和平均值,统计结果见表2。

表2 算例7～算例9的4种算法性能比较

从表2中可以很明显地看出,从最优值这个角度来看,ACPSO寻优获得的最优值均好于ETGA、ISGA和 AIOA寻优获得的最优值,从而说明ACPSO的全局寻优能力要优于其他3种算法;从平均值这个角度来看,ACPSO寻优获得的平均值均要好于ETGA、ISGA和AIOA寻优获得的平均值,特别是算例7和算例8,ACPSO的优势更加明显,从而说明ACPSO在解决问题上比其他3种算法具有更好的稳定性。综上可以得出:ACPSO的寻优性能更好,要远远优于其他算法。

5 结束语

本文提出一种自适应元胞粒子群算法,通过对算法仿真实验发现:引入了自适应因子和元胞邻居理论的自适应元胞粒子群算法能够解决文中算例的大部分问题,与其他算法相比具有更好的性能。本文算法主要优势在于能够快速找到全局最优解,即使找不到全局最优解,也会以很快的速度收敛到距离全局最优解较近的次优解,因此,该算法具有一定的普遍适应性,可以用来解决0/1背包问题。

[1] 马 良.高级运筹学[M].北京:机械工业出版社,2008.

[2] Srinivasan V,Varghese G.Fast Address Lookups Using Controlled Prefix Expansion[J].ACM Transactions on Computer Systems,1999,17(1):1-40.

[3] Gupta P,LinS,McKeownN.RoutingLookupsin Hardware at Memory Access Speeds[C]//Proc.of IEEE INFOCOM’98.San Francisco,USA:IEEE Press, 1998:1240-1247.

[4] Kennedy J,Eberhart R C.Particle Swarm Optimization [C]//Proc.of IEEE International Conference on Neural Networks.Perth,Australia:IEEE Press,1995:1942-1948.

[5] 沈显君,王伟武,郑波尽,等.基于改进的微粒群优化算法的0-1背包问题求解[J].计算机工程,2006,32 (18):23-24.

[6] 柳寅,马 良.0-1背包问题的模糊粒子群算法求解[J].计算机应用研究,2011,28(11):4026-4028.

[7] 马慧民,叶春明,张爽.二进制改进粒子群算法在背包问题的应用[J].上海理工大学报,2006,28(1): 31-34.

[8] 高 尚,杨静宇.背包问题的混合粒子群算法[J].中国工程学,2006,8(11):94-98.

[9] 马 良.蚁群优化算法[M].北京:科学出版社,2008.

[10] 赵新超,韩 宇,艾文宝.求解背包问题的一种改进遗传算法[J].计算机工程与应用,2011,47(24): 34-36.

[11] 刘建芹,贺毅朝,顾茜茜.基于离散微粒群算法求解背包问题研究[J].计算机工程与设计,2007,28(13): 3189-3191.

[12] 贺毅朝,刘坤起,张翠军,等.求解背包问题的贪心遗传算法及其应用[J].计算机工程与设计,2007,28 (11):2655-2657.

[13] 庄中文,钱淑渠.抗体修正免疫算法对高维0/1背包问题的应用[J].计算机应用研究,2009,26(8): 2921-2923.

编辑 索书志

Adaptive Cellular Particle Swarm Algorithm for Solving 0/1 Knapsack Problem

LI Zhi-yong,MA Liang,ZHANG Hui-zhen
(School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China)

0/1 knapsack problem is studied,and adaptive cellular particle swarm optimization algorithm is presented.In the design of the algorithm,the rules about updating the particle’s velocity and position are redefined,an adaptive factor is introduced to provide a basis for the active evolution of the valid particle and the active degradation of the invalid particle,a new coding mode is given to make new particles be valid with great probability and fast speed,cellular and its neighbor are introduced into the algorithm to maintain the swarm’s diversity and the algorithm uses evolutionary rule of cellular in local optimization to avoid local optima.Simulation experimental results of different scale 0/1 knapsack problem and comparisons with other algorithms show that the algorithm not only can solve the 0/1 knapsack problem effectively,but also can get the good second-best solution even for the global optimal solution with a faster rate,and has a certain degree of stability

Particle Swarm Optimization(PSO);0/1 knapsack problem;adaptive factor;cellular automata;

1000-3428(2014)10-0198-06

A

TP301.6

10.3969/j.issn.1000-3428.2014.10.037

高等学校博士学科点专项科研联合基金资助项目(20123120120005);上海市一流学科建设基金资助项目(S1201YLXK);上海高校青年教师培养计划基金资助项目(slg12010);上海市教育委员会科研创新基金资助项目(14YZ090);上海市研究生创新基金资助项目(JWCXSL1202);上海理工大学博士科研启动基金资助项目(1D-10-303-002)。

李枝勇(1986-),男,硕士研究生,主研方向:系统工程,智能优化;马 良,教授、博士、博士生导师;张惠珍,讲师、博士。

2013-10-22

2013-12-13E-mail:lizhiyong.2180869@163.com

中文引用格式:李枝勇,马 良,张惠珍.求解0/1背包问题的自适应元胞粒子群算法[J].计算机工程,2014, 40(10):198-203.

英文引用格式:Li Zhiyong,Ma Liang,Zhang Huizhen.Adaptive Cellular Particle Swarm Algorithm for Solving 0/1 Knapsack Problem[J].Computer Engineering,2014,40(10):198-203.

combinatorial constrained optimization;NP hard problem