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

AGeneticAlgorithmSolutionToTheUnitCommitmentProblem

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

機組組合問題機組組合問題及求解方法簡介遺傳算法簡介遺傳算法求解機組組合問題3.1基本方法3.2改進措施13.3改進措施23.4改進措施3模擬結果結論討論用遺傳算法求解

機組組合問題機組組合問題及求解方法簡介31.機組組合問題及求解方法簡介機組組合問題由于當前的科學技術還不能有效地存儲電力，所以電力生產和消費在任何時刻都要相等，否則就會威脅電力系統(tǒng)安全運行。又由于發(fā)電機組的物理特性限制，（系統(tǒng)備用約束、發(fā)電機組出力范圍約束、最小啟停機時間等等）發(fā)電機組不能夠隨心所欲地發(fā)出需要的電力。為了能夠實時平衡變化劇烈的電力負荷，需要根據(jù)預測的未來電力負荷安排發(fā)電機組起停計劃，在滿足電力系統(tǒng)安全運行條件下，追求發(fā)電成本最小。下面是機組組合問題的一個數(shù)學模型。1.機組組合問題及求解方法簡介機組組合問題41.機組組合問題及求解方法簡介該模型要解決的是一個混合整數(shù)規(guī)劃問題定義一個向量變量xit,其分量為發(fā)電機i在t時段的所有連續(xù)變量,。例如,xit=[pit,rit]T,pit表示發(fā)電機i在t時段的有功;rit表示該發(fā)電機提供的備用。定義一個標量(或向量)變量zit來表示發(fā)電機i在t時段的所有離散變量。把所有的xit和zit寫成矩陣X和Z。是各機組各時段燃料費用的總和;是各機組各時段燃料費用的總和;是各機組的開停機費用之和。1.機組組合問題及求解方法簡介該模型要解決的是一個混合整數(shù)規(guī)51.機組組合問題及求解方法簡介機組組合問題

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

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

拉格朗日松弛法在機組組合問題中應用時,把所有的約束分成兩類,一類是全系統(tǒng)的約束,一類是可以按單臺機組分解的約束,系統(tǒng)約束可以寫成懲罰項的形式,加入目標函數(shù),形成拉格朗日函數(shù),拉格朗日函數(shù)可按單臺機組分解成一系列的子問題。優(yōu)點:隨著機組數(shù)的增加,計算量近似線性增長,克服了維數(shù)障礙,且機組數(shù)目越多,算法效果越好；缺點:由于目標函數(shù)的非凸性，用對偶法求解時,存在對偶間隙,需要根據(jù)對偶問題的優(yōu)化解采取一定的措施構造原問題的優(yōu)化可行解。1.機組組合問題及求解方法簡介拉格朗日松弛法92.遺傳算法簡介設現(xiàn)在有這么個問題需要解決。求f(x)=x2在0～31之間取整數(shù)值時函數(shù)的最大值。準備：對定義域[0，31]內的非負整數(shù)x進行二進制編碼，如x=8時取x=01000，隨機生成4個二進制數(shù):01101(13)、11000(24)、01000(8)、10011(19);這4個數(shù)被稱為一個種群，種群中的每個數(shù)就是一個個體。交叉：將原有種群中的兩個個體隨機匹配，進行交叉繁殖。比如選取01000(8)與10011(19)；將第3位進行交換,得01011(11)與10000(16)。2.遺傳算法簡介設現(xiàn)在有這么個問題需要解決。102.遺傳算法簡介變異：以很小的概率隨機地改變一個個體中的位值。比如若10011(19)被選中，將其第4位由1變?yōu)?。變異的概率很小一般只有千分之幾，其目的是為了防止丟失一些有用的因子。選擇：按個體的適應度進行復制，這里定義個體所定義的函數(shù)值為適應度，比如01101(13)的適應度為169。則每個個體在下一代中的數(shù)量為：2.遺傳算法簡介變異：以很小的概率隨機地改變一個個體中的位值112.遺傳算法簡介mj(t)——為第j個個體在t代中的數(shù)量;mj(t+1)——為第j個個體在t+1代中的數(shù)量;fj——為第j個個體在t代中的適應度。2.遺傳算法簡介mj(t)——為第j個個體在t代中的122.遺傳算法簡介這樣經過交叉、變異、選擇后，“適者生存，不適者淘汰”經每迭代（進化）一次，種群的適應度會有所提高，只要迭代多次，最終會走向全局最優(yōu)解?？梢姡z傳算法中，每一步的操作是非常簡單的，而且對問題的依賴性很小，并不要求目標函數(shù)有連續(xù)光滑或要求目標函數(shù)的導數(shù)等。2.遺傳算法簡介這樣經過交叉、變異、選擇后，“適者生存，不適133.遺傳算法求解機組組合問題3.1基本方法考慮問題，“有N臺機組在在H小時內運行，要求制訂一個開停機的計劃，使得機組運行的總費用最小。”假定每小時內，發(fā)電機不是開啟就是關閉，開啟狀態(tài)用“1”表示，關閉狀態(tài)用“0”表示。如圖1所示:3.遺傳算法求解機組組合問題3.1基本方法143.遺傳算法求解機組組合問題3.1基本解決方法3.遺傳算法求解機組組合問題3.1基本解決方法153.遺傳算法求解機組組合問題3.1基本方法用遺傳算法的思想來解決問題。設N=20，H=24則每個個體的位數(shù)為20×24=480，搜索空間內的元素個數(shù)為2480=3.12×10144。隨機選取一個種群，種群中的個體為480位二進制編碼。適應度F定義如下：3.遺傳算法求解機組組合問題3.1基本方法163.遺傳算法求解機組組合問題3.1基本方法(1)(1)(2)且FCT：燃料的總費用SUT：機組啟動的總費用SDT：機組關閉的總費用NC：違反約束的數(shù)量VIOLj：違反約束的數(shù)量值PFj：違反約束的罰項μj：罰因子(1)(2)(1)(2)(1)且(2)(1)3.遺傳算法求解機組組合問題3.1基本方法(1)(1)(2)173.遺傳算法求解機組組合問題3.1基本方法交叉（Crossover）3.遺傳算法求解機組組合問題3.1基本方法183.遺傳算法求解機組組合問題3.1基本方法變異（Mutation）3.遺傳算法求解機組組合問題3.1基本方法193.遺傳算法求解機組組合問題3.1基本方法選擇（Selection）圖3.1選擇操作的輪盤賭轉盤49.2%30.9%3.遺傳算法求解機組組合問題3.1基本方法圖3.1選擇操203.遺傳算法求解機組組合問題3.1基本方法積木塊假設（Duilding-blockingHypothesis）積木塊假設遺傳算法中，分別具有高適應值、短定義矩或低階的模式（積木塊）在遺傳算子的作用下相互結合，形式同時具有高適應值、短定義矩和低階的更優(yōu)秀的模式，最終接近全局最優(yōu)解。3.遺傳算法求解機組組合問題3.1基本方法213.遺傳算法求解機組組合問題3.1基本方法可能出現(xiàn)的問題及檢測用遺傳算法解決問題時，可能出現(xiàn)過早收斂和分散過廣的情況。可用交叉率（crossoverprobability）和變異率（mutationprobability）來檢測。如下表如示3.遺傳算法求解機組組合問題3.1基本方法223.遺傳算法求解機組組合問題3.1基本方法可能出現(xiàn)的問題及檢測

交叉率變異率

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

啟發(fā)式算法的定義：一個基于直觀或經驗構造的算法，在可接受的花費（指計算時間和空間）下給出待解決組合優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預計。啟發(fā)式算法常能發(fā)現(xiàn)很不錯的解，但也沒辦法證明它不會得到較壞的解；它通?？稍诤侠頃r間解出答案，但也沒辦法知道它是否每次都可以這樣的速度求解。6.討論問題1：交叉產生的下一代個體中，存在違反約束436.討論回答：在問題的約束很多時，采用啟發(fā)式算法來降低問題的復雜度，將不可行的解轉化為最近的可行解，這種方法有兩種方案：a）將不可行的解轉化為最近的可行解，用可行解替換掉原來的解；b）將不可行的解轉化為最近的可行解，保持原來的解。按方案a）進行“進化”過程的選擇，會濾掉所有違反約束的個體。若可行解空間很大，這個方案是可行的，但在機組組合問題中，可行解空間常常被不可行解所包裹著，采用a）會削減種群的多樣性，可能會丟掉全局最優(yōu)解。按方案b）進行“進化”過程的選擇，新產生的可行解會對整個算法有嚴重的誤導作用，導致偏離全局最優(yōu)解。6.討論回答：在問題的約束很多時，采用啟發(fā)式算法來降446.討論問題2：采用罰函數(shù)可以區(qū)別可行解與不可行解，但當適應度的罰項的值很大時，則難以與可行解區(qū)分開來，會導致收斂速度很慢。且(2)(1)6.討論問題2：采用罰函數(shù)可以區(qū)別可行解與不可行解，456.討論回答：選擇操作是基于輪盤賭的概率選擇，最終的解中，不可行解只占很小的一部分，如圖所示。至于適應度的罰函數(shù)問題，采用的是反向比例的方法，即適應度越大，該個體在被選中的概率越小。同時為了加快收斂速度，還采用了一個適應度掃描程序，保護那個越優(yōu)的“基因”，使之在“進化”過程中還被破壞，但如果發(fā)現(xiàn)種群的多樣性減少到一定程度，則該掃描程序失效，一切還原。6.討論回答：選擇操作是基于輪盤賭的概率選擇，最終的466.討論6.討論47謝謝??！謝謝??！48AGeneticAlgorithmSolutionToTheUnitCommitmentProblem

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

機組組合問題機組組合問題及求解方法簡介遺傳算法簡介遺傳算法求解機組組合問題3.1基本方法3.2改進措施13.3改進措施23.4改進措施3模擬結果結論討論用遺傳算法求解

機組組合問題機組組合問題及求解方法簡介511.機組組合問題及求解方法簡介機組組合問題由于當前的科學技術還不能有效地存儲電力，所以電力生產和消費在任何時刻都要相等，否則就會威脅電力系統(tǒng)安全運行。又由于發(fā)電機組的物理特性限制，（系統(tǒng)備用約束、發(fā)電機組出力范圍約束、最小啟停機時間等等）發(fā)電機組不能夠隨心所欲地發(fā)出需要的電力。為了能夠實時平衡變化劇烈的電力負荷，需要根據(jù)預測的未來電力負荷安排發(fā)電機組起停計劃，在滿足電力系統(tǒng)安全運行條件下，追求發(fā)電成本最小。下面是機組組合問題的一個數(shù)學模型。1.機組組合問題及求解方法簡介機組組合問題521.機組組合問題及求解方法簡介該模型要解決的是一個混合整數(shù)規(guī)劃問題定義一個向量變量xit,其分量為發(fā)電機i在t時段的所有連續(xù)變量,。例如,xit=[pit,rit]T,pit表示發(fā)電機i在t時段的有功;rit表示該發(fā)電機提供的備用。定義一個標量(或向量)變量zit來表示發(fā)電機i在t時段的所有離散變量。把所有的xit和zit寫成矩陣X和Z。是各機組各時段燃料費用的總和;是各機組各時段燃料費用的總和;是各機組的開停機費用之和。1.機組組合問題及求解方法簡介該模型要解決的是一個混合整數(shù)規(guī)531.機組組合問題及求解方法簡介機組組合問題

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

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

拉格朗日松弛法在機組組合問題中應用時,把所有的約束分成兩類,一類是全系統(tǒng)的約束,一類是可以按單臺機組分解的約束,系統(tǒng)約束可以寫成懲罰項的形式,加入目標函數(shù),形成拉格朗日函數(shù),拉格朗日函數(shù)可按單臺機組分解成一系列的子問題。優(yōu)點:隨著機組數(shù)的增加,計算量近似線性增長,克服了維數(shù)障礙,且機組數(shù)目越多,算法效果越好；缺點:由于目標函數(shù)的非凸性，用對偶法求解時,存在對偶間隙,需要根據(jù)對偶問題的優(yōu)化解采取一定的措施構造原問題的優(yōu)化可行解。1.機組組合問題及求解方法簡介拉格朗日松弛法572.遺傳算法簡介設現(xiàn)在有這么個問題需要解決。求f(x)=x2在0～31之間取整數(shù)值時函數(shù)的最大值。準備：對定義域[0，31]內的非負整數(shù)x進行二進制編碼，如x=8時取x=01000，隨機生成4個二進制數(shù):01101(13)、11000(24)、01000(8)、10011(19);這4個數(shù)被稱為一個種群，種群中的每個數(shù)就是一個個體。交叉：將原有種群中的兩個個體隨機匹配，進行交叉繁殖。比如選取01000(8)與10011(19)；將第3位進行交換,得01011(11)與10000(16)。2.遺傳算法簡介設現(xiàn)在有這么個問題需要解決。582.遺傳算法簡介變異：以很小的概率隨機地改變一個個體中的位值。比如若10011(19)被選中，將其第4位由1變?yōu)?。變異的概率很小一般只有千分之幾，其目的是為了防止丟失一些有用的因子。選擇：按個體的適應度進行復制，這里定義個體所定義的函數(shù)值為適應度，比如01101(13)的適應度為169。則每個個體在下一代中的數(shù)量為：2.遺傳算法簡介變異：以很小的概率隨機地改變一個個體中的位值592.遺傳算法簡介mj(t)——為第j個個體在t代中的數(shù)量;mj(t+1)——為第j個個體在t+1代中的數(shù)量;fj——為第j個個體在t代中的適應度。2.遺傳算法簡介mj(t)——為第j個個體在t代中的602.遺傳算法簡介這樣經過交叉、變異、選擇后，“適者生存，不適者淘汰”經每迭代（進化）一次，種群的適應度會有所提高，只要迭代多次，最終會走向全局最優(yōu)解。可見，遺傳算法中，每一步的操作是非常簡單的，而且對問題的依賴性很小，并不要求目標函數(shù)有連續(xù)光滑或要求目標函數(shù)的導數(shù)等。2.遺傳算法簡介這樣經過交叉、變異、選擇后，“適者生存，不適613.遺傳算法求解機組組合問題3.1基本方法考慮問題，“有N臺機組在在H小時內運行，要求制訂一個開停機的計劃，使得機組運行的總費用最小?！奔俣啃r內，發(fā)電機不是開啟就是關閉，開啟狀態(tài)用“1”表示，關閉狀態(tài)用“0”表示。如圖1所示:3.遺傳算法求解機組組合問題3.1基本方法623.遺傳算法求解機組組合問題3.1基本解決方法3.遺傳算法求解機組組合問題3.1基本解決方法633.遺傳算法求解機組組合問題3.1基本方法用遺傳算法的思想來解決問題。設N=20，H=24則每個個體的位數(shù)為20×24=480，搜索空間內的元素個數(shù)為2480=3.12×10144。隨機選取一個種群，種群中的個體為480位二進制編碼。適應度F定義如下：3.遺傳算法求解機組組合問題3.1基本方法643.遺傳算法求解機組組合問題3.1基本方法(1)(1)(2)且FCT：燃料的總費用SUT：機組啟動的總費用SDT：機組關閉的總費用NC：違反約束的數(shù)量VIOLj：違反約束的數(shù)量值PFj：違反約束的罰項μj：罰因子(1)(2)(1)(2)(1)且(2)(1)3.遺傳算法求解機組組合問題3.1基本方法(1)(1)(2)653.遺傳算法求解機組組合問題3.1基本方法交叉（Crossover）3.遺傳算法求解機組組合問題3.1基本方法663.遺傳算法求解機組組合問題3.1基本方法變異（Mutation）3.遺傳算法求解機組組合問題3.1基本方法673.遺傳算法求解機組組合問題3.1基本方法選擇（Selection）圖3.1選擇操作的輪盤賭轉盤49.2%30.9%3.遺傳算法求解機組組合問題3.1基本方法圖3.1選擇操683.遺傳算法求解機組組合問題3.1基本方法積木塊假設（Duilding-blockingHypothesis）積木塊假設遺傳算法中，分別具有高適應值、短定義矩或低階的模式（積木塊）在遺傳算子的作用下相互結合，形式同時具有高適應值、短定義矩和低階的更優(yōu)秀的模式，最終接近全局最優(yōu)解。3.遺傳算法求解機組組合問題3.1基本方法693.遺傳算法求解機組組合問題3.1基本方法可能出現(xiàn)的問題及檢測用遺傳算法解決問題時，可能出現(xiàn)過早收斂和分散過廣的情況?？捎媒徊媛剩╟rossoverprobability）和變異率（mutationprobability）來檢測。如下表如示3.遺傳算法求解機組組合問題3.1基本方法703.遺傳算法求解機組組合問題3.1基本方法可能出現(xiàn)的問題及檢測

交叉率變異率

正常情況0.4~0.90.004~0.024過早收斂≤0.10.004(每代)分散過廣0.1(每代)≤0.004狀態(tài)項目3.遺傳算法求解機組組合問題3.1基本方法交叉率713.遺傳算法求解機組組合問題3.1基本方法實例啟動費用熱啟動費用若關機時間≤冷啟動間隔冷啟動費用其它熱啟動費用若關機時間≤冷啟動間隔冷啟動費用其它熱啟動費用若關機時間≤冷啟動間隔冷啟動費用其它啟動費用熱啟動費用若關機時間≤冷啟動間隔冷啟動費用其它3.遺傳算法求解機組組合問題3.1基本方法啟動費用熱啟動費用72機組組合問題用遺傳算法求解課件733.遺傳算法求解機組組合問題3.1基本方法選取50個個體組成一個種群，進化500代；用20個種群并行計算，結果如下：3.遺傳算法求解機組組合問題3.1基本方法743.遺傳算法求解機組組合問題3.1基本方法3.遺傳算法求解機組組合問題3.1基本方法753.遺傳算法求解機組組合問題3.2改進措施1窗交換（Swap-windowOperator）——0.3窗變異（Window-mutationOperator）——0.33.遺傳算法求解機組組合問題3.2改進措施1763.遺傳算法求解機組組合問題加入這兩個操作結果如下：3.遺傳算法求解機組組合問題加入這兩個操作結果如下：773.遺傳算法求解機組組合問題3.3改進措施2交換變異（Swap-mutationOperator）窗交換爬坡（Swap-windowHill-climbOperator）—0.3僅用于適應度最好的個體。交換變異：選定兩個個體，再選定一個H時間，交換該位。將交換后的結果與交換前的結果進行比較?；蜻x定一個個體，再選定一個H時間，改變該位。將改變后的結果與交換前的結果進行比較。窗交換爬坡：按小時逐次進行窗交換，比較。如下圖：3.遺傳算法求解機組組合問題3.3改進措施2783.遺傳算法求解機組組合問題3.3改進措施23.遺傳算法求解機組組合問題3.3改進措施2793.遺傳算法求解機組組合問題執(zhí)行結果：3.遺傳算法求解機組組合問題執(zhí)行結果：803.遺傳算法求解機組組合問題3.4改進措施3改變罰因子：——約束j的最終罰因子——世代數(shù)——總的世代數(shù)3.遺傳算法求解機組組合問題3.4改進措施3——約束j的最終813.遺傳算法求解機組組合問題3.4改進措施3執(zhí)行結果3.遺傳算法求解機組組合問題3.4改進措施3824.模擬結果在10、20、40、60、80、100臺機組上進行模擬，時間為24小時。下圖是10臺機組的相關數(shù)據(jù).4.模擬結果在10、20、40、60、80、100臺機組上進834.模擬結果4.模擬結果844.模擬結果4.模擬結果854.模擬結果模擬20臺機組的問題時，將前面的10臺機組翻倍，用電的需求量也翻倍。備用電量取需求量的10%。其余情況依此類推。下面對10臺機組進行模擬運算，選取20個種群，每個種群包含50個個體，世代選為500。將運算結果與動態(tài)規(guī)劃法、拉格朗日松弛法進行對比。如下表：4.模擬結果模擬20臺機組的問題時，將前面的10臺864.模擬結果遺傳算法動