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

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

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

0 引 言

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

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

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

1 水庫多目標供水調(diào)度模型

水庫供水目標往往包括生活、工業(yè)、灌溉、生態(tài)等，且各供水目標的優(yōu)先級和保證率都不同。本文建立的水庫多目標供水調(diào)度模型，以水庫運行期內(nèi)缺水損失最小為目標，根據(jù)調(diào)度期內(nèi)來水，考慮各類運行約束和邊界條件，通過優(yōu)化限制供水啟動閾值（即多目標供水調(diào)度規(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時段的供水量，由供水調(diào)度規(guī)則決定。

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

水量平衡約束：

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

下泄流量約束：

蓄水量約束：

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

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

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

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

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

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

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

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

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

將合作型協(xié)同進化思想與粒子群算法相結(jié)合，提出一種基于種群停滯搜索技術(shù)的協(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īng)一個種群，各種群采用標準粒子群算法進行優(yōu)化求解，并從各種群中選出相應(yīng)個體以組成問題的一個完整解，再根據(jù)目標函數(shù)計算其個體適應(yīng)度，初始化解由隨機生成。算法計算流程如下：

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

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

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

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

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

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

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

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

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

2.3 水庫供水調(diào)度模型的CCPSO算法求解步驟

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

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

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

圖4 水庫供水調(diào)度模型的協(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)化調(diào)度計算條件

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

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

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

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

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

3.3 優(yōu)化調(diào)度結(jié)果對比分析

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

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

表3給出了三種方案所得的各項調(diào)度評價指標統(tǒng)計結(jié)果?？梢钥闯觯罕疚奶岢龅膮f(xié)同進化粒子群算法求解結(jié)果更逼近動態(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ī)劃各項調(diào)度指標最優(yōu)。而其他兩種方案只知道當(dāng)前決策時段的來用水，決策具有一定的短視性，故長系列總供水效益劣于動態(tài)規(guī)劃結(jié)果。

3.4 算法性能分析

選取獨立運行100次中的適應(yīng)度最優(yōu)值求解過程來對比算法的收斂速度，圖8展示了算法的收斂曲線，橫軸是算法迭代次數(shù)，縱軸是適應(yīng)度值。可以看出，協(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 次的適應(yīng)度值，計算效率提升了2.27 倍，因此，協(xié)同進化粒子群算法單次運算增加的時間是可接受的。

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

4 結(jié) 論

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