基于改進(jìn)多目標(biāo)布谷鳥算法的水資源配置研究

陸 曉，吳 云，楊 侃，湯梓杰

(1.河海大學(xué)水文水資源學(xué)院，南京 210098；2.山西水利職業(yè)技術(shù)學(xué)院，山西 運(yùn)城044004)

隨著社會經(jīng)濟(jì)的發(fā)展以及人口的增長，人們對水資源的需求愈來愈大，區(qū)域水資源緊缺問題日益突出。在不能完全滿足區(qū)域用水的條件下，考慮水庫調(diào)度并對有限水資源進(jìn)行合理優(yōu)化配置就顯得尤為重要。近年來，啟發(fā)式智能算法逐漸被用于優(yōu)化調(diào)度中，如遺傳算法(GA)[1]、粒子群算法(PSO)[2]、差分進(jìn)化算法(DE)[3]和蟻群算法(ACO)[4]等，都取得了較好的效果。

布谷鳥算法(Cuckoo Search，CS)[5]是劍橋大學(xué)學(xué)者Yang Xinshe近年來提出的一種新的智能優(yōu)化算法，得益于其參數(shù)少、操作簡單和魯棒性強(qiáng)，已被成功用于諸多領(lǐng)域。隨后，Yang通過引入支配關(guān)系和非支配集的概念，構(gòu)建了多目標(biāo)布谷鳥算法(Multi-objective Cuckoo Search，MOCS)[6]，將算法拓展到多目標(biāo)領(lǐng)域。2014年，宋玉堅等[7]引入了非均勻變異算子和差分進(jìn)化算子對多目標(biāo)布谷鳥算法進(jìn)行改進(jìn)，并用于資源均衡優(yōu)化問題；2015年，賀興時等[8]對傳統(tǒng)的基于Pareto支配關(guān)系的適應(yīng)度函數(shù)進(jìn)行了改進(jìn)，并提出了基于小生境技術(shù)的逐步檔案縮減法，保證了解的均勻性；2017年，馬藝元等[9]針對標(biāo)準(zhǔn)算法迭代后期尋優(yōu)速度慢、易陷入局部解等缺點(diǎn)，提出了結(jié)合混沌理論和云模型的多目標(biāo)布谷鳥算法，通過函數(shù)仿真結(jié)果證明了該算法的優(yōu)越性；2018年，張鑫帥等[10]改進(jìn)了布谷鳥的局部隨機(jī)游走策略及自適應(yīng)發(fā)現(xiàn)概率，并增加了檔案管理機(jī)制，之后將其應(yīng)用于翼型的多目標(biāo)氣動優(yōu)化設(shè)計中，得到了很好的效果；2019年，楊歡紅等[11]通過設(shè)置動態(tài)發(fā)現(xiàn)概率和步長，將改進(jìn)的多目標(biāo)布谷鳥算法用于微電網(wǎng)調(diào)度，克服了原算法的“早熟”現(xiàn)象。目前，雖然多目標(biāo)布谷鳥算法逐漸受到廣泛關(guān)注，但仍處于起步階段，在水庫調(diào)度與水資源配置方面的應(yīng)用較少，對于如何實現(xiàn)區(qū)域水資源的多目標(biāo)優(yōu)化問題，布谷鳥算法將是一種新的求解思路。

本文針對布谷鳥算法容易陷入局部最優(yōu)解、收斂速度不理想等缺陷，從混沌種群初始化、自適應(yīng)發(fā)現(xiàn)概率和步長及外部檔案集維護(hù)等方面對MOCS進(jìn)行改進(jìn)，并將改進(jìn)后的算法(IMOCS)應(yīng)用于山西省同朔供水區(qū)的水資源優(yōu)化配置中，為該區(qū)域提供了可行可靠的配置方案，并為解決此類優(yōu)化調(diào)度問題提供了行之有效的新途徑。

1 水資源優(yōu)化配置模型

為了實現(xiàn)區(qū)域水資源的高效利用以及促進(jìn)地區(qū)生態(tài)文明，本文從供水和生態(tài)兩個目標(biāo)入手建立數(shù)學(xué)模型。

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

(1)供水單元缺水量最小。

(1)

(2)控制斷面河道最小生態(tài)流量總?cè)彼孔钚　?/p>

(2)

式中：Dit,1為規(guī)劃水平年第i區(qū)間第t時段的需水量；Sit,1為規(guī)劃水平年第i區(qū)間第t時段的實際供水量；Dit,2為規(guī)劃水平年第i區(qū)間第t時段的河道內(nèi)生態(tài)需水量，可采用最枯月平均流量法計算得到；Sit,2為規(guī)劃水平年第i區(qū)間第t時段的實際河道內(nèi)生態(tài)用水量；i=1,2,…,N，t=1,2,…,T，N為水庫個數(shù)，T為供水時段數(shù)。

1.2 約束條件

(1)水量平衡約束：

Vwt=Vw,t-1+(Iwt-qwt) Δt

(3)

(2)水庫水位約束：

Zwt,min≤Zwt≤Zwt,max

(4)

(3)水庫下泄能力約束：

qwt,min≤qwt≤qwt,max

(5)

(4)水庫蓄水量約束：

Vwt,min≤Vwt≤Vwt,max

(6)

(5)變量非負(fù)約束：所有變量均為非負(fù)量。

式中：Vw,t-1、Vwt為第w水庫t時段初、末的庫容；Iwt為第w水庫第t時段的入庫流量；qwt為w水庫第t時段的下泄流量；Zwt,min、Zwt,max為w水庫t時段允許的最小、最大水位；qwt,min、qwt,max為w水庫t時段最小、最大下泄流量；Vwt,min、Vwt,max為w水庫t時段的最小、最大蓄水量。

2 改進(jìn)的多目標(biāo)布谷鳥算法

2.1 標(biāo)準(zhǔn)多目標(biāo)布谷鳥算法

布谷鳥搜索算法(Cuckoo Search, CS)是通過模擬布谷鳥產(chǎn)蛋行為生成的一種新型智能算法，其搜索機(jī)制基于萊維飛行。后來，針對k維多目標(biāo)優(yōu)化問題，Yang等又在CS算法基礎(chǔ)上提出了MOCS算法，將布谷鳥算法推廣至多目標(biāo)領(lǐng)域。在MOCS中，Yang重新修改了CS中的三條準(zhǔn)則[6]，使其滿足k個目標(biāo)的需求：①每只布谷鳥一次產(chǎn)k個蛋，并將這k個蛋隨機(jī)放入一個鳥巢，第k個蛋代表著第k個目標(biāo)；②擁有高質(zhì)量的蛋的鳥巢會保留至下一代；③每個鳥巢中的蛋都有pa的概率被丟棄，并根據(jù)蛋之間的相似性重新生成一個鳥巢。

該算法中，第一條準(zhǔn)則意味著隨機(jī)化的過程，新解可以通過萊維飛行或隨機(jī)游走產(chǎn)生；第二條準(zhǔn)則意味著精英策略，有助于算法收斂；第三條準(zhǔn)則意味著變異過程，差解被丟棄并生成新解。這三條準(zhǔn)則保證了算法的有效性，使之能向最優(yōu)解收斂。

在此基礎(chǔ)上，基于萊維飛行的鳥巢位置更新公式如下：

(7)

其中，u和v服從正態(tài)分布。

(8)

式中：Γ為標(biāo)準(zhǔn)的Gamma函數(shù)；β一般取1.5。

此外，MOCS的另一種更新方式是根據(jù)發(fā)現(xiàn)概率Pa與隨機(jī)生成的數(shù)r之間大小來決定是否生成新解，其更新公式如下：

xi,t+1=xi,t+γH(Pa-r)⊕[xj,t-xk,t]

(9)

式中：γ和r二者均服從均勻分布，γ,r∈U[0,1]；xi,t、xj,t、xk,t分別為第t代中3個不同的隨機(jī)個體；H為赫威賽德函數(shù)。

標(biāo)準(zhǔn)MOCS算法的偽代碼可參考文獻(xiàn)[6]。

2.2 改進(jìn)的多目標(biāo)布谷鳥算法

在MOCS基礎(chǔ)上，本文針對算法搜索性能、收斂速度及求解效率對原算法進(jìn)行了以下3方面的改進(jìn)：通過對種群進(jìn)行混沌初始化，保證了初始種群的多樣性和均勻性，為全局搜索奠定了良好的基礎(chǔ)；根據(jù)外部檔案集的更新情況，動態(tài)調(diào)整發(fā)現(xiàn)概率pa和步長α，有助于算法跳出局部最優(yōu)解；利用3-點(diǎn)最短路徑法對外部檔案集進(jìn)行實時更新和精簡，有效提高算法的運(yùn)行效率，保證最優(yōu)解的輸出。

2.2.1 混沌初始化

MOCS中，初始種群的生成采用隨機(jī)方式，這有可能導(dǎo)致種群分布不均，也有可能產(chǎn)生大量劣解，導(dǎo)致算法收斂過慢，影響算法性能。混沌是由確定性方程得到的具有隨機(jī)性的運(yùn)動狀態(tài)，是一種非線性現(xiàn)象，具有隨機(jī)性、遍歷性、規(guī)律性、對初始條件的敏感性等優(yōu)點(diǎn)[12]。融入混沌原理的特點(diǎn)，能夠有效提高種群多樣性，又不失個體隨機(jī)性，為進(jìn)一步進(jìn)行有效全局搜索提供基礎(chǔ)。

本文采用Logistic映射對種群進(jìn)行混沌初始化，其表達(dá)式為：

(10)

式中：μ為控制變量，當(dāng)μ=4時，Logistic映射完全處于混沌狀態(tài)，本文利用混沌迭代生成布谷鳥的初始鳥窩位置，然后再進(jìn)行優(yōu)化搜索，步驟如下：

step3：將產(chǎn)生的N個混沌變量按下式映射到解的搜索空間：

(11)

式中：Ud和Ld分別為搜索空間第d維的上下限；yid為利用式(11)產(chǎn)生的第i個鳥巢在搜索空間第d維；xid即為第i個鳥巢在搜索空間第d維的坐標(biāo)。

2.2.2 自適應(yīng)發(fā)現(xiàn)概率和步長

MOCS中，發(fā)現(xiàn)概率和步長是一個非常重要的參數(shù)，一般被設(shè)為固定值，但這不利于提高局部搜索精度。國內(nèi)外不少學(xué)者，如楊歡紅[11]、畢曉君[13]等都將發(fā)現(xiàn)概率和步長改為動態(tài)的，一般都是將發(fā)現(xiàn)概率調(diào)整為線性的，步長調(diào)整為連續(xù)的指數(shù)函數(shù)，即隨著迭代次數(shù)的增加，發(fā)現(xiàn)概率和步長是不斷減小的，這雖然提高了算法的收斂速度，但沒有考慮到所有情況。當(dāng)外部歸檔集沒有更新時，即意味著算法沒有搜尋到更優(yōu)秀的解，此時若繼續(xù)減小概率和步長，很容易導(dǎo)致算法陷入局部最優(yōu)解，不利于其跳出局部搜索。因此本文分情況考慮對發(fā)現(xiàn)概率和步長進(jìn)行改進(jìn)。

在迭代初期，本文將參數(shù)pa和α設(shè)為較大的值，保證解向量的多樣性；若第m代的外部檔案集Archive(m)沒有更新，則依舊采用第m-1代的發(fā)現(xiàn)概率和步長；若有更新，則意味著算法搜尋到了更優(yōu)解，此時適當(dāng)減小pa和α，幫助算法局部尋優(yōu)，提高搜索精度；當(dāng)?shù)揭欢ù螖?shù)，pa或α達(dá)到最小值時，保持最小值不變繼續(xù)迭代，以防止發(fā)現(xiàn)概率和步長過小導(dǎo)致算法陷入局部最優(yōu)。

(12)

(13)

2.2.3 外部檔案集的生成與維護(hù)

MOCS中，Yang引入了支配解與非支配解的概念，比較新解與舊解，保留支配關(guān)系最好的一組解，并將非支配存入外部檔案集中。但外部檔案集存在一定的容量，當(dāng)Pareto最優(yōu)解超過其最大容量限制時需要對其進(jìn)行裁剪，因此需要有合理的檔案刪除和保留機(jī)制。本文參考文獻(xiàn)[14]中的方法，利用3-點(diǎn)最短路徑法保證非支配解的均勻性和多樣性。規(guī)則如下：

選定第i個點(diǎn)，設(shè)為i1，尋找出與其距離最近的點(diǎn)，設(shè)為i2，計算出它們之間的距離為Di1,i2；繼續(xù)尋找出距i2最近的點(diǎn)，設(shè)為i3，計算出i2、i3之間的距離為Di2,i3。此時i1點(diǎn)的3-點(diǎn)最短路徑值為：

Di1=Di1,i2+Di2,i3-|Di1,i2-Di2,i3|

(14)

(i1≠i2≠i3)

從公式可以看出，被評估的解點(diǎn)獲得的距離值越大則證明其越稀疏，并且分布均勻的解點(diǎn)獲得的距離值要大于分布不均的解點(diǎn)的距離值，按照距離值排序可有效維護(hù)外部檔案集。

2.2.4 IMOCS計算流程

具體流程如圖1所示。

圖1 IMOCS算法流程圖Fig.1 The flow diagram of IMOCS algorithm

3 實例研究

同朔供水區(qū)屬于“山西大水網(wǎng)”建設(shè)的第一橫，位于山西省北部，該區(qū)域本身水量不足，再加上隨著經(jīng)濟(jì)的發(fā)展，水資源緊缺的問題日益嚴(yán)重，合理高效配置水資源迫在眉睫。同朔供水區(qū)主要涉及12個區(qū)縣，經(jīng)簡化合并后形成7個供水片區(qū)；供水區(qū)內(nèi)的主要河流為桑干河，屬于海河流域永定河水系，區(qū)域內(nèi)可供調(diào)度的水庫為東榆林水庫、孤山水庫和文瀛湖水庫，其中東榆林水庫位于桑干河上游，屬于中型水庫，孤山水庫和文瀛湖水庫位于御河，孤山水庫屬于小(Ⅰ)型水庫，文瀛湖水庫屬于中型水庫，這3個水庫進(jìn)行聯(lián)合調(diào)度。供水區(qū)域及供水路線如圖2所示。

依據(jù)2018年同朔盆地供水區(qū)的需水、當(dāng)?shù)毓┧?、水庫入流及引調(diào)水情況，以2018年為現(xiàn)狀年，對2025年進(jìn)行規(guī)劃，在考慮引調(diào)水和不考慮引調(diào)水兩種情境下，分別對保證率為50%、75%和95% 3種不同情況應(yīng)用改進(jìn)的多目標(biāo)布谷鳥算法求解水庫群供水優(yōu)化調(diào)度模型。采用Matlab編寫，應(yīng)用文獻(xiàn)[15]中的多目標(biāo)決策方法，得出各情境下最優(yōu)調(diào)度方案，水庫調(diào)度過程如圖3所示，配置結(jié)果如表1、表2和表3所示。

由調(diào)度結(jié)果可知，平水年時天然來水較多，能夠滿足部分農(nóng)業(yè)用水，此時整體需水量較小。而在枯水年和特枯水年的農(nóng)業(yè)用水需求更大，總需水量增加明顯。平水年、枯水年和特枯水年時供水區(qū)都出現(xiàn)了不同程度供水不足的現(xiàn)象，且存在不同程度的河道生態(tài)缺水。當(dāng)考慮萬家寨引黃工程后，供水區(qū)可供水量增加，缺水現(xiàn)象得到緩解，能夠基本滿足供水和生態(tài)要求。萬家寨引黃工程在促進(jìn)供水區(qū)經(jīng)濟(jì)發(fā)展以及保護(hù)其生態(tài)環(huán)境方面具有重要意義。

圖2 同朔供水區(qū)分區(qū)及供水路線示意圖Fig.2 Schematic diagram of water resource system in Tongshuo water supply area

圖3 不同情況下2025年各水庫調(diào)度過程線Fig.3 Water level of reservoirs in 2025 under different scenarios

4 結(jié) 語

針對傳統(tǒng)多目標(biāo)布谷鳥算法，本文用混沌映射進(jìn)行種群初始化、改進(jìn)自適應(yīng)步長和發(fā)現(xiàn)概率和通過3-點(diǎn)最短路徑法進(jìn)行檔案集的刪除和保留，從而構(gòu)建IMOCS方法。對于考慮供水和生態(tài)目標(biāo)的水資源配置問題，以同朔供水區(qū)為例，用IMOCS方法進(jìn)行求解。調(diào)度結(jié)果驗證了該算法的合理性，同時表明萬家寨引黃工程對改善供水區(qū)的水資源問題具有重要意義。

表1 同朔供水區(qū)2025年平水情況下年水量調(diào)度方案 萬m3

表2 同朔供水區(qū)2025年枯水情況下年水量調(diào)度方案 萬m3

表3 同朔供水區(qū)2025年特枯情況下年水量調(diào)度方案 萬m3

□