《粒子群解决背包问题.doc》由会员分享，可在线阅读，更多相关《粒子群解决背包问题.doc（3页珍藏版）》请在金锄头文库上搜索。
1、PSO解决0-1背包问题背包问题是经典的NP-hard组合约束优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用。通常求解背包问题的方法有基于深度优先搜索的回溯法、基于广度优先搜索的分支界限法、动态规划法和基于 SIMD共享存储的并行算法，这些都是很成熟的确定性优化方法。随着问题规模的增长，求解背包问题的时间复杂性增长非常快，因此，设计新的高效算法来求解背包问题，具有重要的理论和实际意义。粒子群优化算法(Particle Swarm Optimization，PSO)是一种基于群智能的随机优化技术，在连续域优化问题中已经取得了比较成功的应用，但是在离散域优化上的应用相对
2、较少，本文尝试利用粒子群优化算法求解0-1背包问题。一、粒子群算法的基本原理粒子群优化算法于1995年由Eberhart博士和Kennedy博士提出。在PSO算法中，每个优化问题的解都是搜索空间中的一个“粒子”，算法初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第1个是粒子本身所找到的最优解，称为个体极值xBest，另一个极值是整个种群目前找到的最优解，称为全局极值gBest。在基本粒子群优化算法中，粒子群在一个D维空间中搜索，粒子的总数为n，每个粒子的速度和位置按如下公式进行变化：其中：第k次迭代后粒子i飞行速度矢量的第d维分量；
3、：第k次迭代后粒子i位置矢量的第d维分量；：粒子i个体最好位置xBest的第d维分量；：群体最好位置gBest的第d维分量；，：权重因子；，：随机函数，产生0，1的随机数；：惯性权重函数。式(1)主要通过3部分来计算粒子i的新速度：粒子i前一时刻的速度，粒子i当前位置与自己最好位置之间的距离，粒子i当前位置与群体最好位置之间的距离。粒子i通过式(2)计算新位置的坐标。通过式(1)决定粒子i下一步的运动位置。二、基于0-1背包问题描述背包问题的描述如下：是第i个物品的体积，b是背包的体积，是第i个物品的价值。 本文中所考虑的是0-1背包问题的PSO求解，其数学模型建立如下： 目标函数： 约束条件
4、：三、算法的实现取粒子维数D=20，粒子数n=40，最大代数gnmax=50，加速因子c1=2.0、c2=2.0，惯性权重w=0.8。物品体积和价值可表示为向量：a=92, 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58；c=44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63。通过A=repmat(a,n,1)语句可将a扩展成40*20的矩阵，每一行代表一个粒子，同理也将c扩展成40*20的矩阵
5、C。随机产生初始位置和初始速度，并将单个粒子的初始最佳位置xbest，xbest的适应度fxbest，粒子群的初始最佳位置gbest以及gbest的适应度fgbest都定义为0。然后按照粒子群算法的原理开始循环。在循环过程中更新单个粒子最佳适应度，粒子群最佳适应度，并且计算背包内物品体积是否超过限制,如果超出则将其适应度改为0。最后显示fgbest，即包内物品价值；sgbest，包内物品质量；gbest，显示最佳选择物品方案，1代表选择，0代表不选择。四、结果fgbest = 1024sgbest = 871gbest = Columns 1 through 20 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1图 1五、结果分析与其它进化计算方法相比，PSO算法具有收敛速度快，设置参数少，程序实现异常简洁等优点。但同时由于PSO算法在优化过程中所有粒子都向最优解的方向飞去，所以粒子趋向同一化，群体的多样性逐渐丧失，致使后期算法的收敛速度明显变慢，甚至处于停滞状态，因而很容易陷入局部最优解，也就难以获得较好的优化结果。
