论文研究 基于分工合作和搜索空间重构的粒子群优化.pdf

针对粒子群算法早熟收敛及后期收敛速度慢的缺点，提出一种基于分工合作和搜索空间重构的改进粒子群算法。首先基于分工合作的思想，对不同性能的粒子赋予不同的惯性权值，从微观上提高粒子搜索效率；同时，每当种群迭代到一定次数时，对搜索空间进行自适应重构，从宏观上提高种群的后续搜索效率，并适度重新初始化种群，恢复种群多样性。以4个经典测试函数对算法性能进行了测试比较。仿真结果表明，该算法明显提高了收敛效率，改善了求解质量。王刚,张定华,陈冰:基于分工合作和搜索空间重构的粒子群优化2010,46(2)53f2(x)=∑2-10c05(2rx)+10很大程度上决定于前10%左右的最差解(算法可能陷于局部最优);因此,比较算法性能时,不能只比较MBF值,更要比是一个多峰的、存在许多局部最小的非线性函数,相当于给较DF。Sphere函数加入了正弦噪声。由表1可见,对于BF、MBF值, CRPSO比LPSO精度一般要(3) Griewank函数高出约1~2个数量级。对于DF,LPSO的解50%~80%左右都集中于某一范围,而同样条件下, CRPSO的解分散于更优区域,得f3(4000∑x2-∏Cosi=1到更优解的慨率比LPSO要大约30%~60%。是一个多峰的、存在许多局部最小的、自变量之间互相影响的图1为D=20、M=40、Tm=1000时,两种算法对各函数的典型的非线性多模态函数,具有广泛的搜索空间、大量的局部典型进化曲线。由图可见, CRPSO的收敛能力要优于LPSO。另极小点。外,在CHⅣSO算法的种群进化过程中,有时会出现倒退现象,(4) Rosenbrock函数扣进化曲线回跳。这是因为 CRPSO算法在对种群进行重新初始化时,新种群的位置在一定程度上是随机的。式(10)的后两f(x)=2100x1-2)2+(x1-1)项减弱∫这种凹跳趋势。而限制重新初始化次数的策略,能够是一个倒马鞍形、单峰、非凸、病态的非线性函数,在谷底很大保证最终得到的不会是回跳”后的解。范围内存在很多与全局最优非常接近的值,一般的优化算法很从总体上看, CRPSO算法的抗早熟能力和收敛速度要明难找到全局最优。显优于LPSO算法。单峰函数的 Sphere函数和 Rosenbrock函数可以检验算法的局部搜索能力,多峰的 Giewank函数和 Rastrigin函数,可以5结论用于检验算法的综合(全局、局部)搜索能力。针对PSO算法易于早熟及后期收敛速度慢的缺点,在不测试时,两种算法均设置c1=c2=-1.6,w=0.4~09。各项测试改变PSO算法本身概念简单的基础上,提出了一种惯性权值分里,两种算法各运行1000次。分别设定空间维数D=10、20、工调整及搜索空间重构的改进算法 CRPSO。通过4个典型的30,种群规模M=3D,全局最大迭代次数T=50D,统计出两种非线性测试函数,验证了 CRPSO算法在寻优和收敛速度上均算法对各测试函数得到的最优适应度( Best fitness,BF)、平均有明显提高。最优适应度( Mean best fitness,MBF)、最优适应度的分布情况对PSO算法做了性能上的改进,如何把改进后的算法成功( Distribution of fitnesses,DF)。结果见表1。地应用到实际工程(如排产优化、车间布局优化加工参数优化在1000次实验里,由于“木桶短板效应”,算法的MBF值等)中将是下一步的研究。表1测试结果Function OptimizerMBFf>10f>109f1>102f>1015f>1018f>102f1021LPSO1.21E-241.01E-09%5.3%24.5%32.2%30.4%6.6%D=10CRPSO14E-258.03E-1001.1%5.1%19.8%34.6%31.4%LPSO4.35E-211.14E-117%12.5%45.7%34.9%5.5%0.7%D=20CRPSO1.05E-25229E-131.9%22.1%47.4%25.8%1.35E-18252E-1002.3%40.2%51.8%5.7%D=30CRPSO299E-211.04E-117.7%54.8%33.4%f2>0fx<0LPSO1.99E+013.720.4%15.4%44.9%30.9%8.4%D=10CRPSO4.78E-132.41.3%69%6.4%22.3%16.1%47.0%LPSO6.96E+035.0413.4%73.6%12.8%0.2%D=20CRPSO8.89F-55.481.1%79%14.8%51.9%124%79%LPSO1.99E+158.5763.3%36.6%0.1%D=30CRPSO1.28E-319.749.0%20.6%29.8%28.4%11.7%0.4%0.1%f>10f>102f3>103fs>104f>1f3>f10LPSO7.40E-031.01E-1417%57.5%0.8%00D=10CRPSO7.85E-134.82E-31%4.0%26.2%46.1%17.1%3.6%LPSO1.00E-162.66E-214%67.3%13.5%00.2%17.6%D=20CRPSO1.72E-112.78E-31.3%8.9%18.2%20.3%17.3%14.6%19.LPSO1.00E-161.63E-20.348.7%15.9%035.1%D=30CRPSO2.26E-12976E-32.3%11.6%23.8%17.1%15.7%12.2%17f>103f4>10分>103f>102f>LPSO6.583.10E+8.6%5.8%120%21.8%36.5%2.4%D=10CPSOE-11.37E+10001.2%15.1%83.4%0.3%sS01.93E-15.47E+615.2%11.8%11.3%17.2%394%CRPS5.75E+03.59E+10.2%3.4%95.4%1.0%LPSO2.40E+06.55E+618.2%10.7%10.2%18.1%41.9%D=30CRPSO1.68E+13.01E+207.6%27.4%65.0%542010,46(2)Computer Engineering and Applications计算机工程与应用10SphereRiastrigrin--“----·---CRPSOCPSO注温汀200迭代次数次迭代次数次GriewankRosenbrock4LPSOLPSO创出CRPSOCRPSO~------------------------80010002004008001000迭代次数/次迭代次数次图1进化曲线(D=20,M=40,T=1000)参考文献:using cooperative particle swarm optimisers[ C]/Proceedings of the[I] Kennedy J, Eberhart R Particle swarm optimization[C/EEE Inter3rd Genetic and Evolutionary Computation Conference, San Fran-national Conference on Neural Networks. Perth, Australia, 1995cIsco,200l:126-1311942-1948Sun Jun, Feng Bin, Xu Wen-bo, et al. Particle swarm optimization[2] Eberhart R, Kennedy J. A new optimizer using particle swarm theowith particles having quantum behavior[ Cy/Congress on Evolutiona-ry[ Cp/proceedings of the 6th International Symposium on Microry Computation, 2004: 134-138[8 Shi Yu-hui, Eberhart R A modified particle swarm optimizer[C]/Machine and human Science. 1995: 39-43Proceedings of IEEE International Conference on Evolutionary3]曾建潮,介倩,催志华微粒群算法M北京:科学出版社,2004Computation, Anchorage, Alaska, USA, 1998: 69-73[4] Angeline P J Using selection to improve particle swarm optimiza-9 Eberhart R, Shi Yu-hui. Comparing inertia weights and constrictionC/Proceedings of Congress on Evolutionary Computation, Pisfactors in particle swarm optimization[C]//Proceedings of the 2000cataway, NJ, 1999: 84Congress on Evolutionary Computation. San Diego, USA: [s n. 2000[5 Suganthan P Particle swarm optimizer with neighborhood operator Cy/84-88Proceedings of Congress on Evolutionary Computation, Piscataway, [10) Parsopoulos K E, Vrahatis M N Parameter selection and adapta-N,1999:1958-1961tion in unified particle swarm optimization[J]. Mathematical and16]Van den Bergh F, Engelbrecht A Training product unit networksComputer Modeling, 2007, 46: 198-213(上接38页)偶码利用降维算法构造岀其子码链及导岀其L-链,进而得到45个参数达到文献Ⅳ中的量子码界的量子码。其中[20,4,64量了码构造22,8,5J],[24,2,7],[24,8,5],[26,8,5],26,10,5]超过文利用定理1及文献[1,可以构造量子码如下。献[中量子码参数的下界,改进了文献[量子码的参数结果定理2存在如下量子码(表3)。26,10,5],28,12,5]在参数d不变的情况下改进文献[8]的表320≤n≤30的偶码长量子码[26,8,5],[28,10,5]的参数k。偶码长量子码参数20120,0,8,20,2,6,20,4,6,20,6,5],[20,8,4],[20,10,41,参考文献:20,12,3[1 Calderbank A R, Rains E M, Shor P W,et al. Sloane quantum error22,0,8],[22,2,6,22,4,6,[22,6,5],[22,8,5],[2,10,4]correction via code over GF(4)[J]. IEEE Trans Inform Theory, 1998, 44:22,14,324,0,8,[24,2,,Ⅱ24,4,6,[124,6,6,[124,8,5],[24.10,4],1369-1387.2424,12,4,[24,16,32 Gulliver T AOptimal double circulant self-dual code over F4lJI26126,0,8,[26,6,6,[26,8,5],26,10,5],[26,12,4l,26,14,4],IEEE Trans Inform Theory, 2000, 46: 271-27426,18,3]28,0,10],[28,2,10,[28,6,6,[128,8,6,[28,10,5],[28,12,引],[3] Kim J L New self-dual codes over GF(4) with the highest known28,16,4],28,20,3minimum weights[].IEEE Trans Inform Theory, 2001, 47: 1575-15803030,0,12,30,6,6],[30,8,6],30,10,5N30,12,5],[30,16,4],[4] Lam C WMH, Pless V. There is No(24, 12, 10)self-dual quater30,18,4],[30,22,3nary code[J]IEEE Trans Inform Theory, 1990, 36: 1153-1156定理2给出的45个量子码都达到了文献[中的量子码5 Ostergard PR I. There exists no hermitian self- dual quaternary的界。26, 13, 101 code[JIEEE Trans Inform Theory, 2004, 50: 3316-3317囿6李瑞虎加性量子纠错码的研究[D西安:西北工业大学,2004「7]王雷,冯有前,李益群.F上的短码长的自正交码链门计算机工程5结论与应用,2007,43(34):88-91研究由已知自正交码构造新自正交码的生成矩阵降维方8]郭罗斌,贺筱军,李瑞虎,等距离为6的二元自对偶码的子码肌计法,提出可行的降维算法。对GF(4)上码长20≤n≤30的自对算机工程与应用,2008,44(11):34-36