基于協(xié)同進化粒子群算法的水庫優(yōu)化調度與應用

劉英華，王 敬，王鏡淋，張 濤，齊愛年

（1.武漢設計工程學院，武漢 430070；2.湖北省水利水電科學研究院，武漢 430070；3.湖北省節(jié)水研究中心，武漢 430070；4.長江大學信息與數(shù)學學院，湖北 荊州 434023）

0 引 言

在水庫供水優(yōu)化調度中，旨在尋找水庫最佳調度過程來滿足水庫各供水目標缺水量最小，是一類涉及多目標、非線性、多約束的優(yōu)化問題［1］。求解此類問題，目前一般優(yōu)化算法分為兩種類型，一種是以動態(tài)規(guī)劃［2］為主的數(shù)學規(guī)劃方法。隨著所求解模型的復雜性提高以及決策變量的增多，動態(tài)規(guī)劃等數(shù)學方法會出現(xiàn)“維數(shù)災”這樣的標志化問題。另一種則是以遺傳算法［3］、粒子群算法［4］等為代表的進化算法（Evolutionary Algo‐rithms，EAs）。進化算法采用不依賴于問題特征、通用性較強的群體智能搜索機制求解問題，在搜索過程中可以實現(xiàn)并行化與備選解的多樣化，能夠很好地處理數(shù)學規(guī)劃方法的維數(shù)災問題，因此進化算法被廣泛地應用在水庫調度問題的求解中［5-7］。

粒子群算法（Particle Swarm Optimization，PSO）起源于人們對鳥群覓食行為的研究，通過粒子模擬鳥群等群體的運動，基于速度-位置搜索模式來對優(yōu)化問題的決策空間進行搜索，具有占用計算機內(nèi)存少，計算效率高等優(yōu)點。但傳統(tǒng)PSO 算法只考慮基于個體本身適應性的進化模式，對個體與進化環(huán)境之間的相互影響和復雜關系缺乏考慮，容易導致收斂速度慢或早熟等問題［8，9］。為了解決傳統(tǒng)PSO的早熟現(xiàn)象，很多PSO的變種算法被研究者提出，如CLPSO、LPSO、FIPS等［10-12］。這些算法通過提高種群多樣性避免陷入局部最優(yōu)；另一方面，提高種群多樣性的同時算法的收斂速度又往往難以保障。

為解決上述問題，本研究提出了一種基于種群停滯搜索技術的協(xié)同合作進化粒子群算法（Cooperative Coevolutionary Pari‐cle Swarm Optimization Algorithm，CCPSO），通過種群內(nèi)部個體間競爭進化來提高種群競爭力，通過種群之間的相互合作以提高算法全域搜索能力，并通過種群停滯搜索技術來提高算法收斂速度，應用到水庫多目標供水優(yōu)化調度模型求解中，探討該算法可行性和高效性，為水庫優(yōu)化調度提供一定參考依據(jù)。

1 水庫多目標供水調度模型

水庫供水目標往往包括生活、工業(yè)、灌溉、生態(tài)等，且各供水目標的優(yōu)先級和保證率都不同。本文建立的水庫多目標供水調度模型，以水庫運行期內(nèi)缺水損失最小為目標，根據(jù)調度期內(nèi)來水，考慮各類運行約束和邊界條件，通過優(yōu)化限制供水啟動閾值（即多目標供水調度規(guī)則），決策各時段不同供水目標的供水量，在保證各項用水不發(fā)生深度破壞的前提下，以追求最大化的水庫供水經(jīng)濟效益。

目標函數(shù)為：

式中：dit為第i供水目標、第t時段的缺水量；i為供水目標序列號，也表示供水目標的供水優(yōu)先級，序號越小，優(yōu)先級越高，i=1，…，n；t為時段序列號，t=1，…，T；Dit為第i供水目標、第t時段的需水量；Rit為第i供水目標、第t時段的供水量，由供水調度規(guī)則決定。

約束條件包括等式和不等式約束兩類。其中等式約束為水量平衡約束、多目標供水調度規(guī)則約束；不等式約束為下泄流量約束、蓄水量約束和變量全非負約束，相關數(shù)學表達式如下所示：

水量平衡約束：

多目標供水調度規(guī)則約束：

下泄流量約束：

蓄水量約束：

式中：St、St+1分別為調度期內(nèi)第t時段初、末水庫蓄水量；It為第t時段的入庫徑流；Et為第t時段的下泄流量；Lt為第t時段的庫水損失；μi為第i供水目標的限制供水系數(shù)，0 ≤μi≤1；Etmin為第t時段的最小下泄水量，一般為下游河道最小生態(tài)需水量；Etmax為第t時段的最大下泄水量，一般為保障下游河道安全所能下泄的最大水量；Stmin為第t時段的水庫蓄水量下限，為死水位相應庫容；Stmax為第t時段的水庫蓄水量上限，一般為正常蓄水位或汛期限制水位對應庫容。

用水需求是有一定彈性的，在彈性范圍內(nèi)用戶可以通過節(jié)水和其他措施緩解用水不足［13］，少量缺水一般不會造成大的損失。多目標供水調度規(guī)則是以水庫蓄水量的一系列閾值組合作為限制供水的啟動標準，該閾值組合都處于水庫上限庫容與死庫容之間，并將其劃分為多個調度區(qū)（如圖1所示，以3 個供水目標為例），根據(jù)水庫當前時段蓄水量狀況：I區(qū)，所有供水目標均按需供水；II 區(qū)，對優(yōu)先級最低的供水目標啟動限制供水；III區(qū)，對優(yōu)先級最低的兩個供水目標啟動限制供水；IV區(qū)，對所有供水目標都啟動限制供水。從而避免因缺水量過大而造成難以承受的社會經(jīng)濟損失。限制供水系數(shù)根據(jù)不同供水目標用水特性設置，生活和工業(yè)的限制供水系數(shù)可設置得高一些，農(nóng)業(yè)可設置得相對較低。

圖1 水庫多目標供水調度規(guī)則示意圖Fig.1 Hedging rule of the multi-objective reservoir water supply dispatching

2 協(xié)同進化粒子群算法

2.1 協(xié)同進化算法基本模式

自然界中的物種之間普遍存在競爭與合作。物種之間的競爭與合作促進了信息交流，提高了物種進化效率。受啟發(fā)于這種現(xiàn)象，進化計算的研究者們將多種協(xié)同進化的方法集成到進化算法中，從而提高進化算法的效率，這類基于協(xié)同進化策略設計出的進化算法被稱為協(xié)同進化算法（Coevolution Evolu‐tionary Algorithms，CEA）［14］。

協(xié)同進化算法基本思路是構建多個種群，基于多種群間的合作和競爭關系，通過種群間的相互關系和影響作用提高各種群的性能，以適應復雜的進化環(huán)境，從而實現(xiàn)種群進化的目標。在協(xié)同進化算法的框架下，每一個種群單獨地進化。在對一個種群中的個體評價時，個體將與其他子種群的個體合作組成原始問題的完整解，合作組成的解的質量顯示了該個體的合作能力。該模式利于保持種群在動態(tài)進化中的多樣性，從而保證在求解空間中的搜索效率，若全部種群都以相同的全局適應度衡量，容易收斂于合作度高的不同策略中。因此，協(xié)同進化的分而治之策略為處理大規(guī)模和復雜計算問題提供了一種有效的求解方法。與一般進化算法相比，協(xié)同進化算法有點如下：①多種群之間的相互關系和作用提升了算法的全域搜索能力；②利用少數(shù)作為進化向導的個體，減少非必要計算量，進而加快計算速度。

圖2 協(xié)同合作進化示意圖Fig.2 Basic pattern of cooperative coevolution

2.2 合作型協(xié)同進化粒子群算法

將合作型協(xié)同進化思想與粒子群算法相結合，提出一種基于種群停滯搜索技術的協(xié)同合作進化粒子群算法。本算法中種群內(nèi)部個體之間選用競爭進化模式，種群間選用協(xié)同合作進化模式，一方面通過內(nèi)部個體間的競爭提升種群的競爭力，另一方面通過協(xié)同合作提高系統(tǒng)的整體性能。一般協(xié)同合作進化粒子群算法的工作原理如圖3，整個進化系統(tǒng)由多個種群組成，各種群依次實行進化過程和協(xié)同過程。

圖3 基于3個子種群的協(xié)同進化粒子群算法工作模式Fig.3 Work mode of CCPSO based on three subpopulations

針對優(yōu)化問題“minf(x)，x∈N”，各變量對應一個種群，各種群采用標準粒子群算法進行優(yōu)化求解，并從各種群中選出相應個體以組成問題的一個完整解，再根據(jù)目標函數(shù)計算其個體適應度，初始化解由隨機生成。算法計算流程如下：

（1）種群初始化。各種群代表完整解的其中一個變量，在可行域內(nèi)初始化n個種群的位置和速度，種群規(guī)模均為p。對于第k(k=1，2，…，n)個種群，從其余的(n-1)個種群中隨機選擇一個個體，分別與第k個種群中的變量按順序組成新的種群k。至步驟（3）。

（2）構成完整解。對第k(k=1，2，…，n)個種群，從其余的(n-1)個種群中選擇各自當前最好的個體，分別與第k個種群中的變量按順序組成新的種群k。至步驟（3）。

（3）貢獻度評價。對第k(k=1，2，…，n)個種群，依據(jù)目標函數(shù)計算其適應度。

（4）種群協(xié)同進化。對于第k(k=1，2，…，n)個種群，基于全局最優(yōu)粒子與每個粒子的最優(yōu)值，采用粒子群算法對各種群依次進化。

（5）種群停滯搜索。對于第m(m∈{1，2，…，n})個種群，若步驟（4）后不滿足種群停滯搜索的條件，則進行步驟（7）；否則至步驟（6）。

（6）停滯種群重新初始化。保留停滯種群中貢獻度最好的個體，其余的(p-1)個變量則重新隨機生成。

（7）算法終止。如果滿足算法終止條件，則停止進化，輸出計算結果。否則，轉至步驟（2）。

在上述步驟（5）中，種群停滯搜索技術具體如下：為防止算法早熟收斂，針對協(xié)同進化粒子群算法，若在一定的進化代數(shù)間隔內(nèi)，某個種群對適應度的貢獻值小于設定的預期改進量，即種群進化停滯，粒子可能因陷入局部最優(yōu)而消亡，此時本算法采用新種群來替代停滯種群，從而提高了協(xié)同進化算法的搜索效率。停滯搜索采用如下不等式進行描述：

式中：f(t)表示在第t代種群的最高貢獻度；L表示固定的進化間隔代數(shù)；G表示預設的期望最小貢獻度改進量。

2.3 水庫供水調度模型的CCPSO算法求解步驟

將設計的協(xié)同合作進化粒子群算法引入到水庫供水調度問題求解中，通過一定水庫調度規(guī)則的設置，建立優(yōu)化-調度模型，優(yōu)化調度規(guī)則參數(shù)及相應供水效益。

算法流程是先在可行域內(nèi)初始化多組限制供水啟動閾值，按據(jù)此確定的限制供水規(guī)則運行水庫供水調度模擬模塊，統(tǒng)計出目標函數(shù)對應的評價指標作為該組決策變量的適度值，然后轉入優(yōu)化模塊，按照CCPSO 算法迭代，得到改進的調度規(guī)則再轉入模擬模塊，如此反復，直到滿足要求為止。

采用協(xié)同合作進化粒子群算法求解具有K個供水目標的水庫供水優(yōu)化調度問題時，優(yōu)化目標為累積缺水量最小，優(yōu)化變量為限制供水規(guī)則參數(shù)，考慮到將調度年劃分為J個調度時段，則擁有優(yōu)化變量的總個數(shù)為K×J。算法流程是先在可行域內(nèi)初始化M組限制供水啟動閾值，按據(jù)此確定的限制供水規(guī)則運行水庫供水調度模擬模塊，統(tǒng)計出目標函數(shù)對應的評價指標作為該組決策變量的適度值，然后轉入優(yōu)化模塊，按照CCPSO 算法迭代，得到改進的調度規(guī)則再轉入模擬模塊，如此反復，直到滿足要求為止。算法流程如圖4所示。

圖4 水庫供水調度模型的協(xié)同進化粒子群算法流程圖Fig.4 Framework of CCPSO for reservoir water supply dispatching

圖5 徐家河水庫位置示意圖Fig.5 Location of Xujiahe Reservoir

3 實例研究

3.1 研究區(qū)域概況

徐家河水庫位于湖北省隨州市府河支流徐家河上。壩址控制流域面積749 km2，興利庫容2.99 億m3，年均徑流量2.89 億m3。水庫供水主要滿足城鄉(xiāng)生活、工業(yè)及徐家河灌區(qū)的農(nóng)業(yè)灌溉需水，其多年平均需水量及年內(nèi)需水過程如表1及圖6所示。

表1 各供水目標多年平均需水量 萬m3Tab.1 Annual mean water supply of each water supply target

圖6 多年平均需水量年內(nèi)分配過程Fig.6 Annual allocation process of water supply

3.2 水庫供水優(yōu)化調度計算條件

供水優(yōu)先級從高到低分別為生活用水、工業(yè)用水、灌溉用水，3 種供水目標的供水允許破壞深度分別為10%、10%、20%，相應限制供水系數(shù)分別為0.9、0.9、0.8。模型以月為計算試點，則共有36個決策變量。以長系列來用水資料作為輸入，采用合作型協(xié)同進化粒子群算法（CCPSO）求解，并以標準粒子群算法（OPSO）和動態(tài)規(guī)劃方法（DP）作為對比方案，對供水調度模型進行長系列調節(jié)計算。

各優(yōu)化算法的參數(shù)設置如下：標準粒子群算法和合作型協(xié)同進化粒子群算法慣性權重ω、學習因子c1和c2、種群規(guī)模N、最大迭代次數(shù)Imax設置如表2所示。

表2 算法參數(shù)設置Tab.2 Settings of algorithm parameters

協(xié)同進化粒子群算法中貢獻度值改進量G值的設置對算法計算性能有一定影響。G設置得過大，易導致不斷重新初始化種群，需較多迭代次數(shù)和較長計算時間才能收斂至最優(yōu)值；G設置得過小，種群停滯識別效率下降，模型容易陷入局部最優(yōu)。圖7給出了適應度值隨G值的演變過程，據(jù)此取G 的最佳參數(shù)值40作為模型輸入。

圖7 適應度值隨參數(shù)G的演變過程Fig.7 Evolution process of fitness value with parameter G

3.3 優(yōu)化調度結果對比分析

評價各方案的指標包括累積缺水總量WS、缺水指數(shù)SI、供水保證率γ、年均棄水量S?？紤]到標準粒子群算法和協(xié)同進化粒子群算法均為隨機搜索算法，故取各算法均獨立運行100 次的平均結果來進行對比分析，得到的主要計算結果如表3所示。

表3 各方案優(yōu)化調度結果比較Tab.3 Optimal scheduling results by using three algorithms respectively

表3給出了三種方案所得的各項調度評價指標統(tǒng)計結果。可以看出：本文提出的協(xié)同進化粒子群算法求解結果更逼近動態(tài)規(guī)劃算法的理論最優(yōu)值，生活、工業(yè)和灌溉累積缺水總量相對于標準粒子群算法分別降低了47.2%、33.3%和14.4%；供水保證率分別提高了1.7%、1.9%和4.4%，缺水指數(shù)分別降低了0.064、0.071和0.076，年均棄水量減少了1.9%，水資源利用效率有所增加，證明了該算法的有效性。動態(tài)規(guī)劃是在長系列來用水過程已知條件下逆序遞推求得的水庫蓄水過程，理論上可逼近全局最優(yōu)解［15］，因此動態(tài)規(guī)劃各項調度指標最優(yōu)。而其他兩種方案只知道當前決策時段的來用水，決策具有一定的短視性，故長系列總供水效益劣于動態(tài)規(guī)劃結果。

3.4 算法性能分析

選取獨立運行100次中的適應度最優(yōu)值求解過程來對比算法的收斂速度，圖8展示了算法的收斂曲線，橫軸是算法迭代次數(shù)，縱軸是適應度值?？梢钥闯觯瑓f(xié)同進化粒子群算法在算法迭代早期（約65次迭代）就開始收斂，而標準粒子群算法收斂速度相對較慢。證明了協(xié)同進化粒子群算法可以在更接近理論最優(yōu)解的同時，具有較快的收斂速度，算法性能更優(yōu)。

圖8 OPSO及CCPSO算法迭代過程對比圖Fig.8 Iteration procession of OPSO and CCPSO

為進一步分析引入?yún)f(xié)同進化策略對算法的不確定性影響，各算法獨立運行100次的目標函數(shù)值（累積缺水總量）的箱型圖如圖9所示。據(jù)圖9可知，標準粒子群算法的不確定性較大，多次獨立運行中，更容易陷入局部最優(yōu)。得益于種群停滯探測策略，協(xié)同進化粒子群算法一定程度上避免了粒子陷入局部最優(yōu)，降低了算法的不確定性，求解效率更高，且使得累積缺水總量下降，供水效益增加。

圖9 標準粒子群算法及協(xié)同進化粒子群算法各獨立運行100次的目標函數(shù)值箱型圖Fig.9 Boxplot of objective function values in OPSO and CCPSO after 100 iterations

對比協(xié)同進化粒子群算法及標準粒子群算法100次運行的單次平均運算耗時如表4所示。由表4可知，協(xié)同進化粒子群算法單次運行消耗時間是標準粒子群算法的2.04 倍。因此，種群內(nèi)部競爭、種群間相互合作機制的引入在提升算法收斂性、穩(wěn)定性的同時，也增加了算法單次運行的時間消耗。但根據(jù)圖8，協(xié)同進化粒子群算法單次運算中迭代至88 次即可達到標準粒子群算法單次運算中迭代至200 次的適應度值，計算效率提升了2.27 倍，因此，協(xié)同進化粒子群算法單次運算增加的時間是可接受的。

表4 算法消耗時間對比 sTab.4 The running time of OPSO and CCPSO

4 結 論

本文建立了基于限制供水規(guī)則的水庫多目標供水模擬-優(yōu)化調度模型，并設計了相應的協(xié)同合作進化粒子群求解算法。該算法一方面通過種群內(nèi)部競爭提高種群競爭力，另一方面通過加強種群間的協(xié)同合作提高算法全域搜索能力，并利用種群停滯搜索技術改進算法收斂速度，一定程度上克服了傳統(tǒng)粒子群算法收斂速度慢、計算效率低及早熟的問題。將該算法應用于徐家河水庫調度實例研究中，與動態(tài)規(guī)劃法及標準粒子群算法的調度結果對比分析及算法性能分析表明了協(xié)同進化粒子群算法具有較好的全域搜索能力、較優(yōu)的求解準確度和較快的收斂速度，表明了算法在水庫調度應用中的有效性。