关于0-1背包问题的粒子群优化算法-张蓉蓉

：（1984-），，，，；（1982-），，，，；（1984-），，，，。0/1，，（，430074）：，，。，0/1，。：；：TP312：A：1672-7800（2009）05－0060－021，，，。：NM，wi，ixi，pixi（0≤xi≤1，pi≥0），？M。xi01，，，0/1。，、、、。NP，2n，O（2n）。，，。22.1（ParticleSwarmOptimization，PSO），。，：。。。，。2.2PSO，，“”。，，。，。，，，。2.3PSO，（），。，“”。“”，，pbest；，gbest。，：vk+1=c0vk+c1（pbestk-xk）+c2（gbestk-xk）（1）xk+1=xk+vk+1（2），vk；pbestk；gbestk。vk+1vk、pbestk-xkgbestk-xk，1。1vmax（vmax0），vmax，SoftwareGuide8%620096Vol.8No.6Jun.20096vmax。（1）c0，c1，c2，c0，，，，（0，1）；c1，c2，pbestgbest，（0，2）。2.4：①，n，nn，n；②；While（）do；③；pbest，pbest；④pbestgbest；⑤①，，vmax；⑥②，。End230/13.10/1maxni=1Σpixini=1Σcixi≤Cxi=0，1（i=1，2，3，…，n）X（x1，x2，…，xn）T，，。0/1，，，：（1）c0vk，，c1（pbestk-xk）+c2（gbestk-xk），。3.2①old1old2，old2；②old1old2。old1=100101111001，old2=011010101100，01011，new1=1001001011013.3①X（x1，x2，…，xn），（xi+xi+1，…，xj）；②xj←xj。100101111001，4，10000111001。3.40/1①np，nmax，npX0；②l0，plbest，pxbest，plbest，glbestgxbest。While（nmax）do；forj=1tonp；③jX0（j）gxbestX1（j）；④X1（j）pxbestX1（j）；⑤X1（j）；⑥l1；⑦X1（j）plbest（j），pxbest（j）=X1（j），plbest（j）=l1（j）；End；（8）plbest，glbestgxbest；⑨x0←x1；End；⑩glbestgxbest。：，，O（3np）（），nmax，O（3npnmax）。4：n=10，C=269g，{p1，p2，…，p10}={55，10，57，5，4，50，8，61，85，87}，{c1，c2，…，c10}={95，4，60，32，23，72，80，62，65，46}g。295，X*={0，1，1，1，0，0，0，1，1，1}。（100）：np=10，nmax=10，295，246，28。np=20，nmax=30，295，294，98。5，，，。，，，，。，，。，，。：［1］，，.［M］.：，2000.［2］，.［M］.：，2004.，，：0/161··ParticleSwarmOptimizationabout0/1KnapsackProblemAbstract：AsatypicalcombinatorialoptimizationprobleminOperationsResearch,knapsackproblemhasabroadbackgroundandmanydifferentwaystosolve.ThispaperprovidesamethodbasedonPSOandthismethodusessomeideasaboutGeneticAlgorithmtoapplyPSOinknapsackproblemandgainedbetterresults.KeyWords：KnapsackProblem;PSO［3］，.［M］.：，2006.［4］，.0/1［J］.，2005（10）.［5］.0/1［J］.，2005（12）.（：）：(1975-)，，，，，。（，451191）：，、（A*），:，、。：;;;A*;：TP312：A：1672-7800（2009）06－0062－030，，，（）（），，。：，。，，；，，，，A*。，，，、。1：3×31、2、3、4、5、6、7、8，。（）（），1。1，。1，7。，4，、、、。（4）。，，。SoftwareGuide8%620096Vol.8No.6Jun.2009