基于空間壓縮理論的粒子群算法在輸電網規劃中的應用

崔德義

（上海市電力公司嘉定供電公司，上海 201800）

電網規劃是指在給定的電源規劃和負荷預測基礎上，對現有的線路結構進行新增或擴建，以滿足電力系統安全、可靠的運行。從數學上講，此類問題屬于帶有多約束條件，無法用固定公式來求解的非線性問題。因此，一般采用現代啟發式算法［1］，比如遺傳算法（GA）［2］，粒子群算法（PSO）［3］，蟻群算法（ACO）［4］等進行求解。其中粒子群算法實現簡單，具有較快的計算速度與較好的并行計算能力，并且對問題的初始約束條件要求不高，所以被廣泛應用于電網規劃中。

粒子群算法來源于對簡化社會模型的模擬，利用記憶機制分別記錄全部粒子和各粒子自身的最優適應度值，通過反饋和學習機制逐漸使得粒子向最優解方向移動［5］。與遺傳算法相比，沒有變異過程，而是通過粒子之間的競爭和學習來優化計算結果。同時，更新后的粒子容易受局部最優解的吸引，使算法過早收斂。很多學者，比如Eberhart［6］等通過增加一個慣性權重系數來改變搜索空間的范圍以優化計算結果，但實際效果并不明顯。

當粒子維數在10維以內時，粒子群算法收斂效果較好［7］，但隨著粒子維數的不斷提高，即使加入慣性權重系數也無法得出滿意的全局最優解。本文根據電網規劃獨有的特性，引入空間壓縮理論，解決了過早收斂問題并最終改善了優化結果。

1 電網規劃基本算法模型

1.1 更新和選擇最優粒子

電網規劃的具體研究對象是線路走廊中的線路回數，因此設每個粒子中的第k維變量的值即為第k條線路走廊的線路回路數。對于需要規劃具有D條線路走廊的問題，設粒子維數為D維，假設共有m個這樣的粒子，則粒子可表述為：

每個粒子值配置初始速度為：

引入學習機制對隨后的粒子進行更新［8］，計算式為：

式中：r1，r2分別為均勻分布在0～1之間的隨機數；c1為自我認知權重，c2為學習權重，兩值分別表征了粒子群自我認知程度和向當前全局最優粒子學習的程度。一般設為2。

1.2 確定目標函數

對于實際運行的網絡規劃模型，需確定一個目標函數用來計算適應度值，以判別和。一個考慮網絡投資費用和網絡運行損耗費用的目標函數可表述為：

式中：n0為電網已有的固定線路走廊；n1為允許架設線路走廊；xi為允許新增的第i條線路走廊中的線路回路數；li為第i條線路長度，用來表征線路架設費用；Pi為實際運行過程中第i條線路上流過的功率；Pmixi為第i條線路所允許通過的最大功率。

當線路過負載，即｜Pi｜－＞0時，第二項通過乘上一個懲罰因子W 來使整個目標函數值f′（x）變大。顯而易見，目標函數值f（x）越小，表示網絡投資和電網運行費用越小，其所代表的網絡規劃配置就越好。

需要注意，若某個粒子中0值過多，可能會使輸電網絡產生孤立節點，因此對每一次新生成的網絡圖需要進行判斷。當網絡出現孤立節點時，直接賦予適應度函數一個很大的值，這樣避免了不必要的計算。最終將整個適應度函數表達式改為：

式中：U為一個很大的罰值，可直接取為W的100倍。

如何判斷一個輸電網絡是否存在孤立節點，可利用拓撲搜索法來解決，主要通過判斷是否滿足收斂條件來確定計算是否終止。一是粒子在更新數次后，其全局最優適應度值不發生變化，則認為滿足收斂條件，計算終止；二是每一次更新粒子群計算得到全局最優適應度函數值與前一次所得的全局最優適應度函數值之差小于給定值ε時，即認為滿足收斂條件，計算終止。經過計算證實了，在足夠多的粒子下（一般設定粒子數為維數的7～10倍），粒子更新20次后，其最優適應度值一般不會再發生變化［9］。整個算法流程如圖1所示。

圖1 粒子群輸電網規劃流程圖

實踐表明，傳統的粒子群算法雖然實現簡單，但實際優化效果并不理想，原因是粒子很容易受局部最優解的影響［6］，即使增加迭代次數，也會繼續被上一代的局部最優粒子吸引?，F利用傳統粒子群算法，對一個具有18節點27條線路走廊的網絡進行規劃，其算法收斂效果如圖2所示。

圖2 傳統粒子群算法收斂效果圖

分別對50個，100個，500個粒子進行計算，結果表明，在粒子更新至20～25次后，其適應度值已經趨于平穩，其值分別在56 219，53 533，51 238元左右，而此18節點系統的標準最優適應度函數值為4.5萬元，即使粒子數選擇為500個，迭代次數選擇為30次，其計算結果也與標準結果相差11.11%，可見實際優化效果并不理想。

從圖2也可以看出，為了更快地找到最優解，通過增加初始粒子數目比增加粒子更新次數所得到的效果更好。對于粒子數目為500的算法模型，其第一次計算的結果就比粒子數目為50個，迭代次數為30次的效果要好。大量實驗證明，只需粒子更新20次左右，其結果就趨于某個局部最優解，盲目的增加粒子更新次數只會增加計算時間，對最優解的搜尋沒有任何幫助。

2 改進粒子群算法

2.1 基本原理

現結合輸電網規劃的實際情況，通過引入空間壓縮機制的改進粒子群算法來提高收斂效果?？紤]到粒子更新20次左右時將會收斂到某一局部最優解，可將某一初始粒子采用傳統粒子群算法迭代30次（這樣保證能夠收斂到某一局部最優解），之后若能保證新生成的粒子能產生比前一粒子更優秀的目標函數值，那么計算效果會得到很大提高。為了便于分析，僅考慮粒子維數為二維的情況，如圖3所示。

圖3 二維粒子變異機制圖解

由圖3可知，全部粒子的搜索空間為整個坐標的第一象限，對于1個僅設有2條線路走廊的輸電網規劃模型，即1個二維的粒子（x1，x2），假定經過一定次數的更新后，粒子最優可行解收斂到（a，b）點，目標函數為f（a，b），則以（a，b）坐標為中心點的右上角網格陰影部分（包括邊界線）有任意x1≥a， x2≥b，物理意義為任意取值在網格陰影部分中的粒子，其線路走廊的規劃線路回路數總是大于或者等于（a，b）這種規劃方案，但由于增加線路回路數會增加投資成本，所以對于任意x1≥a，x2≥b所表示的網絡投資都會增加。由此可知，隨機搜索在網格范圍內的所有粒子值可以不予考慮，而所有新生成的粒子理應在網格范圍之外（不包括邊界線）生成。這樣，整個粒子的搜索范圍被壓縮了一部分，這就是空間壓縮的基本原理。

2.2 最優可行解的效率分析

改進粒子群算法中，每次得出的新粒子在壓縮之后的空間范圍內總能找到更優解，并且隨著新粒子不斷的更新和空間的不斷壓縮，使得搜索全局最優可行解的概率越來越大，其搜索效率可用圖4表示。

圖4 空間壓縮和全局最優解的搜尋

由圖4可知，通過第一次算得的f（a1，b2）值確定網格區域1，然后使粒子（x1，x2）的第二次更新范圍在區域1之外產生，而再次計算得到的適應度值f（a2，b2）又繼續會將整個搜索空間進一步壓縮。這樣，第三次生成的粒子（x11，x12）值會在區域1和2之外產生，因此已被壓縮空間的有效搜索范圍被進一步縮小。重復以上步驟，隨著新的局部最優解不斷被找到，搜索空間也隨之不斷的被壓縮，粒子群的搜索效率也會越來越高并最終逼近最優解。而之前得到的所有局部最優解所對應的規劃方案（f（a1，b2）和f（a2，b2））亦可作為輸電網規劃的參考方案。

2.3 收斂判據

改進粒子群算法使得計算效率明顯提高，新生成的粒子保證其目標函數值一定比之前得到的最優解更好，避免了無效粒子的生成。其算法終止判定條件為在一定的迭代次數內，更新后的粒子算得的最優適應度值，與之前生成的最優適應度值相等時計算結束。

3 算例分析

3.1 兩種算法的分析

將上節的算例用引入空間壓縮機制的改進粒子群算法重新計算，計算結果如圖5所示。

圖5 改進粒子群算法收斂效果圖

改進后的目標函數收斂效果在粒子數目分別為50個，100個，500個計算時，其目標函數適應度值，分別比傳統粒子群算法提高了16.67%，9.10%和11.11%，優化效果明顯。

3.2 規劃網絡圖的分析

對于以上算例，采用傳統粒子群算法，設定初始粒子數為200個，迭代計算為600次，得到的規劃結果如圖6所示。

圖6 傳統粒子群算法規劃網絡圖

圖6中粗實線為輸電線路已有固定線路，不參與計算。在滿足約束條件的前提下，圖6總共新增22條線路。跟蹤發現，當迭代至第25次時，算法已經收斂，之后新生成的粒子總會被此局部最優解所吸引。也就是說，之后的575次計算結果與第25次的計算結果一致，為無效計算。

現采用改進粒子群算法，同樣設定初始粒子數為200個，迭代次數為30次后找到相應局部最優解并進行空間壓縮，再在新的壓縮空間里進行計算，按此法循環20次，總計算次數仍然為600，得出的結果如圖7所示。

圖7 改進粒子群算法規劃網絡圖

由圖7可知，只增加了18條線路，即滿足了所有約束條件并保證線路不過載，而且投資費用大大減少。在相同初始條件和迭代次數下改進粒子群算法優化效果明顯。實際結果表明，圖7亦即為該18節點算例的全局最優解。

4 結語

基于空間壓縮的改進粒子群算法在應用中具有三大優點。一是，每次更新計算時的粒子群總是在壓縮后的空間中產生，提高了粒子搜索效率，對于1個18節點的具體算例，在相同的初始粒子群數目和計算次數之內，平均算法優化效果可提高15%左右。二是，不同于傳統算法中粒子群更新的盲目性，改進粒子群算法的新粒子搜索空間總在可能產生更優適應度值的搜索范圍內，避免了重復計算。三是，每次更新后的粒子找到的局部最優可行解都可為規劃方案提供參考，增加了規劃的靈活性。

當然，改進粒子群算法還需要進一步完善：比如，對于每次在壓縮空間以內進行搜索的粒子，若粒子數目選擇的不夠大，容易使更新后的粒子所對應的網絡發生過負荷或者產生孤立節點，進而導致目標函數會非常大（由罰函數造成），反而使計算結果發散，需要對此情況引起高度重視，予以判別并且加以改進。再比如，進一步完善空間壓縮理論，考慮增加網絡線路過負荷約束條件的序特性，使圖3以（a，b）點為原點的網絡第三象限部分也予以屏蔽，可以進一步增加壓縮范圍，提高搜索效率。

［1］ 金義雄，程浩忠，嚴健勇，等.現代啟發式算法及其輸電網絡擴展規劃中的應用［J］.華東電力，2005，33（8）19-25.

［2］ 玄光男，程潤偉，等.遺傳算法與工程優化［M］.北京：清華大學出版社，2004：1-3.

［3］ 紀震，廖惠連，吳青華.粒子群算法及應用［M］.北京：科學出版社，2009：16-19.

［4］ 段海濱，馬冠軍，等.一種求解連續空間優化問題的改進蟻群算法［J］.系統仿真學報，2007.19（5）：974-977.

［5］ 李麗，牛奔.粒子群優化算法［M］.北京：冶金工業出版社，2009：25-34.

［6］ Shi Y，Eberhart R C.A Modified Swarm Optimizer［A］.IEEE International Conference of Evolution Computa-tion［C］.Anchorage，Alaska：IEEE Press，1988：69-73.

［7］ 曾健潮，介婧，崔志華.微粒群算法［M］.北京：科學出版社，2004：15-18.

［8］ 金義雄，程浩忠，嚴健勇，等.改進粒子群算法及其在輸電網規劃中的應用［J］.中國電機工程學報，2005，25（4）：46-50.

［9］ 金義雄，程浩忠，嚴健勇.基于局優化分支優化的粒子群收斂保證算法及其在電網規劃中的應用［J］.電機工程學報，2005，25（23）：12-18.