基于PSO及SA的高维优化方法研究及应用

维普资讯 http://www.cqvip.com

水力发电　２００８年３月　与遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｅｍｓ，ＧＡ）一样也是依据个体的　适应值大小进行操作。其不同之处在于，ＧＡ通过交叉变异操　作产生新的染色体，而ＰＳＯ是通过粒子在解空间追随最优的　粒子而进行搜索。迭代过程中粒子通过飞行完成空间位置的　变化，飞行速度根据自身的飞行经验及搜索空间中其他微粒　的飞行经验进行动态调整。由于存在对个体经历和群体经历　的认知，所以ＰＳＯ是一种启发式搜索寻优算法　与已有的优　化算法如遗传算法、模拟退火算法等相比．其物理意义更加　清楚．运算过程更加简捷　假设在一个ｎ维的目标搜索空间中．有ｍ个粒子组成的　群落。其中，第ｉ个粒子表示一个ｎ维的向量　Ｆ　，…，　，ｉ＝１，２，…，ｍ，　为该粒子在ｎ维搜索空间中的位置，其飞　行速度记为ｖｉ＝（ｖ　，…，　；ｐ　＝（ｐ　Ｐ　，…，ｐ　为第ｉ个粒子　搜索到的最优位置（　；ｐ　（ｐｇｉ，ｐ　，…，ｐ　为整个粒子群搜索　到的最优位置（Ｇ　。　Ｐｓ０算法的速度模型进化方程为　＝　＋ｃ　ｌｒｌ　＋ｃ２ｒ如部《　（１）　＋１；　＋１，　上。　（２）　式中，Ｗ表示惯性权重；　∈［　一，　，　一是常数；Ｃ１，ｃ：为加　速度常数，表示将每个微粒推向　和Ｇ　权重；ｒ　和／＇２为区　间『０，１］随机常数。　ＰＳＯ是一种新型智能算法，其概念简单，容易实现　与其　他算法相比，在求解优化问题时．该算法计算工作量小．精度　高。ＰＳＯ中的种群规模是算法优化特性的关键．快速收敛的　实现是建立在种群规模相对于问题解空间维数的数量协调　一致的基础上的。然而，对于高维优化问题，若种群设置较少　则难以实现优化：若种群设置较大．势必增加计算量和程序　运行时间。因此，求解高维优化问题的困难就在于种群规模　与高维数之间的矛盾　１＿２　ＳＡ算法及其特性　ＳＡ算法是基于蒙特卡罗（ＭｏｎｔｅＣａｒｌｏ）迭代求解法的一　种启发式随机搜索算法。该算法出现于２０世纪８０年代初，　通过类比组合优化问题和统计力学中的热平衡问题．开辟了　组合优化问题的新途径　该算法建立在扰动模型及　Ｍｅｔｒｏｐｏｌｉｓ准则基础上．并通过控制退火温度持续进行解的　更新，实现问题的全局优化。ＳＡ是一种通用的优化算法．目　前在工程中已得到广泛的应用　Ｍｅｔｒｏｐｏｌｉｓ准则由Ｋｉｒｋｐａｔｒｉｃｋ等　提出．其主要内容为：　（１）在模型各参数变化范围内随机选择一个初始模型‰．　并计算相应的目标函数值Ｅ（ｍｏ）：　（２）对当前模型进行扰动产生一个新模型Ｉｎ．计算相应　的目标函数值Ｅ（ｍ、．得到　ＡＥ＝Ｅ（ｍ）一Ｅ（ｍｏ）　（３）　（３）以求解最大值为例。若ＡＥ＞０，则新模型Ｉｎ被接受：　若ＡＥ＜０，则新模型Ｉｎ按概率Ｐ进行接受，ｒ，ｎ为温度。当模型　被接受时，置ｍｏ＝ｍ，Ｅ（ｍｏ）＝Ｅ（ｍ）；则　Ｐ＝ｅｘｐ（－△ＥｆＴ　ｔ４）　Ｍｅｔｒｏｐｏｌｉｓ准则能使ＳＡ以一定的概率接受目标函数值　不太好的状态．这使得ＳＡ算法即使陷入局部最优解也可跳　ＷａｔｅｒＰｏｗｅｒ　Ｖｏ１．３４．Ｎｏ．３　出，从而收敛到全局最优解　但为得到一个好的优化解需要　有足够多的模型扰动次数，并且需要配以严密的退火计划　因此，ＳＡ的效率问题一直是这一算法真正走向实用的最大　的障碍　２改进微粒群模拟退火算法　本文基于ＰＳＯ及ＳＡ．提出一种ＳＡ—ＰＳＯ算法　该算法针　对微粒群规模与所求问题的高维特性之间的矛盾．给出了解　决办法，并有效解决了ＰＳ０局部收敛问题　２．１原理及结构　ＳＡ—ＰＳＯ算法采用迭代方法进行优化计算。如图１所示．　。。，　，…，　为赋给程序的初始值，随机赋值的作用是以　初始值　。为基础得到各微粒空间矢量　及　；经基本ＰＳＯ　算法得到局部最优解后，采用扰动模型进行优化计算．跳出　局部最优空间。一次迭代循环结束后，若不满足计算终止条　件。则采用渐进搜索策略重复以上步骤继续优化．并将所得　的最优值Ｐ　赋给下次迭代初始值　。　图１　ＳＡ—ＰＡＯ算法结构及策略示意　２＿２算法策略　针对高维优化问题．ＳＡ—ＰＳＯ算法主要在以下几个方面　做了改进，即引入了随机选择、小领域赋值、极值扰动．以及　渐进搜索等策略。以求解极大化函数为例．采用ＦＯＲＴＲＡＮ语　言编写程序．对各策略予以说明　２＿２．１　随机选择　一般ＰＳＯ算法会在赋值及飞行操作中对微粒ｉ的　及　矢量所有维数上的数值逐一进行处理，这就使得知及　在操作前后有较大的变化。随着矢量维数的增多．这种变化　也将越来越大。这就在一定程度上加大了为提高ＰＳＯ算法　的收敛效果而对种群微粒规模的需求．同时也大大增加了　计算时长　混合ＰＳ０算法中，随机选择策略的目的即是解决因微粒　矢量的维数较多而造成的收敛速度缓慢的问题　这一策略是　指在对微粒　及　矢量不同维数，上的数值进行操作前增　加一个随机条件，当满足这一条件时，对维数　上的数值进　行更新，否则不予改变。此策略可减小粒子在更新前后的空　间差距．减少较小的种群规模与较多的微粒矢量维数之间的　矛盾，利于迭代过程中优化解的迅速收敛　随机选择策略程　序如下：　维普资讯 http://www.cqvip.com

第３４卷第３期　张晶伟，等：基于ＰＳＯ及ＳＡ的高维优化方法研究及应用　ｉｆ（Ｒａｎｄ（）．ｇｅ．　ｅｎｄｉｆ　ｔｈｅｎ　ｅｎｄｉｆ　其中，　及　分别为扰动前后的适应值。　程序中，Ｏｔ为阈值．当所研究问题维数较高时一般可取０．９～　０．９９，即每次仅对１％～１０％的维空间上的数值赋新值。　２＿２．２小领域赋值　为加快搜索的收敛速度，在赋值时除采用随机选择策略　３应用及分析　应用于清江流域梯级水电站的中长期优化调度研究．检　验ＳＡ—ＰＳＯ算法的优化效果　３．１　流域概况　清江自西向东蜿蜒于湖北省西南部．流域面积１７　６００　ｋｍ２，干流全长４２３　ｋｍ，总落差１　４３０　ｍ。清江干流自上而下　外，还需要引入小领域赋值策略加以配合。即，在以初始解Ｘ。　为基础得到的各微粒空间矢量Ｘ　及　的步骤中，仅在一个　较小的范围内对各微粒进行赋值　对第一个微粒的Ｘ　赋初始值Ｘ。，　赋随机值。程序如下　采用水布垭一隔河岩一高坝洲的三级梯级开发方案．形成以　＼　Ｘｙ＝Ｘ　＼　发电为主，兼顾防洪、航运的梯级水利枢纽工程．各库特征参　ｖｖ＝Ｒａｎｄ（）　数如表１所示。由于清江梯级高坝洲水库有效库容较小．可　其中√　（１，ｎ）。　视为径流调节　采用随机选择策略，对其他的微粒ｉ，按以下程序进行赋　３．２水电站群优化调度模型　值：　水电站群优化调度即在考虑各水电站间的水头、流量关　ｆｉ（Ｒａｎｄ（）．ｇｅ．　ｔｈｅｎ　系，满足电力系统及其他约束条件的前提下，以系统电站年　ＸＯ＂＝Ｘｏｊ＇￣－Ａ１（ｒ６－Ｏ．５）；ｖｏ．＝Ｒａｎｄ（）　发电量最多或总体电能价值最大为优化目标．寻求水电站群　ｅｌｓｅ　整体最优的联合运行方式　ｘＯ－＝Ｘｏｊ；ｖ＃＝Ｏ　３＿２＿１　目标函数　ｅｎｄｉｆ　以调度期内整个系统的水电站总发电效益最大为目标　程序中，Ａ　为步长；　（２，　√　（１，ｎ）；其他符号意义同前。　目标函数如下　２＿２．３极值扰动　ｒ　Ⅳ　随机选择赋值约束技术虽能加快高维数学问题在优化　ｍａｘ　∑∑础　ｆ＝１　ｌ　１　Ｑ．　△　：１，２，…　，ｉ：１，２，…，Ｎ（５）　过程中的收敛速度，但容易使问题陷入局部最优解。为了实　式中，ｉ为水库序号；Ⅳ是系统中的水库总数量；ｔ为计算时段　现全局搜索．考虑引入极值扰动策略使微粒在到达局部解后　序号；Ｔ是总计算时段数；Ｑ　为ｉ水库ｔ时段发电流量；Ｋｉ为　及时跳出　ｉ水库的综合出力系数；日　为ｉ水库ｔ时段发电水头；△　为　借助于随机选择策略，对微粒的最优解进行扰动。给出　计算时段　扰动模型程序：　３－２－２约束条件　ｉｆ（Ｒａ￣（）．ｇｅ．∞ｔｈｅｎ　主要约束条件　町　＝　部＋Ａ２（Ｒａｎｄ（）一０．５）　ＶｉＩ＝Ｖ　－．　．　．　ｑ　．Ｊ△　（６）　ｅｎｄｉｆ　１，　ｑ　，　．　（７）　程序中，Ａ　为步长；卢为阈值　（１，　；Ｘｏ／为扰动后的微粒矢　ｑ　．一≤ｑｉ　＜＜－ｑｌ，一　（８）　量。　Ｎ　２．２．４渐进搜索　≤∑　．＝１　　≤∑Ⅳ　＝１　（９）　渐进搜索策略是指利用渐进优化技术分步骤、分目标逐　式中，　　．为水库ｉ在ｔ时段的初库容；　为ｉ水库ｔ时段入库　渐在迭代过程中向最优解逼近。经过扰动模型的更改，微粒　流量；　为ｉ水库ｔ时段出流；／Ｂ　为水库ｉ在ｔ时段的区间　的适应值会发生变化，根据式（４）由Ｍｅｔｒｏｐｏｌｉｓ法则确定微粒　入库流量；ｑ　．　为水库ｉ　ｔ￣／Ｉ，＇Ｎ流量，用于下游生态需水等；　是否接受扰动模型的更改。若接受，则更新下次迭代计算中　ｑ　，一为水库ｉ最大泄流量，受闸ｔＪ２￣Ｔ游防洪安全；　随机赋值的初值；若不接受则对初值赋值。程序如下：　为水库群的保证出力；　为水库ｉ的最大出力；　．　为水库ｉ　ｉｆ（Ｆ２．ｇｔ．　）ｔｈｅｎ　在ｔ时段的出力　ｘｏ＝ｐｇ　３．３算法应用　ｅｌｓｅ／ｆ（ｅｘｐ（（髓一Ｆ，）／Ｔｏ）．　．Ｒａｎｄ（））　清江流域１９５５年为丰水年，随后两年为平水年　因此该　Ｘ０＝　０　年份组合具有较好的代表性，能反映不同调度方法的特点　表１　清江梯级水库特征参数　ＷａｔｅｒＰｏｗｅｒ　Ｖｏ１．３４．Ｎｏ．３　维普资讯 http://www.cqvip.com

水力发电　表２清江梯级水库调度模拟结果　２００８年３月　选取清江流域１９５５～１９５８水文年旬径流资料，采用建立的模　型对清江梯级水库进行联合调度计算。以水布垭及隔河岩水　库各时段水位系列为粒子向量，两库的初始（终止）水位分别　设定为３６５．０　ｍ及１９５．０　ｌＴｌ。粒子种群规模ｍ为２０，Ｏｔ为０．９，　加速度常数ｃ　、ｃ：均为２．Ｏ，权重系数　为Ｏ．５，　一为Ｏ．８，％　为１０６　调度中，梯级总出力满足设计保证率９５％的条件。　结合清江梯级水电站的实际情况，以式（１０）作为微粒群　模型中的适应度函数。即　Ｎ　Ｎ　ｍａｘ　∑【１　∑　，ｉ＝１　　（∑　．＝１　厂Ｎ）￣ＩＡｔ　（１ｏ）　＝式中，Ａ、　为电力约束惩罚因子，分别取值１Ｏ和１。其中，若　Ｎ　∑　，　≥　，则Ａ＝Ｏ；其他符号意义同前。　ｉ＝１　３．３优化计算及结果分析　根据以上建立的模型．清江梯级水库采用ＳＡ—ＰＳＯ算法　的优化结果见表２。　由以上结果可知．清江梯级水库的调度过程在采用ＳＡ—　ＰＳＯ算法优化后收到了明显的效果，梯级各水库的发电量都　有不同程度的增加．年均增加发电４．３８亿ｋＷ・ｈ，增长率达　到６．４５％：弃水量也有相应的减小，年均减少弃水２１．３０亿　ｍｓ．节约８４．７６％。调度结果能充分提高洪水资源利用率，增　加梯级多年平均发电量。采用不同调度方案得到的１９５５～　１９５７年两库调度过程水位轨迹（见图２）。　图２水布垭　隔河岩水库水位过程线　豳ＷａｔｅｒＰｏｗｅｒ　ＶｏＬ３４．Ｎｏ．３　由图２可知．采用ＳＡ—ＰＳＯ算法优化水电站群调度方案　后．两水库在汛前能加大出力，及时预留较多库容并减少弃　水．汛后能充分发挥水布垭水库的调蓄作用，使隔河岩水库　基本保持在较高的水头，有利于提高梯级发电量和洪水资源　利用率。　４结语　针对一般算法在高维优化问题求解中的各种问题，本文　以ＰＳＯ及ＳＡ为基础．通过引入随机选择、小领域赋值、极值　扰动．以及渐进搜索等策略，提出了一种融合多项改进技术　的ＳＡ—ＰＳＯ算法　该算法应用于清江梯级水库联合优化调　度．取得了较好的效果，能够提高水库群洪水资源利用率。在　满足设计保证率的前提下．清江梯级多年平均发电量为　７６．８４亿ｋＷ．ｈ．比现应用方案增加了６．４５％，年均弃水量为　３．８３亿ｍ］．减少了８４．７６％。在水库群联合调度的优化质量　上．该算法收到较好的效果，并随着所研究问题维数的增长，　其优点更加明显。该算法开辟了ＳＡ和ＰＳＯ算法用于高维优　化问题的新途径．但算法参数较多，其设置工作相对繁琐，有　待进一步地研究改进。　参考文献：　ｆ１］　胡铁松，万永华，冯尚友．水库群优化调度函数的人工神经网　络方法研究ｌＪＪ．水科学进展，１９９５，６（１）：５３—６０．　ｆ２］　Ｃｈａｎｄｒａｍｏｕｌｉ　Ｖ，Ｒａｍａｎ　Ｈ＿Ｍｕｈｉｒｅｓｅｒｖｏｉｒ　ｍｏｄｅｌｉｎｇ　ｗｉｔｈ　ｄｙｎａｍ—　ｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ａｎｄ　ｎｅｕｒａｌ　ｎｅｔｗｏｒｋｓ［ＪＪ．Ｊｏｕｒｎａｌ　ｏｆ　Ｗａｔｅｒ　Ｒｅ—　ｓｏｎｒｅｅｓ　Ｐｌａｎｎｉｎｇ　ａｎｄ　Ｍａｎａｇｅｍｅｎｔ，２００１，１２７（２）：８９—９８．　［３］　Ｗａｒｄｌａｗ　Ｒ，Ｓｈａｆｉｆ　Ｍ．Ｅｖａｌｕａｔｉｏｎ　ｏｆ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｏｐｔｉｍａｌ　ｒｅｓｅｒｖｏｉｒ　ｒｅｓｏｕｒｃｅｓ［Ｊ１．Ｊｏｕｒｎａｌ　ｏｆ　Ｗａｔｅｒ　Ｒｅｓｏｕｒｃｅ　Ｐｌａｎｎｉｎｇ　ａｎｄ　Ｍａｎａｇｅｍｅｎｔ，１９９９，１２５（１）：２５－３３．　］　李炳宇，萧蕴诗，吴启迪．一种基于粒子群算法求解约束优化　问题的混合算法啪．控制与决策，２００４，１９：８０４—８０７．　『５１　靳利霞，唐焕文．模拟退火算法的一种改进及其在蛋白质结构　预测中的应用［１Ｊ１．系统工程与理论实践，２００２，２２（９）：９２—９６．　『６］　刘力，周建中，杨俊杰，等．基于改进粒子群优化算法的新安江　模型参数优选［Ｊ］．水力发电，２００７，３３（７）：１６—１９．　［７　７］Ｂｅｌｌｍａｎ　Ｒ．，Ｄｒｅｙｆｕｓ　ｓ．．Ａｐｐｌｉｅｄ　Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａｍｍｉｎｇ【Ｍ］．１９６２．　【８］　Ｊａｍｅｓ　Ｋｅｎｎｅｄｙ，Ｒｕｓｓ　Ｅｂｅｒｈａｒｔ．Ｐａｒｔｉｃｌｅ　ｓｗａｌＴｎ　ｏｐｔｉｍｉｚ￣ｉｏｎ［Ａ］．　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１９９５　ＩＥＥＥ　Ｉｎｔｅｍａｔｉ０ｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｎｅｕ—　ｒａｌ　Ｎｅｔｗｏｒｋｓ［Ｃ］．Ｐｉｓｃａｔａｗａｙ．１９９５：１９４２—１９４８．　［９］Ｘｉａｏｈｕｉ　Ｈｕ，Ｙｕｈｕｉ　Ｓｈｉ，Ｒｕｓｓ　Ｅｂｅｒｈａｒｔ．Ｒｅｃｅｎｔ　ａｄｖａｎｃｅｓ　ｉｎ　ｐａｒｔｉ—　ｃｌｅ　ｓｗａｒｌｎ　．ＩＥＥＥ　Ｃｏｎｇｒｅｓｓ　ｏｎ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ［Ｃ］．　Ｐｏｒｄａｎｄ，２００４：９０—９８．　［１０】　Ｋｉｒｋｐａｔｒｉｃｋ　Ｓ，Ｇｅｌａｔｔ　Ｃ　Ｄ　ａｎｄ　Ｖｅｃｃｈｉ　Ｍ　Ｐ．Ｏｐｔｉｍｉｚａｔｉｏｎ　ｂｙ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ［Ｊ］．Ｓｃｉｅｎｃｅ，１９８３，２２０：６７１—６８０．