基于遺傳算法的隨機機組組合問題求解

熊高峰， 聶坤凱， 劉喜蘋， 蔡振華， 謝上華

(1.湖南大學電氣與信息工程學院， 長沙 410082；2.長沙南方職業學院信息技術系， 長沙 410208)

基于遺傳算法的隨機機組組合問題求解

熊高峰1， 聶坤凱1， 劉喜蘋2， 蔡振華1， 謝上華1

(1.湖南大學電氣與信息工程學院， 長沙 410082；2.長沙南方職業學院信息技術系， 長沙 410208)

為考慮不確定性負荷對機組組合問題的影響，通過情景分析法引入一系列的情景對不確定性負荷進行建模，建立了隨機機組組合問題的數學模型。采用遺傳算法求解該優化問題，可自行滿足情景簇約束。通過改進初始種群產生方式和變異算子，引進局部搜索算子對遺傳算法進行改進，增強了算法的搜索能力。計算結果顯示了隨機機組組合問題的數學模型和改進遺傳算法求解方法的有效性。

情景分析； 負荷不確定性； 隨機機組組合問題； 遺傳算法

在電力系統中，傳統機組組合問題是指在滿足負荷等約束條件下合理安排機組的開/停機順序與出力以使系統發電成本最小。在市場環境下，它是發電商制定競標策略和電力交易中心編制發電交易計劃的重要基礎。因此機組組合問題一直是電力系統中的一個重點課題。到目前為止，已提出了從簡單的啟發式方法到基于復雜數學優化理論以及基于新型人工智能算法的多種最優求解算法。文獻[1～4]對這些求解算法進行了概括和總結。

盡管在實際中負荷是不可能精確預測的，但是在傳統機組組合問題的建模和求解中，負荷一般作為確定值事先給定，同時，為了應對機組故障和負荷的不確定性，引入了旋轉備用約束條件。然而，對于系統調度員來說，確定由開機機組所提供的旋轉備用大小是一個難題[5]。備用的選取方法一般有兩種[2]：一是以各時段負荷值的10%為備用；二是以所有機組中輸出功率上限的最大值為備用。當第二種方法所選擇機組的最大輸出功率在所有機組中占較大比重時，備用值也隨之取較大，與實際情況不相符。系統調度員必須在“高風險-低運行成本”和“低風險-高運行成本”之間進行折中和決策。因此，基于旋轉備用的方法沒能解決好機組組合問題中機組故障和負荷的不確定性問題。

近年來，隨著數學領域中隨機優化理論的不斷發展和計算機計算能力的飛速提高，考慮不確定性的隨機機組組合問題開始得到日益重視。文獻[6]于1996年首次采用在不確定條件下處理優化問題的隨機規劃法[7]來求解隨機機組組合問題，為該問題提供了一個嶄新的解決思路。該文通過一系列的情景來建模不確定負荷，然后建立了隨機機組組合問題的期望值數學模型，最后采用拉格朗日松弛類型的方法對該優化問題進行了分解和求解。隨后，國內外眾多學者針對隨機機組組合問題提出了眾多數學模型和求解方法，如兩階段隨機規劃數學模型[9]、機會約束規劃數學模型[10]、改進的拉格朗日松弛類型求解方法[11]以及基于列生成法的求解算法[12]等。文獻[13]對隨機機組組合問題的數學模型和求解算法進行了概述。

在求解建立在情景分析基礎上的隨機機組組合問題時，普遍采用拉格朗日松弛類型的求解方法，此類方法處理情景簇約束時較為復雜，而且由于對偶間隙的存在使得該方法難以求得全局最優解。本文采用改進遺傳算法求解建立在情景分析基礎上的隨機機組組合問題，該方法可以自行滿足情景簇約束。實例表明本文方法是可行的。

1 隨機機組組合問題的期望值數學模型

建立在情景分析基礎上、考慮負荷不確定性、并且使用最為普遍的隨機機組組合問題的數學模型是期望值數學模型，其優化目標是最小化在所有情景下的期望發電成本。

1.1 不確定性負荷的建模

假定系統調度周期為T個時刻(通常是以1 h為單位)。采用情景分析法建模不確定性負荷時，一般先假定各調度時刻t的總的電力負荷為一個定義在已知概率空間上、且服從有限離散分布的隨機變量dt(t=1，2，…，T)，則d=(d1，d2，…，dT)構成一個T維隨機向量，d的一個實現值d=(d1，d2，…，dT)稱之為情景；然后，采用適當的方法生成一個包含有S個情景ds(s=1，2，…，S)的集合，并確定集合中每個情景在未來的發生概率Ps，所有情景的概率之和為1。理論上沒有界定情景數量的依據，為考慮計算時間，通常會根據實際情況選擇S的大小。這些情景通常通過圖1所示的情景樹來描述。如果各調度時刻t的負荷均取最大值，則稱此情景為最大負荷情景。

在每一個調度時刻t，情景索引指標s的集合{1，2，…，S}可以被分割成稱之為情景簇的互不相交的子集。很顯然，每個情景在每個調度時刻只能屬于一個情景簇，并且，在調度時刻t的一個情景簇在其隨后的調度時刻里將被細分成更多較小的互不相交的情景簇。一般，用B(s，t)表示在調度時刻t情景s是其一個成員的情景簇。

B(s1，t)=B(s2，t)?B(s1，τ)=B(s2，τ)

τ=1，2，…，t-1

(1)

根據情景分析中的預測不可能性條件[12，14]，到調度時刻t為止為情景ds1所做的決策必須與到調度時刻t為止為情景ds2所做的決策相同。這是建立在情景分析基礎上的隨機機組組合問題的數學模型中必須滿足的情景簇約束條件。

圖1 情景樹

1.2 期望值數學模型

假定系統中有N臺發電機組，則隨機機組組合問題的期望值數學模型[6，12]為

(2)

滿足以下約束條件：

(3)

τ=t+1，…，min{t+Li-1，T}

(4)

i=1，…，N；t=2，…，T；s=1，…，S

τ=t+1，…，min{t+li-1，T}

i=1，…，N；t=2，…，T；s=1，…，S

(5)

i=1，…，N；t=1，…，T；s=1，…，S

(6)

i=1，…，N；t=1，…，T；s=1，…，S

(7)

i=1，…，N；t=1，…，T

?s1，s2∈{1，…，S}，s1≠s2

B(s1，t)=B(s2，t)

(8)

隨機期望值數學模型的目標函數是最小化在所有情景下運行成本與啟動成本之和的期望值。式(3)表示所有機組的出力之和必須滿足情景s下的電力負荷需求。注意，由于采用的是隨機數學模型，因此在約束條件中沒有必要考慮旋轉備用。式(4)和(5)分別為機組的最小開機和最小停機約束條件。式(7)為機組出力的上下限約束條件。式(8)為情景簇約束條件。

隨機期望值數學模型是一個包含有S個確定性機組組合問題的大型混合整數非線性規劃問題，難以求得其最優解。它是傳統機組組合問題數學模型的一個推廣。如果情景樹只有一個分枝，即只有一個情景，則其就是沒有考慮旋轉備用的傳統機組組合問題的數學模型。

(9)

2 基于遺傳算法的求解方法

(10)

這一現實情況的反映也促使了GA求解方法的采用。可以采用GA產生一定數量的候選解(調度表)，并根據期望發電成本的大小來衡量各候選解的優劣，再通過一定世代數的選擇、交叉和變異等遺傳操作最終得到最優解。當采用調度表構成GA中的個體時，可使情景簇約束條件自動得到滿足從而減少計算量。因此，本文采用一種改進遺傳算法來求解隨機機組組合問題。

2.1 編碼

采用二進制矩陣編碼，染色體由N行T列的二維整型數組構成，數組中第i行t列的元素為機組i在調度時刻t的開停機狀態變量的值。

2.2 種群初始化

由于建模不確定性負荷的情景數S一般較大，因此根據測試系統的規模，可以采用動態規劃法或者拉格朗日松弛法求解各情景下的確定性機組組合問題，得到S個滿足各機組最小開/停機時間約束的可行調度表，由其或者其中一部分構成GA的初始種群，以提高初始種群的質量。

2.3 適應度函數

評估個體的優劣的適應度函數為

(11)

式中，A是一個取決于測試系統規模的常數，用來防止適應值太小，其大小通常與測試系統在調度周期內的最大運行成本保持在同一個數量級或更大。由于在改進GA求解算法中采取了保證個體滿足機組最小開/停機時間約束的措施，所以Penalty用于懲罰個體在調度周期內不滿足負荷需求時的總缺供電量，懲罰系數為m$/(MW·h)。

2.4 遺傳操作

采用賭輪選擇法從父代中選擇兩個個體進行交叉和變異操作。

1)交叉操作

由于窗式交叉和在時間軸上的兩點交叉都容易使新生個體不滿足機組最小開/停機時間約束，因此采用圖2所示的機組間的兩點交叉操作。

圖2 交叉操作

2)變異操作

提出一種能夠使變異后的個體滿足機組最小開/停機時間約束的新多點變異操作，具體如下。

(1)以變異概率pm在個體中隨機選擇一臺機組i。

(12)

(3)將正負符號交替的整數序列解碼轉換成該機組在各調度時刻的運行狀態。

圖3給出一個變異示例，并假定發生變異的機組的最小開/停機時間和初始運行狀態分別為3 h/3 h和-3 h，調度周期為24 h。

圖3 變異算子

2.5 精英策略

為避免每一代的最優個體在進化過程中由于遺傳操作而遭到破壞，將其直接復制到下一代中。

2.6 局部搜索

提出一種局部搜索算法并將其應用于每一代的最優個體上，以提高求解質量，具體如下。

(1)在最優個體中依次選擇一臺機組，將其在調度周期內的運行狀態解碼成表示其連續開機和連續停機的正負符號交替的整數序列。

(2)從該序列中的首位整數開始，從左至右依次對各整數進行以下操作：

①在滿足該機組最小開/停機時間約束條件下，將該整數隨機增加或減少1 h，其余整數則在調整次數最小的原則下做相應調整，得到一個新的整數序列。

②將新整數序列解碼轉換成該機組在各調度時刻的運行狀態，并計算改變后個體的適應值。如果優于原最優個體，則將新整數序列取代原整數序列(即新最優個體取代原最優個體)，并在其上進行下一位整數的調整。否則，恢復該機組的原整數序列，并在其上進行下一位整數的調整。

(3)重復步驟(1)和(2)，直至所有機組都被選中一次。

圖4給出一個局部搜索示例，假定被選中調整的機組的最小開/停機時間和初始運行狀態同上。

2.7 終止條件

采用設定最大進化代數G和在給定進化代數g內最優解沒有改善作為終止條件。

圖4 局部搜索示例

3 實例計算

通過在一個N=10，T=24的測試系統上的實例計算來驗證文中隨機機組組合問題的數學模型與GA求解方法的有效性。測試系統中的機組參數和各調度時刻的負荷Dt詳見文獻[15]。

如果Dt為精確預測值、不存在誤差，則稱之為完備負荷信息。但是在現實中負荷是不可能精確預測的。而且，由于受到生產活動及生活習慣的影響，各時段負荷的波動大小不同，一般峰荷波動較大、谷荷波動較小，負荷波動較大時段的負荷預測精度相對較低，文獻[6]選擇4個階段負荷波動，生成16個情景。在仿真過程中，多次選擇不同的負荷波動時段進行計算。多次試驗表明，由于受實例數據本身特點的影響，在選擇其他時段作為驗證依據時無法得到理想的結果。因此，在建模不確定性負荷、并生成適當數量的情景時，如表1所示，假定在兩個峰荷及其附近的6個調度時刻的負荷均有兩個等發生概率的可能值，分別為0.9Dt和1.1Dt，其平均值為Dt，其中1.1Dt應對負荷高于Dt的情況，0.9Dt則應對負荷低于Dt的情況。其余調度時刻的負荷為精確預測值，由此產生64個情景。

表1 負荷波動與情景

在GA求解算法中，令P=64，與情景數相同，Pc= 0.5，Pm=0.1，G=500，g=100；不滿足負荷需求時，施加的懲罰系數為50 000$/(MW·h)。適應度函數中的常數A=107。由動態規劃法求解S個情景下的確定性機組組合問題，產生GA算法中的初始種群。由于GA是一種隨機探索求解的優化方法，不能保證每次求解都能得到相同的最優解，因此在求解SUC問題時執行10次GA求解運算并從中得到最優解。表2給出求得的最優調度表。

表2 SUC問題的最優調度表

作為比較，表3～表5分別給出由動態規劃法求得的最大負荷情景、完備負荷信息以及考慮10%的旋轉轉備用下確定性機組組合問題的最優調度表。表6給出各最優調度表在各自負荷情景下的發電成本和在64個負荷情景下的期望發電成本。

表3 最大負荷情景下確定性UC問題的最優調度表

表4 完備負荷信息下確定性UC問題的最優調度表

表5 考慮旋轉備用時確定性UC問題的最優調度表

表6 發電成本比較

由計算結果可知，SUC問題的最優解與最大負荷情景下以及考慮旋轉備用下的最優解相比，其在64個情景下的平均發電成本分別節省143$和5 024$。同時，由表2中的開機機組所提供的旋轉備用小于該時段負荷的10%的時段總計有10個，并集中在負荷波動相對較小、預測精度相對較高的谷兼顧運行行安全性和經濟性。另一方面，完備負荷信息下的最優發電成本比SUC問題的最優解在64個情景下的平均發電成本節省10 423$。這是信息精確所帶來的利益，也說明加強負荷預測研究、提高預測精度是一項意義重大的工作。

4 結語

采用情景分析法對不確定性負荷進行了建模，建立了考慮負荷不確定性的隨機機組組合問題的數學模型。在采用遺傳算法求解該最優化問題中，改進了初始種群的產生方法，提出了改進的多點變異操作和局部搜索方法。比較了SUC問題的最優解與完備負荷信息、最大負荷情景以及考慮旋轉備用下的最優解。實例計算結果顯示SUC問題的數學模型和基于改進遺傳算法求解方法的有效性。SUC問題的最優解能夠兼顧運行的安全性和經濟性。

[1] Sheble G B, Fahd G N. Unit commitment literature synopsis[J]. IEEE Trans on Power Systems, 1994, 9(1): 128-135.

[2] Wood A J, Wollenberg B F.Power Generation, Operation and Control(2nd edition) [M]. New York: John Wiley amp; Sons, 1996.

[3] 陳皓勇, 王錫凡(Chen Haoyong, Wang Xifan). 機組組合問題的優化方法綜述(A survey of optimization-based methods for unit commitment)[J]. 電力系統自動化(Automation of Electric Power Systems), 1999, 23(5): 51-56.

[4] Padhy N P. Unit commitment-a bibliographical survey[J]. IEEE Trans on Power Systems, 2004, 19(2): 1196-1205.

[5] Merlin A, Sandrin P.New method for unit commitment at Electricite De France[J]. IEEE Trans on Power Apparatus and Systems, 1983, 102(5): 1218-1225.

[6] Takriti S, Birge J R, Long E. Stochastic model for the unit commitment problem[J]. IEEE Trans on Power Systems, 1996, 11(3): 1497-1508.

[7] Birge J R, Louveaux F. Introduction to Stochastic Programming[M]. New York: Springer-Verlag, 1997.

[8] Carpentier P, Cohen G, Culiolo J-C,etal．Stochastic optimization of unit commitment: a new decomposition framework[J]. IEEE Trans on Power Systems, 1996, 11(2): 1067-1073.

[9] Dentcheva D, Romisch W. Optimal Power Generation under Uncertainty via Stochastic Programming: Numerical Techniques and Engineering Applications [M]. Berlin: Springer-Verlag, 1998.

[10]Ozturk U A, Mazumdar M, Norman B A. A solution to the stochastic unit commitment problem using chance constrained programming[J]. IEEE Trans on Power Systems, 2004, 19(3): 1589-1598.

[11]Takriti S, Birge J R. Using integer programming to refine Lagrangian-based unit commitment solutions[J]. IEEE Trans on Power Systems, 2000, 15(1): 151-156.

[12]Shiina T, Birge J R. Stochastic unit commitment problem[J]. International Transactions in Operational Research, 2002, 1252(11): 117-123.

[13]肖昌育，萬仲平，李繼生，等(Xiao Changyu, Wan Zhongping, Li Jisheng,etal).機組組合隨機模型及其算法簡介(The brief introduction of the stochastic unit commitment models and algorithm)[J]. 華中電力(Central China Electric Power), 2005, 18(5): 5-8,12.

[14]Rockafellar R T, Wets Roger J-B. Scenarios and policy aggregation in optimization under uncertainty[J]. Mathematics of Operations Research, 1991, 16(1): 119-147.

[15]Kazarlis S A, Bakirtzis A G, Petridis V. Genetic algorithm solution to the unit commitment problem[J]. IEEE Trans on Power Systems, 1996, 11(1): 83-92.

[16]Valenzuela J， Smith A E. A seeded memetic algorithm for large unit commitment problems[J]. Journal of Heuristics, 2002, 8(2): 173-195.

[17]范宏，韋化(Fan Hong, Wei Hua). 改進遺傳算法及其在機組優化組合中的應用(Improved genetic algorithm and its application in unit commitment optimization)[J].電力系統及其自動化學報(Proceeding of the CSU-EPSA), 2004, 16(4): 46-49,63.

熊高峰(1969-)，男，博士，副教授，研究方向為電力系統運行與控制、電力市場。Email:jiaquanx@yahoo.com.cn

聶坤凱(1986-)，男，碩士研究生，研究方向為電力系統經濟調度。Email:niekunkai@163.com

劉喜蘋(1978-)，女，碩士，講師，研究方向為數據挖掘、人工智能及其應用。Email:liuviviem808@yahoo.com.cn

GA-basedSolutiontoStochasticUnitCommitmentProblem

XIONG Gao-feng1， NIE Kun-kai1， LIU Xi-ping2， CAI Zhen-hua1， XIE Shang-hua1

(1.College of Electrical and Information Engineering, Hunan University,Changsha 410082， China；2.Department of Information Technology, Changsha Nanfang Vocational College,Changsha 410208， China)

In order to consider the effects of uncertain electric power demand on unit commitment, the uncertainty of electric power demand is modeled by using a set of scenarios, which are introduced by scenario analysis. A mathematical formulation of the expected value model of the stochastic unit commitment (SUC) problem is established. This optimization problem is solved by using a genetic algorithm (GA), which can automatically satisfy the bundle constraints. The performance of the algorithm is improved by introducing a new method to generate the initial population, a new mutation operator, and a local search operator. Based on numerical examples, test results show the feasibility of the mathematical model of the SUC problem and its improved GA-based solution method.

scenario analysis； uncertainty of electric power demand； stochastic unit commitment； genetic algorithm(GA)

TM73

A

1003-8930(2012)05-0093-07

2011-02-16；

2011-04-07