機組組合問題用遺傳算法求解課件

AGeneticAlgorithmSolutionToTheUnitCommitmentProblem

(用遺傳算法求解機組組合問題)概要遺傳算法是一種模擬生物進(jìn)化中自然選擇、基因重組、適者生存思想的算法。本文用遺傳算法來解決機組組合問題，雖然多數(shù)情況下找不到最優(yōu)解，但能得到的滿意結(jié)果。并將遺傳算法所得的結(jié)果與拉格朗日松弛法、動態(tài)規(guī)劃所得的結(jié)果進(jìn)行了對比。用遺傳算法求解

機組組合問題機組組合問題及求解方法簡介遺傳算法簡介遺傳算法求解機組組合問題

3.1基本方法

3.2改進(jìn)措施13.3改進(jìn)措施23.4改進(jìn)措施3模擬結(jié)果結(jié)論討論1.機組組合問題及求解方法簡介機組組合問題由于當(dāng)前的科學(xué)技術(shù)還不能有效地存儲電力，所以電力生產(chǎn)和消費在任何時刻都要相等，否則就會威脅電力系統(tǒng)安全運行。又由于發(fā)電機組的物理特性限制，（系統(tǒng)備用約束、發(fā)電機組出力范圍約束、最小啟停機時間等等）發(fā)電機組不能夠隨心所欲地發(fā)出需要的電力。為了能夠?qū)崟r平衡變化劇烈的電力負(fù)荷，需要根據(jù)預(yù)測的未來電力負(fù)荷安排發(fā)電機組起停計劃，在滿足電力系統(tǒng)安全運行條件下，追求發(fā)電成本最小。下面是機組組合問題的一個數(shù)學(xué)模型。1.機組組合問題及求解方法簡介該模型要解決的是一個混合整數(shù)規(guī)劃問題定義一個向量變量xit,其分量為發(fā)電機i在t時段的所有連續(xù)變量,。例如,xit

=[pit,rit]T,pit

表示發(fā)電機i在t時段的有功;rit

表示該發(fā)電機提供的備用。定義一個標(biāo)量(或向量)變量zit

來表示發(fā)電機i在t時段的所有離散變量。把所有的xit

和zit

寫成矩陣X和Z。是各機組各時段燃料費用的總和;是各機組各時段燃料費用的總和;是各機組的開停機費用之和。1.機組組合問題及求解方法簡介機組組合問題

可見機組組合問題是一個高維數(shù)，非凸、離散、非線性的問題，找出其最優(yōu)解是很困難的。對于機組組合問題，國內(nèi)外電力科研工作者一直積極研究，提出各種方法來解決這個問題。本文回顧了優(yōu)先級表法、動態(tài)規(guī)劃法、拉格朗日松弛法。P(X)是系統(tǒng)的負(fù)荷和備用約束;R(X,Z)表示機組爬坡速率限制、燃料總量限制等;M(X,Z)是耦合離散變量zit

和連續(xù)變量xit

的約束;U(Z)是機組最短開停機時間限制。1.機組組合問題及求解方法簡介優(yōu)先級表法

優(yōu)先級表法的基本原理是按機組實際運行統(tǒng)計其運行的平均費用，按此順序進(jìn)行排隊，隨著系統(tǒng)負(fù)荷升降而啟停機組，這樣使平均運行費用低的機組在周期內(nèi)多發(fā)電，期望系統(tǒng)總的運行費用降至最低。優(yōu)先級表法簡單而實用，計算速度快，占用內(nèi)存少，但常常找不到最優(yōu)解，但能滿足一般的應(yīng)用要求。其在機組的經(jīng)濟調(diào)度中獲得了廣泛的應(yīng)用。1.機組組合問題及求解方法簡介動態(tài)規(guī)劃法用動態(tài)規(guī)劃法求解機組組合問題時,整個調(diào)度期間T被分成若干個時段，通常每個時段為1h，每個時段即動態(tài)規(guī)劃過程中的一個階段。各階段的狀態(tài)即為該時段所有可能的機組開停狀態(tài)組合。從初始階段開始，從前向后計算到達(dá)各階段各狀態(tài)的累計費用(包括開停機費用和運行時的燃料費)，再從最后階段累計費用最小的狀態(tài)開始，由后向前回溯，依次記錄各階段使總的累計費用最小的狀態(tài)，這樣就可得到最優(yōu)的開停機方案，對于N臺機組的系統(tǒng)，若要考慮T個時段的機組組合問題，則總的狀態(tài)數(shù)為2N×T，當(dāng)N和T增大時，計算量將急劇增加，形成所謂“維數(shù)災(zāi)”。為克服這個困難，常采取一定的措施來限制狀態(tài)的數(shù)目。1.機組組合問題及求解方法簡介拉格朗日松弛法

拉格朗日松弛法在機組組合問題中應(yīng)用時,把所有的約束分成兩類,一類是全系統(tǒng)的約束,一類是可以按單臺機組分解的約束,系統(tǒng)約束可以寫成懲罰項的形式,加入目標(biāo)函數(shù),形成拉格朗日函數(shù),拉格朗日函數(shù)可按單臺機組分解成一系列的子問題。優(yōu)點:隨著機組數(shù)的增加,計算量近似線性增長,克服了維數(shù)障礙,且機組數(shù)目越多,算法效果越好；缺點:由于目標(biāo)函數(shù)的非凸性，用對偶法求解時,存在對偶間隙,需要根據(jù)對偶問題的優(yōu)化解采取一定的措施構(gòu)造原問題的優(yōu)化可行解。2.遺傳算法簡介設(shè)現(xiàn)在有這么個問題需要解決。求f(x)=x2在0～31之間取整數(shù)值時函數(shù)的最大值。準(zhǔn)備：對定義域[0，31]內(nèi)的非負(fù)整數(shù)x進(jìn)行二進(jìn)制編碼，如x=8時取x=01000，隨機生成4個二進(jìn)制數(shù):01101(13)、11000(24)、01000(8)、10011(19);這4個數(shù)被稱為一個種群，種群中的每個數(shù)就是一個個體。交叉：將原有種群中的兩個個體隨機匹配，進(jìn)行交叉繁殖。比如選取01000(8)與10011(19)；將第3位進(jìn)行交換,得01011(11)與10000(16)。2.遺傳算法簡介變異：以很小的概率隨機地改變一個個體中的位值。比如若10011(19)被選中，將其第4位由1變?yōu)?。變異的概率很小一般只有千分之幾，其目的是為了防止丟失一些有用的因子。選擇：按個體的適應(yīng)度進(jìn)行復(fù)制，這里定義個體所定義的函數(shù)值為適應(yīng)度，比如01101(13)的適應(yīng)度為169。則每個個體在下一代中的數(shù)量為：2.遺傳算法簡介

mj(t)——為第j個個體在t代中的數(shù)量;mj(t+1)——為第j個個體在t+1代中的數(shù)量;

fj——為第j個個體在t代中的適應(yīng)度。2.遺傳算法簡介這樣經(jīng)過交叉、變異、選擇后，“適者生存，不適者淘汰”經(jīng)每迭代（進(jìn)化）一次，種群的適應(yīng)度會有所提高，只要迭代多次，最終會走向全局最優(yōu)解?？梢?，遺傳算法中，每一步的操作是非常簡單的，而且對問題的依賴性很小，并不要求目標(biāo)函數(shù)有連續(xù)光滑或要求目標(biāo)函數(shù)的導(dǎo)數(shù)等。3.遺傳算法求解機組組合問題3.1基本方法考慮問題，“有N臺機組在在H小時內(nèi)運行，要求制訂一個開停機的計劃，使得機組運行的總費用最小?！奔俣啃r內(nèi)，發(fā)電機不是開啟就是關(guān)閉，開啟狀態(tài)用“1”表示，關(guān)閉狀態(tài)用“0”表示。如圖1所示:3.遺傳算法求解機組組合問題3.1基本解決方法3.遺傳算法求解機組組合問題3.1基本方法用遺傳算法的思想來解決問題。設(shè)N=20，H=24則每個個體的位數(shù)為20×24=480，搜索空間內(nèi)的元素個數(shù)為2480=3.12×10144。隨機選取一個種群，種群中的個體為480位二進(jìn)制編碼。適應(yīng)度F定義如下：3.遺傳算法求解機組組合問題3.1基本方法(1)(1)(2)且FCT：燃料的總費用SUT：機組啟動的總費用SDT：機組關(guān)閉的總費用NC：違反約束的數(shù)量VIOLj：違反約束的數(shù)量值PFj

：違反約束的罰項μj

：罰因子(1)(2)(1)(2)(1)且(2)(1)3.遺傳算法求解機組組合問題3.1基本方法交叉（Crossover）3.遺傳算法求解機組組合問題3.1基本方法變異（Mutation）3.遺傳算法求解機組組合問題3.1基本方法選擇（Selection）圖3.1選擇操作的輪盤賭轉(zhuǎn)盤49.2%30.9%3.遺傳算法求解機組組合問題3.1基本方法積木塊假設(shè)（Duilding-blockingHypothesis）積木塊假設(shè)遺傳算法中，分別具有高適應(yīng)值、短定義矩或低階的模式（積木塊）在遺傳算子的作用下相互結(jié)合，形式同時具有高適應(yīng)值、短定義矩和低階的更優(yōu)秀的模式，最終接近全局最優(yōu)解。3.遺傳算法求解機組組合問題3.1基本方法可能出現(xiàn)的問題及檢測

用遺傳算法解決問題時，可能出現(xiàn)過早收斂和分散過廣的情況?？捎媒徊媛剩╟rossoverprobability）和變異率（mutationprobability）來檢測。如下表如示3.遺傳算法求解機組組合問題3.1基本方法可能出現(xiàn)的問題及檢測

交叉率變異率

正常情況0.4~0.90.004~0.024過早收斂≤0.10.004(每代)分散過廣

0.1(每代)≤0.004狀態(tài)項目3.遺傳算法求解機組組合問題3.1基本方法實例啟動費用熱啟動費用若關(guān)機時間≤冷啟動間隔冷啟動費用其它熱啟動費用若關(guān)機時間≤冷啟動間隔冷啟動費用其它熱啟動費用若關(guān)機時間≤冷啟動間隔冷啟動費用其它啟動費用熱啟動費用若關(guān)機時間≤冷啟動間隔冷啟動費用其它3.遺傳算法求解機組組合問題3.1基本方法選取50個個體組成一個種群，進(jìn)化500代；用20個種群并行計算，結(jié)果如下：3.遺傳算法求解機組組合問題3.1基本方法3.遺傳算法求解機組組合問題3.2改進(jìn)措施1窗交換（Swap-windowOperator）——0.3窗變異（Window-mutationOperator）——0.33.遺傳算法求解機組組合問題加入這兩個操作結(jié)果如下：3.遺傳算法求解機組組合問題3.3改進(jìn)措施2交換變異（Swap-mutationOperator）窗交換爬坡（Swap-windowHill-climbOperator）—0.3僅用于適應(yīng)度最好的個體。交換變異：選定兩個個體，再選定一個H時間，交換該位。將交換后的結(jié)果與交換前的結(jié)果進(jìn)行比較?；蜻x定一個個體，再選定一個H時間，改變該位。將改變后的結(jié)果與交換前的結(jié)果進(jìn)行比較。窗交換爬坡：按小時逐次進(jìn)行窗交換，比較。如下圖：3.遺傳算法求解機組組合問題3.3改進(jìn)措施23.遺傳算法求解機組組合問題執(zhí)行結(jié)果：3.遺傳算法求解機組組合問題3.4改進(jìn)措施3改變罰因子：——約束j的最終罰因子——世代數(shù)——總的世代數(shù)3.遺傳算法求解機組組合問題3.4改進(jìn)措施3執(zhí)行結(jié)果4.模擬結(jié)果在10、20、40、60、80、100臺機組上進(jìn)行模擬，時間為24小時。下圖是10臺機組的相關(guān)數(shù)據(jù).4.模擬結(jié)果4.模擬結(jié)果4.模擬結(jié)果模擬20臺機組的問題時，將前面的10臺機組翻倍，用電的需求量也翻倍。備用電量取需求量的10%。其余情況依此類推。下面對10臺機組進(jìn)行模擬運算，選取20個種群，每個種群包含50個個體，世代選為500。將運算結(jié)果與動態(tài)規(guī)劃法、拉格朗日松弛法進(jìn)行對比。如下表：4.模擬結(jié)果遺傳算法動態(tài)規(guī)劃拉格朗日4.模擬結(jié)果為什么選50個個體？一般說來，當(dāng)個體數(shù)量增加時，收斂性變差；當(dāng)每個種群選取75或100個個體時，經(jīng)過運算測試，收斂性無明顯改善。另一方面，每次“進(jìn)化”時，CPU的計算時間也會隨個體數(shù)目線性增加。（CPU時間是基于此芯片得出HPApollo720workstation）4.37h2.79h4.37h2.79h4.37h2.79h4.模擬結(jié)果算法程序運行的時間與機組數(shù)量的關(guān)系如下圖。y=x25.結(jié)論遺傳算法的好處是它可以對基于時間和耦合的限制進(jìn)行建模。遺傳算法可以在多臺計算機上并行操行，用機器的數(shù)量來縮短計算時間。遺傳算法的缺點是無法保證能找到最優(yōu)解，且運算時間較長。6.討論問題1：交叉產(chǎn)生的下一代個體中，存在違反約束的個體（爬坡限制、最小開機時間、最小關(guān)機時間等），是否可以在選擇過程中用啟發(fā)式算法濾去這些違反約束的個體？

啟發(fā)式算法的定義：一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計。啟發(fā)式算法常能發(fā)現(xiàn)很不錯的解，但也沒辦法證明它不會得到較壞的解；