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

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

雙層多種群PSO在水庫群供水優(yōu)化調(diào)度中應(yīng)用

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

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

1 引言

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

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

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

2 基本粒子群優(yōu)化算法

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

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

3 DE-TMPSO算法

3.1 思想與結(jié)構(gòu)

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

圖1 DE-TMPSO算法結(jié)構(gòu)圖

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

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

3.2 進化規(guī)則

（1）下層普通子群的進化規(guī)則

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

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

（2）上層精英種群的進化規(guī)則

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

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

其他情況：

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

總結(jié)上述進化規(guī)則，可以得到DE-TMPSO算法的具體實現(xiàn)流程圖，如圖2所示。

圖2 DE-TMPSO算法流程圖

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

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

表1 測試函數(shù)

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

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

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

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

4 DE-TMPSO算法在水庫群供水優(yōu)化調(diào)度問題中的應(yīng)用

圖5所示為我國贛江流域下游部分的網(wǎng)絡(luò)系統(tǒng)概化圖。

圖5 流域網(wǎng)絡(luò)系統(tǒng)概化圖

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

4.1 水庫群供水優(yōu)化調(diào)度問題的基本模型

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

約束條件：

4.2 帶罰函數(shù)的水庫群供水優(yōu)化調(diào)度模型

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

最終問題的目標函數(shù)修正為：

4.3 問題求解

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

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

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

圖6 水量調(diào)度問題運行20次平均最優(yōu)值對比

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

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

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

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

5 結(jié)語

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

[1]郭生練，陳炯宏，劉攀，等.水庫群聯(lián)合優(yōu)化調(diào)度研究進展與展望[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]王大志.面向?qū)嶋H工程問題的粒子群優(yōu)化算法應(yīng)用技術(shù)的研究[D].沈陽：東北大學，2009.

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

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

[7]呂林，羅綺，劉俊勇，等.一種基于多種群分層的粒子群優(yōu)化算法[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]李愛國.多協(xié)同粒子群優(yōu)化算法[J].復(fù)旦大學學報，2004，43 （5）：923-925.

[11]高芳.智能粒子群優(yōu)化算法研究[D].哈爾濱：哈爾濱工業(yè)大學，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]劉建平.基于混沌和差分進化的混合粒子群優(yōu)化算法[J].計算機仿真，2012，29（2）：208-212.

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

[15]吳茜，鄭金華，宋武.改進的粒子群算法求解非線性約束優(yōu)化問題[J].計算機工程與應(yīng)用，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

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

供水優(yōu)化調(diào)度；水庫群；多種群粒子群；差分進化

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）；上海市優(yōu)秀學術(shù)帶頭人計劃項目（No.11XD1400100）；上海領(lǐng)軍人才專項資金；上海市科學技術(shù)委員會重點基礎(chǔ)研究項目（No.11JC1400200）；中央高校基本科研業(yè)務(wù)費專項資金。

卿逸男（1988—），女，碩士研究生，從事智能系統(tǒng)、優(yōu)化調(diào)度等研究；丁永生（1967—），男，博士，教授，博士生導(dǎo)師，從事智能系統(tǒng)、網(wǎng)絡(luò)智能、物聯(lián)網(wǎng)等研究；曾獻輝（1974—），男，博士，副教授，從事智能系統(tǒng)、數(shù)字化紡織等研究；郝礦榮（1964—），女，博士后，教授，博士生導(dǎo)師，從事機器視覺、模式識別等研究。E-mail：ysding@dhu.edu.cn

2012-08-06

2012-12-05

1002-8331（2013）05-0263-05