方必武，王 波，劉滌塵，羅金號，馬恒瑞，陳思遠

?

基于搜索+調(diào)整的兩階段螢火蟲算法求解機組組合問題

方必武，王 波，劉滌塵，羅金號，馬恒瑞，陳思遠

(武漢大學電氣工程學院，湖北 武漢 430072)

提出了一種新穎的基于搜索+調(diào)整的兩階段螢火蟲算法求解機組組合問題。算法將機組組合求解流程分解為具有離散變量和連續(xù)變量的兩個優(yōu)化問題，通過二進制編碼的螢火蟲算法求解含離散變量的機組啟停主問題，利用改進的實數(shù)編碼螢火蟲算法解決連續(xù)變量的負荷經(jīng)濟分配子問題，采用調(diào)整策略校核和修復約束，實現(xiàn)主子問題的交替迭代求解。算法通過啟發(fā)式的約束調(diào)整策略，以及兩種編碼方式實現(xiàn)了離散變量和連續(xù)變量的分解優(yōu)化，提高了機組組合問題求解的效率和精度。通過對6個不同規(guī)模算例的計算及與其他經(jīng)典算法的對比，驗證了所提算法的有效性和優(yōu)越性。

兩階段螢火蟲算法；機組組合；啟發(fā)式約束調(diào)整

0 引言

機組組合(Unit Commitment，UC)是電力系統(tǒng)一個經(jīng)典的問題，其目的是在某段調(diào)度周期內(nèi)和一定的約束條件下，合理安排機組的啟停狀態(tài)和機組出力，使總的發(fā)電費用最低。機組組合問題的求解是電力系統(tǒng)解決優(yōu)化潮流、經(jīng)濟調(diào)度進而實現(xiàn)自動發(fā)電控制、自動電壓控制的前提，對此問題的研究有很重要的實際意義，一直以來都是學術(shù)界和工業(yè)界研究的重點[1-2]。

機組組合是一個高維、非凸、非線性的混合整數(shù)規(guī)劃問題，在數(shù)學上是一個NP-hard問題。隨著系統(tǒng)規(guī)模的增大，在有限的時間內(nèi)獲得精確可行解是一大難題，至今沒有一個統(tǒng)一的高效解決方法。很多數(shù)學優(yōu)化方法均已應用到這一問題的求解，包括局部尋優(yōu)法[3]、優(yōu)先順序法[4]、動態(tài)規(guī)劃法[5]、混合整數(shù)規(guī)劃法[6]、拉格朗日松弛法[7]等解析類方法以及系統(tǒng)進化算法[8]、遺傳算法[9]、粒子群算法[10]、蟻群算法[11]、量子進化算法[12]等智能優(yōu)化類算法。局部尋優(yōu)法和優(yōu)先順序法計算速度快，所需內(nèi)存少，但往往找不到最優(yōu)解；動態(tài)規(guī)劃是一種被廣泛使用的機組組合算法，但隨著機組數(shù)量和調(diào)度時間的增加，容易引起“維數(shù)災”，難以考慮與時間有關(guān)的約束以及爬坡約束等；混合整數(shù)規(guī)劃直接用于實際問題中時效率低，必須把問題進行有效分解；拉格朗日松弛法在求解過程中對迭代中的振蕩、可行解的獲取、收斂條件等問題不能做到魯棒處理[13]。智能優(yōu)化類方法具有對目標函數(shù)性態(tài)沒有特殊要求，從理論上來說可以找到全局最優(yōu)解，可以得到多個可選方案，方法比較靈活，可以考慮多種約束，適合于并行處理等優(yōu)點，是近年來機組組合領(lǐng)域研究的熱點[14]。但是，智能優(yōu)化方法本質(zhì)上都屬于無約束優(yōu)化算法，如何處理約束將很大程度上影響算法效率，機組組合中離散的啟停約束處理顯得尤為重要，也是研究的重點。

針對上述問題，本文提出一種基于搜索+調(diào)整的兩階段螢火蟲算法求解機組組合問題。使用一種新穎的螢火蟲算法作為搜索引擎，將UC問題的求解流程分解為離散啟停優(yōu)化及連續(xù)的經(jīng)濟調(diào)度兩個子問題，使用離散螢火蟲算法求解離散主問題，改進實數(shù)螢火蟲算法求解經(jīng)濟調(diào)度子問題，二者交替迭代。主問題中提出啟發(fā)式策略處理離散啟停約束，子問題中使用罰函數(shù)處理爬坡等約束并且提出個體變異和參數(shù)自適應調(diào)整的改進策略，提高算法全局搜索能力和收斂速度，仿真驗證了算法的有效性。

1 機組組合模型

本文所考慮的機組組合模型，目標函數(shù)是發(fā)電費用和機組啟動費用最小，考慮系統(tǒng)平衡、旋轉(zhuǎn)備用、機組調(diào)節(jié)能力、機組爬坡、機組最小啟/停時間約束。

2 螢火蟲算法原理及其改進

螢火蟲算法(Firefly algorithm)是一種新的自然啟發(fā)式算法，其靈感來自螢火蟲的社會行為。螢火蟲是自然界中最特殊、迷人的生物之一。自然界中大約有2 000個種類，大多數(shù)螢火蟲能發(fā)出短暫、有節(jié)奏的熒光，大部分螢火蟲的熒光是吸引其他螢火蟲的信號機制。通過將螢火蟲熒光的部分特性進行理想化抽象，劍橋大學的Dr. Yang 發(fā)明了螢火蟲算法[15-16]。

基本螢火蟲算法如下。

1) 吸引度

在螢火蟲算法中，吸引度函數(shù)的主要形式可以是任意的單調(diào)遞減函數(shù)，通常為

(2)

2) 螢火蟲之間的距離

(3)

3) 螢火蟲移動

當螢火蟲被另一只更有吸引力(更亮)的螢火蟲吸引時，其將發(fā)生移動。

式中的第2部分由螢火蟲之間的吸引決定，第3部分引入了隨機參數(shù)，是0到1之間均勻分布的隨機數(shù)。

3 二進制+實數(shù)編碼螢火蟲算法求解UC問題

3.1 二進制編碼螢火蟲算法解機組組合問題

3.1.1編碼方法

在UC問題中，二進制數(shù)據(jù)“1”和“0”用來指示機組的轉(zhuǎn)態(tài)(開或停)。Dr. Yang提出的螢火蟲算法是實數(shù)編碼，因此為了處理二進制優(yōu)化問題需要做一些改進。本文提出的算法，相關(guān)的連續(xù)變量通過概率性變化的閾值控制轉(zhuǎn)換為1或0。在二進制螢火蟲算法中，和取值0或者1則兩者之差將在(-1, 1)之間變化。當值在-1到1之間變化時，則式(2)中的取值在0.367 9~ 2.718 3之間變化，進而依據(jù)式(4)將在-2.218 0到4.218 0之間變化。若由0和1表示機組的啟停狀態(tài)，需要固定一個閾值。如果大于閾值，則該個體更有可能選擇為“1”反之則選擇為“0”。閾值水平可以從0到1變化，為了增強二進制螢火蟲的表現(xiàn)，采用改進的閾值函數(shù)(圖1)tanh為

產(chǎn)生一個0到1之間的隨機數(shù)，用0或者1表示機組的狀態(tài)，當大于，機組狀態(tài)為1否則為0。

3.1.2約束調(diào)整策略

當隨機產(chǎn)生初始解或者螢火蟲進行了位置的更新后，螢火蟲可能不滿足約束，備用約束等。求解機組組合問題的難點就是系統(tǒng)備用和最小開停機時間約束條件的處理，一般的懲罰函數(shù)法雖概念簡單，實施方便，但在01離散問題中懲罰系數(shù)的確定卻非常困難，且當懲罰系數(shù)過大時可能導致懲罰函數(shù)值在可行域的邊界附近呈現(xiàn)病態(tài)[17]。本文采用如下啟發(fā)式策略進行約束修復：

1) 若旋轉(zhuǎn)備用約束不滿足，則處于關(guān)停狀態(tài)的經(jīng)濟性較好機組識別出來并依次啟動，直到備用約束滿足，其中機組的經(jīng)濟性優(yōu)先順序按照平均煤耗確定，平均煤耗按式(6)確定。

圖3修復開機時間約束示意圖

3.2 改進實數(shù)編碼螢火蟲算法實現(xiàn)負荷經(jīng)濟分配

一旦機組的最小啟/停時間約束得到滿足，則可以用改進的實數(shù)編碼螢火蟲算法求解機組當前開停狀態(tài)下的經(jīng)濟調(diào)度問題，約束使用罰函數(shù)處理。

3.2.1個體變異機制

(8)

(10)

(11)

(13)

3.2.2參數(shù)自適應調(diào)整

3.3 算法詳細步驟

至此，兩階段螢火蟲算法的具體步驟如下。

步驟3：實數(shù)矩陣映射為二進制編碼。利用式(6)的閾值判斷將步驟2中的實數(shù)矩陣映射為二進制編碼的初始解，一個二進制種群的結(jié)構(gòu)如圖4所示。

圖4種群初始化結(jié)構(gòu)示意圖

步驟4：按照3.1.2節(jié)的約束校核與修復策略對種群編碼進行調(diào)整，生成新的滿足備用和啟停約束的新種群。

步驟5：按照3.2節(jié)的改進連續(xù)編碼的螢火蟲算法進行當前機組組合的經(jīng)濟調(diào)度求解。

步驟6：計算適應度值。機組出力為步驟4中經(jīng)濟調(diào)度的結(jié)果。

步驟7：評價種群所有螢火蟲，計算兩兩之間的吸引度及距離。

步驟8：按照式(3)更新螢火蟲位置，=+1,轉(zhuǎn)3)。

步驟9：停機準則，達到設(shè)置的最大迭代次數(shù)。

算法整體流程如圖5所示。

圖5算法流程圖

4 算例分析

為驗證本文算法的有效性，分別針對10機、20機、40機、80機和100機算例系統(tǒng)進行求解，其中10機系統(tǒng)參數(shù)取自文獻[18]，其余算例數(shù)據(jù)為10機系統(tǒng)復制而來。

算法中，離散和連續(xù)螢火蟲的種群規(guī)模均為30，最大迭代次數(shù)1 000，初始吸引度取1，熒光吸收系數(shù)取0.2，隨機參數(shù)的初值取0.5。

仿真環(huán)境：CPU Intel(R)Core(TM) i3-2310M @2.10G Hz, windows 7 64位，Matab 8.1.0。

4.1 經(jīng)典10機系統(tǒng)仿真結(jié)果

首先，將本文算法與未進行改進的螢火蟲算法應用到10機系統(tǒng)，兩者的收斂曲線如圖6所示。標準螢火蟲算法得到最優(yōu)成本78 863.4 t標煤，迭代到234代才收斂，改進的螢火蟲算法得到最優(yōu)成本78 625.6 t標煤，迭代57代即收斂?？梢姳疚奶岢龅淖儺惒呗院妥赃m應參數(shù)調(diào)整的改進策略能夠加強算法的全局搜索能力和收斂速度。

圖6 10機系統(tǒng)的算法收斂曲線

同時應用拉格朗日松弛法[18]、系統(tǒng)進化算法[8]、啟發(fā)式粒子群[19]、遺傳算法[20]、標準粒子群、改進離散粒子群[21]、改進雙重粒子群[2]、蟻群粒子群混合[11]、自學習策略粒子群[22]等多種現(xiàn)有文獻中的算法進行求解，均進行30次獨立試驗，取最好結(jié)果如表1所示。

由表1可知，在現(xiàn)有的這些算法中，本文提出的兩階段螢火蟲算法找到的機組組合成本最低，表明了本文方法極好的搜索能力。同時，在時耗上僅次于改進的離散粒子群算法，表明本文方法在具有極強搜索能力的同時保證了算法的較小時耗。

表1 10機系統(tǒng)不同算法結(jié)果

4.2 多機系統(tǒng)仿真結(jié)果

將初始10機數(shù)據(jù)進行復制得到20、40、60、80、100機系統(tǒng)，分別應用本文算法進行機組組合求解。由表2可知，隨著系統(tǒng)規(guī)模的增大，煤耗和時耗均在增加，但從增長率來看，隨著機組規(guī)模的增加，煤耗增長略微大于機組增長倍數(shù)，但時耗增長小于機組增長倍數(shù)。表明，隨著機組規(guī)模的增加，尋優(yōu)空間增大，算法的搜索能力有一定的降低，但是算法收斂速度依然迅速，但總體來講時間的增長近似線性，如圖7所示，避免了維數(shù)災難引起的指數(shù)級增長，充分表明了算法的有效性。

圖7時耗與系統(tǒng)規(guī)模的關(guān)系示意圖

表2多機系統(tǒng)算法的表現(xiàn)

Table 2 Algorithm performance of multi-units systems

5 結(jié)論

針對機組組合問題，本文提出了一種基于搜索+調(diào)整的兩階段螢火蟲算法。用離散螢火蟲算法求解啟停問題，用改進的連續(xù)螢火蟲算法求解經(jīng)濟調(diào)度問題，二者交替迭代求解。迭代中，離散的啟停相關(guān)約束通過科學的啟發(fā)式調(diào)整規(guī)則進行調(diào)整，連續(xù)的爬坡等約束利用罰函數(shù)進行處理，保證了解的可行性，通過個體變異和參數(shù)自適應調(diào)整兩項改進提高了算法的收斂速度和全局搜索能力。在10~100機的6個算例中，驗證了本文算法的有效性和優(yōu)越性。

[1] 程世軍, 孟杰, 王曉暉, 等. 風電-儲能聯(lián)合日運行優(yōu)化調(diào)度模型[J]. 電網(wǎng)與清潔能源, 2014, 30(4): 68-72, 80.

CHENG Shijun, MENG Jie, WANG Xiaohui, et al. A joint daily operational optimization model for wind power and energy storage devices[J]. Power System and Clean Energy, 2014, 30(4): 68-72, 80.

[2] 李整, 譚文, 秦金磊. 一種用于機組組合問題的改進雙重粒子群算法[J]. 中國電機工程學報, 2012, 32(25): 189-195.

LI Zheng, TAN Wen, QIN Jinlei. An improved dual particle swarm optimization algorithm for unit commitment problem[J]. Proceedings of CSEE, 2012, 32(25): 189-195.

[3] HAPP H H, JOHNSON R C, WRIGHT W J. Large scale hydro-thermal unit commitment method and results[J]. IEEE Transactions on PAS, 1971, 90(3).

[4] FAN J Y, ZHANG L, MCDONALD J D. Enhanced techniques on sequential unit commitment with interchange transactions[J]. IEEE Transactions on PW RS,1996, 11(1).

[5] PARK J H, KIM S K, PARK G P, et al. Modified dynamic programming based unit commitment technique[C] // Power and Energy Society General Meeting, 2010 IEEE, 25-29 July, 2010: 1-7.

[6] 楊佳俊, 雷宇, 龍淼, 等. 考慮風電和負荷不確定性的機組組合研究[J]. 電力系統(tǒng)保護與控制, 2014, 42(3): 63-70.

YANG Jiajun, LEI Yu, LONG Miao, et al. Study of unit commitment considering the uncertainty of wind farm and load[J]. Power System Protection and Control, 2014, 42(3): 63-70.

[7] 葛曉琳, 張粒子. 考慮調(diào)峰約束的風水火隨機機組組合問題[J]. 電工技術(shù)學報, 2014, 29(10): 222-230.

GE Xiaolin, ZHANG Lizi. Wind-hydro-thermal stochasticunit commitment problem considering the peak regulation constraints[J]. Transactions of China Electrotechnical Society, 2014, 29(10): 222-230.

[8] 陳皓勇, 張靠社, 王錫凡. 電力系統(tǒng)機組組合問題的系統(tǒng)進化算法[J]. 中國電機工程學報, 1999, 19(12): 9-13.

CHEN Haoyong, ZHANG Kaoshe, WANG Xifan. Evolutionary optimization method of power system unit commitment problem[J]. Proceedings of the CSEE, 1999, 19(12): 9-13.

[9] 張杰, 劉曉明, 孫東磊, 等. 基于混合遺傳算法的電力系統(tǒng)源網(wǎng)協(xié)同調(diào)度[J]. 電網(wǎng)與清潔能源, 2015, 31(7): 20-25, 32.

ZHANG Jie, LIU Xiaoming, SUN Donglei, et al. Synergistic dispatch of power source and electric network in power system based on hybrid genetic algorithm[J]. Power System and Clean Energy, 2015, 31(7): 20-25, 32.

[10] 盧鵬銘, 溫步瀛, 江岳文. 基于多時間尺度協(xié)調(diào)機組組合的含風電系統(tǒng)旋轉(zhuǎn)備用優(yōu)化研究[J]. 電力系統(tǒng)保護與控制, 2015, 43(5): 94-100.

LU Pengming, WEN Buying, JIANG Yuewen. Study on optimization of spinning reserve in wind power integrated power system based on multiple timescale and unit commitment coordination[J]. Power System Protection and Control, 2015, 43(5): 94-100.

[11] 陳燁, 趙國波, 劉俊勇, 等. 用于機組組合優(yōu)化的蟻群粒子群混合算法[J]. 電網(wǎng)技術(shù), 2008, 32(6): 52-56.

CHEN Ye, ZHAO Guobo, LIU Junyong, et al. An ant colony optimization and particle swarm optimization hybrid algorithm for unit commitment based on operate coding[J]. Power System Technology, 2008, 32(6): 52-56.

[12] 吉鵬, 周建中, 張睿, 等. 改進量子進化混合優(yōu)化算法在溪洛渡電站機組組合中的應用研究[J]. 電力系統(tǒng)保護與控制, 2014, 42(4): 84-91.

JI Peng, ZHOU Jianzhong, ZHANG Rui, et al. Study of unit commitment in Xiluodu based on a hybrid optimization algorithm of improved quantum evolution algorithm[J]. Power System Protection and Control, 2014, 42(4): 84-91.

[13] 陳皓勇, 王錫凡. 機組組合問題的優(yōu)化方法綜述[J]. 電力系統(tǒng)自動化, 1999, 23(4): 51-56.

CHEN Haoyong, WANG Xifan. Unit commitment optimization methods[J]. Automation of Electric Power Systems, 1999, 23(4): 51-56.

[14] 陳皓勇, 王錫凡. 機組組合問題的優(yōu)化方法綜述[J]. 電力系統(tǒng)自動化, 1999, 23(5): 51-56.

CHEN Haoyong, WANG Xifan. Unit commitment optimization methods[J]. Automation of Electric Power Systems, 1999, 23(5): 51-56.

[15] YANG Xinshe. Nature-inspired mata heuristic algorithms[M]. UK: Lunvier Press, 2008.

[16] YANG X S. Firefly algorithm stochastic test functions and design optimization[J]. International Journal of Bio-Inspired Computation, 2010, 2(2): 78-84.

[17] 吳小珊, 張步涵, 袁小明, 等. 求解含風電場的電力系統(tǒng)機組組合問題的改進量子離散粒子群優(yōu)化方法[J]. 中國電機工程學報, 2013, 33(4): 45-52.

WU Xiaoshan, ZHANG Buhan, YUAN Xiaoming, et al. Solutions to unit commitment problems in power systems with wind farms using advanced quantum-inspired binary PSO[J]. Proceedings of the CSEE, 2013, 33(4): 45-52.

[18] 韓學山, 柳焯. 考慮發(fā)電機組輸出功率速度限制的最優(yōu)機組組合[J]. 電網(wǎng)技術(shù), 1994, 18(6): 11-16.

HAN Xueshan, LIU Zhuo. Optimal unit commitment consider unit’s ramp rate limits[J]. Power System Technology, 1994, 18(6): 11-16.

[19] 胡家聲, 郭創(chuàng)新, 曹一家. 一種適合于電力系統(tǒng)機組組合問題的混合粒子群優(yōu)化算法[J]. 中國電機工程學報, 2004, 24(4): 28-32.

HU Jiasheng, GUO Chuangxin, CAO Yijia. A hybrid particle swarm optimization method for unit commitment problem[J]. Proceedings of the CSEE, 2004, 24(4): 28-32.

[20] 蔡超豪, 蔡元宇. 機組優(yōu)化組合的遺傳算法[J]. 電網(wǎng)技術(shù), 1997, 21(1): 44-47, 51.

CAI Chaohao, CAI Yuanyu. Optimization of unit commitment by genetic algorithm[J]. Power System Technology, 1997, 21(1): 44-47, 51.

[21] 婁素華, 余欣梅, 熊信艮, 等. 電力系統(tǒng)機組啟停優(yōu)化問題的改進 DPSO 算法[J]. 中國電機工程學報, 2005, 25(8): 30-35.

LOU Suhua, YU Xinmei, XIONG Xinyin, et al. Unit commitment using improved discrete particle swarm optimization algorithm[J]. Proceedings of the CSEE, 2005, 25(8): 30-35.

[22] 陳海良, 郭瑞鵬. 基于改進離散粒子群算法的電力系統(tǒng)機組組合問題[J]. 電網(wǎng)技術(shù), 2011, 35(12): 94-99.

CHEN Hailiang, GUO Ruipeng. Unit commitment based on improved discrete particle swarm optimization[J]. Power System Technology, 2011, 35(12): 94-99.

(編輯 葛艷娜)

A two-stage firefly algorithm based on search + adjustment for solving unit commitment problem

FANG Biwu, WANG Bo, LIU Dichen, LUO Jinhao, MA Hengrui, CHEN Siyuan

(School of Electrical Engineering, Wuhan University, Wuhan 430072, China)

This paper proposes a novel two-stage firefly algorithm based on search + adjustment for solving unit commitment problem. The solving process of UC will be broken down into two optimization problems with discrete and continuous variables respectively. The main discrete problem to determine the off/on status is solved by binary encoding firefly algorithm, the continuous sub-problem of economic load variables assignment is solved by improved real-coded firefly algorithm, and check and repair constraints are used to achieve alternative and iterative calculation. Heuristic constraints adjustment, as well as two-stage coding approach is used to achieve the decompose optimization of discrete and continuous variables, and improve the efficiency and accuracy of the algorithm. The algorithm proposed is applied to six different systems and compared with classical algorithms, the results verify the effectiveness and superiority.

This work is supported by National Natural Science Foundation of China (No. 51477121).

two-stage firefly algorithm; unit commitment; heuristic constraint adjustment

10.7667/PSPC152128

2015-12-07；

2016-01-13

方必武(1991-)，男，碩士研究生，研究方向電力系統(tǒng)經(jīng)濟調(diào)度與負荷調(diào)度；E-mail: bwfwhu@163.com

王 波(1978-)，男，博士，副教授，研究方向為源荷協(xié)調(diào)及智慧能源。

國家自然科學基金面上項目(51477121)；國家科技支撐計劃項目(2015BAA01B01)