基于遺傳算法與蟻群算法的電網(wǎng)規(guī)劃

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

（北京交通大學(xué) 電氣工程學(xué)院，北京 100044）

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

在處理具體問題時，每種智能方法在優(yōu)化性能與時間性能方面都表現(xiàn)出各自的優(yōu)勢與缺陷，各種改進(jìn)算法旨在克服算法各自的缺陷，在增強(qiáng)算法本身優(yōu)勢方面做的工作并不多［6］。融合算法考慮到在處理電網(wǎng)規(guī)劃問題上遺傳算法的快速隨機(jī)的全局搜索能力和蟻群算法的分布式并行全局搜索能力的優(yōu)勢，旨在將2種數(shù)學(xué)優(yōu)化算法融合，從而彌補(bǔ)各自的缺陷，達(dá)到優(yōu)勢互補(bǔ)的目的。

1 電網(wǎng)規(guī)劃問題的數(shù)學(xué)模型

為了驗(yàn)證融合算法在求解電網(wǎng)規(guī)劃目標(biāo)函數(shù)時相對單一算法的優(yōu)勢，本模型以新建的線路作為規(guī)劃變量，以新建線路的投資年費(fèi)用最小為目標(biāo)函數(shù)，如式（1）所示［4］。

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

約束條件為：①流通性約束：確保每個負(fù)荷點(diǎn)均有網(wǎng)絡(luò)連通；②潮流約束：實(shí)際傳輸?shù)某绷鲬?yīng)該不大于線路允許的最大潮流；③“N-1”校驗(yàn)約束：網(wǎng)絡(luò)中任意一個區(qū)域在所有與之相連的線路中任何一條線路故障的情況下，其它線路的傳輸容量之和必須大于該區(qū)域的凈負(fù)荷需求。

2 基于融合算法的電網(wǎng)規(guī)劃

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

圖1 融合算法應(yīng)用于電網(wǎng)規(guī)劃流程圖

2.1 染色體編碼

生成蟻群算法初始化信息素的過程為遺傳算法求解最優(yōu)解的階段，因此必須對求解的目標(biāo)問題進(jìn)行染色體編碼。考慮到此染色體結(jié)果需要轉(zhuǎn)化成蟻群算法的初始信息素，本文將待選的線路排序，每一條排好序的待選線路作為染色體的一個基因。基因采用十進(jìn)制編碼，即待選的走廊數(shù)均作為一個基因位，基因的數(shù)值大小則表示走廊架設(shè)的回路數(shù)，這樣編碼為轉(zhuǎn)化成初始信息素提供方便，而且各走廊架設(shè)的線路數(shù)與基因位也一一對應(yīng)［8］。其表達(dá)式如式（2）所示。

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

2.2 適應(yīng)度函數(shù)

遺傳算法將求解問題表示為染色體位串空間，為了執(zhí)行適者生存的原則，必須對個體位串的適應(yīng)性進(jìn)行評價。本文以架設(shè)線路的費(fèi)用最小為目標(biāo)函數(shù)，因此將目標(biāo)函數(shù)f與適應(yīng)度函數(shù)g做相應(yīng)的調(diào)整［6］，如式（3）所示。

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

2.3 遺傳操作

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

電網(wǎng)規(guī)劃編碼采用實(shí)值形式，因此變異也采用實(shí)值變異，如式（4）所示。

2.4 螞蟻轉(zhuǎn)移概率

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

在螞蟻轉(zhuǎn)移過程中，螞蟻會繼續(xù)產(chǎn)生信息素，路線上原有的信息素強(qiáng)度也會隨著時間的推移而揮發(fā)，當(dāng)螞蟻?zhàn)咄阯個節(jié)點(diǎn)后，信息素濃度［6］

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

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

2.5 基于融合算法的電網(wǎng)規(guī)劃

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

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

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

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

3 算例分析

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

圖2 網(wǎng)絡(luò)路徑示意圖

表1 節(jié)點(diǎn)參數(shù)

若僅運(yùn)用遺傳算法求解，設(shè)置最大迭代次數(shù)為100，不同迭代次數(shù)的規(guī)劃結(jié)果如表2所示。迭代次數(shù)為50次時，子代進(jìn)化率約為3%，因此最佳迭代點(diǎn)為迭代50次的結(jié)果。同時，本算例也計(jì)算了迭代到100次的結(jié)果，絕對差別僅為0.123億元，從擴(kuò)建支路長度來看，擴(kuò)建費(fèi)用差別較少。因此可以認(rèn)為在50次到100次迭代期間，產(chǎn)生了大量的冗余迭代。

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

表3 蟻群算法規(guī)劃結(jié)果

為了發(fā)揮遺傳算法與蟻群算法各自的優(yōu)勢，采用融合算法，將遺傳算法的迭代次數(shù)設(shè)置為50，蟻群算法迭代次數(shù)設(shè)置為100，其規(guī)劃結(jié)果如表4所示。融合算法在迭代次數(shù)為50次時是遺傳算法迭代50次的結(jié)果，迭代100次與150次時則是用遺傳算法的最優(yōu)解產(chǎn)生的初始信息素，再利用蟻群算法求解得到的最優(yōu)方案，其最優(yōu)方案的結(jié)果如圖3所示［16］。

表4 融合算法規(guī)劃結(jié)果

比較表2與表4迭代100次的結(jié)果可以發(fā)現(xiàn)，融合算法擴(kuò)建費(fèi)用比遺傳算法高0.06億元，這是由于融合算法是以遺傳算法的最優(yōu)解為初始信息素進(jìn)行迭代，在使用蟻群算法迭代初期有一個適應(yīng)過程，方能轉(zhuǎn)化為最適合蟻群算法的解集，因此在迭代100次時出現(xiàn)這種結(jié)果是可能的。比較表3與表4可以發(fā)現(xiàn)，融合算法在迭代100次和150次時均有較大的改進(jìn)。

圖3 融合算法確定的網(wǎng)絡(luò)結(jié)構(gòu)

4 結(jié)論

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

［1］ 王錫凡.電力系統(tǒng)規(guī)劃基礎(chǔ)［M］.北京：水利電力出版社，1994.

［2］ 張俊芳，王秀麗，王錫凡.遺傳算法在電網(wǎng)規(guī)劃應(yīng)用中的改進(jìn)［J］.電網(wǎng)技術(shù)，1997，21（4）：25-32.

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

［4］ 顧益磊，許諾，王西田.遺傳算法應(yīng)用于電網(wǎng)規(guī)劃的難點(diǎn)與改進(jìn)［J］.電網(wǎng)技術(shù)，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］ 朱福喜，朱三元，伍春香.人工智能基礎(chǔ)教程［M］.北京：清華大學(xué)出版社，2006.

［7］ 楊劍峰.基于遺傳算法和螞蟻算法求解函數(shù)優(yōu)化問題［J］.浙江大學(xué)學(xué)報，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］ 林嬌燕.運(yùn)用改進(jìn)遺傳算法的輸電網(wǎng)規(guī)劃［J］.華南理工大學(xué)學(xué)報：自然科學(xué)版，2002，30（8）：36-39.

［10］ 符楊，孟令合，胡榮，等.改進(jìn)多目標(biāo)蟻群算法在電網(wǎng)規(guī)劃中的應(yīng)用［J］.電網(wǎng)技術(shù)，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］ 韓富春，王晉，楊翠茹，等.遺傳算法與螞蟻算法相融合的電力系統(tǒng)最優(yōu)潮流計(jì)算［J］.電力學(xué)報，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蟻群算法在多目標(biāo)電網(wǎng)規(guī)劃中的應(yīng)用［J］.電力系統(tǒng)及其自動化學(xué)報，2009，21（4）：41-45.

［15］ 涂亞平，劉萍，謝寶陵，等.基本螞蟻算法中算法參數(shù)的優(yōu)化［J］.小型微型計(jì)算機(jī)系統(tǒng)，2007，28（11）：1985-1987.

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