離散猴群算法及其在輸電網(wǎng)擴展規(guī)劃中的應(yīng)用

王靖然，余貽鑫，曾 沅

離散猴群算法及其在輸電網(wǎng)擴展規(guī)劃中的應(yīng)用

王靖然，余貽鑫，曾 沅

(天津大學(xué)智能電網(wǎng)教育部重點實驗室，天津 300072)

猴群算法(MA)是一種只適于求解連續(xù)變量優(yōu)化問題的群智能算法. 針對MA的局限并結(jié)合輸電網(wǎng)擴展規(guī)劃問題的特點，設(shè)計了能夠求解含有離散變量優(yōu)化問題的離散猴群算法(DMA). 算法中提出的大、小2種爬過程解決了原猴群算法求解離散優(yōu)化問題時爬過程失效的問題，合作過程和隨機擾動機制的引入也提高了算法的計算效率. 算例結(jié)果表明，DMA計算速度快，魯棒性強，用很小的猴群規(guī)模就能夠?qū)Σ煌S數(shù)的輸電網(wǎng)擴展規(guī)劃問題均達(dá)到很好的計算效果.

輸電網(wǎng)擴展規(guī)劃；離散猴群算法；爬過程；進(jìn)化計算；群智能

輸電網(wǎng)擴展規(guī)劃問題在數(shù)學(xué)上是一個大規(guī)模的組合優(yōu)化問題．目前，其求解技術(shù)主要包括3類：數(shù)學(xué)優(yōu)化方法、啟發(fā)式方法和現(xiàn)代啟發(fā)式方法[1]．雖然經(jīng)典的數(shù)學(xué)優(yōu)化方法能夠從理論上保證解的最優(yōu)性，但在求解較大規(guī)模的問題時往往需要相當(dāng)長的計算時間[2]．而啟發(fā)式方法在求解大規(guī)模問題時更難以保證解的質(zhì)量[3]．

近年來，現(xiàn)代啟發(fā)式方法由于實現(xiàn)簡單、不受搜索空間和目標(biāo)函數(shù)形態(tài)的制約而得到了廣泛的應(yīng)用．文獻(xiàn)[4-7]將遺傳算法應(yīng)用于求解輸電網(wǎng)擴展規(guī)劃問題，取得了不錯的效果．文獻(xiàn)[8]采用了一種新的離散化粒子群方法求解該問題．文獻(xiàn)[9-10]分別對粒子群算法進(jìn)行改進(jìn)以提高算法的全局收斂能力．此外，模擬退火算法[11]、禁忌搜索算法[12]以及蟻群算法[13]等也都在求解輸電網(wǎng)擴展規(guī)劃問題中得到了應(yīng)用．但這類算法在求解大規(guī)模問題時必須具有較大的(種)群規(guī)模，而這會導(dǎo)致更長的計算時間；如果種群規(guī)模過小，則極易陷入局部最優(yōu)．

猴群算法(monkey algorithm，MA)是一種適于求解大規(guī)模優(yōu)化問題的群智能算法，但只能夠求解含連續(xù)變量的優(yōu)化問題．筆者根據(jù)輸電網(wǎng)擴展規(guī)劃問題的特點，改進(jìn)了猴群算法的爬過程，并引入合作過程和隨機擾動機制，設(shè)計了能夠求解含有離散變量優(yōu)化問題的離散猴群算法．將該算法應(yīng)用于求解目標(biāo)年輸電網(wǎng)擴展規(guī)劃問題，算例的對比結(jié)果表明了其實用性和有效性．

1 猴群算法基本原理

猴群算法是模擬猴子的爬山過程而設(shè)計的群優(yōu)化算法，適合于求解多變量、多峰函數(shù)的優(yōu)化問題[14]．算法在問題的求解過程中，利用目標(biāo)函數(shù)在當(dāng)前解處的偽梯度信息，通過猴群中每只猴子的爬過程、當(dāng)前解鄰域內(nèi)的望-跳過程以及各猴子的翻過程，不斷搜索解空間的各個區(qū)域直至找到問題的全局最優(yōu)解．

猴群算法的優(yōu)點體現(xiàn)在：①不要求目標(biāo)函數(shù)連續(xù)或可微，線性或非線性的問題均可求解；②算法實現(xiàn)簡單，需要調(diào)整的參數(shù)較少；③能夠求解維數(shù)較高的優(yōu)化問題，且猴群規(guī)模對問題的維數(shù)不敏感．但該算法只適于求解連續(xù)變量的優(yōu)化問題，而對含有離散變量的優(yōu)化問題，偽梯度不能總是給出下降的搜索方向，從而導(dǎo)致爬過程失效，算法無法求解．

2 求解輸電網(wǎng)擴展規(guī)劃問題的離散猴群算法

2.1 輸電網(wǎng)擴展規(guī)劃問題的數(shù)學(xué)模型

對規(guī)劃水平年確定的電源規(guī)劃方案和負(fù)荷水平，滿足靜態(tài)安全性約束的目標(biāo)年輸電網(wǎng)擴展規(guī)劃模型為

式中：X=(x1,x2,···,xn)T；xj為第j條可擴建輸電走廊上新建的線路數(shù)量；xMj為其上限；cj為建設(shè)1條線路的投資成本；n為系統(tǒng)可擴建輸電走廊數(shù)；B為系統(tǒng)電納矩陣；θ為節(jié)點電壓相角向量；Pg和Pd分別為節(jié)點有功發(fā)電出力和有功負(fù)荷列向量；Pl為支路l的有功潮流；PlM為支路l最大容許傳輸功率；L和L′分別為系統(tǒng)原有支路和新建支路的集合．整個模型求解的是在滿足節(jié)點功率平衡約束式(2)、支路潮流約束式(3)和架線數(shù)量約束式(4)的條件下投資最小的規(guī)劃方案．

2.2離散猴群算法

第2.1節(jié)中的輸電網(wǎng)擴展規(guī)劃模型是一個含有離散變量的組合優(yōu)化問題，難以用原有的猴群算法求解．為此設(shè)計離散猴群算法(discrete MA，DMA)如下．

1)解的表述

設(shè)猴群的規(guī)模為M，對猴群中的第i只猴子，其當(dāng)前位置定義為

式中Xi的各分量對應(yīng)于系統(tǒng)可擴建的輸電走廊，每一分量上的值xi,1,xi,2,···,xi,n表示相應(yīng)輸電走廊上的架線數(shù)．這樣每只猴子的當(dāng)前位置對應(yīng)于一個候選規(guī)劃方案．

2)目標(biāo)函數(shù)的修正

電網(wǎng)規(guī)劃中常常需要將孤立的發(fā)電、負(fù)荷節(jié)點或孤立的小系統(tǒng)連入已有系統(tǒng)，而隨機產(chǎn)生的規(guī)劃方案往往難以滿足連通性或線路傳輸功率限值要求，因此將網(wǎng)絡(luò)連通性和支路有功潮流約束式(3)以懲罰項的形式加入目標(biāo)函數(shù)，修正的目標(biāo)函數(shù)為

式中：OW為網(wǎng)絡(luò)連通但出現(xiàn)支路過負(fù)荷時的懲罰系數(shù)；IW為網(wǎng)絡(luò)不連通時的懲罰值．

3)爬過程

設(shè)第i只猴子的當(dāng)前位置為Xi=(xi,1,xi,2, ···,x)T，i∈{1,2,··,M}．爬過程可分為2種，大步爬i,n

過程和小步爬過程．

(1)大步爬過程步驟如下．

步驟1 隨機產(chǎn)生向量ΔX=(Δx,Δx,···,Δx)T,ii,1i,2i,n其中Δxi,j為從區(qū)間[?aL,aL]中隨機產(chǎn)生的整數(shù)，j∈{1,2,··,n}．a(chǎn)L稱為大步爬過程的步長．

步驟2 計算f(Xi+ΔXi)和f(Xi?ΔXi)．

步驟3 如果f (Xi+ΔXi)＜f(Xi?ΔXi)且f(Xi+ ΔXi)＜f (Xi)，則令Xi=Xi+ΔXi；

如果f (Xi?ΔXi)＜f (Xi+ΔXi)且f(Xi?ΔXi)＜f(Xi)，則令Xi=Xi?ΔXi．

步驟4 重復(fù)步驟1～步驟3，直到目標(biāo)函數(shù)值不再發(fā)生變化或達(dá)到預(yù)先設(shè)定的次數(shù)C,LN．

(2)小步爬過程步驟如下．

步驟1 依次隨機產(chǎn)生向量ΔXi=(0,···,0,Δxi,j, 0,···,0)T，j∈{1,2,··,n}，其中Δx為從區(qū)間[?a,a]中

i,jSS隨機產(chǎn)生的非零整數(shù)．a(chǎn)S稱為小步爬過程的步長．

步驟2 計算f(Xi+ΔXi)和f(Xi?ΔXi)．

步驟3 如果f (Xi+ΔXi)＜f(Xi?ΔXi)且f(Xi+ ΔXi)＜f (Xi)，則令Xi=Xi+ΔXi；

如果f (Xi?ΔXi)＜f (Xi+ΔXi)，且f(Xi?ΔXi)＜f(Xi)，則令Xi=Xi?ΔXi．

步驟4 重復(fù)步驟1～步驟3，直到目標(biāo)函數(shù)值不再發(fā)生變化或達(dá)到預(yù)先設(shè)定的次數(shù)C,SN．

4)望-跳過程

經(jīng)過爬過程，每只猴子都達(dá)到了各自較優(yōu)的位置，在此位置上，每只猴子都在一定的視野范圍內(nèi)向周圍眺望，如果發(fā)現(xiàn)了更好的位置(更優(yōu)的解)，則跳向那個位置，進(jìn)而重復(fù)爬過程．對于第i只猴子，i∈{1,2,··,M}，望-跳過程的計算步驟如下．

步驟2 如果f(Xi′ )＜f(Xi)，則令Xi=Xi′．

步驟3 重復(fù)步驟1和步驟2，直至達(dá)到預(yù)先設(shè)定的次數(shù)WN．

5)合作過程

在爬過程和望-跳過程之后，每只猴子都到達(dá)了其鄰域內(nèi)的較優(yōu)位置，但各猴子的位置必然存在優(yōu)劣的差異．合作過程就是讓爬山能力強、處于較優(yōu)位置的猴子與處于較差位置的猴子合作，以共同找到更好的解．

設(shè)本代中出現(xiàn)的最優(yōu)猴子的位置為X?=,,···,)T，對于第i只猴子的當(dāng)前位置，合作過程的步驟如下．

步驟1 在[0,1]內(nèi)隨機產(chǎn)生實數(shù)α．

步驟3 令Xi=重復(fù)爬過程．

合作過程能夠顯著增強算法的尋優(yōu)能力，增加找到的解的多樣性．

6)翻過程

翻過程的目的是使猴群能夠探索新的搜索區(qū)域，其步驟如下．

步驟1 在[c,d]區(qū)間內(nèi)隨機產(chǎn)生實數(shù)β．

步驟3 對?i∈{1,2,··,M}，?j∈{1,2,··,n}計算

步驟4 令Xi=，重復(fù)爬過程．

在步驟1中，區(qū)間[c,d]稱為翻區(qū)間，決定了猴子從當(dāng)前位置能夠翻至的最大距離．如果猴子的新位置大于其上限，則令=；如果小于0，則令=0．

7)隨機擾動機制

在翻過程中，當(dāng)所有猴子的第j位xi,j均相同時，由式(7)可知，此時=xi,j，翻過程將失去作用．為此，引入隨機擾動機制：隨機選取猴群中的某只猴子k∈{1,2,··,M}，令中隨機產(chǎn)生的均勻分布的整數(shù)，且e不等于xi,j的原值，之后再進(jìn)行猴群的翻過程．

隨機擾動機制的引入增加了猴群的多樣性，使搜索過程避免陷入局部最優(yōu)．

8)終止準(zhǔn)則

與通常的智能算法相似，DMA可以有兩種終止準(zhǔn)則：

(1)當(dāng)達(dá)到預(yù)先設(shè)定的搜索代數(shù)時計算終止；(2)當(dāng)所找到的最優(yōu)解連續(xù)K代不發(fā)生變化時計算終止．

為了減少額外的計算時間，采用第2種終止準(zhǔn)則，其中K的取值應(yīng)根據(jù)問題規(guī)模的大小確定．

2.3離散猴群算法的計算流程

求解目標(biāo)年輸電網(wǎng)擴展規(guī)劃問題的離散猴群算法計算流程如圖1所示．

在圖1中，猴群經(jīng)過爬過程、望-跳過程、合作過程和翻過程之后完成了一次搜索過程，稱之為一代．問題的最優(yōu)解可能出現(xiàn)在搜索過程中的任何一代，算法也不存在所有猴子都收斂的說法．

圖1 離散猴群算法計算流程Fig.1 Flow chart for DMA

3 算例分析

3.118節(jié)點系統(tǒng)

18節(jié)點系統(tǒng)的簡化網(wǎng)絡(luò)接線圖如圖2所示，虛線表示可擴建線路走廊，實線表示已有線路．系統(tǒng)原始參數(shù)見文獻(xiàn)[15]，所求問題的規(guī)模為21維．采用Matlab編程，取猴群規(guī)模M=5，爬過程的步長aL=1，aS=1，次數(shù)NC,L=7，NC,S=4，眺望視野b=1，翻區(qū)間為[?20,20]．隨機產(chǎn)生初始猴群，每代4次合作，經(jīng)過50次測試計算的結(jié)果如表1所示，表中同時列出了原始猴群算法(primary MA，PMA)、加入模擬退火機制的改進(jìn)遺傳算法(improved genetic algorithm，IGA)和慣性權(quán)重隨代數(shù)逐漸下降的離散粒子群算法(discrete particle swarm optimization， DPSO)的計算結(jié)果，其中原始猴群算法是指嚴(yán)格按照文獻(xiàn)[14]的計算流程且將所涉及到的變量全部整數(shù)化的猴群算法．

圖2 18節(jié)點系統(tǒng)簡化網(wǎng)絡(luò)接線Fig.2 Simplified network connection for 18-bus system

表1 DMA與PMA、IGA和DPSO算法計算18節(jié)點系統(tǒng)的比較Tab.1 Comparison among DMA，PMA，IGA and DPSO in 18-bus system

從表1中可以看到，對于18節(jié)點系統(tǒng)，由于此時問題的規(guī)模較大，未經(jīng)改進(jìn)的原始爬過程失效，PMA完全找不到最優(yōu)解．而DMA僅需要5只猴子在5代之內(nèi)就能找到最優(yōu)解，50次計算中有25次在第1代就找到了最優(yōu)解，其首次出現(xiàn)的平均代數(shù)為1.9代，從開始到計算終止的平均計算時間為32.9 s．DPSO和IGA算法需要用300個粒子或個體才能達(dá)到接近100%的收斂率，計算時間也較DMA長．計算中還發(fā)現(xiàn)，DMA能夠找到2個投資成本相同的最優(yōu)解：1-111x=，4-161x=，5-121x=，6-131x=(或7-131x=)，6-142x=，7-81x=，8-91x=，9-102x=，14-151x=，16-172x=，17-181x=，有時這2個最優(yōu)解甚至在同一代內(nèi)出現(xiàn)，這說明DMA不但具有很強的尋優(yōu)能力，而且找到的解具有很強的多樣性．

表2為猴群規(guī)模取不同值時DMA的計算結(jié)果．可以看到，隨著猴群規(guī)模的減小，每代的計算時間相應(yīng)減小，而最優(yōu)解首次出現(xiàn)的代數(shù)有所增加．但即使只有2只猴子，DMA也能夠以100%的概率找到最優(yōu)解．經(jīng)對比可知，當(dāng)猴群規(guī)模為4～6時，算法均能達(dá)到滿意的計算效果．

表2 猴群規(guī)模對DMA尋優(yōu)能力的影響Tab.2 Effect of population size of monkeys on computational capability of DMA

3.2IEEE 24節(jié)點系統(tǒng)

IEEE 24節(jié)點系統(tǒng)共有41條可擴建線路走廊，網(wǎng)絡(luò)結(jié)構(gòu)和原始參數(shù)見文獻(xiàn)[16-17]．表3列出了DMA與IGA、DPSO算法的對比結(jié)果．其中，DMA的參數(shù)設(shè)置如下：猴群規(guī)模5M=，爬過程的步長aL=1，aS=1，次數(shù)NC,L=8，NC,S=4，眺望視野b=1，翻區(qū)間為[?20,20]，每代4次合作．

表3 DMA與IGA、DPSO算法計算24節(jié)點系統(tǒng)的比較Tab.3 Comparison among DMA，IGA and DPSO in 24-bus system

當(dāng)所求解系統(tǒng)的規(guī)模增加到41維時，IGA和DPSO算法需要的(種)群規(guī)模和計算時間均顯著增加，且難以達(dá)到100%的收斂率；而DMA仍然只需要5只猴子就能以100%的概率找到最優(yōu)解：6-101x=，7-82x=，10-121x=，14-161x=，16-171x=，20-231x=，其平均計算終止時間僅為80.7 s．由此可見，當(dāng)系統(tǒng)的規(guī)模增加時，DMA仍具有很強的尋優(yōu)能力，相比之下的優(yōu)越性也更為明顯．

表4示出了合作過程對DMA尋優(yōu)能力的影響．從表4中可見，當(dāng)沒有合作過程時，算法雖然也能以100%的概率找到最優(yōu)解，但最優(yōu)解首次出現(xiàn)的代數(shù)顯著增加．這說明合作過程能夠顯著提高DMA的搜索能力，加快尋優(yōu)過程．

表4 合作過程對DMA尋優(yōu)能力的影響Tab.4 Effect of cooperation process on computational capability of DMA

4 結(jié) 論

針對猴群算法只能求解連續(xù)變量優(yōu)化問題的不足，結(jié)合輸電網(wǎng)擴展規(guī)劃問題的特點，本文從解的表述、目標(biāo)函數(shù)的修正、爬過程、望-跳過程、合作過程、翻過程、隨機擾動機制以及終止準(zhǔn)則等方面設(shè)計了能夠求解含有離散變量優(yōu)化問題的離散猴群算法，解決了爬過程失效的問題．通過對18節(jié)點系統(tǒng)和IEEE 24節(jié)點系統(tǒng)的計算，結(jié)果表明：

(1)通常情況下，離散猴群算法僅需4～6只猴子就能夠達(dá)到很好的計算效果；

(2)合作過程的引入顯著增強算法的尋優(yōu)能力；

(3)相對于遺傳算法和離散粒子群算法，離散猴群算法計算速度快，魯棒性強，尤其適于求解較大規(guī)模的優(yōu)化問題．

本文中提出的僅是基本的離散猴群算法，具有一定的求解離散優(yōu)化問題的通用性，如何與更高效的局部優(yōu)化方法相結(jié)合以提高其計算效率，是需要進(jìn)一步研究的工作．

［1］ 段 剛，余貽鑫. 電力系統(tǒng)NP難問題全局優(yōu)化算法的研究[J]. 電力系統(tǒng)自動化，2001，25(5)：14-18.

Duan Gang，Yu Yixin. A study on global optimization for NP hard problems in power systems [J]. Automation of Electric Power Systems，2001，25(5)：14-18(in Chinese).

［2］ Latorre G，Cruz R D，Areiza J M，et al. Classification of publications and models on transmission expansion planning [J]. IEEE Transactions on Power Systems，2003，18(2)：938-946.

［3］ Romero R，Monticelli A，Garcia A，et al. Test systems and mathematical models for transmission network expansion planning [J]. IEE Proceedings：Generation，Transmission and Distribution，2002，149(1)：27-36.

［4］ 段 剛，余貽鑫. 輸配電系統(tǒng)綜合規(guī)劃的全局優(yōu)化算法[J]. 中國電機工程學(xué)報，2002，22(4)：109-113.

Duan Gang，Yu Yixin. Giobal optimization for power transmission and distribution system planning[J]. Proceedings of the CSEE，2002，22(4)：109-113(in Chinese).

［5］ 王秀麗，王錫凡. 遺傳算法在輸電系統(tǒng)規(guī)劃中的應(yīng)用[J]. 西安交通大學(xué)學(xué)報，1995，29(8)：1-9.

Wang Xiuli，Wang Xifan. Transmission system planning with genetic algorithm[J]. Journal of Xi’an JiaotongUniversity，1995，29(8)：1-9(in Chinese).

［6］ Gallego R A，Monticelli A，Romero R. Transmission system expansion planning by an extended genetic algorithm [J]. IEE Proceedings：Generation，Transmission and Distribution，1998，145(3)：329-335.

［7］ da Silva E L，Gil H A，Areiza J M. Transmission network expansion planning under an improved genetic algorithm[J]. IEEE Transactions on Power Systems，2000，15(3)：1168-1175.

［8］ Jin Yixiong，Cheng Haozhong，Yan Jianyong，et al. New discrete method for particle swarm optimization and its application in transmission network expansion planning[J]. Electric Power Systems Research，2007，77(3/4)：227-233.

［9］ 胡家聲，郭創(chuàng)新，葉 彬，等. 離散粒子群優(yōu)化算法在輸電網(wǎng)絡(luò)擴展規(guī)劃中的應(yīng)用[J]. 電力系統(tǒng)自動化，2004，28(20)：31-36.

Hu Jiasheng，Guo Chuangxin，Ye Bin，et al. Application of discrete particle swarm optimization to transmission network expansion planning[J]. Automation of Electric Power Systems，2004，28(20)：31-36(in Chinese).

［10］ 金義雄，程浩忠，嚴(yán)健勇，等. 改進(jìn)粒子群算法及其在輸電網(wǎng)規(guī)劃中的應(yīng)用[J]. 中國電機工程學(xué)報，2005，25(4)：46-50.

Jin Yixiong，Cheng Haozhong，Yan Jianyong，et al. Improved particle swarm optimization method and its application in power transmission network planning[J]. Proceedings of the CSEE，2005，25(4)：46-50(in Chinese).

［11］ Romero R，Gallego R A，Monticelli A. Transmission system expansion planning by simulated annealing[J]. IEEE Transactions on Power Systems，1996，11(1)：364-369.

［12］ da Silva E L，Ortiz J M A，de Oliveira G C，et al. Transmission network expansion planning under a tabu search approach[J]. IEEE Transactions on Power Systems，2001，16(1)：62-68.

［13］ 陳根軍，王 磊，唐國慶. 基于蟻群最優(yōu)的輸電網(wǎng)絡(luò)擴展規(guī)劃[J]. 電網(wǎng)技術(shù)，2001，25(6)：21-24.

Chen Genjun，Wang Lei，Tang Guoqing. An ant colony optimization method for transmission network expansion planning[J]. Power System Technology，2001，25(6)：21-24(in Chinese).

［14］ Zhao Ruiqing，Tang Wansheng. Monkey algorithm for global numerical optimization[J]. Journal of Uncertain Systems，2008，2(3)：164-175.

［15］ Wang Xifan，McDonald J R. Modern Power System Planning[M]. London：McGraw-Hill Publishing Company，1994.

［16］ Reliability Test System Task Force of the Application of Probability Methods Subcommittee. IEEE Reliability Test System[J]. IEEE Transactions on Power Apparatus and Systems，1979，98(6)：2047-2054.

［17］ Fang Risheng，Hill D J. A new strategy for transmission expansion in competitive electricity markets[J]. IEEE Transactions on Power Systems，2003，18(1)：374-380.

Discrete Monkey Algorithm and Its Application in Transmission Network Expansion Planning

WANG Jing-ran，YU Yi-xin，ZENG Yuan
(Key Laboratory of Smart Grid of Ministry of Education，Tianjin University，Tianjin 300072，China)

Monkey algorithm(MA)is a swarm intelligence algorithm only for optimization problems with continuous variables. In view of the limitations of MA and the features of transmission network expansion planning，discrete monkey algorithm(DMA)is proposed for optimization problems with discrete variables. Large-step and small-step climb processes were designed to tackle the problem of invalid climb process in discrete optimization with primary MA. Cooperation process and stochastic perturbation mechanism were also introduced to improve the computational efficiency of the proposed algorithm. The numerical results demonstrate that DMA has strong robustness and is capable of solving expansion planning problems of various dimensions efficiently and rapidly with small population size. Keywords：transmission network expansion planning；discrete monkey algorithm；climb process；evolutionary computation；swarm intelligence

TM715

A

0493-2137(2010)09-0798-06

2009-10-10；

2010-05-05.

“十一五”國家科技支撐計劃重大資助項目(2008BAA13B01)．

王靖然（1982— ），男，博士研究生，jrwang@tju.edu.cn.

余貽鑫，yixinyu@tju.edu.cn.