改進并行蟻群算法在配電網網架優化中的應用

卜冠南 劉建華 張冬陽 胡任遠 羅逸軒

(福建工程學院計算機科學與數學學院 福建 福州 350118)

(福建省大數據挖掘與應用技術重點實驗室 福建 福州 350118)

0 引 言

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

1 配電網網架優化的數學模型

配電網網架優化的目標是使配電網架建設費用和電能損失費用最小,同時滿足線路允許通過的最大電流、電壓上下限約束,輻射性和連通性網架結構。

優化目標函數為:

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

(1)

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

約束條件為:

① 支路電流約束:

Ii

(2)

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

② 負荷點電壓約束:

Umin

(3)

式中:Um為節點m的電壓;Umax、Umin分別為負荷節點的電壓的上下限。

③ 網架輻射性約束,即電源點與任意負荷節點之間的路徑唯一。

④ 網架連通性約束,即任意兩個負荷或電源節點之間都連通。

2 自適應分組的并行蟻群算法

2.1 蟻群算法分析

蟻群算法,又稱螞蟻算法,最早是由Dorigo等學者提出的,是一種基于群體的模擬進化算法,其靈感來源于螞蟻在尋找食物過程中發現路徑的行為。螞蟻在運動過程中,會留下一種稱為信息素的東西,而螞蟻自身會根據信息素去選擇方向,當然路徑信息素越濃,被選擇的概率也就越大。螞蟻根據由信息素強度和路徑啟發函數決定的狀態轉移概率選擇下一步所要走的路徑。螞蟻經過多次循環迭代尋找最短路線在較短路線上的信息素量增多,較長路徑上的信息素量減少,最終最短路徑上的信息素量最短。最終螞蟻根據路徑上信息素的量全部傾向于選擇最短路徑,從而螞蟻算法找到最優解。

2.2 并行蟻群算法原理

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

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

(4)

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

(5)

式中:α為信息啟發因子;β為期望啟發因子;allowk為螞蟻尚未訪問過的城市。

當第g組的第k只螞蟻完成一次旅程后,根據局部信息素更新規則更新每組螞蟻的路徑信息素,更新規則如下:

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

(6)

式中:τ0是一個很小的正常數,σ是信息素揮發因子,0<σ<1。

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

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

(7)

(8)

式中:ρ是信息素揮發因子;Q是常數;Lg是第g組的最優路徑長度;Rgbest為第g組的最優路徑。

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

更新規則如下:

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

(9)

(10)

式中:ε是信息素揮發系數;Lg,b是所有組中螞蟻的最優路徑長度。

2.3 改進并行蟻群算法

針對蟻群算法收斂速度慢以及容易陷入局部最優的缺點。文中基于PACS提出兩個改進策略:

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

(11)

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

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

(12)

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

圖2 根據環形結構更新信息素

信息素更新規則就是將式(10)轉換為:

(13)

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

3 改進蟻群算法求解配電網網架優化

3.1 生成樹方法構造配電網網絡結構

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

3.2 改進算法求解配電網架優化步驟

算法求解過程中,使用前推回代法計算螞蟻搜索得到的網絡規劃方案中的潮流參數,進而使用式(1)中配電網網架優化目標函數f(X)評價每只螞蟻的規劃方案的好壞,改進蟻群算法流程如圖3所示。

圖3 算法流程

4 算例分析

本文采用文獻[15]中的算例,表1為各負荷節點的大小及坐標,坐標單位為cm,與真實街道的比例尺是1∶20 000,該配電網網架結構為中國北方某城市一區域的實際街道圖,該區域有33條街道、21個負荷點,節點1為變電站位置,如圖4所示。

表1 節點負荷數據

圖4 城市街道圖

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

表2 優化結果比較

圖5 優化后網架結構圖

圖6 目標函數收斂曲線

從圖6的目標函數曲線走勢可以看出,改進蟻群算法在三種算法求解中求得的解是最優的,且改進算法求解算例相較于基本蟻群算法和并行蟻群算法有更快的收斂速度。從表2中可以看出,改進蟻群算法的各項指標都要好于并行蟻群算法,且與基本蟻群算法相比,雖然線路總投資費用較高,但是功率損耗費用低。綜合看來,本文改進算法是更優的,驗證了改進算法求解網架優化問題上的可行性和有效性。

5 結 語

本文以系統年綜合費用作為目標函數,采用自適應分組策略的改進并行蟻群算法,對并行蟻群算法中的螞蟻進行自適應分組,且提出一種新的螞蟻組間信息溝通方式,克服了蟻群算法易陷入局部最優解的缺點,一定程度上加快了算法的收斂速度,使得其尋優性能有了顯著的提高。通過具體實例的實驗結果驗證了改進蟻群算法在可行性和有效性。