面向梯級水庫多目標優化調度的進化算法研究

紀昌明，馬皓宇，彭 楊

（華北電力大學水利與水電工程學院，北京 102206）

1 研究背景

水庫作為一種徑流調節的工程手段，在實現水能資源的合理高效利用上發揮著重要作用。隨著我國金沙江、雅礱江、瀾滄江等流域水庫群的相繼建成與互聯智能電網的有序推進，梯級水庫已成為承載多方利益訴求的水資源利用載體，亟需開展多目標優化調度的研究，以有效協調水庫防洪、發電、供水、生態等多方面的任務，滿足新形勢下的調度要求［1-3］。

梯級水庫多目標優化調度包括生成備選方案集與方案優選這兩部分，首先求解所構建的多目標優化調度模型得到一定數量的非劣解，接著通過理想點法、均變率法等多目標決策方法從中挑選出最佳方案。本文的重點在于第一部分即研究模型的高性能計算方法，以期在給定的計算資源下獲得一組高質量的非劣解集供調度人員決策。而水庫調度領域目前主要有兩種求解方式：通過約束法、權重法等方法將多目標優化轉變為單目標優化，再利用傳統的數學規劃方法求解；通過NSGA-Ⅱ、MOPSO等基于Pareto支配理論的經典多目標進化算法（MOEAs）求解。

多目標轉變為單目標求解的方法早期便得到了應用：Foued BA 等［4］應用隨機目標規劃處理水庫群的多目標調度問題，并以突尼斯北部的多庫系統為例驗證方法的有效性；梅亞東等［5］建立了兼顧發電量與保證出力的黃河上游梯級水電站優化調度模型，采用約束懲罰法將多目標轉化為單目標，利用DP-DDDP的組合算法完成求解；武新宇等［6］利用灰色關聯度法將多目標優化模型轉換成多個單目標優化模型，使用逐步優化算法獲得非劣解集；黃草等［7］以長江上游15座大型水庫為研究對象，建立包含發電、河道外供水與河道內生態用水等目標的非線性優化調度模型，提出E-POA作為求解算法以提高效率。該方法雖能有效降低多目標優化問題的求解難度，但存在較多的缺點：（1）權重系數等實現問題轉變的重要參數只能依據主觀經驗設置，目前尚無客觀合理的取值規則可循；（2）每次求解僅能得到一個調度方案，且因問題Pareto前沿的形狀未知，多次計算可能無法獲得等計算次數規模的非劣解集，即無法保證能為決策者提供一定規模的備選方案集；（3）非線性規劃、動態規劃等傳統單目標算法在處理大規模水電調度問題上存在嚴重的“維數災”問題。

上述缺點導致該方法的使用受到限制，許多學者開始利用經典MOEAs：Chang L C 等［8］構建最小化各庫供水短缺指數的臺灣翡翠與石門水庫的優化調度模型，通過NSGA-Ⅱ算法進行研究；覃暉等［9］建立三峽梯級水電站的中長期發電優化調度模型，提出SPDE算法完成求解；Ahmadi M等［10］利用NSGA-Ⅱ算法研究Karoon4水電站的多目標發電優化調度，并提取其最優運行規則；Luo J等［11］考慮安康水庫防洪與供水兩方面目標，提出一種基于偏好選擇的多目標免疫算法MOIA-PS 求解模型；王麗萍等［12］建立溪洛渡-向家壩梯級水庫多目標優化調度模型，采用NSGA-Ⅱ算法獲取非劣解集，接著引入結構方程模型定量分析各目標間的互饋關系。該方法計算效率較高，單次求解即可得到一組調度方案，且對問題的目標函數與約束條件的形式不作要求，但缺陷在于經典MOEAs的算法性能通常隨決策空間或目標空間維數的增長而下降，隨著水庫群規模的不斷擴大與調度管理要求的不斷提升，梯級水庫多目標優化調度本質上已屬于大規模高維多目標優化問題，其復雜性是經典算法所難以解決的。

如何處理多目標優化調度的高維特性已成為計算關鍵，而水庫調度領域尚未針對此提出或引入相應的優化策略或算法，故本文以多目標粒子群算法為基礎，采用超體積指標保證高維目標空間下算法的選擇壓力，采用問題變換策略保證高維決策空間下算法的搜索力度，提出LMPSO（Large-scale Many-objective Particle Swarm Optimization）算法，通過溪洛渡-向家壩梯級水庫的實例研究，驗證所提方法在梯級水庫多目標優化調度這一實際工程問題中的應用效果。

2 梯級水庫多目標優化調度模型

本文以金沙江下游最末梯級的溪洛渡-向家壩為研究對象，考慮發電、河道外供水與河道內生態用水這三方面目標，構建溪洛渡-向家壩梯級水庫發電-供水-生態的多目標優化調度模型。

2.1 目標函數

（1）發電目標：調度期內的發電量f1、發電保證率f2與棄水量f3。

式中：t和i分別為時段編號與水庫水電站編號；T和n分別為調度期時段總數與水庫水電站總數；Ni，t為i電站t時段的平均出力，kW；Δt為單位時段長度，h或s；表示t時段系統出力Nt是否滿足保證出力，1表示滿足，0表示不滿足；為i庫t時段的平均棄水流量，m3/s。

（2）供水目標：調度期內的供水缺水量f4、供水保證率f5與供水最長破壞歷時f6。

（3）生態目標：調度期內的生態缺水量f7、生態保證率f8與生態最長破壞歷時f9。

2.2 約束條件

（1）水量平衡約束：

式中：Vi，t和Vi，t+1為i庫t時段的時段初末庫容，億m3；Qi-1,t、Qi,t和分別為（i-1）庫t時段的平均出庫流量和i庫t時段的平均出入庫流量，m3/s。

（2）水位約束：

式中：Zi，t為i庫t時段初水位；和為i庫t時段初的水位上下限，m。

（3）流量約束：

（4）出力約束：

（5）邊界約束：

式中：Zi,start和Zi,end為i庫給定的調度期初末水位，m。

3 求解算法

3.1 基于超體積指標處理高維目標空間高維多目標優化問題（MaOPs）一般指目標個數大于5 的多目標優化問題（MOPs）［13］，經典MOEAs多用于處理2 ～3維目標的MOPs，由于以下兩方面的原因難以解決MaOPs：（1）高維目標空間下算法的收斂壓力喪失。此時種群中大部分個體之間相互非支配，導致基于非支配排序的選擇策略失效，算法的選擇進程被多樣性指標所支配；（2）高維目標空間下結果的多樣性難以保證。種群個體在高維目標空間內分布稀疏，導致基于目標空間內歐氏距離的多樣性維持策略失效。為解決上述問題學者們提出了一系列方法，大致可分為4類［14-19］：直接修改傳統Pareto支配的定義；采用算法的性能評價指標作為選擇標準；基于分解思想將原問題分解為一組簡單的子問題；刪除冗余或不相關的目標以實現維度縮減。本文選擇第2類處理方法，將超體積指標作為個體適應值引導算法的交配選擇與環境選擇。

超體積指標（hypervolume）由Zitzler E 等［20-21］提出并用于定量比較不同MOEAs 的性能，是目前最為通用的集合質量度量標準之一。該指標具有優秀的數學性質，是已知的唯一與Pareto支配嚴格單調的一元指標［22-23］，且不同于GD、IGD等指標，其可在Pareto前沿未知的情況下同時評價解集的收斂性與多樣性，故可應用于實際的科研與工程問題中。超體積指標IH定義如下：

式中：A為決策空間內的待評價集合；r為目標空間內的參考點；λ為勒貝格測度；H（A，r）表示目標空間Z內被A對應的目標向量集f（A）與r所包圍的區域。

IH以單個標量值衡量整個集合的質量，而選擇操作要求指標的評價對象是集合中的單個個體，故需對該指標進行修改。此處使用修改后的超體積指標，將移除集合中某一個體所造成的超體積損失值作為評判該個體優劣的標準，其定義如下［24］：

式中：k為待移除個體的總數；表示目標空間內被a和A中其它任意（i-1）個個體所共同且唯一弱支配的區域。

（1）準備階段：首先輸入估算所需參數：集合A、參考點r、參數k以及取樣規模M；接著構建包含所有Hi（a，A，r）的樣本空間S，為方便體積計算與樣本點生成，令S為包含所有Hi（a，A，r）的邊長軸平行的最小超立方體；最后完成參數ai的計算與適應值vi的初始化。

（2）取樣階段：首先均勻隨機生成樣本點sj∈S，j=1，…，M；接著針對每一個樣本點sj，檢查其是否位于任何滿足1≤i≤k且a∈A的Hi（a，A，r）區域內，檢測方法為獲取A內所有弱支配sj的個體組成的集合UP，若其基數滿足1≤|UP|≤k，則sj位于所有滿足i=|UP|且a∈UP的Hi（a，A，r）內，更新A中相應個體的適應值；最后即可獲得集合A中個體的適應值。

3.2 基于問題變換處理高維決策空間影響優化問題復雜性與求解難度的一個重要因素是決策變量的維數，大規模多目標優化問題（Large-scale MOPs）通常指維數在200以上的多目標優化問題［27］，大多數多目標算法在30維以下的問題上表現良好而無力解決高維問題，主要原因在于：為使搜索能覆蓋整個決策空間，種群的規模應隨決策變量維數的增長而擴大，即實現高維決策空間內的有效搜索需要大規模種群集合，而實際設計中為保證計算效率，學者們一般將種群規模限制在10 ～1000的范圍內，致使高維情況下無法搜尋至決策空間內的部分區域，導致所得結果往往并不理想。為解決該難題目前傾向于使用一種名為協同進化（cooperative coevolution，CC）的機制，其由Potter和De Jong［28］提出并成功應用于求解大規模優化問題。CC基于分解思想，按一定的劃分原則將問題的高維決策向量分解為一組低維決策子向量，由多個相互獨立的種群同時優化向量的不同部分，并在規定階段進行重組以開展整體優化，由此將復雜的高維優化問題轉化為一組簡單的低維子問題，通過多種群協同優化的方式完成求解。

然而協同進化并不適用于梯級水庫多目標優化調度，其原因在于該問題的約束條件復雜繁多，通常包括調度期內各時段初末的水位約束與各時段內的平均流量、出力約束，無論是以各庫各時段初的水位為決策變量，還是以各庫各時段內的平均出庫流量為決策變量，都必須將其作為一個整體進行優化，以保證優化過程中個體的可行性，避免算法在不可行域內的無效搜索。為此本文引入問題變換策略［29］，在整體優化的前提下實現搜索空間的降維，以期有效降低問題的求解難度。

首先介紹問題變換的相關概念。令Z為n維決策向量與m維目標向量的多目標優化問題，其數學表達式如下：

圖1 基于蒙特卡洛法的指標估算流程圖

對于任意決策向量x′，可通過變換函數ψ與權重向量w將其轉化為另一決策向量x，數學表達式如下：

在ψ內參數x′給定的情況下，改變w的值即可獲得不同的決策向量x，由此將Z轉換為新的問題Zx′，將待優化對象由決策向量x轉變為權重向量w：

轉換后搜索空間的維數依然為n，為實現降維進行變量分組，與CC不同各組變量并未實行相互獨立的優化：將n維決策變量劃分為γ組{g1，…，gγ}，接著修改權重變量與決策變量間的對應關系，由一一對應改為一個權重變量與一組決策變量相對應，由此將待優化的權重向量w由n維降至γ維。通過上述方法將n維決策空間的多目標優化問題Z變換為γ維的問題Zx′，再利用MOEAs 進行求解，即可在降維后的子空間內更快更徹底地搜索優秀個體。然而該方法有一明顯缺點，被劃分至同一組中的決策變量，當相應權重變量的值改變時其值將一同改變，即同一組變量的值無法相互獨立地變化，這將較大程度地限制算法在原決策空間內的可搜索區域。

3.3 LMPSO算法本文選擇以速度限制策略為特征，在低維MOPs上表現優異的多目標粒子群算法SMPSO［30］為基礎，以3.1節的超體積指標I h k取代擁擠距離這一傳統的多樣性指標，以3.2節的問題變換作為實現搜索空間降維的手段，由此提出一種能有效處理梯級水庫多目標優化調度這一大規模高維多目標優化問題的進化算法LMPSO。首先對改進策略的應用細節進行說明：

（2）問題變換降低搜索空間維數。算法求解原問題理論上能探索整個決策空間，但在高維情況下的收斂速度可能非常慢，致使給定迭代次數下所得結果的收斂性較差，而問題變換策略能在決策向量整體優化下實現搜索空間的降維，使算法能更深入地挖掘較小空間內的優化信息，進而提高收斂速度，但缺點正如3.2節末尾所述，其限制了決策空間內的搜索范圍，不利于維護多樣性，因而降低了算法近似整個Pareto前沿的能力。為此采取原問題與變換后問題交替優化的形式，以兼顧結果的收斂性與多樣性，并在變換后問題的優化階段，從存檔中選取不同個體的決策向量作為變換函數ψ的參數x′，以探索決策空間內的不同區域。

接著給出LMPSO的算法流程圖，如圖2所示。

最后對圖2中的重要操作，即優化操作Optimise和更新操作Update進行說明。

優化操作記為Optimise（Z，Pop，t），輸入參數分別為待優化問題Z、初始種群Pop和最大函數評價次數t，該操作的流程如圖3所示，具體步驟為：

（1）初始化個體歷史最優集合Pbest與種群歷史最優集合Gbest。Pbest用于記錄種群Pop中每個個體所經歷過的最優位置，將其初始化為Pop；Gbest的初始化則較為復雜，首先將Pop內位于第一非支配層的個體添加至Gbest，接著檢查|Gbest|是否超過給定值size，若是則基于適應值迭代刪除較差個體，最后計算Gbest內各個成員的適應值I|Gbest|h作為交配選擇的依據。

圖2 LMPSO算法流程圖

（2）更新種群Pop，再利用Pop更新Gbest與Pbest，重復此操作直至函數評價次數達到t。首先針對種群中的每個個體，從Gbest中基于I|Gbest|h選取優秀個體作為粒子速度更新的參數gbest，從Pbest中選取對應編號的個體作為參數pbest，以此計算個體的速度與位置，有必須滿足的硬性約束則需檢查并修正決策向量；接著利用新生成的Pop，將其與Gbest混合并對混合集合執行如Gbest初始化般的操作以更新Gbest，將其與Pbest內的個體一一比較以更新Pbest。

更新操作記為Pop=Update（Gbest，W_Gbest1，…，W_Gbestq），輸入參數分別為原問題Z的優化成果Gbest和變換后問題Zx′的q次優化成果{W_Gbestk}k=1，···，q，該操作的流程如圖4所示，具體步驟為首先清空給定規模size的種群集合Pop，接著從所有存檔的混合集合mixedGbest中挑選優秀個體加入Pop，按|mixedGbest|分為三種情況：

圖3 Optimise操作流程圖

（1）|mixedGbest|＜size。此時為滿足Pop的規模要求，對mixedGbest集合執行交叉變異操作，生成（size-|mixedGbest|）個新個體以填充集合，令Pop=mixedGbest。

（2）|mixedGbest|=size。令Pop=mixedGbest即可。

（3）|mixedGbest|＞size。此時對mixedGbest集合執行非支配排序，從第1層開始將各層個體依次移入Pop直至|Pop|≥size，若|Pop|＞size，則基于迭代刪除最后加入的層中（|Pop|-size）個個體。

4 實例分析

金沙江作為長江上游河段，起于青海省、四川省交界處的玉樹州直門達，止于四川省宜賓市東北翠屏區合江門的長江干流河段，全長3481 km，流域面積為50.2萬km2，流域地形呈北高南低。溪洛渡-向家壩梯級水庫位于金沙江的下游干流，作為開發與利用金沙江水能資源的骨干工程，該系統以發電為主，兼有防洪、攔沙、供水、生態等任務，其參數與拓撲圖如表1與圖5所示。

本文以溪洛渡-向家壩梯級水庫為研究實例，以2.1節中的發電、供水和生態這三方面的指標最優為目標，建立梯級水庫多目標優化調度模型，并利用LMPSO算法完成求解。為驗證所提算法的有效性，將計算結果與4 種具有代表性的MOEAs 進行比較，即NSGA-Ⅱ、SMPSO、NSGA-Ⅲ及KnEA，且為測試各算法在不同維度的決策空間與目標空間上的表現，分別以2010—2012年和2007—2012年為調度期，以月和旬為調度時段，在來水已知條件下，分別以（f1，f4，f7）、（f1，f2，f4，f5，f7，f8）和（f1，…，f9）為目標，構建12種維度組合的多目標優化調度問題Zi，j，其中i為決策向量的維數，，j為目標向量的維數，j∈{3，6，9}。

圖4 Update操作流程圖

表1 梯級水庫特征參數

4.1 參數設置首先選取決策變量并決定約束條件和目標函數的處理方式。為有效處理水量平衡、調度期初末水位限制等約束，將調度期內各庫各時段初的水位作為決策變量以實現編碼；為滿足調度中的硬性約束，在計算前依據水位、流量、出力等約束條件構建整個調度期梯級水庫的水位約束廊道，在計算中通過水庫當前階段的水位值確定下一階段水位的可行范圍；由于算法涉及目標空間內的歐式距離計算，故需對各維目標實現無量綱化，將其均轉化為越小越優型。

圖5 梯級水庫拓撲圖

接著進行算法的參數設置，分為通用參數與特有參數。通用參數設為：每個算法在每個問題上獨立運行30次，每次運行的種群與存檔的規模均取100，每次運行的最大函數評價次數取105。特有參數設為：4種對比算法的特有參數均參考原文獻進行設置；LMPSO 中，為估算超體積指標將取樣規模設為104，為實現問題變換將分組策略、分組規模與變換函數分別設為線性分組、12與區間交集變換，算法單次運行的每輪迭代中，當優化原問題時令最大函數評價次數為103，當優化變換后問題時令決策向量的選取規模為目標向量維數，種群與存檔規模均為50，最大函數評價次數為500。

最后選擇算法的性能評價指標。本文以超體積指標IH綜合評價所得解集的收斂性與多樣性，且為檢驗不同算法的指標值之間是否存在顯著差異，使用顯著性水平a=0.01的Mann-Whitney U檢驗。

4.2 結果分析通過比較5種算法在12個維度組合的多目標優化調度問題Zi，j上所取得的IH值，以評價各算法處理該類問題的性能，其實驗結果如表2所示。表中第2 ～6列括號外的數字為對應列算法在對應行問題上所測得的IH指標中位數的相對值，該值是對應列算法在對應行問題上獨立運行30次所統計的結果，不同算法在同一問題上的最優值以粗體標記，表現過差的算法其值以破折號標記。第2 ～6列括號內的數字為對應列算法在對應行問題上的得分，該值表示參與求解的方法中表現顯著優于對應列算法的數量。

表2 不同算法的結果對比

首先分析不同維度的問題上各個算法的表現。當變量維數i與目標維數j較小時，SMPSO能取得高質量的非支配解集，其在Z72，3上的指標值與最佳的KnEA無顯著差距，在Z144，3和Z216，3上均取得最優的IH值，由此驗證了SMPSO在解決低維問題上的優秀性能。當目標維數j增加時，SMPSO的表現隨之惡化，原因在于該算法并未針對高維目標空間設計相應的策略，而NSGA-Ⅲ和KnEA 的表現則較低維情況有明顯提升，且NSGA-Ⅲ在Z72，9上取得最優值，KnEA在Z72，6和Z144，6上的表現與最佳的LMPSO無顯著差距，原因在于NSGA-Ⅲ和KnEA是專門用于處理MaOPs的方法，NSGA-Ⅲ采用了基于參考點的多樣性維護策略，KnEA則提出在選擇操作中優先考慮拐點，兩者在處理變量維數較低的高維多目標優化問題上表現較好。當變量維數i也增加時，即可觀察到LMPSO 較其它算法的顯著優勢，在Z216，6、Z216，9、Z432，6與Z432，9這4 個大規模高維多目標優化問題（i＞200 且j＞5）上，LMPSO均獲得最佳指標值，且在最高維數的Z432，9上其值明顯高于其它算法，這歸功于LMPSO不僅利用超體積指標來指導算法的選擇操作，以保證高維目標空間下的收斂壓力與集合多樣性，而且采用問題變換策略對搜索空間進行降維，以確保高維決策空間內信息的高效挖掘。NSGA-Ⅱ這一經典算法在除Z72，3的其它問題上表現均不理想，尤其在高維問題上其值常接近0。

接著評價各個算法在該類問題上的總體表現。本文所提出的LMPSO在12個問題上取得了8個最優的IH值，在Z216，3和Z72，9上的指標值與最優值無顯著差異，由此體現出LMPSO較其它方法的競爭力，SMPSO 在Z144，3和Z216，3這兩個問題上取得最優值，NSGA-Ⅲ和KnEA 則分別在Z72，9與Z72，3上取得最好的結果。對表2中不同算法括號內的分數進行累加可得，LMPSO取得最佳的總分數3，接著是KnEA其分數為12，SMPSO與NSGA-Ⅲ的分數非常接近，分別為24和25，NSGA-Ⅱ則取得最差的分數43。由此表明在超體積指標IH評價非支配解集質量的條件下，LMPSO在處理多目標優化調度問題上的總體表現顯著優于其它4種對等比較的方法，其解集質量具有明顯的優勢，故更適合作為梯級水庫多目標優化調度的求解方法。

5 結論

梯級水庫多目標優化調度這一問題的高維特性日益凸顯，如何實現有效處理已成為水庫調度領域的研究熱點與難點。本文提出以多目標粒子群算法為基礎框架的LMPSO算法，針對所優化問題的高維特征，利用超體積指標作為適應值以指導算法的交配選擇與環境選擇，通過問題變換策略充分挖掘決策空間內的優化信息。最終以溪洛渡-向家壩梯級水庫為研究實例，將4種多目標進化算法與LMPSO進行比較分析，實驗結果表明：LMPSO算法的總體表現較對比算法有明顯提升，且在高維情況下其性能優勢更為顯著，故更適合應用于當前形勢下的梯級水庫多目標優化調度中。下一步的工作將著力于研究LMPSO算法在其它類型的水資源多目標優化調度上的使用效果。