论文研究-一种求解背包问题的更贪心粒子群算法 .pdf

所需积分/C币:10 2019-08-16 15:43:14 556KB .PDF
4
收藏 收藏
举报

一种求解背包问题的更贪心粒子群算法,赵新超,杨婷婷,将粒子群算法与贪心思想相融合,本文提出一种用于求解0/1背包问题的更贪心混合粒子群算法。对超过背包重量约束的粒子的处理措施是
山国利技论文在线 http://www.paper.edu.cn 58},W-{44,46,90,72,91,40,75,35.8,54,78 VGPSO算法求解背包问题的步骤如下: 40,77,15,61,17,75,29,7563}。 步骤1>用公式(5)产生群体规模为 的初 实例:n=50,C=100,V={220,208,198,192, 始粒子群:和mx,mx]范围内随机均匀产牛粒 180,180,165,162,160,158,155,130,125,122,120,118,1 子的初始速度 15,110,105,101,100.100,98,96,9590,88,82,80,77,75,7 3,72,70,69,66,65,63,60,58,56,50,30,20,15,10,8,5,3,1} ;=1,2,…,);对不满足公式(2) W={80,82,85,70,72 的粒子用策略τX10修正为可行解,再用策略TX0170.6650.5525,50.,540,48,50,32,2260,30,3240,38,3 对粒子群中其余满足公式(2)的粒子进行追加操作 5,32,25,28,30,22,50,30.45,30,60,50,20,65,20,25,30.10 将当前位置作为粒子历史最优位置(),并求出 ,20.25,15,10,10,10,4,4,2,1 实例:n=100,C=6718,V={597,596593 全局最优位置(),置t0。 586,581,68,567,560,549.548,547,529,529,527,520,4 步骤每个粒子用公式(3),(4)计算下一代91,482478475,475,466462459,458,45445144944 的速度(和位置(),继续分别用贪心策略344421.4104095394390377375360361347 TX10和TX01对当前群体中粒子进行修正和追加操334,32,315,31311309296,295294,289,285,2792 77,276,272,248,246,245,238,237,232,231,230,225,19 步骤对个粒子用公式(1)计算其造应度值2,184,183,176.174.171169,165,165,154,153,150,49 fitness(+),并与其史最优位置(的這应141431.1381132.127124,1231.1019 度值 fitness)比较,若较好,则将其更新为当 ,74,63,62,58,55,48,27,2,12,6)} 前粒子的历史最优位置,即(+=(+, W={54,183,106,82,30,58.71,166,117 )=fitness( (+1) 190,90,191,205,128,110,89,63,6,140.86,30,91,156,31, 步骤将粒子的全局最优位置的适应度值与粒子70,199142,98,178,16140,31,24,197,101,73,169,73,9 当前个体最优位置的适应度值比较,用步骤3的同2,159,71,102,144.151,27,131.09,164,17,17,129 样方式更新仝局最优位置 146,17,53,164,146,43,170,180,171,130,183,5 步骤若达到终止条件(搜索到足够好的适应值、,113,207,57,13,163,20,63,12,24,9,42,6,109,1 达到预先设置的最人迭代代数T或者迭代Δ次全70,108,46,69,43,175,81,5,34,146,148,114,160 局最伉位置没冇改变),则算法结束,输出结果, 174,156,82,47,126,102,83,58,34,21,14 含则置t-t+1,转步骤2。 为了比较算法的性能,选择文献中算法GGA、 HGAL1]和算法 GBPSOA[2]进行比较,其中GA、HGA 中参数见参考文献[1],GH0A和V(S0中参数为 5算法实验 为了验证算法的性能,采用文献[1中的 Q=0.8,1=1.3,2=2.8,△=300,各个算法 经典算例,假设物品的规模、价值、重量和背包最在计算机上独立运行20次,保让20次中至少60% 大容纳重量分别为n、V、W、C 的成功牽收敛到最(次)优解的种群规樸(size)和 迭代次①T),比较算法求得的最好结果价值/重量 实例:n-20,C=1000,V={92,4,43,83, (vw),结果如表1 84,68,92,82,6,44,32,18,56,83,25,96.70,48,14, 山国利技文在线 http://www.paperedu.cn 表1:VGPS0算法与HGA、GGA 佳,计算结果表明该算法能够有效求解大规模0/1 GBPSOA算法求解背包问题结果比较 背包问题。进一步的工作是将ⅤGPSO算法的应用 实例1 实例 实例3 从一维扩充到多维问题以及将这种贪心思想应用 Gww1042/8783075/99724864651 B 到其他算法框架中,以使解决更多的实际问题。 30 30 S O 参考文献 A T 500 700 1000 「1贺毅朝,刘坤起,张翠车等,求解背包问题的贪心遗传 vW1037/8743103/1000264876718 算法及其应用.计算机⊥程与设计.第迟卷第11期 G size 100 100 2007,28(11):2655-2657,2681 A [2]叶永春,车林仙,何兵,一种求解0/背包问题的混合粒 T 500 500 500 子群算法,长沙电力学院学报.第21卷第4期,2006, vw1042/878 03/100026559/6717 G size 100 100 100 [3]王晓东,算法设计与分析,北京:清华大学出版社,2003 们]游维,基于贪焚策略的0八背包问题算法研究.计算机与 T 500 500 50(0 现代化.第110期,2007,1:10-16 ww1042878310310026596717 5]Kennedy Eberhart R C, Particle Swarm G OptimizationlCI. Proceedings of IEEE International P size 30 20 onference on Neural Networks, Perth, Australia 200 300 500 通过对不同规模的KP问题实例的实验结果 [6]王丽三晓凯一种非线性改变惯性权重的粒子群算法 可以看出,随着KP问题规模的增大,HGA 计算机工程与应用2007,43(4):47-48 GBPSOA算法的性能急剧变差,比GGA和ⅴGPSO 郝式伟曾建潮基于聚类分析的微粒群算法计算机工 算法表现的差距越来越大,因此HGA和 GBPSOA 程与应用2008,44(201:41-44 不太适合求解大规模背包问题。算法GGA和 [8]喻学才,张出文,多维背包问题的一个蚁群优化算法 ⅤGPSO能找到最优解,但是遗传算法参数多且 计算机学报.第31卷第5期,2008,5:810-819 参数近择严重影响解的品质,所以相比对遗传算法 [9]Szu H H, Hartley R L, Fast Simulated Annealing, 的改进,对粒子群算法的改进更容易实现。显然, Physics Letters A, 1987, 122: 157-162 获得最终解的算法讼代次数和粒子群规模方面表 L10]Ingber L, Very fast sinulated reannealing, Mathl 明ⅤGPSO能以较小群体规模较快的收敛于问题的 CompuT.Mode1lirg,1989,12(8):967-973 最优解,所以ⅤGPSO更适合求解大规模背包问题 [1冂]沈显君,王仹武,郑波尽等,基于改进的微粒群伏化算 法的01背包问題求解,计算机T程,2006,第32卷第18 结束语 期,9:23-24 VGPSO算法基于粒子群算法和贪心思想,每 [12] Kennedy J, EberhartR C Swarm intelligence[M], Morgan 迭代一次将贪心思想应用两次,比通常贪心算法更 Kaufmann publishers 2001 贪心”,这样増强了算法精细搜索的能力,提高 了搜索到最优解的概率。该算法实现简单,效果极 山国技记文在线 http://www.paperedu.cn ZHAO Xinchao. YANG Ting-Ting Department of Mathematics, School of Science, Beijing University of Posts and Telecommunications, Optic Communication and Optoelectronics Institution, Beijing University of Posts and Telecommunications, Beijing 100876, China E-mail:xcmmrc(@gmail.com Combining particle swarm optimization algorithm and greed idea, a Very greedy Particle Swarm Optimization algorithm (VGPSO) is proposcd for knapsack problcm(KP). The strategy of dealing the overweight particle is to take out the enclosed and the worst goods in ratio between value and weight, until to satisfy the weight constraint. Simultaneously, the question of sensitive parameter's choice is avoided under this measure. The strategy of managing the feasible particle is to enclose the goods which is out of knapsack and best in ratio between value and wcight, until nonc goods can be put into. Bascd on thc classic instances in thc rcfcrcncc numcrical experiments are made and compared with other algorithms. The vgPso is better than hybrid genetic algorithm(HGA), greedy genetic algorithm(GGA) and greed binary particle swarm optimization algorithm(GBPSoa)in Ref [1, 2] in the ability of finding optimal solution, the efficiency and the robustness knapsack problcm; particlc swarm optimization; vcry greed idca

...展开详情
试读 5P 论文研究-一种求解背包问题的更贪心粒子群算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39841882 你的留言是对我莫大的支持
2019-08-16
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-一种求解背包问题的更贪心粒子群算法 .pdf 10积分/C币 立即下载
    1/5
    论文研究-一种求解背包问题的更贪心粒子群算法 .pdf第1页

    试读结束, 可继续读1页

    10积分/C币 立即下载 >