基于自適應(yīng)量子遺傳算法的電力系統(tǒng)機(jī)組組合問題

于艾清，劉 滔

(上海電力學(xué)院 電氣工程學(xué)院，上海 200090)

節(jié)能減排發(fā)電調(diào)度[1]要求在電力系統(tǒng)安全穩(wěn)定運(yùn)行和連續(xù)供電的前提下，最大限度地減少能源和資源的消耗，以及污染物的排放.其中，機(jī)組組合優(yōu)化是編制短期發(fā)電計(jì)劃首先要解決的問題，是整個(gè)發(fā)電計(jì)劃的基礎(chǔ).火電機(jī)組組合調(diào)度問題(Unit Commitment Problem，UCP)是指在滿足大量運(yùn)行約束下在某一特定時(shí)間內(nèi)安排機(jī)組運(yùn)行狀態(tài)來滿足預(yù)測(cè)的負(fù)荷需求，使其達(dá)到某些目標(biāo).[2]

由于UCP的非確定多項(xiàng)式(NP)的難特性及其經(jīng)濟(jì)重要性，一直以來都是電力生產(chǎn)企業(yè)的重點(diǎn)關(guān)注問題.傳統(tǒng)的確定性算法有優(yōu)先權(quán)(PL)方法、動(dòng)態(tài)規(guī)劃(DP)、混合整數(shù)規(guī)劃、分支定界算法和拉格朗日松弛法，利用這些方法在求解過程中或多或少都存在一些缺點(diǎn)，得不到十分理想的結(jié)果.[3]

現(xiàn)代的智能優(yōu)化方法如遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、粒子群算法、蟻群算法和量子進(jìn)化算法[4-9]等，為解決 UCP問題提供了較好的方法，因此得到了廣泛應(yīng)用.其中，量子遺傳算法(Quantum Genetic Algorthm，QGA)結(jié)合了量子計(jì)算和遺傳算法的優(yōu)點(diǎn)，得到了較多學(xué)者的關(guān)注和研究.

但這些文獻(xiàn)有很多相似之處，一是采用二進(jìn)制編碼方式，用0-1表示發(fā)電機(jī)組的運(yùn)行狀態(tài)，將所有機(jī)組的運(yùn)行狀態(tài)編碼串接起來作為種群中的一個(gè)個(gè)體，編碼規(guī)模大，影響算法效率;二是量子旋轉(zhuǎn)角根據(jù)表格查詢，根據(jù)問題不同有所區(qū)別，沒有規(guī)則可循.

本文研究的火力發(fā)電機(jī)組組合問題以最小標(biāo)準(zhǔn)煤耗為優(yōu)化目標(biāo)，考慮機(jī)組自身約束和基本系統(tǒng)約束，提出了自適應(yīng)量子遺傳算法(Adaptive Quantum Genetic Algorithm，AQGA)求解該模型.對(duì)個(gè)體進(jìn)行量子編碼，縮短編碼長度;采用量子旋轉(zhuǎn)門作為遺傳的進(jìn)化操作，定義了針對(duì)個(gè)體適應(yīng)值和進(jìn)化代數(shù)的自適應(yīng)量子旋轉(zhuǎn)角，使個(gè)體向更好的解靠近;采用改進(jìn)的隨機(jī)窗口變異操作.最后，在仿真實(shí)驗(yàn)中改變各參數(shù)，分析和總結(jié)了其對(duì)算法求解機(jī)組組合問題性能的影響，并驗(yàn)證了算法的有效性.

1 機(jī)組組合問題的數(shù)學(xué)模型

本文研究的機(jī)組組合優(yōu)化問題就是在一定的約束條件下求得目標(biāo)函數(shù)的極小值，這是一個(gè)有整數(shù)變量、連續(xù)變量及非線性函數(shù)的混合整數(shù)非線性規(guī)劃問題.

1.1 目標(biāo)函數(shù)

要求系統(tǒng)在T小時(shí)時(shí)段內(nèi)各機(jī)組的總發(fā)電成本為最小.總發(fā)電成本包括發(fā)電機(jī)組運(yùn)行耗能成本和啟動(dòng)耗能成本(煤耗成本).目標(biāo)函數(shù)可寫為:

式中:T——機(jī)組調(diào)度總周期，將其分為T個(gè)時(shí)段;

N——機(jī)組或等效機(jī)組臺(tái)數(shù);

U it——機(jī)組i在t時(shí)段運(yùn)行狀態(tài)變量，U it=0表示運(yùn)行;

Pit——機(jī)組i在t時(shí)段的功率變量，MW;

Fi(Pit)——機(jī)組i的運(yùn)行耗能，t/h;

Si——機(jī)組i的啟動(dòng)耗量，它與停機(jī)時(shí)間的長短有關(guān)，t/h.

式(1)中發(fā)電機(jī)組的燃料費(fèi)用采用二次函數(shù)形式表示為:

式中:a——發(fā)電機(jī)組i成本函數(shù)中二次項(xiàng)，t/WM2h;

b——發(fā)電機(jī)組i成本函數(shù)中一次項(xiàng)，t/MWh;

c——發(fā)電機(jī)組i成本函數(shù)中常數(shù)項(xiàng)系數(shù)，t/h.

1.2 約束條件

(1)功率平衡約束條件為:

式中:PDt——t時(shí)刻系統(tǒng)中的總負(fù)荷，MW.

式(3)表示任何時(shí)段電力負(fù)荷之和必須等于發(fā)電機(jī)發(fā)電出力之和.

(2)機(jī)組容量約束條件為:

式中:Pimin——機(jī)組i發(fā)電能力下限;

Pimax——機(jī)組i發(fā)電能力上限.

(3)機(jī)組啟停次數(shù)約束條件為:

式中:M——機(jī)組啟停的次數(shù)，機(jī)組不能頻繁的啟停.

(4)機(jī)組最小連續(xù)停運(yùn)和連續(xù)運(yùn)行小時(shí)數(shù)約束條件為:

式中:T1，T2——每臺(tái)機(jī)組的最小連續(xù)停運(yùn)和連續(xù)運(yùn)行小時(shí)數(shù).

2 求解UCP的自適應(yīng)量子遺傳算法

量子遺傳算法(QGA)是一種概率進(jìn)化算法，是量子計(jì)算與進(jìn)化計(jì)算理論相結(jié)合的新興交叉產(chǎn)物.它使用量子位編碼染色體這一概率幅值表示，可以使一個(gè)量子染色體同時(shí)表達(dá)多個(gè)狀態(tài)的信息，用量子門對(duì)疊加態(tài)的作用作為進(jìn)化操作，能很好地保持種群的多樣性，避免選擇壓力問題，使得種群以大概率向著優(yōu)良模式進(jìn)化，從而實(shí)現(xiàn)目標(biāo)的優(yōu)化求解.

2.1 UCP的量子編碼

本文提出了新的量子編碼方式，在編碼中考慮兩個(gè)約束，即機(jī)組啟停次數(shù)約束，機(jī)組最小連續(xù)停運(yùn)和連續(xù)運(yùn)行小時(shí)數(shù)約束.一個(gè)量子個(gè)體由N行5M+1列的矩陣構(gòu)成.矩陣中每一行代表一個(gè)機(jī)組在24 h內(nèi)的啟停狀態(tài).每一行的第一列為機(jī)組的初始狀態(tài)(0表示停止;1表示啟動(dòng))，后面每5列代表一個(gè)啟停位置的二進(jìn)制碼.矩陣中每一個(gè)二進(jìn)制碼都采用量子位表示:

由此可以看出，一個(gè)具有m個(gè)量子位的個(gè)體可以表示2m個(gè)狀態(tài).這樣，種群的多樣性得到了豐富，更加有利于算法在搜索空間中搜索.

2.2 種群初始化

本文在初始化過程中，即對(duì)生成的矩陣進(jìn)行約束處理.約束處理的先后順序?yàn)?機(jī)組啟停次數(shù);機(jī)組最小連續(xù)停運(yùn)和連續(xù)運(yùn)行小時(shí)數(shù);機(jī)組容量約束;功率平衡約束.

以某一臺(tái)機(jī)組的啟停位置生成為例，具體方法如圖1所示.

圖1 機(jī)組啟停位置編碼生成范例

2.3 自適應(yīng)量子旋轉(zhuǎn)操作

本文采用量子旋轉(zhuǎn)門作為AQGA的主要進(jìn)化操作，根據(jù)一般情況，量子門必須為可逆的酉矩陣.每個(gè)量子位都通過如下的量子旋轉(zhuǎn)門來更新:

更新后的量子位如下:

在量子旋轉(zhuǎn)中，旋轉(zhuǎn)角的選擇對(duì)算法尤為重要，其幅度選擇會(huì)影響算法的收斂速度，若幅度過大，會(huì)導(dǎo)致算法跨越的步長過大，從而會(huì)使算法陷入早熟;反之，又會(huì)使算法進(jìn)行大量的冗余計(jì)算，導(dǎo)致算法的收斂速度變慢.

針對(duì)本文的最小總成本的機(jī)組組合優(yōu)化模型，定義了自適應(yīng)旋轉(zhuǎn)角θi:

式中:θmin——最小旋轉(zhuǎn)角;

θmax——最大旋轉(zhuǎn)角;

fi——第i個(gè)體的適應(yīng)值;

fmin——最小適應(yīng)值;

fmax——最大適應(yīng)值;

G——當(dāng)前代數(shù);

Gmax——最大代數(shù).

式(12)表示個(gè)體較為優(yōu)秀時(shí)，對(duì)旋轉(zhuǎn)角進(jìn)行較小的調(diào)整;個(gè)體較差時(shí)，使用相對(duì)較大的旋轉(zhuǎn)角.在算法運(yùn)行初期，設(shè)置較大的角步長大范圍搜索最優(yōu)解，后期則采用較小的角步長局部搜索最優(yōu)解，從而在保證搜索效率的同時(shí)，兼顧了搜索精度.

2.4 變異操作

文獻(xiàn)[10]針對(duì)實(shí)數(shù)編碼的機(jī)組組合問題，提出了多窗口變異操作，但其窗口寬度w是一固定值，本文改進(jìn)其窗口變異操作，寬度w隨機(jī)確定.具體操作如下.

步驟1 將整數(shù)編碼轉(zhuǎn)換成二進(jìn)制編碼，并且根據(jù)二進(jìn)制編碼來確定機(jī)組出力矩陣，以此實(shí)數(shù)矩陣進(jìn)行變異操作，變異前個(gè)體為:

進(jìn)行變異操作個(gè)體中的任意行向量R表示為:

式中:C i，t——編碼矩陣中的第i行、第t列元素，表示發(fā)電機(jī)組i在時(shí)段t中的發(fā)電量大小.

變異后的個(gè)體為:

步驟2 生成隨機(jī)數(shù) α，α∈(0，1);確定窗口變異的起始位子j，滿足j+w-1≤T;確定變異前的行向量

步驟3 進(jìn)行窗口變異操作，生成變異個(gè)體O m.

具體方法如下:

2.5 算法流程

AQGA的算法流程如圖2所示.

圖2 AQGA算法流程

3 仿真算例分析

為驗(yàn)證本文中AQGA算法的有效性，采用文獻(xiàn)[11]中的機(jī)組組合模型進(jìn)行仿真研究.此次仿真在Intel Core-i5 3337U 1.8 GHz處理器4 G內(nèi)存的Aspire V5-472G上運(yùn)行，軟件環(huán)境為Matlab 7.6.0(R2008a).

算法中的參數(shù)確定規(guī)則為，在確定其他參數(shù)不變的情況下，只對(duì)其中一個(gè)參數(shù)進(jìn)行調(diào)整，并進(jìn)行10次運(yùn)算.綜合考慮所得10次運(yùn)算結(jié)果的平均值、最優(yōu)值及運(yùn)算時(shí)間，確定最優(yōu)參數(shù).經(jīng)過大量仿真，最優(yōu)算法參數(shù)設(shè)置為:進(jìn)化代數(shù)為1 000代;種群規(guī)模為100;量子進(jìn)化率為75%;變異率為2%;量子旋轉(zhuǎn)角范圍 θmin=0.05π，θmax=0.1π;機(jī)組啟停次數(shù)為2次時(shí)的仿真結(jié)果為最優(yōu).

仿真的最優(yōu)值結(jié)果進(jìn)化曲線與甘特圖見圖3.其中，圖3a的線的變化代表最優(yōu)值隨著進(jìn)化代數(shù)的變化趨勢(shì)，圖3b是機(jī)組啟停調(diào)度圖，圖中黑色框代表機(jī)組運(yùn)行，白色框代表停機(jī).

經(jīng)過10次運(yùn)算之后，最低耗費(fèi)值的最小值是79 036 t，其運(yùn)算時(shí)間是 26.482 9 s，10 次運(yùn)算的平均耗量為 79 133.5 t，平均計(jì)算時(shí)間 27.831 4 s.相比于文獻(xiàn)[11]所求得的運(yùn)行耗量(80 766 t)降低了1 730，表明該AQGA算法有很好的收斂性和有效性.最優(yōu)值各機(jī)組出力見表1.

圖3 最優(yōu)值結(jié)果進(jìn)化曲線與甘特圖

表1 最優(yōu)值各機(jī)組出力

4 結(jié)語

本文提出了一種使用量子編碼的自適應(yīng)量子遺傳算法來求解電力系統(tǒng)機(jī)組組合問題.提出的量子編碼，采用了二維量子矩陣代替?zhèn)鹘y(tǒng)的二進(jìn)制矩陣對(duì)發(fā)電安排進(jìn)行編碼，有效減小了矩陣規(guī)模，簡化了計(jì)算，提高了計(jì)算效率.采用量子旋轉(zhuǎn)門代替了傳統(tǒng)遺傳算法的交叉操作.提出的自適應(yīng)量子旋轉(zhuǎn)角，可根據(jù)問題自適應(yīng)變化旋轉(zhuǎn)角度.通過算例仿真分析，驗(yàn)證了該算法在求解機(jī)組組合問題時(shí)的有效性.

[1]中華人民共和國中央人民政府門戶網(wǎng)站.國務(wù)院辦公廳關(guān)于轉(zhuǎn)發(fā)發(fā)展改革委等部門節(jié)能發(fā)電調(diào)度辦法(試行)的通知(國辦發(fā)[2007]53 號(hào))[EB/OL].[2007-08-07].http:∥ www.gov.cn/zwgk/2007 - 08/07/content_708486.htm.

[2]王錫凡.機(jī)組組合問題的優(yōu)化方法綜述[J].電力系統(tǒng)自動(dòng)化，1999，23(4):51-56.

[3]PADHY N P.Unit commitment——a bibliographical survey[J].IEEE Trans on Power Systems，2004，19(2):1 196-1 205.

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

[5]GIL E，BUSTOS J，RUDNICK H.Short-term hydrothermal generation scheduling model using a genetic algorithm[J].IEEE Trans.on Power Systems，2003，18(4):1 256-1 264.

[6]趙波，曹一家.電力系統(tǒng)機(jī)組組合問題的改進(jìn)粒子群優(yōu)化算法[J].電網(wǎng)技術(shù)，2004，28(21):6-10.

[7]SISHAJ P Simon，PADHY Narayana Prasad，ANAND R S.An ant colony system approach for unit commitment problem[J].International Journal of Electrical Power ＆ Energy Systems，2006，28(5):315-323.

[8]LAU T W，CHUNG C Y，WONG K P，et al.Quantuminspired evolutionary algorithm approach for unit commitment[J].IEEE Transactions on Power Systems，2009，24(3):1 503-1 512.

[9]于艾清，顧幸生.一種求解同等并行機(jī)調(diào)度的混合量子衍生進(jìn)化算法[J].控制與決策，2011，26(10):1 473-1 478.

[10]孫力勇，張焰，蔣傳文.基于矩陣實(shí)數(shù)編碼遺傳算法求解大規(guī)模機(jī)組組合問題[J].中國電機(jī)工程學(xué)報(bào)，2006，1(2):82-87.

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