基于免疫優(yōu)勢算法的配電網(wǎng)規(guī)劃

周愈鵬，覃拓，危秋珍，藍慧

（廣西河池市供電局調度所，廣西 河池 547000）

1 引言

長期以來，我國城市中低壓配電網(wǎng)網(wǎng)絡結構不合理，主要體現(xiàn)在網(wǎng)架結構薄弱，主次網(wǎng)架不清晰，多分段、多關聯(lián)的網(wǎng)絡聯(lián)接未形成，造成了用戶電壓不穩(wěn)定、網(wǎng)絡損耗大、頻繁發(fā)生故障等問題。根據(jù)2000年對全國286座城市的統(tǒng)計，我國中低壓配電網(wǎng)的平均供電可靠性為99.887%，有80%的用戶停電是由于配電網(wǎng)的問題引起的。因此，進行配電網(wǎng)規(guī)劃優(yōu)化配電網(wǎng)絡網(wǎng)架結構，降低配網(wǎng)容量要求、網(wǎng)絡損耗，減少建設資金投入和降低維護費用，對提高社會和電網(wǎng)公司的經(jīng)濟效益等具有重要意義［1］。

2 配電網(wǎng)規(guī)劃算法

配電網(wǎng)優(yōu)化規(guī)劃問題實質上就是一個具有離散、不確定、多目標、多階段的復雜系統(tǒng)的組合優(yōu)化問題。目前，配電網(wǎng)規(guī)劃的算法主要有數(shù)學優(yōu)化規(guī)劃方法和啟發(fā)式優(yōu)化規(guī)劃方法。數(shù)學優(yōu)化規(guī)劃含線性規(guī)劃法和模糊數(shù)學類的不確定性規(guī)劃法，由于配電網(wǎng)規(guī)劃是一個非常復雜的非線性規(guī)劃問題，它是非可微性的，所以直接用傳統(tǒng)的數(shù)學優(yōu)化方法來進行配電網(wǎng)規(guī)劃往往會出現(xiàn)迭代發(fā)散、收斂速度慢和難以得到比較準確的結果等問題。針對數(shù)學優(yōu)化規(guī)劃方法的不足，人們提出了啟發(fā)式規(guī)劃算法，它綜合考慮了規(guī)劃效率和規(guī)劃效果兩個指標，具有直觀、靈活、計算速度快等突出優(yōu)點，便于規(guī)劃人員在規(guī)劃過程中參與具體的決策，從而得出更符合工程實際的規(guī)劃方案［2］。啟發(fā)式規(guī)劃方法有分為傳統(tǒng)式啟發(fā)方法即支路交換法、專家式啟發(fā)方法、和現(xiàn)代啟發(fā)式方法。目前應用現(xiàn)代啟發(fā)式方法有神經(jīng)網(wǎng)絡、模擬退火法、蟻群最優(yōu)化、遺傳算法、免疫算法等。遺傳算法是模仿生物進化過程的一種自適應隨機搜索優(yōu)化算法，由于其編碼簡單易行，且基于精英保留策略的遺傳算法在理論上是一種全局收斂的算法，從而得到了較多的應用［3］。但在實際應用中，遺傳算法仍有諸多不足，如種群多樣性的喪失使算法有可能只收斂到局部最優(yōu)，以及由于配電網(wǎng)輻射狀的特點，使得遺傳操作會產(chǎn)生不可行解［4］。為了解決上述問題，一些學者提出了改進的遺傳算法，如文獻［5］利用單親遺傳法獲得了最優(yōu)網(wǎng)架結構；同時，一些學者開始在遺傳學基礎上將免疫算子引入，提出了一種多種群免疫遺傳算法來解決配電網(wǎng)規(guī)劃問題，并取得了較好的效果，開啟了利用免疫算法來進行配電網(wǎng)優(yōu)化規(guī)劃的途徑［6］。文獻［7］在保留遺傳算法雜交、變異等因子基礎上，提出了一種改進免疫算法的配電網(wǎng)規(guī)劃，并采用信息熵理論來控制種群的多樣性，以避免算法不成熟收斂，加快了算法的收斂速度。

本文在常規(guī)免疫算法的基礎上提出一種免疫優(yōu)勢算法用于配電網(wǎng)規(guī)劃。在樹形編碼的基礎上，利用免疫機理對初始種群進行接種疫苗、利用免疫優(yōu)勢因子和改進的選擇、變異、克隆等免疫操作來傳統(tǒng)免疫算法進行改進，提高了種群的多樣性，避免早熟收斂和加快算法收斂速度等，本文最后給出一個具體配電網(wǎng)規(guī)劃的算例，以驗證本文所提出的算法的有效性。

3 配電網(wǎng)規(guī)劃的數(shù)學模型

其中:n為饋線總數(shù)；i為饋線支路編號；ci為饋線i的投資建設費用；χi該饋線i是否為新建，新建則為1，否則為0；?i為饋線投資回收率；δi為饋線線i的年折舊率；α為單位電價；τmaxi為最大負荷利用小時數(shù)；ΔPi為饋線i的有功損耗。

上式服從如下條件約束:

①潮流約束AP=D

式中，A為節(jié)點—支路關聯(lián)矩陣；P為饋線潮流向量；D為負荷向量。

②容量約束Pi≤Pimax

式中，Pi為饋線支路潮流；Pimax為該支路最大允許容量。

③電壓降落約束Umin≤U≤Umax

本文配電網(wǎng)規(guī)劃以年總費用最小為目標函數(shù)，包括建設投資費用、投資回收率、年折舊維護費用、運行費用（網(wǎng)損）其數(shù)學表達式是:

其中i=1，2，3……N，N為節(jié)點數(shù)

④輻射狀網(wǎng)絡約束

4 免疫優(yōu)勢算法的配電網(wǎng)規(guī)劃

4.1 概述

免疫算法將求解問題的目標函數(shù)和約束條件對應于入侵生物體的抗原，最優(yōu)問題的可行解對應于免疫系統(tǒng)產(chǎn)生的抗體，通過抗體和抗原的親和度來描述可行解與最優(yōu)解的逼近程度。

該免疫優(yōu)勢算法實際上就是一個通過克隆選擇使群體的親和度或適應度“成熟”的過程，即在克隆選擇機制的作用下，不斷地從群體中選擇出一定數(shù)量的個體使之獲得免疫優(yōu)勢，再對免疫優(yōu)勢個體進行克隆形成新的群體，判斷新群體適應度是否符合要求，若不符合再通過變異等免疫基因操作，以產(chǎn)生越來越多的親和度高的個體，如此循環(huán)直至群體親和度逐步提高到一定水平。

4.2 接種疫苗

研究表明，對抗體進行接種疫苗，能有效地改進算法的性能。接種疫苗是指按照先驗知識來修改個體的某些基因位上的基因，使所得個體以較大的概率具有更高的適應度。本文把配電網(wǎng)確定的打開開關的數(shù)目這一先驗知識作為疫苗。在種群初始化時，先將抗體全部基因位設置為1，然后對每一個最小閉環(huán)注射一位0元素（這相當于把閉環(huán)打開），而注射的基因位是隨機選取的。每個個體所注射0元素的總數(shù)，與確定的打開開關的數(shù)目相等。顯然，這種方法能在很大程度上避免了采用隨機初始化方法所產(chǎn)生大量的不可行解，獲得的可行解占種群的比例更大。而對于產(chǎn)生的不可行解，可以使用下文的方法進行修復，使之成為可行解［8］。

4.3 抗體編碼

本文在文獻［9，10］的編碼格式為基礎經(jīng)過改進得到了抗體的樹形編碼。假設某配網(wǎng)中有N個節(jié)點（編號從1～N），建立一個N階方陣，方陣的行列號與節(jié)點編號相同，矩陣元素有0、1兩種取值，用方陣來描述該配電網(wǎng)網(wǎng)絡拓撲。矩陣元素aij的取值含義如下:矩陣元素a為“1”則相連，表示該矩陣元素對應的兩節(jié)點i和j就有饋線支路相連接，自身節(jié)點矩陣元素為1；矩陣元素a為“0”則該矩陣元素對應的節(jié)點i和j沒有直接的支路連接。例如，某輻射狀配電網(wǎng)絡有5個節(jié)點，接線示意圖如圖1。圖2為該圖對應的五階方陣，節(jié)點與節(jié)點相連的則對應的矩陣元素為1，若節(jié)點間沒有直接相連的則對應的矩陣元素值為0。

圖1 輻射狀配電網(wǎng)片斷

圖2 對應矩陣

4.4 適應度計算

在研究某個問題和現(xiàn)象時，其對應的結果總有個標準或機制來評價其優(yōu)劣。本文免疫優(yōu)勢算法也和其他免疫算法一樣，主要用親和度或適應度函數(shù)對算法的解（抗體）進行評估。一般來說，算法的適應度函數(shù)Fit（f（x））是由目標函數(shù)f（x）轉換而成的，由于本文的抗體目標函數(shù)為求最小化的問題，本文算法將式（1）的目標函數(shù)的倒數(shù)作為親和度評估函數(shù)，c為控制常數(shù)，從而抗體（解）的親和度越小，表明抗體（解）越優(yōu)。

4.5 抗體免疫優(yōu)勢的獲得與算法

由于抗體種群種的最優(yōu)抗體與其他抗體相比，更能適應抗原的刺激，廣義地講，它具有免疫優(yōu)勢。因此，分析每次迭代中的最優(yōu)抗體，從而獲得免疫優(yōu)勢，使算法更具有通用性?；谏厦嫠悸?，針對采用二進制編碼的抗體種群，提出了如下的抗體免疫優(yōu)勢算子［11］。

記抗體群A=［a1，a1……an］為

定義參考抗體m=［m1，m2……ml］，其中

設αi∈A是抗體群中最好的抗體。若親和度f（m） ＞f（ai），則互換。以一定概率Pd，使 αi?A，j=1，2，…，l并且在j≠i時該抗體獲得免疫優(yōu)勢。其中，Pd是一個自適應調節(jié)參數(shù)，若f（a'j）＞f（aj）或f（m）＞f（ai）表明免疫優(yōu)勢的作用是有效的，則增大Pd，否則減小。具體地，令

H（·）是一門限函數(shù)，即

4.6 免疫操作

免疫基因操作主要包括克隆選擇、交叉變異，它是免疫算法的核心操作，是產(chǎn)生新的優(yōu)秀個體最主要的手段，也是保持群體多樣性，避免早熟收斂的基礎

（1）克隆選擇

克隆選擇過程是一個親和度或適應度“成熟”的過程，即在克隆選擇機制的作用下，不斷地從群體中選擇出一定數(shù)量的個體，并對它們進行克隆和變異等免疫基因操作，以產(chǎn)生越來越多的親和度高的個體，直至群體親和度逐步提高到一定水平。從上面可以看出，克隆選擇的過程從本質上講，它也是一個類似達爾文式的“優(yōu)勝劣汰”的選擇進化過程。本文的選擇克隆是選擇獲得免疫優(yōu)勢的抗體，按照一定倍數(shù)進行克隆，以獲得一個新的種群。

（2）交叉變異

本文在基于免疫優(yōu)勢算法的配電網(wǎng)規(guī)劃具體實現(xiàn)中，交叉、變異操作是按與抗體親和度或適應度成反比的概率從種群中選取個體來進行的。即親和度越高的抗體被選中進行交叉、變異操作的概率就越低；反之，親和度越低的抗體被選中進行交叉、變異操作的幾率就越大，這樣可以使種群中最優(yōu)的部分個體能夠在反復的免疫迭代過程中得以保存，而親和度或適應度差的個體在反復的被交叉、變異親和度不斷提升直至達到要求。而已經(jīng)確定選中進行交叉、變異的抗體，其交叉點是隨機確定的，變異的基因位也隨機確定的。至于整個群體中在每次迭代過程中有多少個體被選中進行免疫基因操作則由參數(shù)設置中的交叉率和變異率來決定。

4.6 算法的實現(xiàn)

（1）初始化參數(shù)設置。確定抗體編碼長度L；k=0，生成初始規(guī)模為N0的初始抗體群落A（0）；設定算法參數(shù)，變異率為Pm，克隆倍數(shù)為Nk。

（2）抗體編碼和接種疫苗。對種群中的抗體進行樹形編碼和接種疫苗。

（3）進化開始。根據(jù)式（1）的目標函數(shù)計算親和度:A（k）。

（4）獲得免疫優(yōu)勢。按文中方法獲得免疫優(yōu)勢抗體群體Xk。

（5）依據(jù)設定的抗體克隆規(guī)模，進行選擇克隆，獲得新的抗體群落A（k+1）。

（6）抗體親和度度量，并判斷是否滿足終止條件，是，則中止計算，輸出結果；否則繼續(xù)。

（7）對新抗體群落A（k+1）進行高頻變異得到新的群落，并返回步驟（2）。

圖3 免疫優(yōu)勢算法的計算程序的流程圖

5 算例

本文所提出的免疫優(yōu)勢算法的配電網(wǎng)規(guī)劃采用文獻［10］中的配電網(wǎng)規(guī)劃算例進行優(yōu)化規(guī)劃，該配電網(wǎng)共17個節(jié)點（含一個電源節(jié)點）。饋線投資回收率統(tǒng)一為?=0.1；饋線的年折舊率為δ=0.05；電價為α=0.5元/kW·h；最大負荷利用小時數(shù)為τmaxi=3000；該算例的抗體長L=17，種群規(guī)模N=100，免疫優(yōu)勢抗體種群規(guī)模M=20，抗體克隆倍數(shù)N=5c，交叉率Pm=0.4，變異率Pn=0.2，最大種群迭代終止代數(shù)tmax=100。

對于算例的應用，本文提出的免疫優(yōu)勢算法、文獻［12］的常規(guī)免疫算法、文獻［10］的改進單親遺傳算法進行配電網(wǎng)優(yōu)化規(guī)劃，得到的最優(yōu)規(guī)劃結果都一樣，即最優(yōu)規(guī)劃支路為:{1，6，7，2，3}、{1，13，5，14}、{1，13，12，11，4}、{1，15，16，8，9，10}、{1，15，16，8，9，17}。在最優(yōu)目標函數(shù)值即年總費用都為517.2（萬元）的情況下，本文的免疫優(yōu)勢算法，不僅適應度曲線較好，而且收斂速度快。同時，按本文的優(yōu)化方法運行三十次顯示，最差的一次的迭代次數(shù)為31次，最好的一次的迭代次數(shù)為9次，大多數(shù)是迭代次數(shù)在20左右便得到了最優(yōu)解。三種優(yōu)化方法的平均迭代次數(shù)如表1所示，比較中可以看出，本文的免疫優(yōu)勢算法收斂速度和得到最優(yōu)結果所需進化次數(shù)明顯優(yōu)于文獻［10，12］。

表1 三種優(yōu)化算法得到最優(yōu)結果的平均迭代次數(shù)比較

6 結束語

本文詳細介紹了免疫優(yōu)勢算法在配電網(wǎng)規(guī)劃中的應用，在種群初始化和免疫補充時進行接種疫苗，通過修改個體基因上的某些基因位，對不可行解利用啟發(fā)式進行修復，使之成為可行解，提高了計算效率，使得種群中可行解的比例增大；改進型樹形編碼保證了（抗體）配電網(wǎng)絡的輻射性；抗體免疫優(yōu)勢因子的引入使抗體免疫優(yōu)勢則著眼于抗體本身上的獨特型，對問題本身（抗原）依賴程度較低，可以不要需要依靠問題本身的先驗知識，這讓算法可以在線自適應動態(tài)地獲得先驗知識的體制，大大提高了算法的效率。而免疫克隆選擇及變異再選擇兩算子利用大大加快了運算速度和有效地維持了種群的多樣性，同時避免了算法早熟收斂。

［1］劉健，畢鵬翔，楊文宇，等.配電網(wǎng)理論及應用［M］.北京：中國水利水電出版社，2007.

［2］Rayward-Smith V.J.，Osman I.H.，etc..Midern Henristic search methods［M］.John Wiley ＆Sons Ltd，1996.

［3］Miranda V.，Ranito J.V.，Proenco L.M..Genetic algorithms in optimal distribution network planning［J］.IEEE Trans on Power Systems，1994，9（11）：1927 －1933..

［4］謝敏，敬東.遺傳算法在配電網(wǎng)規(guī)劃中的應用［J］.電站系統(tǒng)工程，2002，18（1）：30 －32.

［5］劉曉飛，彭建春等.基于單親遺傳算法的配電網(wǎng)絡規(guī)劃［J］.電網(wǎng)技術，2002，26（30）：53 －56

［6］韓生廉，周文愚.基于免疫更新機制的遺傳算法及其在規(guī)劃問題中的應用［J］.控制與決策，2002，17（3）：20 －23.

［7］顏偉，王麗娜.基于改進免疫遺傳算法的配電網(wǎng)網(wǎng)架規(guī)劃［J］.重慶大學學報：自然科學版，2007，30（1）：29 －30.

［8］蒙文川，邱家駒.基于免疫算法的配電網(wǎng)重構［J］.中國電機工程學報，2006，8：470 －40.

［9］李靖霞，鞠平.配電網(wǎng)絡優(yōu)化規(guī)劃的基因算法［J］.電力系統(tǒng)自動化，1999，23（20）：12 －14.

［10］王雷，顧潔.中壓配電網(wǎng)優(yōu)化規(guī)劃的單親遺傳算法［J］.電力系統(tǒng)自動化，2006，18（3）：72 －76.

［11］焦李成，杜海峰，等.免疫優(yōu)化計算、學習與識別［M］.北京：科學出版社，2006.

［12］周湶，孫才新，張曉星.基于多種群免疫遺傳算法的配電網(wǎng)網(wǎng)架規(guī)劃［J］.重慶大學學報：自然科學版，2005，28（4）：36 －40.