背包问题pso实现报告

《背包问题pso实现报告》由会员分享，可在线阅读，更多相关《背包问题pso实现报告（6页珍藏版）》请在装配图网上搜索。

1、PSO应用于背包问题的实验设计报告一、背包问题的描述1.1背包问题的概念描述背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定 一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得 物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题 经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包 问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V?它是在1978 年由Merkel和Hellman提出的。由于它的实际应用性，因此被广泛应用于算法的实验。本文将通

2、过利用pso算法来实现 背包问题。1.2背包问题数学描述背包问题就是在总的体积有限的条件下，追求总价值最大的有效资源分配问题。因此我们可以把背包问题整数化为整数0-1问题，定义变量：0携带第i个物品(一 2)Xi I不携带第个物品，n目标函数转化为：max；工c x I i=1丿约束条件：sFT X (t +1)= X (t)+ V (t +1)iii其中，c，c为正常数，称为加速因子；rand()为(0,1之间的随机数；w为惯性因子；1 2 2. t表示某一次迭代；P为粒子的最优位置；P为种群最优位置Ij2.2背包问题的pso算法描述背包问题中的X是一个0-1序列，每一个粒子的位置可以用向量

3、X来表示，粒子的位置 就表示一个可行解，粒子的适应值函数就可以表示为f(X)=丫 vx,(背包内物品的价值总和)i ii=1粒子群算法的寻优可以表示为求取使得f (X)值最大的X粒子群中的速度定义为物品选择的变换集，即为两次位置的距离，用V表示，则IVI表 示速度所含的交换的数目，从而该速度可定义为V = X X = v I v g 4),1 i = (1,2, , n)其中12i if0 : x = xV = s1i2ii I 1 : X 丰 XV1i2i以此作为用粒子群算法解决背包问题的切入点，待解决的背包问题如下所示：0-1背包问题：对于n个体积为ai、价值分别为ci的物品，如何将它们装

4、入总体积为b 的背包中，使得所选物品的总价值最大。三、实验设计过程3.1初始化过程在此试验中，我们初始化数据如下所示：n=10，在此次试验中选择10个物品进行实验；ai=95, 4, 60, 32, 23, 72, 80, 62, 65, 46,初始化这 10 个物品的体积大小；ci=55, 10, 47, 5, 4, 50, 8, 61, 85, 87，初始化这 10 个物品的价值；b=269，背包最大允许体积；3.2实际matlab程序如下所示：%0-1背包问题:对于n个体积为ai、价值分别为ci的物品，如何将它们装入总体积为b的背 包中，使得所选物品的总价值最大。%n = 10%aj=9

5、5, 4, 60, 32, 23, 72, 80, 62, 65, 46%cj=55, 10, 47, 5, 4, 50, 8, 61, 85, 87%b=269%a=95 4 60 32 23 72 80 62 65 46;% 物品的体积c=55 10 47 5 4 50 8 61 85 87;% 物品的价值b=269;%背包的重量限制%初始化程序：Dim=10; %粒子的维数 xSize=20;% 种群数MaxIt=30;%最大迭代次数c1=0.7;c2=0.7; %定义加速因子 w=0.8;%定义惯性因子A=repmat(a,xSize,1);% 将 a 扩展成一个 20*10 的矩阵

6、C=repmat(c,xSize,1);% 将 c 扩展成一个 20*10 的矩阵 x=round(rand(xSize,Dim);%随机取一个20*10的0/1矩阵作为粒子的初始位置- 随机的选取n个物品中哪些作为被选物品，对应位置值为1即表示被选 v=rand(xSize,Dim);%粒子的初始速度 xbest=zeros(xSize,Dim); %单个粒子的初始最佳位置 fxbest=zeros(xSize,1);%xbest 的适应度 gbest=zeros(1,Dim);%粒子群的初始最佳位置 fgbest=0; %gbest的适应度%粒子群最优位置和单个粒子最优位置的选定%迭代循环

7、算法：iter=0;while iterMaxItiter=iter+1; fx=sum(C.*x) %计算粒子群的适应度，即背包内物品的价值 sx=sum(A.*x) %限制函数，背包内物品的体积for i=1:xSizeif sx(i)269fx(i)=%当被包内物品的体积超过限制时，将期适应度设置为0endendfor i=1:xSizeif fxbest(i)fx(i) fxbest(i)=fx(i);xbest(i,:)=x(i,:%当粒子的适应度fx(i)大于其最佳适应度时 fxbest(i),用其替代原来粒子的最佳适应度，并记下此解endendif fgbestmax(fxbes

8、t) fgbest,g=max(fxbest);gbest=xbest(g,: %当存在粒子的最佳适应度fxbest(g)大于种群的最佳适 应度时，用其替代原来种群的最佳适应度，并记下此解endfor i=1:xSizeif x(i,:)=gbest x(i,:)=round(rand(1,Dim)%为防止算法陷入局部最优，若某个粒子 的位置等于种群最佳位置，将对该粒子的位置重新初始化赋值endendRl=rand(xSize,Dim);R2=rand(xSize,Dim); v=v*w+c1*Rl.*(xbest-x)+c2*R2.*(repmat(gbest,xSize,1)-x) %用速

9、度 迭代公式产生新的速度x=x+v %更新粒子群的位置for i=1:xSizefor j=1:Dimif x(i,j)0.5x(i,j)=0;else x(i,j)=1;endendend%由于粒子的位置只有(0,1)两种状态,此处以0.5为分界点对函数值进行离散化 end%fgbestsgbest=sum(a.*gbest)Gbest3.3实验仿真结果(最好结果)fgbest =295sgbest =269gbest = 1101100011四、调试实验4.1改变最大迭代次数，其他不变改变迭代最大次数MaxIt，调试10次取其平均值结果如下所示:测试结果MaxIt3050100200fgb

10、est的最大值295295295295sgbest的最大值269269269269fgbest的平均值289.9284288.4274.2sgbest的平均值266.6263.4263.2263.2gbest的最好值0111000111011100011101110001110111000111测试效果显示，简单的粒子群算法对于多群体以及复杂问题的效果不是很好，应该做些 改进。4.2迭代次数不变，修改PSO参数：c1=c1e-iter.*(c1e-c1s)/MaxIt;c2=iter.*(c2e-c2s)/MaxIt+c2s; w=wmax-(wmax-wmin).*iter/MaxIt;4.

11、2.1权重因子的取值在速度更新公式中由3个部分构成。第1个部分是Vi,表示粒子在解空间有按照原有方 向和速度进行搜索的趋势，这可以用人在认知事物时总是用固有的习惯来解释。第2个部分是c1*R1.*(xbest-x),表示粒子在解空间有朝着过去曾碰到的最优解进行搜 索的趋势，一般按c1从cle线性递减到cls，(一般c1e的范围是0.9-0.8， c2s的范围是 0.3-0.5),因为前期整个群体的经验值不足，这样有利于群体在前期只根据自己的经验值搜 索更大的空间。第3部分是c2*R2.*(repmat(gbest,xSize,1)-x),表示粒子在解空间有朝着整个邻域过 去曾碰到的最优解进行搜

12、索的趋势，一般取c2从c2s线性递增到c2e (一般c2e的范围是 0.9-0.8, c2s的范围是0.3-0.5),因为在迭代后期整个群体的经验值比较丰富，在此时c1 值比较少而c2值比较大，有利于整个群体根据群体的经验值搜索到最优解。4.2.2惯性权重函数w的取值wmax，wmin分别是W的最大值和最小值；it er，Maxi t分别是当前迭代次数和最大迭代 次数。通常调整W对于PSO算法的收敛性起到很大的作用。当W大时，则速度V就小，有利于粒子搜索更大的空间，可能发现新的解域；反之，W 越小时，则速度V就越小，有利于在当前解空间挖掘更好的解。因此，在迭代开始时设W=wmax，W在迭代过程中逐渐减小，直到W=wmin。这样使PSO 更好控制探索与开发，在开始优化时搜索较大的解空间，得到合适的种子，然后在后期逐渐 收缩到较好的区域进行更精致的搜索以加快收敛速度。根据前人的经验可设置 wmax=0.90.8, wmin=0.10.4.4.2.2 10次测试仿真结果如下：测试项目修改之前修改之后fgbest的取大值295295sgbest的取大值269269fgbest的平均值278.4293.5sgbest的平均值264.7261.3从测试效果可以看出，修改PSO参数后效果有所提高。