粒子群解决背包问题.pdf

《粒子群解决背包问题.pdf》由会员分享，可在线阅读，更多相关《粒子群解决背包问题.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、PSOPSO 解决解决 0-10-1 背包问题背包问题背包问题是经典的 NP-hard 组合约束优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用。通常求解背包问题的方法有基于深度优先搜索的回溯法、基于广度优先搜索的分支界限法、动态规划法和基于 SIMD共享存储的并行算法，这些都是很成熟的确定性优化方法。随着问题规模的增长，求解背包问题的时间复杂性增长非常快，因此，设计新的高效算法来求解背包问题，具有重要的理论和实际意义。粒子群优化算法(Particle Swarm Optimization，PSO)是一种基于群智能的随机优化技术，在连续域优化问题中已经取得了比较成功的

2、应用，但是在离散域优化上的应用相对较少，本文尝试利用粒子群优化算法求解 0-1 背包问题。一、粒子群算法的基本原理一、粒子群算法的基本原理粒子群优化算法于 1995 年由 Eberhart 博士和 Kennedy 博士提出。在 PSO 算法中，每个优化问题的解都是搜索空间中的一个“粒子”，算法初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己，第 1 个是粒子本身所找到的最优解，称为个体极值 xBest，另一个极值是整个种群目前找到的最优解，称为全局极值 gBest。在基本粒子群优化算法中，粒子群在一个 D 维空间中搜索，粒子的总数为n，

3、每个粒子的速度和位置按如下公式进行变化：其中：第 k 次迭代后粒子 i 飞行速度矢量的第 d 维分量；：第 k 次迭代后粒子 i 位置矢量的第 d 维分量；：粒子 i 个体最好位置 xBest 的第 d 维分量；：群体最好位置 gBest 的第 d 维分量；，：权重因子；，：随机函数，产生0，1的随机数；：惯性权重函数。式(1)主要通过 3 部分来计算粒子 i 的新速度：粒子 i 前一时刻的速度，粒子i 当前位置与自己最好位置之间的距离，粒子 i 当前位置与群体最好位置之间的距离。粒子 i 通过式(2)计算新位置的坐标。通过式(1)决定粒子 i 下一步的运动位置。二、基于二、基于 0-10-1

4、 背包问题描述背包问题描述背包问题的描述如下：是第 i 个物品的体积，b 是背包的体积，是第 i 个物品的价值。本文中所考虑的是 0-1 背包问题的 PSO 求解，其数学模型建立如下：目标函数：约束条件：三、算法的实现三、算法的实现取粒子维数 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,

5、17,75,29,75,63。通过 A=repmat(a,n,1)语句可将 a 扩展成 40*20 的矩阵，每一行代表一个粒子，同理也将 c 扩展成 40*20 的矩阵 C。随机产生初始位置和初始速度，并将单个粒子的初始最佳位置 xbest，xbest的适应度 fxbest，粒子群的初始最佳位置 gbest 以及 gbest 的适应度 fgbest 都定义为 0。然后按照粒子群算法的原理开始循环。在循环过程中更新单个粒子最佳适应度，粒子群最佳适应度，并且计算背包内物品体积是否超过限制,如果超出则将其适应度改为 0。最后显示fgbest，即包内物品价值；sgbest，包内物品质量；gbest，显示最佳选择物品方案，1 代表选择，0 代表不选择。四、结果四、结果fgbest=1024sgbest=871gbest=Columns 1 through 201 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1图 1五、结果分析五、结果分析与其它进化计算方法相比，PSO 算法具有收敛速度快，设置参数少，程序实现异常简洁等优点。但同时由于 PSO 算法在优化过程中所有粒子都向最优解的方向飞去，所以粒子趋向同一化，群体的多样性逐渐丧失，致使后期算法的收敛速度明显变慢，甚至处于停滞状态，因而很容易陷入局部最优解，也就难以获得较好的优化结果。