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

卿逸男，丁永生，2，曾獻(xiàn)輝，2，郝礦榮，2

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

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

卿逸男1，丁永生1，2，曾獻(xiàn)輝1，2，郝礦榮1，2

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

1 引言

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

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

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

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

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

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

3 DE-TMPSO算法

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

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

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

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

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

3.2 進(jìn)化規(guī)則

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

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

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

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

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

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

其他情況：

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

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

圖2 DE-TMPSO算法流程圖

3.3 DE-TMPSO與基本PSO的對(duì)比測(cè)試

為了測(cè)試DE-TMPSO算法的性能，使用標(biāo)準(zhǔn)的Benchmar 和Rastrigin函數(shù)進(jìn)行測(cè)試實(shí)驗(yàn)。它們?cè)诮饪臻g內(nèi)都有多個(gè)局部極值，是測(cè)試算法全局搜索性能較好的函數(shù)，如表1所示。

表1 測(cè)試函數(shù)

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

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

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

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

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

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

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

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

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

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

約束條件：

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

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

最終問(wèn)題的目標(biāo)函數(shù)修正為：

4.3 問(wèn)題求解

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

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

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

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

表3 2種算法運(yùn)行20次的各項(xiàng)指標(biāo)對(duì)比

表4 2種算法計(jì)算得各時(shí)段各水庫(kù)下泄流量對(duì)比

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

表5 2種算法計(jì)算得各時(shí)段各河段缺水流量對(duì)比

5 結(jié)語(yǔ)

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

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

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

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

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

[11]高芳.智能粒子群優(yōu)化算法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，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ìn)化的混合粒子群優(yōu)化算法[J].計(jì)算機(jī)仿真，2012，29（2）：208-212.

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

[15]吳茜，鄭金華，宋武.改進(jìn)的粒子群算法求解非線性約束優(yōu)化問(wèn)題[J].計(jì)算機(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

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

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

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.

國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目（No.61134009）；國(guó)家自然科學(xué)基金（No.60975059）；教育部高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金（No.20090075110002）；上海市優(yōu)秀學(xué)術(shù)帶頭人計(jì)劃項(xiàng)目（No.11XD1400100）；上海領(lǐng)軍人才專項(xiàng)資金；上海市科學(xué)技術(shù)委員會(huì)重點(diǎn)基礎(chǔ)研究項(xiàng)目（No.11JC1400200）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金。

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

2012-08-06

2012-12-05

1002-8331（2013）05-0263-05