粒子群算法求解0-1背包问题

问题背景

假设有n个物品和一个背包，物品的重量为wi，价值为vi，背包能容纳的重量为M，从这n件物品中取出若干件，使得总重量不超过M，并且总价值达到最大。

粒子群算法

算法框架

粒子群优化算法(Particle Swarm Optimization, PSO)，是进化计算的一个分支，和遗传算法一样，粒子群算法也是一种模拟自然界生物活动的随机搜索算法。

粒子群算法最早是在1995年由Eberhart和Kennedy提出的[1][2]，它是模拟自然界鸟群觅食的一种搜索方法。

PSO算法要求每个个体（粒子）在进化过程中维持着两个向量，分别为速度向量Vi[vi1,vi2,,viD]和位置向量Xi[xi1,xi2,,xiD]，其中i表示粒子的编号，D是求解问题的维数。速度决定了粒子的运动的方向和速率，而位置则体现了粒子所代表的解在解空间中的位置，是评估该解质量的基础。同时粒子还要维护着一个pbest值和一个gbest值，分别代表粒子的历史最优和群体的全局最优。

算法流程如图1：

开始初始化粒子的速度和位置令粒子的历史最优为当前位置g = 1评估每个粒子并得到全局最优nog < Gmaxyes评估每个粒子的适应值结束更新每个粒子的历史最优更新群体的全局最优更新每个粒子的速度更新每个粒子的位置g = g+1

图1 算法流程图

离散PSO

粒子群算法是作为优化连续领域问题的优化器而提出的，因此它特别适合于求解连续问题。对于离散问题的求解，今年来很多学者都尝试了不同的做法。本实验采用的离散PSO版本是1997年由Eberhart和Kennedy提出的方法[3]。

BPSO与传统PSO的不同之处在于以下几个方面：

首先是编码。BPSO将位置定义为0、1的二进制位串，而粒子的速度则通过sigmoid函数转化为修改位置向量的一个概率值。

其次是粒子的更新方式。速度的更新公式为

ddddddvidvidc1rand1(pBestixi)c2rand2(gBestxi) (1)

不使用参数w，vi被限定在[–Vmax, Vmax]范围内，Vmax的取值为6。速度

igmoid通过sigmoid函数转化为区间[0,1]上的一个实数p，如ps(vid)11evid。

通过Sigmoid函数的作用，速度将被解释为一个概率值。BPSO随机生成一个[0,1]之间的实数r，如果rBPSO在0-1背包问题上的应用

初始化编码

每个粒子代表了一种解决方案。速度向量的每一维都被随机初始化为区间[–Vmax, Vmax]上的一个实数，位置向量的每一维被随机初始化为0或1，1表示该物体被选中放入背包，0表示不被选中。粒子历史最优pbest指向当前位置，群体全局最优pbest指向当前群体的全局最优。

评价函数

问题求解的是价值最大化，因此评价函数为背包的总价值。根据物体被选中的情况，将相应的价值累加得到评估函数值。同时将选中的物体的重量累加，如果超过背包所能容纳的总重量，则将该粒子的评估函数值设为0 。

更新

首先根据评价函数的值更新粒子的历史最优位置pbest和群体的全局最优位置gbest。

粒子的当前速度和位置的更新方法按照BPSO的做法。速度公式中的c1和

c2均取0.2。

实验结果及分析

表1 实验结果

物体数 5 8 10 100 100 文件名 5.txt 8.txt 10.txt 100_1.txt 100_2.txt 理论最优值 133 334 388 2614 2397 粒子数 20 20 20 100 100 迭代次数 10 20 20 1000 1000 实验结果 133 334 388 2614 2371 从上表可以看到，粒子群算法在求解0-1背包问题上还是比较有效的。 由于0-1背包问题的搜索空间为2n，当物体数为5、8、10、100时，搜索空间的大小分别为32、256、1024、1.31030。而由上表可以看到，粒子群算法在较少的迭代代数下就可以求得较好的解甚至最好的解，所以证明了粒子群算法中的引导信息是有效的。

存在着一个问题，当求解100个物体时，有些数据即使迭代了5000代也达不到最好的值，陷入了局部最优。

实验心得

本文实现的粒子群算法在求解0-1背包问题上虽然相对有效，但并不总能得到最优的解。对于参数的调整还有算法的其它一些方面都还有改进的余地。

通过了这次实验，又了解了另一种高级搜索算法——粒子群算法，以及离散版本的粒子群算法。但是理解还较为粗糙，今后还将进一步加深。

参考文献

[1] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Networks. 1995, vol. 4, pp. 1942–1948.

[2] R.C. Eberhart and J. Kennedy, “A new optimizer using particle swarm theory,” in Proc. 6th Int. Symp. Micro Machine and Human Science, 1995, pp 39-43.

[3] J. Kennedy and R. C. Eberhart, “A discrete binary version of the particle swarm algorithm,” in

Proc. IEEE International Conf. on Syst., Man, and Cybern., 1997, pp 4104–4109.