求解线性约束问题的微粒群优化算法.pdf

《求解线性约束问题的微粒群优化算法.pdf》由会员分享，可在线阅读，更多相关《求解线性约束问题的微粒群优化算法.pdf（5页珍藏版）》请在三一文库上搜索。

1、求解线性约束问题的微粒群优化算法 陈战平 1, 2 ( 1 . 南京师范大学 计算机科学与技术学院, 江苏 南京 210046; 2 . 江苏省信息安全保密技术工程研究中心, 江苏 南京 210097) 摘要 ?直接用微粒群算法求解约束优化问题存在收敛速度慢和精度低的缺点, 研究了一种求解线性约束问题的微粒群优 化算法. 通过引入拉格朗日乘子将约束优化问题转化为无约束优化, 先利用拉格朗日对偶原理, 将拉格朗日乘子和优化参数分 离出来, 然后分别采用微粒群算法进行优化. 另外, 为了使微粒群算法更好地收敛到全局最优解, 设计了一个突变的微粒群算 法. 最后通过低通滤波器的设计证明该方法的效果优

2、于不带约束的微粒群算法. 关键词 ?线性约束, 优化, 微粒群算法 中图分类号 TP301?6?文献标识码 A ?文章编号 1672?1292(2010) 04?0026?05 Particle Swarm Algorithm for Linear Constrained Opti m ization Proble m Chen Zhanping 1, 2 ( 1. School of Computer Science and T echnology, Nanjing N or malUniversity, Nanjing 210046 , China ; 2 . Jiangsu Resear

3、ch Center of Infor mation Security and Privacy T echnology, Nanjing 210097, China) Abstract : The shortage in slow convergence rate and low convergence precision existwhen the particle swar m algorithm is directly used to solve the constrained opti m ization proble m.In this paper , we are concerned

4、 with an new particle swar m algorithm, which can be used to solve the linear constrained problems .In our method ,the constrained opti m iza? tion proble m is first translated into a non?constrained opti m ization one by introducing the Lagrangemultipliers , and then by using the Lagrange duality p

5、rinciple ,the Lagrange multipliers and opti m ization parameters are separated , which w ill be opti mized respectively by using the particle swar m algorithm. M oreover ,in order tomake the particle swar m algorithm converge to the global opti m ization solution, an i mproved particle swar m algori

6、thm w ithmutation is proposed. Finally , a design exa mple of a lo w?pass FI R filter shows that ourmethod is better than the particle swar m algorithm w ithout con? straints. K ey words :linear constraint , opti mization, particle swar m algorithm ? 收稿日期: 2010?08?06 . 通讯联系人: 陈战平,讲师, 研究方向: 测控系统与计算机管

7、理信息系统的开发与应用. E? ma i:l czpcjx 163 . com ? 标准微粒群算法在优化过程中, 种群中的最优解常常几代都无变化, 这很容易产生 ?早熟 现象, 使优 化过程陷入局部最优 1 , 2. 另外, 在科学研究和工程实践中, 许多优化问题都带有一定的线性约束条 件 3?5. 直接使用微粒群算法求解时, 为了满足约束条件, 需要对初始产生种群的个体以及新产生的个体进 行约束条件判断, 不满足约束条件的个体就舍去并重新产生, 直到满足约束为止. 这种方法在保证种群满 足约束的同时, 明显地影响了微粒群算法的求解速度, 可能将一个最优解丢弃了. 为了使微粒群算法能更 好地收

8、敛于全局最优解, 并能快速、 准确的求解带线性约束的优化问题. 本文对微粒群算法进行了改进, 改 进后的微粒群算法在找到每代的最优解时, 保留最优解, 并对种群进行变异, 以扩大寻优的空间, 使微粒群 算法能更好地收敛于全局最优解. 同时, 为了更好的解决带约束线性约束的优化问题, 引入拉格朗日乘子 法, 将线性约束的优化问题转化为无约束的优化问题, 再利用对偶原理 6 能精确地解决线性问题的特性, 对拉格朗日乘子和要求解的问题分别用改进的微粒群算法优化. 该方法很好的解决了一般微粒群算法不 易求解的约束线性问题. 并通过对带线性约束的 FI R滤波器的优化设计, 验证了该方法的有效性. !2

9、6! 第 10卷第 4期 2010年 12月 ? 南京师范大学学报 (工程技术版 ) JOURNAL OF NAN JI NG NORMAL UNI VERSI TY( ENG I NEER I NG AND TECHNOLOGY ED I T I ON) ? Vo. l 10 No. 4 Dec , 2010 1? 微粒群算法的改进 微粒群算法将寻优的参数组合成群体, 再通过环境的适应度使群体中的个体向好的区域移动. 微粒群 的个体 (这里称作微粒 ) 代表问题的一个可能解, 每个微粒具有位置和速度两个特征. 设 D维搜索空间中, 第 i个微粒位置可以表示成Xi= xi1, xi2, , x

10、i D, 微粒的速度表示成 Vi= vi1, vi2, , viD. 微粒位置坐标 对应的目标函数值即可作为该微粒的适应度, 算法通过适应度来衡量微粒的优劣. 算法首先初始化一群随 机微粒, 然后通过迭代找到最优解. 在每一次迭代中, 微粒通过跟踪两个 ?极值 来更新自己: 一个是微粒 本身所找到的最优解, 即个体极值 Pi= pi1, pi2, , pi Di; 另一个是整个微粒群目前找到的最优解, 称之为 全局极值 Pg= pg1, pg2, , pgDi, 最后输出的 Pg就是算法得到的最优解. 微粒在每一次迭代中找到上述 两个极值后, 微粒通过一定规则进化, 以第 i个微粒的第 j维从

11、 n代进化到 n + 1代为例: v n+ 1 ij= v n ij+ c1r n 1(p n ij- x n ij) + c2r n 2(p n gj- x n ij),( 1) v n+ 1 ij= vmax, if v n+ 1 ij vm ax, v n+ 1 ij= - vmax, if v n+ 1 ij - vmax, x n+ 1 ij= x n ij+ v n+ 1 ij.( 2) 其中, 加速常数 c1和 c2均为正实数, 表示将每个微粒推向 Pi和 Pg的加速度的权重, 取值一般在 0 , 2, r1 和 r2是范围在 0, 1 内取值的随机数, vm ax是常数, 它一

12、般取 2?0 . 由进化方程 ( 1)分析可知, 微粒的速度只 取决于微粒自身经历的最好位置 Pi和所有微粒经历的最好位置 Pg. 微粒群优化算法的结构相对简单, 运 行速度很快. 但是, 算法运行过程中, 如果某微粒发现一个当前最优位置, 其他微粒将迅速向其靠拢. 如果 该最优位置为一局部最优点, 微粒群就无法在解空间内重新搜索, 因此, 算法陷入局部最优, 出现了所谓的 早熟收敛现象. 为了使算法具有良好的全局寻优能力, 出现很多改进的算法, 其中, Shi 7 等引入惯性权重 w, 其作用在于维护全局和局部搜索能力的平衡, 一般可将它设为随迭代的次数线性减小, 如由 0?9到 0?4 7

13、. 这样, 进化方程 (1) 变为: v n+ 1 ij= wv n ij+ c1r n 1(p n ij- x n ij) + c2r n 2(p n gj- x n ij).( 3) 在加了惯性权重的基础上, 当微粒 Xi经历全局最好位置时, 该微粒只能做匀速运动, 随着 w 的不断减 小, 该微粒几乎不变, 仍有陷入局部解的可能. 为了解决这个问题, 作者对微粒群算法进行了改进, 设计了 一个突变微粒群算法. 即在当微粒经历全局最好位置时, 保存这个最好位置, 同时重新随机产生一个新的 个体, 也就是说当产生了最优解时, 增加一个扰动, 扩大寻找的空间, 更有利于找到全局最优解. 改进的

14、算 法流程如下: Step 1?初始化, 设定 vm ax、 c1、 c2、 w 和最大迭代次数M 的值, 产生原始种群并计算种群中个体的适应 度 f, 记下 Pi和 Pg, 保留 Pg的值, 同时随机产生出得到 Pg的相应新个体; Step 2?如果迭代次数等于M 则转 Step 5 , 否则转 Step 3; Step 3?种群按式 ( 3) 和式 ( 2) 进化, 计算个体适应度 fs; Step 4? 比较 fs与 f; 如果 fs#f则修改Pi, 产生新的 Pg, 保留Pg的值, 同时随机产生出得到Pg的相应 新个体, 否则, 转 Step 2 ; Step 5?输出最优个体. 用了

15、一个非线性的测试函数对突变微粒群算法进行测试, 并与一般微粒群算法 (加入惯性权重 ) 比 较, 设测试函数: f (x) = sin 2 x 2 1+ x 2 2- 0?5 1+ 0?001(x 2 1+ x 2 2) 2- 0?5 , ? ? x - 100 , 100,( 4) 该函数的全局极小点是 (0 , 0), 而在距全局极小点约 3?14范围内的隆起有无限多全局极大点, 取值为 - 0?990283 , 因此很容易陷入局部极小点, 由于该函数的强烈震荡性质以及它的全局最优点被局部最优点 所包围的特性, 使得一般算法很难找到它的全局最优解. 实验中, 突变微粒群算法和标准微粒群算法

16、中参数取值为: c1与 c2都取 0?5 , w 从 1?2到 0?4随迭代次 数线性减少, vm ax= 2?5 . 对上述问题进行了 50次仿真计算, 群体规模为 20 , 最大进化代数为 500 . 用 F表示 !27! 陈战平: 求解线性约束问题的微粒群优化算法 平均收敛代数, R 表示平均收敛率, 算法结果见表 1 . 表 1?两种算法的比较结果 Table 1? Com parative result bet ween the t wo algorithm s 算法误差平均收敛代数 F平均收敛率 R /% 突变微粒群算法0?000 01102?45100 标准微粒群算法0?000

17、01138?2345 实验结果表明, 虽然都是随机优化算法, 但突 变微粒群算法能够更好更准确地找到最优解, 标 准微粒群算法易陷入局部解, 收敛不如突变微粒 群算法稳定. 2?带线性约束的优化问题 标准的约束最优化问题: 目标函数为: m inf (X) = m inf (x1, x2, , xn) .( 5) 约束条件为: gi(X) = gi(x1, x2, , xn) #0 , ?i = 1 , , q, hk(X ) = gi(x1, x2, , xn) = 0 , ? k = 1 , , l. ( 6) 式中, X为设计向量, X = (x1, x2, xn) T; x i为第 i

18、个设计变量,i = 1 ,2 , n; f (X) 为目标函数; gj(X) 为第 i个不等式约束; hk(X)为第 k个等式约束; n为设计变量个数; q为不等式约束的个数; l为等式 约束的个数. 当 ( 5)、 (6) 都是线性时, 称为线性约束, 否则称为非线性约束. 常用的求解约束优化问题的方法是引入拉格朗日乘子, 构造拉格朗日函数, 将约束优化问题转化为无 约束优化问题. 通过引入拉格朗日乘子 ? , ?% 0 , 由式 ( 5) 和 (6) 构成的拉格朗日函数: L (X) = f (X) + ? g(X) + ? h(X ).( 7) 这样, 由 (5) 和 ( 6) 式表示的

19、约束优化问题转化为 m inL(X), 这是一个无约束的优化问题. 但是, 优化的参 数变为多个, 即: X, ? , ? , 故无法用直接微粒群算法进行优化求得最优的设计变量向量 X. 而根据拉格朗日 对偶原理可知, 一个给定的线性约束问题都存在一个与其相关联的另一个线性约束问题 6. 这两个问题 互为对偶, 例如, 对公式 (5), 其对偶问题可表示为 maxF(X ) = maxF (x1, x2, , xn) = , #!时为弱对 偶. 两个对偶问题可以相互转化, 从而导出新的求解途径. 且在解线性约束问题时, 利用对偶理论可以使问 题更精确且简便易行 6. 为此, 本文设计了一个算法

20、, 利用对偶性原理, 将 X, ? , ?分离出 来, 分别采用突变微粒群算法进行优化. 用对偶性原理求解线性约 束优化问题的微粒群算法结构如图 1所示. 求解步骤如下: ( 1) 随机产生一组 X作为 X c, 通过在拉格朗日乘子的取值范围 内选取适当乘子 ? c, ?c, 采用微粒群算法进行优化, 使得: m inL (X, ? c, ?c ) = ! ,( 8) 得到一个最优的 X. ( 2) 将 X作为 X c, 再利用拉格朗日对偶式, 采用微粒群算法进 行优化, 使得: m axF (X) = m axL (X c, ? , ?) = , ( 9) 得到一个最优的拉格朗日乘子 ? ,

21、 ? . ( 3) 再将最优 ? , ?作为 ? c, ?c, 代入式 ( 8), 重复 (1)、 (2), 直到 X, ? , ?不再发生变化时停止. 便可找到满足约束的最优解. 由拉格朗日对偶定理可知, 若 !有限, X R n, 使得 f (X) # 0 , g(X) #0 , h(X) = 0 , 且 != , 则 ( 8)和 ( 9)有最优解. 这样, 通过对偶性原理将 X与 ? , ? 分离出来, 分 别进行优化, 在进行若干次迭代后便完成了对线性约束问题的优化. 3?实例分析 FIR滤波器在满足一定的对称条件下, 可以实现严格的线性相位. 而对 F I R滤波器的设计是一个带有

22、线性约束的一个最优化问题 8, 即在满足一定的约束条件下, 希望所设计的 FIR滤波器频率特性与理想的 !28! 南京师范大学学报 (工程技术版 ) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?第 10卷第 4期 ( 2010年 ) 低通滤波器频率特性的误差最小. 设 F I R滤波器的单位冲激响应 h(n) 是有限长的 ( 0#n # N - 1), 即滤波器的设计阶数为 N, 其频率 响应H ( e j ) 为 H ( e j ) = 在 = 0?25%时, H ( c) = 0?5 . 分别用阶数N为 11和 17进 行设计. 表 1

23、列出了一般微粒群算法、 突变微粒群算法、 一般微粒群约束算法和突变微粒群约束算法的实 验结果. 表 2?实验结果 Table 2? Exper i m ental results 优化算法种群规模迭代次数 约束H (0) = 1处 平均误差 约束H (w ) = 0?5处 平均误差 平均耗时间 /min N = 11N = 17N = 11N = 17N = 11N = 17 一般微粒群2002000?00830?09710?10470?188128?235?4 突变微粒群2002000?00690?06730?04080?058724?028?0 一般微粒群约束2002000?00350?0

24、6200?03710?043512?114?7 突变微粒群约束2002000?00210?05990?03630?04695?66?9 ? 通过对表 2中的数据分析可以看出, 由于在初始种群及新种群产生时, 非约束的微粒群算法需要对种 群进行约束条件判断, 明显影响了求解的速度, 且通过对标准微粒群的改进, 也无法提高求解的速度. 而采 用约束的微粒群算法, 克服了这个缺点, 可以大大地提高求解速度和精度. 4? 结论 本文在一般微粒群的基础上进行改进, 并与拉格朗日法相结合, 研究了带约束微粒群算法. 通过拉格 朗日对偶原理, 将拉格朗日乘子分离出来进行优化, 使得线性约束问题通过微粒群优化

25、及少量迭代可得到 最优解. 该算法可以用于解决工程中带约束的问题. 最后, 通过对低通滤波器的设计, 验证了改进算法的有 效性. 参考文献 ( References) 1 Boucher C, Noyer J . A hybrid particle approach for GNSS applications w ith partial GPS outages J.IEEE Trans Instrum M eas, 2010, 59( 3): 498?505 . 2 陈保娣, 曾建潮. 改进的吸引扩散微粒群算法 J. 控制理论与应用, 2010, 27( 4): 451?456 . Chen

26、Baod, i Zeng Jianchao . M odified attractive and repulsive particle swar m opti m ization J.ControlTheory and Applica ? tions , 2010, 27( 4): 451?456. ( in Chinese) 3 Naka S, GenjiT, YuraT,et a. l A hybrid particle swar m opti m ization for distribution state esti mation J. IEEE T rans on Pow? er Sy

27、ste ms , 2003, 18( 1): 60?68 . 4 王万雷, 杨静萍, 薄洪光. 基于微粒群和满足质量约束的组炉方案优化方法 J. 控制理论与应用,2010, 27( 4): 509?512. W angW anle,iY ang Jingping, BoHongguang . Opti mization of charge designw ith quality constraints based on particle swar m op? ti m ization J. ControlTheory andApplications , 2010, 27( 4):509?512

28、. ( in Chinese) 5 朱海梅, 吴永萍. 一种高速收敛粒子群优化算法 J. 控制与决策, 2010, 25( 1): 20?24. Zhu Hai me, i W uYongping. A PSO algorithm with high speed convergence J. Control and Decision ,2010, 25( 1): 20?24 . ( in Chinese) 6 胡适耕, 施保昌. 最优化原理 M . 武汉: 华中理工大学出版社, 2000 : 134?138. Hu Shigeng, ShiBaochang . Opti m ization T

29、heoryM . W uhan : Huazhong University of Technology Press ,2000: 134?138 . ( in Chinese) 7 ShiYuhu,i EberhartR. A modified particle swar m opti m izer C / Proc IEEE IntConfonEvolutionary Co mputation . Anchor ? age , 1998: 69?73. 8 赖晓平. FIR滤波器约束 M inM ax设计算法 J. 系统工程与电子技术, 2002, 24( 2): 84?88. LaiX iaoping . Constrained mini max design algorithm for FI R filters J.Systems Engineering and Electronics , 2002, 24( 2): 84?88. ( in Chinese) 责任编辑: 刘 ? 健 !30! 南京师范大学学报 (工程技术版 ) ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?第 10卷第 4期 ( 2010年 )