遺傳算法在配電網(wǎng)的網(wǎng)架結構優(yōu)化中的應用

侯德明

摘要：本文闡述了配電網(wǎng)網(wǎng)架結構優(yōu)化的數(shù)學模型,在傳統(tǒng)優(yōu)化算法基礎上改進了一種新的自適應遺傳算法，在一定程度上克制了偏離最優(yōu)解而陷入局部最優(yōu)，直至獲得全局最優(yōu)解。

關鍵詞：遺傳算法網(wǎng)架結構配電網(wǎng)優(yōu)化

1 問題的提出

配電系統(tǒng)中的網(wǎng)架結構優(yōu)化問題主要有兩個特點：非線性和整數(shù)性，這也正是解決問題的困難所在。用非線性規(guī)劃方法解題常常會遇到搜索方向錯誤，迭代不收斂，逼近速度慢等問題。當變量和約束條件數(shù)目較多時，這些問題更加突出。另外，線路都是按整回和確定的電壓等級來架設的，若變量取線路的某電氣量，則變量應是整數(shù)值或某種離散值。對于這樣的非線性整數(shù)規(guī)劃問題，目前還沒有理想的優(yōu)化算法。若試圖嚴格地解決這種問題，將會遇到一個典型的組合數(shù)目以指數(shù)形式增長，即所謂“組合爆炸”問題。綜觀以前的各種傳統(tǒng)優(yōu)化方法，各有優(yōu)勢，要么容易偏離最優(yōu)解陷入局部最優(yōu)，要么受到維數(shù)的限制而難以達到實用的目的。為了解決這兩個方面的問題，下面把遺傳算法引入城市電力網(wǎng)網(wǎng)架結構的優(yōu)化中來，以欺得到一個較滿意的解決問題的辦法。

2 遺傳算法介紹

遺傳算法是一種搜索算法，是通過模擬自然進化過程來搜索最優(yōu)解的方法。其目的是解釋自然界的自適應過程而設計的一個體現(xiàn)自然界進化機理的軟件系統(tǒng)。大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進行演化的。自然選擇決定了群體中哪些個體能夠存活并繁殖，即適者生存，不適者淘汰；有性生殖保證了后代基因中的混合與重組，加快了進化過程。由于該方法隱含并行性和全局信息的有效利用能力，尤其適合于處理傳統(tǒng)搜索方法解決不了的復雜問題，近十多年來在各領域得到廣泛應用。

遺傳算子：一個簡單的遺傳算法由復制、雜交和變異三個遺傳算子組成。其中復制算子是把當前群體中的個體按與適應值成正比的概率復制到新群體中去。這樣，低適應值的個體趨向于被淘汰，高適應值的個體趨向于被復制，復制算子的作用效果提高了群體的平均適應值，也充分體現(xiàn)了“優(yōu)勝劣汰”這種自然進化機制；雜交算子是模擬生物界的有性繁殖，可以產(chǎn)生新的個體，使其比它的兩個父代有更高的適應值。雜交算子是遺傳算法的重要組成部分；變異算子是用一個很小的概率隨機地改變?nèi)旧w串上的位置，其效果是增加群體的多樣性，擴大搜索空間。

主要特點：遺傳算法與傳統(tǒng)的優(yōu)化算法相比，主要體現(xiàn)在它不是直接作用參變量集上，而是利用參變量集的某種編碼；不是從單個點，而是從一個點的群體開始搜索，因而能夠快速全局收斂；它還利用了概率轉移規(guī)則，而非確定性規(guī)則，因而能夠搜索離散的有噪聲的多峰值復雜空間；以及利用適應值信息，無須導數(shù)或輔助信息，具有廣泛的適應性；在解空間內(nèi)進行充分的搜索，但并不是盲目地窮舉或瞎碰，因此在其搜索時間和效率上往往優(yōu)于其他優(yōu)化方法。首先，它在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲情況下，它也能以很大的概率找到整體最優(yōu)解。為了尋找最優(yōu)解，傳統(tǒng)方法是用啟發(fā)式策略，在單個猜測解的領域尋找，即使算法中允許偶爾地跳到解空間中更遠的部分，這些啟發(fā)式算法也往往趨于局部最優(yōu)。理論上遺傳算法像撒網(wǎng)一樣，通過保持在參變量的解空間區(qū)域中的多個點的搜索可以以很大的概率找到全局最優(yōu)解。其次，由于它固有的并行性，遺傳算法非常適用于大規(guī)模并行計算機。由于遺傳算法的操作主要是在單個位串上，至多是一對位串之間的雜交，所以可讓每個處理機負責處理單個位串，從而可以并行處理整個群體。

計算步驟：在進行個體遺傳算法之前，需要作好如下準備工作。首先是選擇編碼；一般編碼選擇由多個二進制串（0，1）構成，其中“0”、“1”分別表示支路不連通和連通。應注意的是編碼不局限于二進制，根據(jù)對象不同也可選其他的數(shù)來編碼。其次是確定適應值函數(shù)；相當于確定數(shù)學規(guī)劃中的目標函數(shù)。然后在選擇控制算法的參數(shù)；最后確定停止運行的準則。

3 網(wǎng)架結構優(yōu)化的遺傳算法

網(wǎng)絡結構優(yōu)化的目標函數(shù)：網(wǎng)絡結構優(yōu)化問題是基于現(xiàn)有網(wǎng)架結構，在已知水平年電源及負荷需求下，并假定變電站的擴建或新建的時間、地點和容量都已確定，決定在規(guī)劃期內(nèi)何時何地架設多少回輸電線路，以使得線路年費用最小。這里采用考慮了貼現(xiàn)的線路建設投資費用和運行費用的最小年費用法，即。其中Z為方案總的線路建設投資費用，為方案第年的運行費用。

編碼的選擇：遺傳算法是一個搜索特征串空間的過程，其目的是找到具有相對高適應值的串。在應用遺傳算法求解特殊問題之前，第一步就要確定用類似于染色體的串來表示問題的辦法，即染色體的編碼形式。這里采用二進制編碼形式，直接對待選線路進行編碼，反映其是否架設，以及選用多大截面等。這種編碼形式非常直觀，便于規(guī)劃方案和染色體之間的編碼和解碼。若只考慮線路架設與否，則可將各待選線路排序，然后按此順序將每條待選線路作為染色體串中的一個基因，每個基因是一個一位的二進制數(shù)。當基因值為1時，表示其對應的待選線路被選中加入系統(tǒng)，當基因值為0時，則相反。但考慮到對方案進行評估時需對方案所表示的網(wǎng)絡進行潮流分析，這樣的染色體解碼成規(guī)劃方案時應能得到線路參數(shù)，所以需在基因中加入線路截面的信息。

城網(wǎng)優(yōu)化遺傳算法的計算過程：首先輸入原始數(shù)據(jù)；其中包括網(wǎng)絡拓撲，即節(jié)點數(shù)、已有和待架線路數(shù)、各線路的首末節(jié)點號和線路的有關參數(shù)。節(jié)點的發(fā)電出力及負荷，遺傳算數(shù)本身所需參數(shù)，即群體大小、基因位數(shù)、最大遺傳代數(shù)、變異率和計算適應函數(shù)時用到的有關參數(shù)等。然后形成初始方案，接著計算適應值，進行遺傳操作，最后輸出計算結果。

適應函數(shù)的建立：在編碼方案選定以后，接著就是要確定適應函數(shù)以檢測由特定位串所表示的規(guī)劃方案的好壞程度，從而指引遺傳操作的正常進行。適應函數(shù)應該反映電網(wǎng)規(guī)劃的目的和要求，即要使規(guī)劃方案在滿足正常運行要求和安全運行要求的情況下，使電網(wǎng)的建設和運行費用最小。建設費用和運行費用最小的目標函數(shù)，在考慮約束條件后的增廣函數(shù)數(shù)學模型為。其中為方案的年費用，為懲罰因子，為方案的約束條件。電網(wǎng)規(guī)劃的目的是希望電網(wǎng)的建設和運行費用最小，為符合遺傳算法最大值的特點，適應函數(shù)可表示為。其中的選取以保證為非負數(shù)為準。由的表達式可知適應函數(shù)是一個非線性的、不連續(xù)和非凸的，這對于嚴格的數(shù)學規(guī)劃方法是難以求解的，而遺傳算法則是在解碼得到一個解之后才對適應函數(shù)進行計算評估的，因此對適應函數(shù)形式無任何限制，這充分顯示了遺傳算法的優(yōu)越性。

參考文獻：

[1]孫杰.基于單親遺傳算法的配電網(wǎng)絡優(yōu)化規(guī)劃[D].華北電力大學（河北）.2005年.

[2]閆大威.基于遺傳算法的城市中壓配電網(wǎng)規(guī)劃自動布線[D].天津大學；2005年.

[3]石鋒杰，蘭海燕. 遺傳算法用于配電網(wǎng)絡優(yōu)化規(guī)劃[J].現(xiàn)代電子技術.2006年13期.