機(jī)組組合問(wèn)題用遺傳算法求解課件

AGeneticAlgorithmSolutionToTheUnitCommitmentProblem

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

機(jī)組組合問(wèn)題機(jī)組組合問(wèn)題及求解方法簡(jiǎn)介遺傳算法簡(jiǎn)介遺傳算法求解機(jī)組組合問(wèn)題

3.1基本方法

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

=[pit,rit]T,pit

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

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

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

和zit

寫成矩陣X和Z。是各機(jī)組各時(shí)段燃料費(fèi)用的總和;是各機(jī)組各時(shí)段燃料費(fèi)用的總和;是各機(jī)組的開(kāi)停機(jī)費(fèi)用之和。1.機(jī)組組合問(wèn)題及求解方法簡(jiǎn)介機(jī)組組合問(wèn)題

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

和連續(xù)變量xit

的約束;U(Z)是機(jī)組最短開(kāi)停機(jī)時(shí)間限制。1.機(jī)組組合問(wèn)題及求解方法簡(jiǎn)介優(yōu)先級(jí)表法

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

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

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

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

：違反約束的罰項(xiàng)μj

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

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

交叉率變異率

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

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

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