基于遺傳算法與蟻群算法的電網規劃

唐杰斌，周渝慧，陳向婷，郭昱霄，段 煒

（北京交通大學 電氣工程學院，北京 100044）

電網規劃是電力規劃的重要環節，如何加強主網網架結構是電網規劃最重要的內容之一，也是規劃成敗的關鍵［1］。近年來，智能優化算法在解決多目標電網規劃中得到了較廣泛的應用，如：遺傳算法、蟻群算法等。為了克服遺傳算法與蟻群算法本身的缺陷，許多文獻對其進行了改進：文獻［2］提出了用競賽法進行生殖操作、兩點交叉、保留優良品種等改進措施；文獻［3］提出了把改進的自適應代溝遺傳算法引入電網規劃分析網架優化；文獻［4］通過改進傳統的初始種群生成方法以及遺傳操作使之更適應于電網規劃；文獻［5］提出一種基于Pareto蟻群算法的多目標電網規劃方法，把多目標問題轉化為單目標問題來進行電網規劃。

在處理具體問題時，每種智能方法在優化性能與時間性能方面都表現出各自的優勢與缺陷，各種改進算法旨在克服算法各自的缺陷，在增強算法本身優勢方面做的工作并不多［6］。融合算法考慮到在處理電網規劃問題上遺傳算法的快速隨機的全局搜索能力和蟻群算法的分布式并行全局搜索能力的優勢，旨在將2種數學優化算法融合，從而彌補各自的缺陷，達到優勢互補的目的。

1 電網規劃問題的數學模型

為了驗證融合算法在求解電網規劃目標函數時相對單一算法的優勢，本模型以新建的線路作為規劃變量，以新建線路的投資年費用最小為目標函數，如式（1）所示［4］。

式中：i=1，2，…，n；j=1，2，…，n，i≠j，n 為系統節點數；cij為節點i、j之間架設一回新建線路的投資費用；t為節點i、j之間待選線數，在不同節點的待選線路中，t是不同的；xij的值表示節點i、j之間需架設待選線路數。

約束條件為：①流通性約束：確保每個負荷點均有網絡連通；②潮流約束：實際傳輸的潮流應該不大于線路允許的最大潮流；③“N-1”校驗約束：網絡中任意一個區域在所有與之相連的線路中任何一條線路故障的情況下，其它線路的傳輸容量之和必須大于該區域的凈負荷需求。

2 基于融合算法的電網規劃

遺傳算法和蟻群算法相融合，旨在彌補單一算法的缺陷，充分發揮2種算法各自的優勢。由于遺傳算法在求解到一定程度時會產生大量的冗余迭代，此時若改用蟻群算法則能有效避免冗余迭代，使求解的方案更加精確。同時，蟻群算法的初期信息素匱乏、求解速度緩慢，若在初期先用遺傳算法產生最優解，生成蟻群算法初期的信息素，可以有效彌補蟻群算法初期信息素匱乏的缺陷［7］。圖1為融合算法應用于電網規劃的流程圖。

圖1 融合算法應用于電網規劃流程圖

2.1 染色體編碼

生成蟻群算法初始化信息素的過程為遺傳算法求解最優解的階段，因此必須對求解的目標問題進行染色體編碼?？紤]到此染色體結果需要轉化成蟻群算法的初始信息素，本文將待選的線路排序，每一條排好序的待選線路作為染色體的一個基因?；虿捎檬M制編碼，即待選的走廊數均作為一個基因位，基因的數值大小則表示走廊架設的回路數，這樣編碼為轉化成初始信息素提供方便，而且各走廊架設的線路數與基因位也一一對應［8］。其表達式如式（2）所示。

式中：x為目標函數的染色體編碼；n為待選線路的數量；xi為輸電線路走廊架設的線路回數；t為走廊待選回路數的最大值。

2.2 適應度函數

遺傳算法將求解問題表示為染色體位串空間，為了執行適者生存的原則，必須對個體位串的適應性進行評價。本文以架設線路的費用最小為目標函數，因此將目標函數f與適應度函數g做相應的調整［6］，如式（3）所示。

在求解適應度函數時，將約束條件應用懲罰因子加以處理，當染色體滿足目標函數的約束條件時，直接將目標函數代入式（3）計算染色體的適應值；當染色體不滿足約束條件的限制時，則引入相應的懲罰因子。

2.3 遺傳操作

遺傳操作是保留優良個體、淘汰缺陷個體、保持種群多樣性的重要操作，包括選擇、交叉、變異。為了更好地保留種群中的優良個體，在選擇前先對所有個體根據適應度排序，選擇一定比例的個體直接遺傳到下一代，然后對其他的個體利用基于轉盤賭的選擇方式進行選擇操作。對于選定的2個個體位串，隨機選擇多個交叉點，構成交叉點集合，采用多點交叉方式進行交叉操作。變異是為了保持物種的多樣性，但是變異的概率不能太大，否則容易變成隨機算法，因而對不同的算例采用不同的變異概率，隨機選擇變異的個體，然后隨機選擇變異的基因，從而維持個體的多樣性［9］。

電網規劃編碼采用實值形式，因此變異也采用實值變異，如式（4）所示。

2.4 螞蟻轉移概率

首先將m只螞蟻放入n只隨機選擇的節點上，每只螞蟻都以當前點為中心，按照偽隨機比例規則選擇并走到下一節點。螞蟻每走一步后，都要對其走過的路徑進行局部信息素更新，這樣可避免所有螞蟻收斂到同一路徑。當m只螞蟻中有一只到達目標點時，這只螞蟻即為本次迭代的精英螞蟻，對其所找到的路徑進行全局信息素更新，使得屬于本次迭代最優路徑上的信息素得到增強，反之則會逐漸減弱［10，11］。

在螞蟻轉移過程中，螞蟻會繼續產生信息素，路線上原有的信息素強度也會隨著時間的推移而揮發，當螞蟻走完n個節點后，信息素濃度［6］

式中：ρ表示信息素的保留率，1-ρ表示信息素的揮發率，為了防止信息的無限累積，ρ取值范圍限定在0～1；Δτij（t+n）表示螞蟻k在時間段t到（t+n）的過程中，在i到j的路徑上留下的殘留信息濃度，本文采用的是ant-quantity 模型，如式（6）所示。

式中：Q為常數，對不同的算例取不同的值。

2.5 基于融合算法的電網規劃

融合算法的基本思想就是在最佳銜接點采用遺傳算法生成初始信息素分布，在最佳點之后采用蟻群算法求取最優解。遺傳算法設置最大迭代次數Genmax、最小迭代次數Genmin，同時在迭代中引入子代最小進化率rmin，即子代平均適應度與父代平均適應度之差與子代平均適應度的比值。在迭代次數超過Genmin、小于Genmax的過程中，計算子代的進化率，若連續2代的進化率都低于最小進化率rmin，則輸出遺傳算法結果；若未超過則進入最大迭代次數。

遺傳算法結束后，將計算結果以信息素的方式反映到各條規劃線路上，即為蟻群算法初始信息素強度的一部分。另一部分為蟻群算法根據求解問題的具體規模給定的信息素常數，此2部分即為蟻群算法的初始信息素。隨后，信息素更新模型利用式（5）進行信息素強度更新。由于遺傳算法得出的最優解在一定程度上向最優方案接近，因此通過最優解轉換成蟻群算法的初始信息素也加快了螞蟻收斂的速度［12］。

融合算法求解電網規劃的另一個問題是螞蟻在尋找最優路徑時［13］，通過轉移概率選擇某一輸電走廊時還會涉及到選擇的輸電回路數，這是與蟻群算法求解旅行商問題（traveling salesman problem，TSP）的區別。因此，轉移的概率公式也發生變化，它采用偽隨機比例規則［14］選擇下一路徑，即設定一個常數q0，并生成一個在［0，1］上均勻分布的隨機變量q，如果q≤q0，選擇公式（7），否則選擇公式（8）［15］。

式中：α為軌跡的相對重要性；β為能見度的相對重要性；ηij為啟發信息，本文主要考慮輸電線路的擴建費用，取ηij=1/dij。

3 算例分析

算例采用文獻［1］中的現有網絡和待選路徑，如圖2所示。該系統現有10個節點，9條線路，未來系統將增加為18個節點，節點參數如表1所示。本算例存在新增的線路走廊21個，即取染色體長度為21位，待選線路33條，取染色體域N=100，交叉率pc=0.5，即交叉個數Nc=50個，變異率為0.5%，變異個數Nm=21，迭代次數為100次，線路單位長度造價3.0×105元/（km·回），螞蟻個數為20，Q=100，α=1，β=5，ρ=0.7，最小迭代次數Genmin為40次，最大迭代次數Genmax為100次，本例中由于適應度函數由最小費用轉化而來，因此最小進化率rmin=5%。

圖2 網絡路徑示意圖

表1 節點參數

若僅運用遺傳算法求解，設置最大迭代次數為100，不同迭代次數的規劃結果如表2所示。迭代次數為50次時，子代進化率約為3%，因此最佳迭代點為迭代50次的結果。同時，本算例也計算了迭代到100次的結果，絕對差別僅為0.123億元，從擴建支路長度來看，擴建費用差別較少。因此可以認為在50次到100次迭代期間，產生了大量的冗余迭代。

若僅運用蟻群算法求解，設置迭代次數為150，不同迭代次數的規劃結果如表3所示。迭代次數約為100次時，擴建費用與遺傳算法迭代到50次時絕對差為0.093億元，相對擴建線路長度來說，擴建費用差別較少。因此，可以認為在100次迭代之前產生的信息素與遺傳算法迭代到50次產生的信息素相匹配。

表3 蟻群算法規劃結果

為了發揮遺傳算法與蟻群算法各自的優勢，采用融合算法，將遺傳算法的迭代次數設置為50，蟻群算法迭代次數設置為100，其規劃結果如表4所示。融合算法在迭代次數為50次時是遺傳算法迭代50次的結果，迭代100次與150次時則是用遺傳算法的最優解產生的初始信息素，再利用蟻群算法求解得到的最優方案，其最優方案的結果如圖3所示［16］。

表4 融合算法規劃結果

比較表2與表4迭代100次的結果可以發現，融合算法擴建費用比遺傳算法高0.06億元，這是由于融合算法是以遺傳算法的最優解為初始信息素進行迭代，在使用蟻群算法迭代初期有一個適應過程，方能轉化為最適合蟻群算法的解集，因此在迭代100次時出現這種結果是可能的。比較表3與表4可以發現，融合算法在迭代100次和150次時均有較大的改進。

圖3 融合算法確定的網絡結構

4 結論

使用遺傳算法進行電網規劃在迭代后期容易產生大量冗余迭代，大大降低了遺傳算法求解電網規劃的效率。蟻群算法處理電網規劃問題時初始信息匱乏，最初求解速度緩慢。為了更好地運用遺傳算法與蟻群算法的優勢，引入融合算法進行電網規劃，既能避免求解到一定程度后產生大量冗余迭代，同時也充分利用了蟻群算法求解精度高的優勢，最終使得規劃方案達到最優。

［1］ 王錫凡.電力系統規劃基礎［M］.北京：水利電力出版社，1994.

［2］ 張俊芳，王秀麗，王錫凡.遺傳算法在電網規劃應用中的改進［J］.電網技術，1997，21（4）：25-32.

［3］ 黃武忠，鐘丹虹，孔德鍵，等.改進的遺傳算法在汕頭電網規劃中的應用［J］.廣東電力，2001，14（5）：8-11.

［4］ 顧益磊，許諾，王西田.遺傳算法應用于電網規劃的難點與改進［J］.電網技術，2007，31（增刊1）：29-33.

［5］ Miranda V，Ranito JV.Genetic algorithms in optimalmul-tistage distribution network planning［J］.IEEE Transac-tionson Power Systems，1994，9（4）：1927-1933.

［6］ 朱福喜，朱三元，伍春香.人工智能基礎教程［M］.北京：清華大學出版社，2006.

［7］ 楊劍峰.基于遺傳算法和螞蟻算法求解函數優化問題［J］.浙江大學學報，2007，41（3）：427-430.

［8］ Gallego R A，Monticelli A，Romero R.Transmission sys-tem expansion planning by extended genetic algorithm［J］.IEE Proceedings Generation Transmission and Distribu-tion，1998，145（3）：329-335.

［9］ 林嬌燕.運用改進遺傳算法的輸電網規劃［J］.華南理工大學學報：自然科學版，2002，30（8）：36-39.

［10］ 符楊，孟令合，胡榮，等.改進多目標蟻群算法在電網規劃中的應用［J］.電網技術，2009，33（18）：57-62.

［11］ Ippolito M G，Sanseverino ER，Vuinovich F.Multiobjec-tive ant colony search algorithm for optimal electrical distribution system strategical planning［C］.Portland：CEC 2004Congresson Evolutionary Computation，2004.

［12］ 韓富春，王晉，楊翠茹，等.遺傳算法與螞蟻算法相融合的電力系統最優潮流計算［J］.電力學報，2005，20（4）：340-342.

［13］ MarcoDorigo，Gambardella，Luca Maria.Ant colonies for the traveling salesman problem［J］.Biosystems，1997，43（2）：73-81.

［14］ 符楊，孟令合，朱蘭，等.Pareto蟻群算法在多目標電網規劃中的應用［J］.電力系統及其自動化學報，2009，21（4）：41-45.

［15］ 涂亞平，劉萍，謝寶陵，等.基本螞蟻算法中算法參數的優化［J］.小型微型計算機系統，2007，28（11）：1985-1987.

［16］ 雷英杰，張善文，李續武，等.MATLAB遺傳算法工具箱及應用［M］.西安：西安電子科技大學出版社，2005.