卜冠南 劉建華 張冬陽(yáng) 胡任遠(yuǎn) 羅逸軒

(福建工程學(xué)院計(jì)算機(jī)科學(xué)與數(shù)學(xué)學(xué)院 福建 福州 350118)

(福建省大數(shù)據(jù)挖掘與應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室 福建 福州 350118)

0 引 言

配電網(wǎng)網(wǎng)架優(yōu)化是一個(gè)復(fù)雜的非線性組合優(yōu)化問(wèn)題,網(wǎng)絡(luò)中擁有大量的線路和負(fù)荷點(diǎn),主要內(nèi)容是找到一種使配電網(wǎng)絡(luò)建設(shè)的投資和運(yùn)行費(fèi)用最小的線路規(guī)劃方案,且同時(shí)需要滿足相關(guān)約束條件。常規(guī)數(shù)學(xué)優(yōu)化算法雖然在理論上可以求得最優(yōu)解,但實(shí)際上隨著配電網(wǎng)網(wǎng)架問(wèn)題的規(guī)模與復(fù)雜度的不斷增大時(shí),常規(guī)數(shù)學(xué)優(yōu)化算法很難有效地解決問(wèn)題,因此以往學(xué)者將智能算法應(yīng)用到配電網(wǎng)規(guī)劃問(wèn)題中,如禁忌搜索算法[2]、模擬退火算法[3-4]、粒子群算法[5-7]、遺傳算法[8-9]、差分進(jìn)化算法[10]、免疫二進(jìn)制螢火蟲(chóng)算法[11]等。但是這些算法也有一些不足,就是在求解大規(guī)模的配電網(wǎng)絡(luò)系統(tǒng)時(shí),往往無(wú)法實(shí)現(xiàn)對(duì)整個(gè)解空間的完全搜索,難以求得最優(yōu)解。而蟻群算法[12]具有信息正反饋和啟發(fā)式搜索的特點(diǎn),對(duì)求解組合優(yōu)化問(wèn)題有很好的適用性,但傳統(tǒng)蟻群算法有收斂速度慢、易陷入局部最優(yōu)的不足。因此本文在并行蟻群算法[13]的基礎(chǔ)上,通過(guò)改進(jìn)蟻群組間信息溝通方式及分組策略,提高了算法收斂性,增強(qiáng)了算法的全局搜索能力。文中將改進(jìn)算法應(yīng)用到配電網(wǎng)優(yōu)化問(wèn)題具體案例,實(shí)驗(yàn)結(jié)果表明此改進(jìn)算法相較于傳統(tǒng)蟻群算法和并行蟻群算法有更好的尋優(yōu)能力。

1 配電網(wǎng)網(wǎng)架優(yōu)化的數(shù)學(xué)模型

配電網(wǎng)網(wǎng)架優(yōu)化的目標(biāo)是使配電網(wǎng)架建設(shè)費(fèi)用和電能損失費(fèi)用最小,同時(shí)滿足線路允許通過(guò)的最大電流、電壓上下限約束,輻射性和連通性網(wǎng)架結(jié)構(gòu)。

優(yōu)化目標(biāo)函數(shù)為:

C1×|ΔI|+C2×|ΔU|

(1)

式中:γi為資本回收率;?i為年設(shè)備維修率;X=(x1,x2,…,xi),xi∈(0,1);ai為支路i單位長(zhǎng)度投資費(fèi)用;li為支路i的線路長(zhǎng)度;C0為電價(jià);τmax為系統(tǒng)最大負(fù)荷損耗時(shí)間;ΔPi為支路i的功率損耗;C1為支路過(guò)流懲罰系數(shù);ΔI是支路電流超限的數(shù)值;C2為節(jié)點(diǎn)電壓越限的懲罰系數(shù);ΔU為電壓超限的數(shù)值。

約束條件為:

① 支路電流約束:

Ii

(2)

式中:Ii為支路i流過(guò)的電流;Iimax為支路i允許流過(guò)的最大電流。

② 負(fù)荷點(diǎn)電壓約束:

Umin

(3)

式中:Um為節(jié)點(diǎn)m的電壓;Umax、Umin分別為負(fù)荷節(jié)點(diǎn)的電壓的上下限。

③ 網(wǎng)架輻射性約束,即電源點(diǎn)與任意負(fù)荷節(jié)點(diǎn)之間的路徑唯一。

④ 網(wǎng)架連通性約束,即任意兩個(gè)負(fù)荷或電源節(jié)點(diǎn)之間都連通。

2 自適應(yīng)分組的并行蟻群算法

2.1 蟻群算法分析

蟻群算法,又稱(chēng)螞蟻算法,最早是由Dorigo等學(xué)者提出的,是一種基于群體的模擬進(jìn)化算法,其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。螞蟻在運(yùn)動(dòng)過(guò)程中,會(huì)留下一種稱(chēng)為信息素的東西,而螞蟻?zhàn)陨頃?huì)根據(jù)信息素去選擇方向,當(dāng)然路徑信息素越濃,被選擇的概率也就越大。螞蟻根據(jù)由信息素強(qiáng)度和路徑啟發(fā)函數(shù)決定的狀態(tài)轉(zhuǎn)移概率選擇下一步所要走的路徑。螞蟻經(jīng)過(guò)多次循環(huán)迭代尋找最短路線在較短路線上的信息素量增多,較長(zhǎng)路徑上的信息素量減少,最終最短路徑上的信息素量最短。最終螞蟻根據(jù)路徑上信息素的量全部?jī)A向于選擇最短路徑,從而螞蟻算法找到最優(yōu)解。

2.2 并行蟻群算法原理

Chu等[13]在Dorigo等的基礎(chǔ)上提出了并行蟻群系統(tǒng)(Parallel ant Colony System,PACS),該并行算法將螞蟻分成若干組,每組螞蟻獨(dú)立按照傳統(tǒng)蟻群算法搜索可行解。螞蟻在搜索過(guò)程中,每搜索一定的迭代次數(shù)后,所有螞蟻通過(guò)組間的信息溝通更新路徑信息素。

在PACS中,將所有螞蟻分為若干組,第g(g=1,2,…,G)組的螞蟻第k(k=1,2,…,m)只螞蟻在當(dāng)前位置i處,按照偽隨機(jī)比例規(guī)則來(lái)選擇下一個(gè)訪問(wèn)的城市j,其表達(dá)式如下:

(4)

式中:q是區(qū)間[0,1]上的一個(gè)隨機(jī)變量;q0是一個(gè)[0,1]范圍之間的常數(shù);τg(i,j)是第g組的螞蟻的路徑信息素;η(i,j)為啟發(fā)函數(shù),是i城市與j城市之間的歐氏距離的倒數(shù);J是根據(jù)式(5)的路徑轉(zhuǎn)移概率公式產(chǎn)生的一個(gè)變量。

(5)

式中:α為信息啟發(fā)因子;β為期望啟發(fā)因子;allowk為螞蟻尚未訪問(wèn)過(guò)的城市。

當(dāng)?shù)趃組的第k只螞蟻完成一次旅程后,根據(jù)局部信息素更新規(guī)則更新每組螞蟻的路徑信息素,更新規(guī)則如下:

τg(i,j)=(1-σ)×τg(i,j)+σ×τ0

(6)

式中:τ0是一個(gè)很小的正常數(shù),σ是信息素?fù)]發(fā)因子,0<σ<1。

當(dāng)每組中的所有螞蟻都已經(jīng)完成一次旅程后,根據(jù)全局信息素更新規(guī)則更新每組螞蟻的路徑信息素,更新規(guī)則如下:

τg(i,j)=(1-ρ)×τg(i,j)+ρ×Δτg(i,j)

(7)

(8)

式中:ρ是信息素?fù)]發(fā)因子;Q是常數(shù);Lg是第g組的最優(yōu)路徑長(zhǎng)度;Rgbest為第g組的最優(yōu)路徑。

隨著算法迭代,當(dāng)算法運(yùn)行R次后,各組螞蟻相互之間信息溝通交流,根據(jù)圖1所示溝通方式更新每組螞蟻的路徑信息素。

更新規(guī)則如下:

τg(i,j)=τg(i,j)+ε×Δτbest(i,j)

(9)

(10)

式中:ε是信息素?fù)]發(fā)系數(shù);Lg,b是所有組中螞蟻的最優(yōu)路徑長(zhǎng)度。

2.3 改進(jìn)并行蟻群算法

針對(duì)蟻群算法收斂速度慢以及容易陷入局部最優(yōu)的缺點(diǎn)。文中基于PACS提出兩個(gè)改進(jìn)策略:

1) PACS中將螞蟻分為若干組,增強(qiáng)了全局搜索能力,提高了蟻群算法求解性能。但對(duì)于并行蟻群算法,螞蟻分組并不是越多越好[14],PACS中每組螞蟻的求解原理還是按照基本蟻群算法的思想在運(yùn)行,故分組過(guò)多,因螞蟻總數(shù)是固定的,這樣就導(dǎo)致每組中的螞蟻過(guò)少,算法性能會(huì)受到影響,使算法收斂速度降低,全局搜索能力下降;如果增加螞蟻數(shù)量,則會(huì)導(dǎo)致算法的時(shí)間復(fù)雜度增大,降低算法的求解速度。因此本文提出了一種自適應(yīng)分組策略,即采用一種隨迭代分組數(shù)自適應(yīng)減少的方法。在算法前期分組多,增強(qiáng)全局搜索能力且加快算法收斂速度,算法后期分組少,增強(qiáng)局部搜索能力。因此本文將算法迭代周期分為若干段,分組規(guī)則如下:

(11)

式中:μ表示自適應(yīng)分組算子;G表示算法最大分組數(shù);t表示當(dāng)前迭代次數(shù);g(t)表示當(dāng)前迭代次數(shù)為t時(shí),螞蟻的分組數(shù);Tmax表示最大迭代次數(shù)。

自適應(yīng)分組的策略方法是算法前期分組多,后期分組少。組數(shù)減少時(shí),為了保證算法的時(shí)間復(fù)雜度不變,消失的螞蟻需要和留存的螞蟻合并為一組,因此各組螞蟻的路徑信息素要合并融合。融合規(guī)則如下:

(12)

2) 針對(duì)PACS組間螞蟻溝通交流過(guò)程,用所有組最短路徑距離進(jìn)行路徑信息素更新,文中提出一種環(huán)形結(jié)構(gòu)的溝通方式,如圖2所示。將不同組的螞蟻連接成一個(gè)環(huán)形結(jié)構(gòu),螞蟻搜索迭代R次時(shí),環(huán)形結(jié)構(gòu)中的相鄰組螞蟻進(jìn)行信息溝通,比較螞蟻所找到的最佳路徑,從而進(jìn)行路徑信息素更新。此種方式盡可能地保留了每組螞蟻的信息,降低了算法陷入局部最優(yōu)的風(fēng)險(xiǎn)。

圖2 根據(jù)環(huán)形結(jié)構(gòu)更新信息素

信息素更新規(guī)則就是將式(10)轉(zhuǎn)換為:

(13)

式中:Lg,b是相鄰組中螞蟻的最短路徑距離。即組4的路徑信息素,由組4螞蟻和組3螞蟻溝通后即比較路徑長(zhǎng)短后確定;組3的路徑信息素,由組3螞蟻和組2螞蟻溝通后確定,其他組同理。

3 改進(jìn)蟻群算法求解配電網(wǎng)網(wǎng)架優(yōu)化

3.1 生成樹(shù)方法構(gòu)造配電網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)

在算法求解過(guò)程中,為了避免螞蟻在搜索規(guī)劃方案時(shí)形成過(guò)多的非輻射狀的解,提高算法的搜索效率,減少修復(fù)非輻射形解的時(shí)間,進(jìn)而減少計(jì)算時(shí)間,應(yīng)盡量使每一只螞蟻的規(guī)劃方案限制為輻射狀網(wǎng)絡(luò)結(jié)構(gòu)方案。Vkt為連入樹(shù)的節(jié)點(diǎn)集合,Ukt為未連入樹(shù)的節(jié)點(diǎn)集合,Ekt為當(dāng)前可建線路的集合,Enew為螞蟻搜索過(guò)的路線集合,第k只螞蟻每一次游程時(shí),先以Pk(i,j)從Ekt中選擇一個(gè)邊,將選擇的邊放到Enew中,然后更新Vkt、Ukt、Ekt集合里的元素,重復(fù)上述步驟,直到Ukt集合為空,Enew中的邊就是第k只螞蟻的路線規(guī)劃方案。

3.2 改進(jìn)算法求解配電網(wǎng)架優(yōu)化步驟

算法求解過(guò)程中,使用前推回代法計(jì)算螞蟻搜索得到的網(wǎng)絡(luò)規(guī)劃方案中的潮流參數(shù),進(jìn)而使用式(1)中配電網(wǎng)網(wǎng)架優(yōu)化目標(biāo)函數(shù)f(X)評(píng)價(jià)每只螞蟻的規(guī)劃方案的好壞,改進(jìn)蟻群算法流程如圖3所示。

圖3 算法流程

4 算例分析

本文采用文獻(xiàn)[15]中的算例,表1為各負(fù)荷節(jié)點(diǎn)的大小及坐標(biāo),坐標(biāo)單位為cm,與真實(shí)街道的比例尺是1∶20 000,該配電網(wǎng)網(wǎng)架結(jié)構(gòu)為中國(guó)北方某城市一區(qū)域的實(shí)際街道圖,該區(qū)域有33條街道、21個(gè)負(fù)荷點(diǎn),節(jié)點(diǎn)1為變電站位置,如圖4所示。

表1 節(jié)點(diǎn)負(fù)荷數(shù)據(jù)

圖4 城市街道圖

用MATLAB 2018軟件編寫(xiě)程序,蟻群算法中:α=1;β=2;σ=0.1;ρ=0.1;ε=0.1;Tmax=80;Q=1; 螞蟻總數(shù)為16;最大分組數(shù)G=8。目標(biāo)函數(shù)中參數(shù)設(shè)置為:電價(jià)C0=0.5元/(kW·h),懲罰系數(shù)C1=C2=1 000;年等值系數(shù)γi+?i=0.155,系統(tǒng)年等效損耗小時(shí)數(shù)τmax=3 000 h。線路單位投資費(fèi)用為20.5萬(wàn)元/km,導(dǎo)線選用LGJ50。通過(guò)基于自適應(yīng)分組策略的改進(jìn)蟻群算法生成的網(wǎng)架優(yōu)化結(jié)果如圖5所示。該算例很好地驗(yàn)證了改進(jìn)算法在網(wǎng)架優(yōu)化中的可行性。為驗(yàn)證本文算法的優(yōu)劣性,采用并行蟻群算法和基本蟻群算法分別對(duì)算例進(jìn)行分析計(jì)算,將所得結(jié)果與上述結(jié)果進(jìn)行對(duì)比,收斂曲線如圖6所示,對(duì)比結(jié)果如表2所示。

表2 優(yōu)化結(jié)果比較

圖5 優(yōu)化后網(wǎng)架結(jié)構(gòu)圖

圖6 目標(biāo)函數(shù)收斂曲線

從圖6的目標(biāo)函數(shù)曲線走勢(shì)可以看出,改進(jìn)蟻群算法在三種算法求解中求得的解是最優(yōu)的,且改進(jìn)算法求解算例相較于基本蟻群算法和并行蟻群算法有更快的收斂速度。從表2中可以看出,改進(jìn)蟻群算法的各項(xiàng)指標(biāo)都要好于并行蟻群算法,且與基本蟻群算法相比,雖然線路總投資費(fèi)用較高,但是功率損耗費(fèi)用低。綜合看來(lái),本文改進(jìn)算法是更優(yōu)的,驗(yàn)證了改進(jìn)算法求解網(wǎng)架優(yōu)化問(wèn)題上的可行性和有效性。

5 結(jié) 語(yǔ)

本文以系統(tǒng)年綜合費(fèi)用作為目標(biāo)函數(shù),采用自適應(yīng)分組策略的改進(jìn)并行蟻群算法,對(duì)并行蟻群算法中的螞蟻進(jìn)行自適應(yīng)分組,且提出一種新的螞蟻組間信息溝通方式,克服了蟻群算法易陷入局部最優(yōu)解的缺點(diǎn),一定程度上加快了算法的收斂速度,使得其尋優(yōu)性能有了顯著的提高。通過(guò)具體實(shí)例的實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)蟻群算法在可行性和有效性。