基于空間壓縮理論的粒子群算法在輸電網(wǎng)規(guī)劃中的應(yīng)用

崔德義

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

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

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

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

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

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

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

每個(gè)粒子值配置初始速度為：

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

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

1.2 確定目標(biāo)函數(shù)

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

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

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

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

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

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

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

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

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

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

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

2 改進(jìn)粒子群算法

2.1 基本原理

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

圖3 二維粒子變異機(jī)制圖解

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

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

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

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

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

2.3 收斂判據(jù)

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

3 算例分析

3.1 兩種算法的分析

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

圖5 改進(jìn)粒子群算法收斂效果圖

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

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

［4］ 段海濱，馬冠軍，等.一種求解連續(xù)空間優(yōu)化問題的改進(jìn)蟻群算法［J］.系統(tǒng)仿真學(xué)報(bào)，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］ 金義雄，程浩忠，嚴(yán)健勇，等.改進(jìn)粒子群算法及其在輸電網(wǎng)規(guī)劃中的應(yīng)用［J］.中國電機(jī)工程學(xué)報(bào)，2005，25（4）：46-50.

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