崔德義

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

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

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

當(dāng)粒子維數(shù)在10維以內(nèi)時，粒子群算法收斂效果較好［7］，但隨著粒子維數(shù)的不斷提高，即使加入慣性權(quán)重系數(shù)也無法得出滿意的全局最優(yōu)解。本文根據(jù)電網(wǎng)規(guī)劃獨有的特性，引入空間壓縮理論，解決了過早收斂問題并最終改善了優(yōu)化結(jié)果。

1 電網(wǎng)規(guī)劃基本算法模型

1.1 更新和選擇最優(yōu)粒子

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

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

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

式中：r1，r2分別為均勻分布在0～1之間的隨機數(shù)；c1為自我認知權(quán)重，c2為學(xué)習(xí)權(quán)重，兩值分別表征了粒子群自我認知程度和向當(dāng)前全局最優(yōu)粒子學(xué)習(xí)的程度。一般設(shè)為2。

1.2 確定目標函數(shù)

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

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

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

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

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

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

圖1 粒子群輸電網(wǎng)規(guī)劃流程圖

實踐表明，傳統(tǒng)的粒子群算法雖然實現(xiàn)簡單，但實際優(yōu)化效果并不理想，原因是粒子很容易受局部最優(yōu)解的影響［6］，即使增加迭代次數(shù)，也會繼續(xù)被上一代的局部最優(yōu)粒子吸引。現(xiàn)利用傳統(tǒng)粒子群算法，對一個具有18節(jié)點27條線路走廊的網(wǎng)絡(luò)進行規(guī)劃，其算法收斂效果如圖2所示。

圖2 傳統(tǒng)粒子群算法收斂效果圖

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

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

2 改進粒子群算法

2.1 基本原理

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

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

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

2.2 最優(yōu)可行解的效率分析

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

圖4 空間壓縮和全局最優(yōu)解的搜尋

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

2.3 收斂判據(jù)

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

3 算例分析

3.1 兩種算法的分析

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

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

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

3.2 規(guī)劃網(wǎng)絡(luò)圖的分析

對于以上算例，采用傳統(tǒng)粒子群算法，設(shè)定初始粒子數(shù)為200個，迭代計算為600次，得到的規(guī)劃結(jié)果如圖6所示。

圖6 傳統(tǒng)粒子群算法規(guī)劃網(wǎng)絡(luò)圖

圖6中粗實線為輸電線路已有固定線路，不參與計算。在滿足約束條件的前提下，圖6總共新增22條線路。跟蹤發(fā)現(xiàn)，當(dāng)?shù)恋?5次時，算法已經(jīng)收斂，之后新生成的粒子總會被此局部最優(yōu)解所吸引。也就是說，之后的575次計算結(jié)果與第25次的計算結(jié)果一致，為無效計算。

現(xiàn)采用改進粒子群算法，同樣設(shè)定初始粒子數(shù)為200個，迭代次數(shù)為30次后找到相應(yīng)局部最優(yōu)解并進行空間壓縮，再在新的壓縮空間里進行計算，按此法循環(huán)20次，總計算次數(shù)仍然為600，得出的結(jié)果如圖7所示。

圖7 改進粒子群算法規(guī)劃網(wǎng)絡(luò)圖

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

4 結(jié)語

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

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

［1］ 金義雄，程浩忠，嚴健勇，等.現(xiàn)代啟發(fā)式算法及其輸電網(wǎng)絡(luò)擴展規(guī)劃中的應(yīng)用［J］.華東電力，2005，33（8）19-25.

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

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

［4］ 段海濱，馬冠軍，等.一種求解連續(xù)空間優(yōu)化問題的改進蟻群算法［J］.系統(tǒng)仿真學(xué)報，2007.19（5）：974-977.

［5］ 李麗，牛奔.粒子群優(yōu)化算法［M］.北京：冶金工業(yè)出版社，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］.北京：科學(xué)出版社，2004：15-18.

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

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