國海濤 劉性泉 岳峻 趙含雨

摘要：針對粒子群算法易陷入局部最優(yōu)問題，從數(shù)學(xué)角度分析了粒子群算法易陷入局部最優(yōu)的理論原因，提出一種自適應(yīng)混沌變異粒子群算法，對陷入局部最優(yōu)的粒子產(chǎn)生變異，增加算法的遍歷性、種群的多樣性，以跳出局部最優(yōu)解，用來解決水庫優(yōu)化調(diào)度問題。與現(xiàn)有算法相比，自適應(yīng)混沌變異粒子群算法計算快，穩(wěn)定性強(qiáng)，既避免了粒子群算法陷入局部最優(yōu)，同時在一定程度上又保證了收斂性。

關(guān)鍵詞：水庫優(yōu)化調(diào)度；粒子群優(yōu)化；混沌；變異；自適應(yīng)；局部最優(yōu)；收斂性

中圖分類號：TV697 文獻(xiàn)標(biāo)志碼：A 文章編號：1672-1683（2014）06-0181-03

水庫優(yōu)化調(diào)度是一類動態(tài)最優(yōu)控制問題。傳統(tǒng)的解決方法主要基于數(shù)學(xué)規(guī)劃技術(shù)，如線性規(guī)劃、動態(tài)規(guī)劃等[1]。隨著生物智能仿真算法的興起，有學(xué)者用遺傳算法[2-6] 、模擬退火算法[7]解決此問題。實驗表明，現(xiàn)有算法存在“維數(shù)災(zāi)難”、收斂速度慢等問題。

粒子群算法[8]（PSO算法）因收斂速度快，計算簡單，較易實現(xiàn)等優(yōu)點(diǎn)，獲得廣大學(xué)者的青睞，并被引入水庫優(yōu)化調(diào)度研究領(lǐng)域中[9-10]。但研究表明，與其他仿生算法一樣，粒子群算法依然存在早收斂問題。為此，諸多學(xué)者對粒子群算法[11-12]進(jìn)行了改進(jìn)，在某種程度上確實提高了粒子群算法的搜索能力，但對于多維函數(shù)而言，解的搜索能力還不是很好。

本文擬根據(jù)基本粒子群算法易陷入局部最優(yōu)的原因，融合混沌思想，對可能陷入局部最優(yōu)的粒子進(jìn)行自適應(yīng)混沌變異操，產(chǎn)生極值變異，繼續(xù)搜索，以便獲得更優(yōu)解。

1 問題描述

1.1 目標(biāo)函數(shù)

以發(fā)電為主，兼顧灌溉、防洪等任務(wù)的水庫為研究對象，確定的優(yōu)化目標(biāo)是發(fā)電量最大。因此目標(biāo)函數(shù)為

式中：E為電站的年發(fā)電量；A為電站的綜合出力系數(shù)；Qi為第i時段發(fā)電流量；Hi為第i時段平均發(fā)電凈水頭；T為總時段數(shù)；Mi為第i時段小時數(shù)。

1.2 主要約束條件

（1）水量平衡約束。

式中：Vi、Vi+1分別為第i時段初、末的水庫庫容；qi為第i時段入庫平均流量；Qi表示第i時段發(fā)電引用流量；Si表示第i時段棄水量。

（2）水庫蓄水量約束。

式中：Vi，min為第i時段應(yīng)保證的水庫最小蓄水量；Vi，max表示第i時段允許的水庫最大蓄水量。

（3）水庫下泄流量約束。

式中：Qi，min為第i時段必須保證的最小下泄流量；Qi，max表示第i時段允許的最大下泄流量。

（4）出力約束。

式中：Ni，min為電站允許的最小出力；Ni，max為電站的最大出力限制（一般為裝機(jī)容量）。

2 水電站水庫優(yōu)化調(diào)度混沌粒子群算法

2.1 基本粒子群算法及其局部最優(yōu)原因分析

假設(shè)m個粒子，在n維空間中搜索，第i粒子在第d維的位置用xid表示，飛行速度用vid表示，當(dāng)前最優(yōu)位置用pid表示，整個粒子群中當(dāng)前的最優(yōu)位置用pgd表示?；玖Ｗ尤核惴ㄖ形恢?、速度的更新見式（6）、式（7）

式中：t為當(dāng)前進(jìn)化代數(shù)；r1、r2為隨機(jī)數(shù)，在[0，1]之間取值；ω表示慣性權(quán)重；c1、c2為學(xué)習(xí)因子，是非負(fù)常數(shù)。

通過實驗發(fā)現(xiàn)：粒子群尋優(yōu)過程中表現(xiàn)出強(qiáng)烈的“趨同性”，使種群多樣性損失過快，導(dǎo)致早收斂。參照文獻(xiàn)[13]的思路分析如下：

由式（6）、式（7）代數(shù)變換整理可得

在算法的運(yùn)行過程中，每一維獨(dú)立更新自己的速度和位置，因此可以省略下標(biāo)d，將式（8）簡化成一維表示，即式（9）：

以上推理不難看出，粒子群算法易陷入局部最優(yōu)的原因之一是：在搜索過程中若所有粒子均沒有發(fā)現(xiàn)比pg更優(yōu)的位置，則進(jìn)化過程將陷入停滯狀態(tài)，粒子將逐漸向pd+pg2靠攏，陷入局部最優(yōu)。

文獻(xiàn)[14]中的研究表明，在算法運(yùn)行過程中，對pg附近的部分個體做出變異，可能會找到比pg更優(yōu)的位置，從而跳出局部極值，而且當(dāng)參與調(diào)整的個體數(shù)量不大時，算法復(fù)雜度不會有明顯的增加。因此，在本文改進(jìn)的算法中引入了混沌變異操作，當(dāng)大部分個體都得到相同解或相近解時，則認(rèn)為種群沒有了多樣性，陷入局部極值，需要進(jìn)行變異操作，使粒子逃脫局部極值。

文獻(xiàn)[15]在智能優(yōu)化算法中引入了Logistic映射，使其搜索范圍擴(kuò)大，候選解增多，增強(qiáng)了算法的搜索能力。本文采用的變異公式如下：

式中：μ為控制混沌狀態(tài)的參數(shù)。

混沌變異操作時，個體的位置在[0，1]取值內(nèi)，本文采取如下計算方法：

式中：R=max{pid-pgd}。變異后pid及其適應(yīng)值可以由式（11）和式（12）聯(lián)合重新計算，如果得到更優(yōu)的解，則對pid和pgd進(jìn)行更新。

2.2 算法步驟

步驟1：根據(jù)水庫水位的可能變化范圍（要搜索的解的集合），隨機(jī)初始化Xi、Vi，限定粒子的最大速度Vmax =0.1（Xmax- Xmin ），并初始化最大迭代次數(shù)等相關(guān)參數(shù)。

步驟2：由式（6）計算各個粒子的新速度Vi（t+1），依據(jù)式（7）計算更新各個粒子的位置Xi（t+1）。

步驟3：由式（13）求每一個粒子的適應(yīng)度，并對個體最優(yōu)值pid和全局最優(yōu)值pgd進(jìn)行計算更新。

式中：E為目標(biāo)函數(shù)；Cmax為一正數(shù)，用來確保適應(yīng)度函數(shù)值恒大于0；P為懲罰項，取值如下：

首先令Ni=AQiHi，若Qmin≤Qi+Si≤Qmax且Nmin≤Ni≤Nmax，則P=0；若（Qi+Si）>Qmax或Qi

步驟4：由（14）式計算適應(yīng)度變化率（FCR），若t2/3iter max（t為已迭代次數(shù)）并且FCR低于預(yù)先設(shè)定的閾值時，說明粒子在局部位置做微小調(diào)整，即粒子進(jìn)入局部最優(yōu)，則進(jìn)行步驟 5；否則轉(zhuǎn)到步驟 6。

式中：Fi（t）是第t次迭代后得到的適應(yīng)度值。

步驟5：利用式（11），對pgd進(jìn)行變異操作。

步驟6：若循環(huán)計數(shù)器的值等于最大迭代次數(shù)，則輸出最優(yōu)，否則轉(zhuǎn)到步驟3繼續(xù)求解。

3 仿真實驗

為說明本文算法的先進(jìn)性及有效性，在種群規(guī)模及粒子群算法基本參數(shù)相同的條件下，本文算法與已有算法進(jìn)行了對比，結(jié)果見表1及圖1。就優(yōu)化結(jié)果而言，免疫粒子群、退火粒子群以及本文提出的混沌粒子群算法得到的計算結(jié)果比基本粒子群算法好，但在計算時間上較基本粒子群算法耗時稍多。就收斂性方面而言，基本粒子群算法大約進(jìn)化60代左右，免疫粒子群和退火粒子群大約進(jìn)化到40代左右，混沌粒子群大約進(jìn)化到20代左右算法收斂。就算法的穩(wěn)定性而言，基本粒子群算法得到的計算結(jié)果波動較大，而混沌粒子群算法最穩(wěn)定?；玖Ｗ尤核惴ㄈ菀紫萑刖植孔顑?yōu)；免疫粒子群算法利用自我調(diào)節(jié)機(jī)制跳出局部極值，其局部搜索效果較差，進(jìn)化緩慢現(xiàn)象偶現(xiàn)；退火粒子群算法利用退火機(jī)制保持種群多樣性，但算法性能受溫度衰減速度控制的影響。

4 結(jié)論

本文在分析粒子群算法易陷入局部最優(yōu)問題原因的基礎(chǔ)上，提出一種自適應(yīng)混沌變異粒子群算法，在提出的算法中對可能陷入局部最優(yōu)的個體采取自適應(yīng)混沌變異操，避免早熟，使其重新獲得更優(yōu)解。將該算用于解決水電站水庫優(yōu)化調(diào)度問題的計算機(jī)仿真表明，與已有算法相比，本文算法增加了粒子的多樣性，擴(kuò)大了搜索的范圍，算法性能最為突出。對該算法稍作修改，亦可以應(yīng)用于解決其他優(yōu)化問題。

參考文獻(xiàn)（References）：

[1] 李順新，杜輝.動態(tài)規(guī)劃-粒子群算法在水庫優(yōu)化調(diào)度中的應(yīng)用[J].計算機(jī)應(yīng)用研究，2010，30（6）：1550-1580.（LI Shun-xin，DU Hui.Optimal operation of reservoir based on dynamic programming and particle swarm optimization[J].Journal of Computer Applications，2010，30（6）：1550-1580.（in Chinese））

[2] 葉碎高，溫進(jìn)化，王士武.多目標(biāo)免疫遺傳算法在梯級水庫優(yōu)化調(diào)度中的應(yīng)用研究[J].南水北調(diào)與水利科技，2011，9（1）：64-67.（YE Sui-gao，WEN Jin-hua，WANG Shi-wu.Application of the multi-objective immune genetic algorithm in the operation of cascade reservoirs[J].Journal of South-to-North Water Diversion and Water Science & Technology，2011，9（1）：64-67.（in Chinese））

[3] AKTER T，SIMONOVIC S P.Modelling uncertainties in short-term reservoir operation using fuzzy sets and a genetic algorithm[J] .Hydrological Sciences Journal，2004，49（6）：1081-1097.

[4] AHMED J A，SARMA A K.Genetic algorithm for optimal operating policy of a multipurpose reservoir[J] .Water Resources Management，2005，19（2）：145-161.

[5] 張忠波，張雙虎，蔣云鐘.結(jié)合廣度搜索的遺傳算法在水庫調(diào)度中的應(yīng)用[J].南水北調(diào)與水利科技，2011，9（5）：85-88.（ZHANG Zhong-bo，ZHANG Shuang-hu，JIANG Yun-zhong.Genetic algorithm based on deep search and its application to reservoir optimal operation[J].South-to-North Water Diversion and Water Science & Technology，2011，9（5）：85-88.（in Chinese））

[6] 暢建霞，黃強(qiáng)，王義民.基于改進(jìn)遺傳算法的水電站水庫優(yōu)化調(diào)度[J].水力發(fā)電學(xué)報，2001，74（3）：85-89.（CHANG Jian-xia，HUANG Qiang，WANG Yi-min.Optimal operation of hydropower station reservoir by using an improved genetic algorithm[J].Journal of Hydroelectric Engineering，2001，74（3）：85-89.（in Chinese））

[7] 陳立華，梅亞東，董雅潔，等.改進(jìn)遺傳算法及其在水庫群優(yōu)化調(diào)度中的應(yīng)用[J].水利學(xué)報，2008，39（5）：550-556.（CHEN Li-hua，MEI Ya-dong，DONG Ya-jie，et al.Improved Genetic Algorithm and its Application in Optimal Dispatch of Cascade Reservoirs[J].Journal of Hydraulic Engineering，2008，39（5）：550-556.（in Chinese））