雙層多種群PSO在水庫群供水優化調度中應用

卿逸男，丁永生，2，曾獻輝，2，郝礦榮，2

1.東華大學 信息科學與技術學院，上海 2016202.數字化紡織服裝技術教育部工程研究中心，上海 201620

雙層多種群PSO在水庫群供水優化調度中應用

卿逸男1，丁永生1，2，曾獻輝1，2，郝礦榮1，2

1.東華大學 信息科學與技術學院，上海 201620
2.數字化紡織服裝技術教育部工程研究中心，上海 201620

1 引言

我國水資源時空分布不均，缺水問題嚴重影響著人民的生活生產以及生態環境，合理高效地利用水資源是目前亟待解決的問題。如何通過水庫群聯合水量優化調度，更好地調配有限水資源一直是研究的熱點問題。水庫群供水優化調度問題是一個具有各類約束條件的大型、動態的負載非線性系統的優化問題，國內外學者進行了廣泛研究，其中包括：動態規劃法、網絡流法、大系統分解協調、人工神經網絡法、遺傳算法、模擬退火算法等[1]。

粒子群優化（PSO）算法是由Kennedy和Eberhart于1995年提出的一類基于群智能的隨機優化算法[2]，其思想來源于對鳥群捕食行為的研究，PSO算法有著算法簡單、容易實現，并且可調參數少等特點，適用于求解大量非線性、不可微和多峰值的復雜優化問題，已應用于多個學科和工程領域[3-5]。但通過研究發現基本PSO算法本身存在較強的“趨同性”，在進化過程中會導致多樣性的大量喪失，常常會陷入到局部最優解中，全局搜索能力較差，求解精度不高；同時，在算法后期收斂速度較慢。如何保持群體的多樣性，避免算法過早地陷入局部極值是改進粒子群算法的一個直接出發點。

本文在前人研究[6-11]的基礎上提出一種帶差分進化的雙層多種群粒子群優化算法（DE-TMPSO），利用多個普通子群覆蓋不同的解空間，加大粒子的多樣性；同時利用精英種群重點進行局部搜索，添加差分進化操作有效地減少陷入局部極值的概率，具有更好的全局搜索能力和局部搜索能力，提高了算法的效能。

2 基本粒子群優化算法

其中，i=1，2，…，m，m為種群規模；d=1，2，…，n，n為粒子維數；c1和c2分別為認知部分和社會部分的加速常數，一般設定速度上限vmax；r1和r2為均勻分布于[0，1]之間的隨機數；ω為慣性權重值，是一種控制群的搜索和挖掘能力的機制，大的ω值有利于全局探索，多樣性增加，小的ω值促進局部的挖掘[12]，建議采用線性遞減權策略：

其中，k為當前進化代數，kmax為最大進化代數，ωstart為初始慣性權值，ωend為進化至最大代數時的慣性權值（終止慣性權值）。

3 DE-TMPSO算法

3.1 思想與結構

DE-TMPSO算法分成上下兩個層次：上層由具有問題較好解的粒子組成的精英種群，下層由N個普通子群構成，上下兩層組成一個相互影響的閉環循環，如圖1所示。

圖1 DE-TMPSO算法結構圖

下層的各個普通子群之間相互獨立地進化，并從精英種群中得到優良信息指導自己的進化進程；各個基礎種群將進化得到的優良粒子貢獻出來，輸送給精英種群。每個普通子群分別進行初始化和獨立搜索。為了確保候選解的多樣性以防止算法陷入局部最優解，每個子群分別設置不同的參數。具有粗粒度參數的子群負責搜索全局最優解，而其他種群用于細化局部搜索和增強求解精度。

上層的精英種群從每個子群選擇較好的粒子來進行初始化，并在迭代過程中不斷地選取每個子群中最好的粒子來替換自身較差的個體。為減少算法陷入局部最小值的可能，在精英種群中添加差分進化操作，有助于粒子跳出局部極值，同時差分進化操作不會出現因變異而產生的倒退，能夠保證算法的整體最優值不受到影響。反過來，選取精英種群中前N（N為下層普通種群個數）個粒子隨機分配到各個普通子群中指導它們進化更新。

3.2 進化規則

（1）下層普通子群的進化規則

在普通子群的進化規則中添加向精英粒子飛行的速度分量，將基本粒子群中的粒子速度更新公式更改如下：

其中，c3是加速度常量，r3是[0，1]區間的隨機數，Gbest為精英粒子位置，粒子位置按照公式（2）進行更新，慣性權值ω按照公式（3）進行更新。

（2）上層精英種群的進化規則

精英種群中的粒子通過式（1）（2）更新速度和位置，進一步用差分進化操作為精英粒子群增加一定的隨機擾動，減少算法陷入局部最優解的可能[13-14]。差分進化（DE）利用3個隨機選擇的父代的算術交叉算子。令 x1(t)≠x2(t)≠ x3() t為從群中隨機取出的3個粒子位置。粒子i的每一維根據下式進行計算：

如果U(0 ，1)≤Pc或j=U(1 ，n)：

其他情況：

其中Pc∈( ) 0，1為交叉概率，且β＞0為縮放因子。僅當新的個體位置取得更好的適應度值時，xi( ) t+1才被置為xi′(t +1)。

總結上述進化規則，可以得到DE-TMPSO算法的具體實現流程圖，如圖2所示。

圖2 DE-TMPSO算法流程圖

3.3 DE-TMPSO與基本PSO的對比測試

為了測試DE-TMPSO算法的性能，使用標準的Benchmar 和Rastrigin函數進行測試實驗。它們在解空間內都有多個局部極值，是測試算法全局搜索性能較好的函數，如表1所示。

表1 測試函數

在測試中，維數取10，迭代200次，DE-TMPSO算法取3個普通子群和1個精英種群，種群規模均為30，基本PSO算法種群規模取120，運行30次測試，求平均最優值作為性能比較的依據，得到的進化曲線如圖3和圖4所示。

從測試結果可以看出，在粒子總體規模相同、迭代次數相同的情況下，DE-TMPSO算法取得的最優值明顯優于基本PSO算法。測試結果表明DE-TMPSO算法具有更好的穩定性，并在一定程度上避免了“早熟”現象的發生，具有更好的全局搜索能力，同時收斂速度也得到了提高。

圖3 求解Benchmark函數30次的平均最小值對比

圖4 求解Rastrigin函數30次的平均最小值比較

4 DE-TMPSO算法在水庫群供水優化調度問題中的應用

圖5所示為我國贛江流域下游部分的網絡系統概化圖。

圖5 流域網絡系統概化圖

圖5中顯示了1條干流與4條支流，流域上有5座大中型水庫和5個水文站，以流域源頭、水庫和水文站作為節點，可將整條流域劃分為15個河段，河段標號如圖5所示。流域水庫群水量調度是對干支流上的水庫進行統一調度。為了協調上、中、下游和全年各月供水水量的矛盾，要求干支流水庫聯合調動，保證流域缺水量最小，由此建立流域水庫群供水優化調度數學模型。

4.1 水庫群供水優化調度問題的基本模型

目標函數：流域所有河段的最大供水缺水量最小。TW=min F() Q

約束條件：

4.2 帶罰函數的水庫群供水優化調度模型

水量調度基本模型中，水庫水量平衡約束是一個復雜約束。復雜約束的處理問題是各種進化算法在實際應用過程中的難點。目前，進化算法處理約束優化問題主要有四種方法：拋棄不可行解法、修復不可行解法、改進進化因子法和懲罰函數法[15]。本文將懲罰函數法引入PSO算法中解決此復雜約束問題：粒子更新后，進行最大值最小值的約束判別，對于不滿足約束的解，依照懲罰函數對該粒子的適應度值進行懲罰，設計懲罰函數如下：

最終問題的目標函數修正為：

4.3 問題求解

為保證算法公平性，基本PSO算法與DE-TMPSO算法的參數選取如表2所示，基本PSO算法的參數與DE-TMPSO算法中的精英種群一致。

表2 基本PSO算法與DE-TMPSO算法的參數選取

粒子的維數由水庫數與時段數決定，即維數=水庫數×時段數。本問題中考慮7～11月每個月的水庫下泄流量，則粒子為25維。水量調度中涉及到的各河段需水流量、耗水流量、區間來水流量及水庫庫容等相關數據都來自于江西省贛江流域。運行20次后，求平均值并作圖進行比較。從圖6可以看出DE-TMPSO算法在收斂速度和求解精度上都優于基本PSO算法，兩種算法求解的最優值比較如表3所示。由DE-TMPSO算法和基本PSO算法分別求解得到的各水庫每個月的下泄流量如表4所示，各河段每個月的缺水流量如表5所示。需要說明的是，表4中未列出河段1、3、4、10，因為這些河段在流域的源頭處，不能通過水庫的調節影響其水量分配。

圖6 水量調度問題運行20次平均最優值對比

表3 2種算法運行20次的各項指標對比

表4 2種算法計算得各時段各水庫下泄流量對比

從以上結果可以看出，DE-TMPSO算法取得了較好的調度效果，特別是能夠在7月至9月這些用水高峰期，通過增大各大出庫的出庫流量來滿足需求。算法在時段上有很好的均衡效果，例如調度方案中不會因為7月水量需求較大，過大地增加放水量，導致需求量依舊很大的8月份缺水很大，這樣不僅滿足了當月的需求量，還兼顧到了下一個月的水量分配。調度結果將所有河段在所有調度時段內的缺水都控制在150 m3/s以內，實現了在缺水情況下全流域聯動、等跨破壞的調度要求。同時，注意到基本PSO算法計算得到的所有河段在所有調度時段內的最大缺水量為160.84 m3/s，較此數據，DE-TMPSO算法將最大缺水量降低了7%左右。可見，應用DE-TMPSO算法求解水庫群水量調度問題結果更合理，更能夠滿足實際應用的要求。

表5 2種算法計算得各時段各河段缺水流量對比

5 結語

本文提出了一種帶差分進化的雙層多種群粒子群算法，算法由多個普通子群和1個精英種群組成，普通子群采用不同參數增加粒子群的多樣性，精英種群加入了差分進化操作，減低了算法陷入局部極值的概率。實驗證明這種DE-TMPSO算法具有更好的全局搜索能力，求解精度提高，收斂速度加快。將該算法應用于水庫群水量調度問題中，得到了庫群最優下泄水量策略和河段的供缺水情況，計算表明，本文提出的DE-TMPSO算法可以求解具有各類約束條件的大型、動態的負載非線性系統的優化問題，能緩減水庫群水量調度中的“維數災”問題，為水庫群供水優化調度提供了一種新途徑。

[1]郭生練，陳炯宏，劉攀，等.水庫群聯合優化調度研究進展與展望[J].水科學進展，2010，21（4）：496-500.

[2]Eberhart R C，Shi Y H.Particle swarm optimization：developments，applications and resources[C]//Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway，USA：IEEE Service Center，2001：81-86.

[3]謝曉峰，張文俊，楊之廉，等.粒子群算法綜述[J].控制與決策，2003，18（2）：129-134.

[4]王大志.面向實際工程問題的粒子群優化算法應用技術的研究[D].沈陽：東北大學，2009.

[5]鄧顯羽，彭勇，葉碎高，等.粒子群算法在水庫（群）優化調度研究中的應用綜述[J].水利水電科技進展，2010，30（5）：90-94.

[6]羅德相，周永權，黃華娟，等.多種群粒子群優化算法[J].計算機工程與應用，2010，46（19）：51-54.

[7]呂林，羅綺，劉俊勇，等.一種基于多種群分層的粒子群優化算法[J].四川大學學報：工程科學版，2008，40（5）：171-176.

[8]Van den Bergh F，Engelbrecht A P.A study of particle swarm optimization particle trajectories[J].Information Sciences，2006，176：937-971.

[9]Alba E，Luna F，Nebro A J，et al.Parallel heterogeneous genetic algorithms forcontinuous optimization[J].ParallelComputing，2004，30：699-719.

[10]李愛國.多協同粒子群優化算法[J].復旦大學學報，2004，43 （5）：923-925.

[11]高芳.智能粒子群優化算法研究[D].哈爾濱：哈爾濱工業大學，2008.

[12]Shi Y，Eberhart R C.A modified particle swarm optimizer[C]// Proceedings of the IEEE Congress on Evolutionary Computation.Anchorage，AK：[s.n.]，1998：69-73.

[13]劉建平.基于混沌和差分進化的混合粒子群優化算法[J].計算機仿真，2012，29（2）：208-212.

[14]辛斌，陳杰.粒子群優化與差分進化混合算法的綜述與分類[J].系統科學與數學，2011，31（9）：1130-1150.

[15]吳茜，鄭金華，宋武.改進的粒子群算法求解非線性約束優化問題[J].計算機工程與應用，2007，43（24）：61-64.

QING Yinan1,DING Yongsheng1，2,ZENG Xianhui1，2,HAO Kuangrong1，2

1.College of Information Sciences and Technology,Donghua University,Shanghai 201620,China
2.Engineering Research Center of Digitized Textile&Fashion Technology,Ministry of Education,Shanghai 201620,China

Aiming at the problem of optimal water supply dispatching for multi-reservoirs,it presents a Two-layer Multi-swarm Particle Swarm Optimal algorithm with Differential Evolution（DE-TMPSO）.The DE-TMPSO realizes the swarm size expansion and the dual parallel-running mechanism,so it can purposefully enhance the global search ability.Meanwhile the different granularity in multi sub-swarms parallel mechanism,dual direction optimal information flow between sub-swarms and differential evolution strategy also increase the local search ability.The DE-TMPSO can avoid the premature problem and increase the stability and the convergence rate.The DE-TMPSO is applied to optimal multi-reservoir water supply dispatching of a river in the south China.Results show that the DE-TMPSO is reasonable,and it provides a new approach for multi-dimensional and complicated optimization of multi-reservoir water supply dispatching.

optimal water supply dispatching;multi-reservoir;multi-swarm Particle Swarm Optimization（PSO）;differential evolution

針對水庫群供水優化調度問題，提出了一種帶差分進化的雙層多種群粒子群算法（DE-TMPSO）。該算法實現粒子群優化算法的群體拓展和雙并行運行機制，針對性地提高粒子群算法的全局搜索能力，同時采用不同粒度的多子群并行機制、種群間的雙向最優信息流動以及引入差分進化策略也提高了該算法的局部搜索能力，在一定程度上避免了“早熟”現象的發生，具有較好的穩定性，收斂速度也得到了提高。該算法應用于我國南方某流域的水庫群供水優化調度問題中，調度結果合理，為求解高維、復雜的水庫群供水優化調度提供了新的思路和方法。

供水優化調度；水庫群；多種群粒子群；差分進化

A

TP391

10.3778/j.issn.1002-8331.1208-0076

QING Yinan,DING Yongsheng,ZENG Xianhui,et al.Two-layer multi-swarm particle swarm optimal algorithm with application to optimal water supply dispatching of multi-reservoirs.Computer Engineering and Applications,2013,49 （5）：263-267.

國家自然科學基金重點項目（No.61134009）；國家自然科學基金（No.60975059）；教育部高等學校博士學科點專項科研基金（No.20090075110002）；上海市優秀學術帶頭人計劃項目（No.11XD1400100）；上海領軍人才專項資金；上海市科學技術委員會重點基礎研究項目（No.11JC1400200）；中央高校基本科研業務費專項資金。

卿逸男（1988—），女，碩士研究生，從事智能系統、優化調度等研究；丁永生（1967—），男，博士，教授，博士生導師，從事智能系統、網絡智能、物聯網等研究；曾獻輝（1974—），男，博士，副教授，從事智能系統、數字化紡織等研究；郝礦榮（1964—），女，博士后，教授，博士生導師，從事機器視覺、模式識別等研究。E-mail：ysding@dhu.edu.cn

2012-08-06

2012-12-05

1002-8331（2013）05-0263-05