基于改進(jìn)細(xì)菌覓食優(yōu)化算法的輸電網(wǎng)規(guī)劃

王 瑞，王起琦，段柯均，趙 丹

（1.東北電力大學(xué)，吉林 吉林 132012；2.國(guó)網(wǎng)營(yíng)口供電公司，遼寧 營(yíng)口 115000）

輸電網(wǎng)規(guī)劃問(wèn)題在數(shù)學(xué)上是一個(gè)帶有大量約束條件的非線性組合優(yōu)化問(wèn)題。近年來(lái)，由于現(xiàn)代啟發(fā)式算法具有實(shí)現(xiàn)簡(jiǎn)單，不受目標(biāo)函數(shù)的形態(tài)約束，能夠?qū)崿F(xiàn)多維有效搜索等特點(diǎn)，在輸電網(wǎng)規(guī)劃問(wèn)題求解中得到了快速的發(fā)展，如差分進(jìn)化算法［1］、人工魚(yú)群算法［2］、粒子 群算法［3］、蟻群 算法等［4］，每種方法各有其利弊，但是這些方法拓展了輸電網(wǎng)規(guī)劃求解的思路，有利于快速精確獲得最優(yōu)規(guī)劃方案。細(xì)菌覓食優(yōu)化（BFO）算法［5］是近年來(lái)提出的一種模擬細(xì)菌覓食行為的仿生進(jìn)化算法。在求解大規(guī)模輸電網(wǎng)規(guī)劃問(wèn)題時(shí)，該算法容易陷入局部最優(yōu)，搜索精度和后期收斂速度明顯下降。利用禁忌表和能量因子分別針對(duì)算法中的趨向性操作和遷徙操作進(jìn)行改進(jìn)，從而增強(qiáng)算法的全局搜索能力及跳出局部極值的能力，減少了逃逸現(xiàn)象的發(fā)生并提高算法的收斂速度和搜索精度，使改進(jìn)細(xì)菌覓食優(yōu)化算法（IBFO）適用于大規(guī)模輸電網(wǎng)規(guī)劃問(wèn)題的求解。本文使用IBFO 算法，在已有的負(fù)荷預(yù)測(cè)和電源規(guī)劃的基礎(chǔ)上，根據(jù)已經(jīng)存在的網(wǎng)絡(luò)結(jié)構(gòu)和已知的待選線路，從而得出滿足運(yùn)行要求的經(jīng)濟(jì)性最佳的網(wǎng)絡(luò)方案，其規(guī)劃后的結(jié)果使方案投資費(fèi)用、運(yùn)行費(fèi)用以及正常運(yùn)行時(shí)的過(guò)負(fù)荷費(fèi)用三項(xiàng)之和最小。

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

本文采用的是靜態(tài)輸電網(wǎng)規(guī)劃模型［6］。根據(jù)規(guī)劃后使方案投資費(fèi)用、方案的運(yùn)行費(fèi)用以及正常運(yùn)行時(shí)的過(guò)負(fù)荷費(fèi)用三項(xiàng)之和最小的假設(shè)，輸電網(wǎng)規(guī)劃數(shù)學(xué)模型可以描述為：

式中：k1為新建每km 線路的建設(shè)費(fèi)用；li為支路i中新建線路的長(zhǎng)度；xi為輸電走廊i上的新建線路的數(shù)量；k2為年網(wǎng)損費(fèi)用系數(shù)；ri為支路i的電阻；Pi為正常運(yùn)行情況下支路i傳輸?shù)挠泄β?；k3W為過(guò)負(fù)荷懲罰項(xiàng)，其中k3為過(guò)負(fù)荷懲罰系數(shù)，其值為一個(gè)非常大的正數(shù)，W為模型中各支路總的過(guò)負(fù)荷量，當(dāng)系統(tǒng)存在過(guò)負(fù)荷狀況時(shí)，由于懲罰系數(shù)k3的影響，目標(biāo)函數(shù)值會(huì)迅速變大，使當(dāng)前規(guī)劃方案變?yōu)榇蝺?yōu)方案，從而保證了得到的優(yōu)化結(jié)果不存在過(guò)負(fù)荷現(xiàn)象；Pmax為線路i的傳輸功率上限；m為輸電走廊的總數(shù)；B為系統(tǒng)節(jié)點(diǎn)導(dǎo)納矩陣；θ為節(jié)點(diǎn)相角；PL為負(fù)荷；PG為發(fā)電機(jī)出力；Bl為各支路導(dǎo)納組成的對(duì)角矩陣；A為系統(tǒng)關(guān)聯(lián)矩陣；ximax為走廊可以新增線路的上限。

2 改進(jìn)細(xì)菌覓食優(yōu)化算法（IBFO）

2.1 對(duì)BFO 算法的改進(jìn)

2.1.1 對(duì)趨向性操作的改進(jìn)

在趨向性操作中，細(xì)菌通過(guò)隨機(jī)性翻轉(zhuǎn)并與記憶中的上次時(shí)刻進(jìn)行能量比較，如果環(huán)境變化則選擇作為前進(jìn)方向，這使得細(xì)菌對(duì)環(huán)境信息識(shí)別方式單一。這一反向選擇機(jī)制帶有更多的隨機(jī)性成分，沒(méi)有充分體現(xiàn)細(xì)菌對(duì)環(huán)境細(xì)菌濃度、食物濃度的信息感知，也無(wú)法體現(xiàn)細(xì)菌與細(xì)菌之間、細(xì)菌與環(huán)境之間的信息交流與反饋，致使算法容易陷入局部最優(yōu)，效率較低，搜索精度不高。

禁忌搜索算法［7］具有強(qiáng)大的全局搜索能力。禁忌搜索算法的核心思想是將已經(jīng)搜索過(guò)的局部最優(yōu)解的位置進(jìn)行記錄，并在后期迭代搜索中避開(kāi)這些位置，進(jìn)而使得搜索路徑多樣化，避免重復(fù)搜索。為完成以上的核心行為，禁忌搜索算法使用禁忌表來(lái)記錄搜索路徑的歷史信息，這可在一定程度上避開(kāi)局部極值點(diǎn)，開(kāi)辟新的搜索區(qū)域。禁忌表的存在使禁忌搜索算法能夠很容易跳出局部最優(yōu)解且不出現(xiàn)振蕩，使算法具有強(qiáng)大的全局搜索能力，因此引入禁忌表來(lái)改進(jìn)趨向性操作。

禁忌表的更新采用先入先出模式。利用禁忌表來(lái)記錄細(xì)菌以前若干次的移動(dòng)，禁止這些移動(dòng)在近期內(nèi)返回。在迭代固定次數(shù)后，禁忌表釋放這些移動(dòng)，可以重新參加尋優(yōu)，因此禁忌表是一個(gè)循環(huán)記錄的表。當(dāng)禁忌表滿的時(shí)候，每迭代一次，它的禁忌對(duì)象被記錄在禁忌表的尾端，而它最先記錄的一個(gè)移動(dòng)就從禁忌表中釋放出來(lái)。這樣可以保證多樣化的有效覓食，以最終實(shí)現(xiàn)全局優(yōu)化，防止陷入局部最優(yōu)解。引入禁忌表后新的趨向性操作步驟見(jiàn)圖1。

圖1 改進(jìn)的趨向性操作流程圖

2.1.2 對(duì)遷徙操作的改進(jìn)

在基本BFO 算法的遷徙操作中，算法只是以某一固定的概率將細(xì)菌群體重新分配到尋優(yōu)空間當(dāng)中去，借此改善細(xì)菌跳出局部極值的能力，但是該算法中對(duì)每個(gè)細(xì)菌賦予相同的遷徙概率Ped。由于遷徙是以一定概率隨機(jī)發(fā)生的，因此遷徙操作同樣有可能選中已經(jīng)找到最優(yōu)位置的細(xì)菌，使其發(fā)生遷徙而離開(kāi)最優(yōu)位置，這種現(xiàn)象被稱(chēng)為逃逸［8］（escape）。逃逸現(xiàn)象的發(fā)生相當(dāng)于丟失了精英個(gè)體。

遷徙概率越大，逃逸發(fā)生的可能性就越大；減小遷徙概率可以使發(fā)生隨機(jī)遷徙的細(xì)菌個(gè)數(shù)減少，但并不能避免逃逸的發(fā)生，以隨機(jī)概率選擇的細(xì)菌個(gè)體并不能完全避開(kāi)已經(jīng)找到全局最優(yōu)值的個(gè)體，而小的遷徙概率會(huì)使函數(shù)跳出局部極值的能力減小。遷徙實(shí)際上變成了解的退化。因此對(duì)遷徙操作進(jìn)行改進(jìn)，根據(jù)文獻(xiàn)［9］改進(jìn)遷徙概率，新的遷徙概率PE為：

式中：Ji為細(xì)菌i的適應(yīng)度函數(shù)值即能量值，Jmax、Jmin是目前細(xì)菌種群中最大和最小的能量值，Ped為固定的遷移概率；γi為能量因子，細(xì)菌i的能量大于能量最小的細(xì)菌γi時(shí)值就越小，新的遷移概率PE也就越??；反之，γi值越大，遷移概率PE也就越小。

2.2 IBFO 算法流程圖

IBFO 算法需要輸入初始的數(shù)據(jù)和參數(shù)包括細(xì)菌的種群規(guī)模數(shù)N，遷徙概率Ped游動(dòng)次數(shù)Ns，進(jìn)行趨化性操作的次數(shù)Nc，進(jìn)行復(fù)制操作的次數(shù)Nre，進(jìn)行遷徙操作的次數(shù)Ned，禁忌表長(zhǎng)度LT。IBFO 算法采用的是3層嵌套循環(huán)方式。最內(nèi)層的是趨向性操作循環(huán)，外邊一層的是復(fù)制操作循環(huán)，最外層的是遷徙操作循環(huán)，具體步驟見(jiàn)圖2。

圖2 IBFO 算法流程圖

3 算例

3.1 算例1

采用IEEE－18節(jié)點(diǎn)系統(tǒng)進(jìn)行試驗(yàn)，算例網(wǎng)絡(luò)結(jié)構(gòu)及相關(guān)參數(shù)參見(jiàn)文獻(xiàn)［8］，該系統(tǒng)有32條待選輸電線路。參考相關(guān)文獻(xiàn)取細(xì)菌的種群規(guī)模N＝40個(gè)，遷徙概率Ped＝0.25，游動(dòng)Ns＝4次，進(jìn)行趨化性操作Nc＝20次，進(jìn)行復(fù)制操作Nre＝5次，進(jìn)行遷徙操作Ned＝10次，這樣總的迭代達(dá)到1 000次，禁忌表長(zhǎng)度LT＝5。過(guò)負(fù)荷檢驗(yàn)采用直流潮流。應(yīng)用數(shù)學(xué)軟件MATLAB 編制計(jì)算程序，求解得到的規(guī)劃方案與文獻(xiàn)［6］的網(wǎng)絡(luò)規(guī)劃結(jié)果相吻合。

BFO 與IBFO 計(jì)算結(jié)果比較見(jiàn)表1。由表1可見(jiàn)，記錄的50次試驗(yàn)計(jì)算中，BFO 算法出現(xiàn)了8次未收斂的情況且沒(méi)有得到全局最優(yōu)解，而IBFO 算法則全部收斂。在最優(yōu)解出現(xiàn)代數(shù)次數(shù)和計(jì)算所使用的時(shí)間方面，IBFO 算法相比較于BFO 算法有著很明顯的優(yōu)勢(shì)。

表1 BFO 與IBFO 計(jì)算結(jié)果比較

圖3為記錄其中1次計(jì)算過(guò)程中IBFO 算法和BFO 算法的尋優(yōu)路徑，可以得出BFO 算法在20次迭代算就以后出現(xiàn)多次陷入局部機(jī)制的情況，而IBFO 算法在第18次就已經(jīng)尋找到了全局最優(yōu)解，進(jìn)一步說(shuō)明IBFO 算法在全局搜索能力上有明顯的提高。

圖3 IBFO 算法和BFO 算法尋優(yōu)路徑比較

3.2 算例2

本算例采用巴西南部46節(jié)點(diǎn)系統(tǒng)，該系統(tǒng)已有輸電線路47條，待選輸電線路79條。本算例的網(wǎng)絡(luò)結(jié)構(gòu)及參數(shù)參見(jiàn)文獻(xiàn)［10］。應(yīng)用IBFO 算法對(duì)網(wǎng)絡(luò)進(jìn)行求解所得規(guī)劃結(jié)果見(jiàn)表2，IBFO 算法和BFO 算法尋優(yōu)路徑比較見(jiàn)圖4。每km 線路的建設(shè)費(fèi)用取25萬(wàn)元，模型中優(yōu)化后的結(jié)果為188 005萬(wàn)元，得出的規(guī)劃方案與文獻(xiàn)［10］中的方案一致。

表2 規(guī)劃方案（算例2）

圖4為記錄其中1次計(jì)算過(guò)程中IBFO 算法和BFO 算法的尋優(yōu)路徑，可以得出BFO 算法在進(jìn)行335次迭代計(jì)算后才得到最優(yōu)解；而IBFO 算法只進(jìn)行了100次迭代計(jì)算就已經(jīng)尋找到了全局最優(yōu)解，說(shuō)明IBFO算法在全局搜索能力上有明顯的提高。

圖4 IBFO 算法和BFO 算法尋優(yōu)路徑比較

本算例表明，IBFO 算法在維度較高的電力系統(tǒng)規(guī)劃問(wèn)題中適用。

4 結(jié)論

本文將IBFO 算法應(yīng)用于輸電網(wǎng)規(guī)劃求解問(wèn)題中。針對(duì)基本BFO 算法在求解大規(guī)模輸電網(wǎng)規(guī)劃問(wèn)題時(shí)所暴露出的缺點(diǎn)，引入禁忌表來(lái)改進(jìn)趨向性操作以及利用能量因子對(duì)遷徙操作進(jìn)行改進(jìn)，從而使IBFO 算法能夠更有效地求解輸電網(wǎng)規(guī)劃問(wèn)題。

通過(guò)IEEE－18節(jié)點(diǎn)系統(tǒng)和巴西南部46節(jié)點(diǎn)系統(tǒng)的計(jì)算，結(jié)果表明：IBFO 算法后期陷入局部極值的概率降低，同時(shí)算法的收斂速度和搜索精度得到了優(yōu)化。作為一種新興的算法，IBFO 算法仍需進(jìn)一步的研究，來(lái)拓展其在輸電網(wǎng)規(guī)劃方面的應(yīng)用。

［1］ 聶宏展，鄭鵬飛，于婷，等.基于多策略差分進(jìn)化算法的輸電網(wǎng)規(guī)劃［J］.電工電能新技術(shù)，2013，32（1）：13－18.

［2］ 劉耀年，李迎紅，劉俊峰，等.基于人工魚(yú)群算法的徑向基神經(jīng)網(wǎng)絡(luò)的研究［J］.東北電力大學(xué)學(xué)報(bào)，2006，26（4）：23－27.

［3］ 金義雄，程浩忠.改進(jìn)粒子群算法及其在輸電網(wǎng)規(guī)劃的應(yīng)用［J］.中國(guó)電機(jī)工程學(xué)報(bào)，2005，25（4）：46－50.

［4］ 翟海保，程浩忠，呂干云，等.基于模式記憶并行蟻群算法的輸電網(wǎng)規(guī)劃［J］.中國(guó)電機(jī)工程學(xué)，2005，25（9）：17－22.

［5］ 周雅蘭.細(xì)菌覓食優(yōu)化算法的研究與應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46（20）：16－21.

［6］ 聶宏展，呂盼，喬怡，等.基于人工魚(yú)群算法的輸電網(wǎng)絡(luò)規(guī)劃［J］.電工電能新技術(shù)，2008，27（2）：11－15.

［7］ 王賽一，王成山.遺傳禁忌混合算法及其在電網(wǎng)規(guī)劃中的應(yīng)用［J］.電力系統(tǒng)自動(dòng)化，2005，28（20）：43－46.

［8］ 李王君，黨建武，卜鋒.細(xì)菌覓食優(yōu)化算法的研究與改進(jìn)［J］.計(jì)算機(jī)仿真，2013，（4）：344－347.

［9］ 胡潔.細(xì)菌覓食優(yōu)化算法的改進(jìn)及應(yīng)用研究［D］.武漢：武漢理工大學(xué)，2012.

［10］ Haffner S，Monticelli A，Garcia A，etal.Branch and bound algorithm for transmission system expansion planning using a transportation model［J］.IEE Proceedings－Generation，Transmission and Distribu－tion，2000，147（3）：149－156.