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

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

0 引 言

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

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

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

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

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

目標(biāo)函數(shù)為：

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

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

水量平衡約束：

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

下泄流量約束：

蓄水量約束：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）貢獻(xiàn)度評(píng)價(jià)。對(duì)第k(k=1，2，…，n)個(gè)種群，依據(jù)目標(biāo)函數(shù)計(jì)算其適應(yīng)度。

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)例研究

3.1 研究區(qū)域概況

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

表1 各供水目標(biāo)多年平均需水量 萬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)度計(jì)算條件

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

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

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

協(xié)同進(jìn)化粒子群算法中貢獻(xiàn)度值改進(jìn)量G值的設(shè)置對(duì)算法計(jì)算性能有一定影響。G設(shè)置得過大，易導(dǎo)致不斷重新初始化種群，需較多迭代次數(shù)和較長(zhǎng)計(jì)算時(shí)間才能收斂至最優(yōu)值；G設(shè)置得過小，種群停滯識(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é)果對(duì)比分析

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

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

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

3.4 算法性能分析

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

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

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

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

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

表4 算法消耗時(shí)間對(duì)比 sTab.4 The running time of OPSO and CCPSO

4 結(jié) 論

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