基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 -論文 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 本文針對(duì)當(dāng)前科技水平不足以有效存儲(chǔ)電力的情況下產(chǎn)生的發(fā)電機(jī)機(jī)組組合的問(wèn)題，考慮負(fù)荷平衡、輸電線傳輸容量限制等實(shí)際情況產(chǎn)生的約束條件，建立機(jī)組組合優(yōu)化模型，追求發(fā)電成本最小。同時(shí)采用矩陣實(shí)數(shù)編碼遺傳算法（ MRCGA）和窮舉搜索算法，利用 MATLAB 7.0.1 和 C+編程，分別對(duì)模型進(jìn)行求解，并對(duì)所得結(jié)果進(jìn)行分析比較，以此來(lái)幫助電力部門制定機(jī)組啟停計(jì)劃。 首先，建立發(fā)電成本最小目標(biāo)函數(shù)和各項(xiàng)約束條件的數(shù)學(xué)表達(dá)式。其中機(jī)組空載成本和增量成本之和隨該機(jī)組發(fā)電出力增長(zhǎng)呈折線關(guān)系，在分析計(jì)算時(shí)為了簡(jiǎn)便，本文采用一條平滑的二次曲線來(lái)近似代替。 對(duì)于問(wèn)題 1，選取相應(yīng)的約束條件對(duì)目標(biāo)函數(shù)進(jìn)行約束，從而給出優(yōu)化模型。由于問(wèn)題 1 的求解規(guī)模很小，所以采用窮舉搜索算法，利用 C+編程求解，得到了 3 母線系統(tǒng) 4 小時(shí)的最優(yōu)機(jī)組組合計(jì)劃（見表一）。 對(duì)于問(wèn)題 2，在優(yōu)化模型的基礎(chǔ)上，增加最小穩(wěn)定運(yùn)行出力約束、機(jī)組啟動(dòng)和停運(yùn)時(shí)的出力約束以及機(jī)組最小運(yùn)行時(shí)間和最小停運(yùn)時(shí)間約束這三個(gè)約束條件 ，建立了優(yōu)化模型 II。同時(shí)采用遺傳算法和窮舉搜索算法，利用 MATLAB 和 C+編程，分別對(duì)模型進(jìn)行求解，部分結(jié)果如下： 發(fā)電總成本（單位：元） 矩陣實(shí)數(shù)編碼遺傳算法 6780 窮舉搜索算法 6820 在對(duì)所得結(jié)果進(jìn)行了分析比較，重新制定了 3 母線系統(tǒng) 4 小時(shí)最優(yōu)機(jī)組組合計(jì)劃（見表三）。 對(duì)于問(wèn)題 3，用 IEEE118 系統(tǒng)對(duì)優(yōu)化模型 II 進(jìn)行測(cè)試。由于求解規(guī)模巨大，同樣采用遺傳算法和窮舉搜索算法，利用 MATLAB 和 C+編程，分別對(duì)模型進(jìn)行求解，部分結(jié)果如下： 發(fā)電總成本（單位：百萬(wàn)） 矩陣實(shí)數(shù)編碼遺傳算法 2.034 窮舉搜索算法 2.135 在對(duì)所得結(jié)果進(jìn)行比較時(shí)發(fā)現(xiàn)對(duì)于大規(guī)模問(wèn)題，遺傳算法優(yōu)勢(shì)明顯，將其求解結(jié)果作為 24 小時(shí)的最優(yōu)機(jī)組組合計(jì)劃（見附錄）。 最后，我們就模型存在的不足之處提出了改進(jìn)方案，并對(duì)優(yōu)缺點(diǎn)進(jìn)行了分析。 關(guān)鍵字 機(jī)組組合優(yōu)化模型 矩陣實(shí)數(shù)編碼遺傳算法 窮舉搜索算法 一、問(wèn)題的提出 當(dāng)前的科學(xué)技術(shù)還不能有效地存儲(chǔ)電力，所以電力生產(chǎn)和消費(fèi)在任何時(shí)刻都要相等，否則就會(huì)威脅電力系統(tǒng)安全運(yùn)行。為了能夠?qū)崟r(shí)平衡變化劇烈的電力負(fù)荷，電力部門往往需要根據(jù)預(yù)測(cè)的未來(lái)電力負(fù)荷安排發(fā)電機(jī)組起停計(jì)劃，在滿足電力系統(tǒng)安全運(yùn)行條件下，追求發(fā)電成本最小。 在沒(méi)有電力負(fù)荷損耗以及一個(gè)小時(shí)之內(nèi)的電力負(fù)荷和發(fā)電機(jī)出力均不變的前提下，假定所有發(fā)電機(jī)組的發(fā)電成本都是由 3部分組成 :1.啟動(dòng)成本（ Startup Cost），2.空載成本（ No load cost）， 3.增量成本（ Incremental Cost）。需要考慮的約束有 : 1負(fù)荷平衡約束 2系統(tǒng)備用約束 3輸電線路傳輸容量約束 4發(fā)電機(jī)組出力范圍約束 5機(jī)組增出力約束 6機(jī)組降出力約束。 問(wèn)題 1： 3 母線系統(tǒng) 有一個(gè) 3 母線系統(tǒng)，其中有 2 臺(tái)機(jī)組、 1 個(gè)負(fù)荷和 3 條輸電線路，已知 4 個(gè)小時(shí)的負(fù)荷和系統(tǒng)備用要求。請(qǐng)求出這 4 個(gè)小時(shí)的最優(yōu)機(jī)組組合計(jì)劃。最終結(jié)果應(yīng)該包括總成本、各小時(shí)各機(jī)組的狀態(tài)、各小時(shí)各機(jī)組的發(fā)電出力和各小時(shí)各機(jī)組提供的備用。 問(wèn)題 2： 3 母線系統(tǒng) 在問(wèn)題 1 的基礎(chǔ)上，考慮發(fā)電機(jī)組的下列物理特性約束 :1.發(fā)電機(jī)組的穩(wěn)定出力范圍約束 2.機(jī)組啟動(dòng)時(shí)的出力約束 3.機(jī)組停運(yùn)時(shí)的出力約束 4.機(jī)組最小運(yùn)行時(shí)間約束 5.機(jī)組最小停運(yùn)時(shí)間約束。重新制定最優(yōu)機(jī)組組合計(jì)劃。 問(wèn)題 3： IEEE 118 系統(tǒng) 用 IEEE 118 節(jié)點(diǎn)的電力系統(tǒng)對(duì)問(wèn)題 2 的求解模型進(jìn)行測(cè)試，試求出 24 個(gè)小時(shí)的最優(yōu)機(jī)組組合計(jì)劃 。最終結(jié)果應(yīng)該包括總成本、各小時(shí)各機(jī)組的狀態(tài)、各小時(shí)各機(jī)組的發(fā)電出力和各小時(shí)各機(jī)組提供的備用。 二、問(wèn)題的分析 機(jī)組優(yōu)化組合和優(yōu)化啟停就是要在滿足約束條件的情況下，優(yōu)化地選定各時(shí)段參加運(yùn)行的機(jī)組，求出機(jī)組的最佳運(yùn)行方案，實(shí)現(xiàn)發(fā)電成本最小。 然而，機(jī)組組合問(wèn)題是一個(gè)多變量、多約束的混合整數(shù)非線性規(guī)劃問(wèn)題。針對(duì)此類問(wèn)題的求解，數(shù)學(xué)類優(yōu)化方法如線性規(guī)劃、非線性規(guī)劃、動(dòng)態(tài)規(guī)劃等，都存在明顯不足之處。而采用智能優(yōu)化算法對(duì)此問(wèn)題的研究較多，主要包括遺傳算法、模擬退火算法、禁忌搜索、人工神經(jīng)網(wǎng)絡(luò)、模糊優(yōu)化等算法。其中模 擬退火算法收斂速度慢、禁忌搜索算法對(duì)初始解依賴性較強(qiáng)、人工神經(jīng)網(wǎng)絡(luò)算法存在網(wǎng)絡(luò)合適的隱含層數(shù)目和節(jié)點(diǎn)數(shù)目難以確定、模糊優(yōu)化方法的隸屬函數(shù)和模糊推理規(guī)則的確定較困難。鑒于遺傳算法作為一種新的全局 優(yōu)化搜索算法，以其簡(jiǎn)單通用、魯棒性強(qiáng)、適于并行處理及應(yīng)用范圍廣等顯著特點(diǎn)，本文采用基于矩陣實(shí)數(shù)編碼遺傳算法來(lái)解決機(jī)組組合問(wèn)題。 可以將整個(gè)問(wèn)題分為以下兩個(gè)任務(wù)來(lái)完成： 一、 建立機(jī)組組合問(wèn)題的數(shù)學(xué)模型 二、 采用窮舉搜索法和遺傳算法，利用 C+或者 MATLAB 編程，求解模型，得到最優(yōu)機(jī)組組合計(jì)劃 由于題目中的三個(gè)問(wèn)題所考慮的約束條件復(fù)雜程度不同，發(fā)電機(jī)組數(shù)與負(fù)荷情況也不相同，本文將三個(gè)問(wèn)題逐一建立模型并求解： 問(wèn)題 1 根據(jù)負(fù)荷平衡、系統(tǒng)備用、輸電線路傳輸容量、發(fā)電機(jī)組出力范圍、機(jī)組增出力、機(jī)組降出力等約束建立優(yōu)化模型 I，采用窮舉搜索算法，利用 C+編程進(jìn)行求解。 問(wèn)題 2 和問(wèn)題 3 在問(wèn)題 1 的基礎(chǔ)上，增加機(jī)組啟動(dòng)和停運(yùn)時(shí)的出力、機(jī)組最小運(yùn)行時(shí)間和最小停運(yùn)時(shí)間約束條件，建立了優(yōu)化模型 II，采用窮舉搜索法和遺傳算法，分別利用C+和 MATLAB 編程進(jìn)行求解。 三、模型假設(shè)和符號(hào)系統(tǒng) 3.1 模型假設(shè) 1. 假設(shè)系統(tǒng)不存在電力負(fù)荷損耗 2. 假設(shè)一個(gè)小時(shí)之內(nèi)的電力負(fù)荷和發(fā)電機(jī)出力均不變 3. 假設(shè)參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例為 0.40.99 4. 假設(shè)發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例為 0.00010.1 3.2 符號(hào)系統(tǒng) 為機(jī)組 在 時(shí)段的運(yùn)行狀態(tài)， 為機(jī)組 的啟動(dòng)成本 為機(jī)組 在 時(shí)段的發(fā)電成本 為機(jī)組 在 時(shí)段的出力； 為負(fù)荷 在 時(shí)段的負(fù)荷量； 為發(fā)電機(jī)組 的最大出力； 810 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 為 時(shí)段系統(tǒng)備用要求； 為線路 上流過(guò)的電能； 為第 根輸電線路第 條母線的線性傳輸因子； 為母線 上的注入功率； 為第根輸電線路的最大傳輸容量； 發(fā)電機(jī)組最小穩(wěn)定運(yùn)行出力； 為機(jī)組 最大減出力； 為機(jī)組 最大增出力； 為機(jī)組 最小運(yùn)行時(shí)間； 為機(jī)組 最小停運(yùn)時(shí)間； 四、模型的建立與求解 4.1 模型建立分析 4.1.1 先考慮目標(biāo)函數(shù) 1) 空載成本和增量成本 觀察空載成本和增量成本構(gòu)成的部分成本隨該機(jī)組發(fā)電出力變化特性圖，如圖一中折線所示。 圖一 空載成本和增量成本之和隨該機(jī)組發(fā)電出力增長(zhǎng)走勢(shì)圖 在分析計(jì)算時(shí)為了簡(jiǎn)便，通常用一條平滑曲線來(lái)近似代替有起伏的部分成本特性，如圖一中平畫曲線所示。當(dāng) n 段直線近似表示時(shí)，部分成本特性可表示為 （ 1） 2) 啟動(dòng)成本 （ 2） 其中： 為機(jī)組 在 時(shí)段的運(yùn)行狀態(tài)， 為機(jī)組 的啟動(dòng)成本 3) 目標(biāo)函數(shù) 機(jī)組組合的目的是針對(duì)在指定的周期內(nèi)，滿足系統(tǒng)負(fù)荷、備用容量、機(jī)組最小時(shí)間和最小停機(jī)時(shí)間等限制，優(yōu)化確定各機(jī)組的啟停機(jī)計(jì)劃和優(yōu)化分配其發(fā)電負(fù)荷，使發(fā)電總費(fèi)用最小。因此，要以機(jī)組 的費(fèi)用最小為依據(jù)建立相應(yīng)的目標(biāo)函數(shù)。 設(shè)所研究的計(jì)劃周期為 ，機(jī)組臺(tái)數(shù)為 ，則該問(wèn)題的目標(biāo)函數(shù)可以表示為 : （ 3） 其中： 為機(jī)組 在 時(shí)段的發(fā)電成本 4.1.2 再考慮約束條件 1) 負(fù)荷平衡約束 任何時(shí)段，電力負(fù)荷之和必須等于發(fā)電機(jī)發(fā)電出力之和。 （ 4） 其中： 為機(jī)組 在 時(shí)段的運(yùn)行狀態(tài)， ； 為機(jī)組 在 時(shí)段的出力； 為負(fù)荷 在 時(shí)段的負(fù)荷量； 2) 系統(tǒng)備用約束 任何時(shí)段，發(fā)電機(jī)的備用容量之和必須大于系統(tǒng)備用要求。 （ 5） 其中： 為發(fā)電機(jī)組 的最大出力； 為 時(shí)段系統(tǒng)備用要求； 3) 輸電線路傳輸容量約束 線路傳輸?shù)碾娔鼙仨氃谒膫鬏斎萘糠秶鷥?nèi)。 （ 6） 其中： 為線路 上流過(guò)的電能； 為第 根輸電線路第 條母線的線性傳輸因子； 為母線 上的注入功率； 為第根輸電線路的最大傳輸容量； 4) 發(fā)電機(jī)組出力范圍約束與穩(wěn)定出力范圍約束 處于運(yùn)行狀態(tài)的發(fā)電機(jī)組的發(fā)電出力必須小于其最大發(fā)電出力，同時(shí)必須大于其最小穩(wěn)定運(yùn)行出力。 （ 7） 其中： 發(fā)電機(jī)組最小穩(wěn)定運(yùn)行出力； 5) 機(jī)組增降出力約束 發(fā)電機(jī)組在增加發(fā)電出力時(shí)，增加出力的速度要小于其最大增出力；發(fā)電機(jī)組在減少發(fā)電出力時(shí)，減少出力的速度要小于其最大減出力。 （ 8） 其中： 為機(jī)組 最大減出力； 為機(jī)組 最大增出力； 6) 機(jī)組啟動(dòng)和停運(yùn)時(shí)的出力約束 當(dāng)機(jī)組從停運(yùn)狀態(tài)變?yōu)檫\(yùn)行狀態(tài)時(shí)，機(jī)組在該小時(shí)的發(fā)電出力必須為其最小穩(wěn)定運(yùn)行出力，且當(dāng)機(jī)組從運(yùn)行狀態(tài)變?yōu)橥＿\(yùn)狀態(tài)時(shí)，機(jī)組在該小時(shí)的發(fā)電出力必須為其 最小穩(wěn)定運(yùn)行出力。 （ 9） 7) 機(jī)組最小運(yùn)行時(shí)間和最小停運(yùn)時(shí)間約束 機(jī)組每次啟動(dòng)后，連續(xù)運(yùn)行時(shí)間至少為該臺(tái)機(jī)組的最小運(yùn)行時(shí)間。機(jī)組每次停運(yùn)后，連續(xù)停運(yùn)時(shí)間至少為該臺(tái)機(jī)組的最小停運(yùn)時(shí)間。 （ 10） （ 11） 其中： 為機(jī)組 最小運(yùn)行時(shí)間； 為機(jī)組 最小停運(yùn)時(shí)間； 4.2 模型及其求解 問(wèn)題 1 1） 優(yōu)化模型 問(wèn)題 1 中的 3 母線系統(tǒng)僅考慮負(fù)荷平衡約束 系統(tǒng)備用約束、輸電線路傳輸容量約束、發(fā)電機(jī)組出力范圍約束與穩(wěn)定出力范圍約束和機(jī)組增降出力約束，所建優(yōu)化方程模型如下。 （ 12） （ 13） 其中： 為機(jī)組 在 時(shí)段的發(fā)電成本； 為機(jī)組 的啟動(dòng)成本； 2)優(yōu)化模型的求解算法 機(jī)組組合問(wèn)題在數(shù)學(xué)規(guī)劃上屬于 NP 完全問(wèn)題，任何 NP 完全問(wèn)題只有通過(guò)列舉所有可能的組合，才能得到最優(yōu)解，即 采用窮舉搜索法。由于問(wèn)題 1 的求解規(guī)模不大，所以該問(wèn)題將采用窮舉搜索法對(duì)模型進(jìn)行求解。我們?cè)O(shè)置一計(jì)數(shù)器 （ ）用以記錄機(jī)組已運(yùn)行的時(shí)間。 讀取各機(jī)組和負(fù)荷的原始數(shù)據(jù)。另 。 設(shè)置機(jī)組 1 的第 小時(shí)的出力大小（從小到大依次搜索，跨度為 1），使其出力大小的變化滿足增出力約束和降出力約束。 判斷機(jī)組 1 是否滿足其出力范圍約束。若滿足則繼續(xù)下一步，否則，重復(fù) 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 步驟 2。 根據(jù)系統(tǒng)負(fù)荷平衡約束，求出機(jī)組 2 的出力大小。 判斷機(jī)組 2 出力大小的變化和出力范圍 是否滿足增出力約束、降出力約束和出力范圍約束。若滿足則繼續(xù)下一步，否則重復(fù)步驟 2、 3、 4。 判斷機(jī)組 1 和機(jī)組 2 是否滿足系統(tǒng)備用約束，若滿足則繼續(xù)下一步，否則重復(fù)步驟 2、 3、 4、 5。 判斷機(jī)組 1 和機(jī)組 2 是否滿足輸電線路傳輸容量約束，若滿足繼續(xù)下一步，否則重復(fù)步驟 2、 3、 4、 5、 6。 判斷計(jì)數(shù)器 是否為 4，若是則輸出該種情況下兩臺(tái)機(jī)組各時(shí)段出力大 小，否則重復(fù)步驟 2、 3、 4、 5、 6、 7，另 。直到所有的情況搜索完畢為止。 執(zhí)行完該算法，可以得到一最優(yōu)機(jī)組組合計(jì)劃。 3)模型求解與分析 我們根據(jù) 上面的算法步驟，我們編 C+程序（附錄 1），并代入各機(jī)組和負(fù)荷的初始數(shù)據(jù)。可以得到一總成本為 6580￥的最優(yōu)機(jī)組組合計(jì)劃，如表一所示： 表一 3 母線系統(tǒng)的最優(yōu)機(jī)組組合計(jì)劃 機(jī)組 G1 機(jī)組 G2 小時(shí) 1 狀態(tài) 運(yùn)行 關(guān)機(jī) 出力 (MW) 100 0 備用 (MW) 100 0 2 狀態(tài) 運(yùn)行 關(guān)機(jī) 出力 (MW) 130 0 備用 (MW) 70 0 3 狀態(tài) 運(yùn)行 運(yùn)行 出力 (MW) 130 40 備用 (MW) 70 60 4 狀態(tài) 運(yùn)行 關(guān)機(jī) 出力 (MW) 140 0 備用 (MW) 60 0 總成本 (￥ ) 6580 使用窮舉搜索法對(duì)該問(wèn)題雖然能得出結(jié)果，但其運(yùn)行效率太低，不能用于求解大規(guī)模問(wèn)題，且編程實(shí)現(xiàn)較復(fù)雜，不是一種優(yōu)良的算法。 問(wèn)題 2 和問(wèn)題 3 1） 優(yōu)化模型 問(wèn)題 2 和問(wèn)題 3 的優(yōu)化模型為 （ 14） （ 15） 2）求解算法 對(duì)于問(wèn)題 2 和 3，我們同時(shí)采用窮舉搜索法和遺傳算法兩種算法進(jìn)行求解，并將求得結(jié)果進(jìn)行比較，以比較兩種算法的優(yōu)劣。窮舉搜 索法的算法思想與問(wèn)題 1的求解算法思想一致。遺傳算法的流程圖如圖二所示。 圖二 遺傳算法流程圖 矩陣實(shí)數(shù)編碼遺傳算法的描述： 針對(duì)機(jī)組組合問(wèn)題的矩陣實(shí)數(shù)編碼 本文以要安排發(fā)電機(jī)組起停計(jì)劃作為遺傳算法中的個(gè)體，采用實(shí)數(shù)矩陣形式進(jìn)行編碼。其具體形式為 （ 16） 其中： 為遺傳種群中的第 個(gè)個(gè)體 為編碼矩陣中的第 行第 列元素，含義為發(fā)電機(jī)組 在 時(shí)段的發(fā)電出力 為編碼矩陣中的第 個(gè)列向量，含義為 時(shí)段內(nèi)發(fā)電機(jī)組間的負(fù)荷分配情況 為編碼矩陣中的第 個(gè)行向量，含義為發(fā)電機(jī)組 在發(fā)電計(jì)劃制定周期 內(nèi)的出力過(guò)程 發(fā)電機(jī)組的運(yùn)行狀態(tài)取決于矩陣中元素的具體取值，即根據(jù)機(jī)組在某時(shí)段中的出力大小來(lái)確定啟停狀態(tài)，具體表達(dá)式為 （ 17） 遺傳種群初始化 遺傳種群初始化時(shí)，按編碼矩陣中列向量的順序進(jìn)行。以 中 為例，初始過(guò)程如下： （ 1）生成服從均勻分布的隨機(jī)數(shù)數(shù)組 （ 18） 其中： 為在發(fā)電機(jī)組 最大最小出力之間隨機(jī)生成的正數(shù) （ 2）計(jì)算百分比系數(shù)數(shù)組 （ 19）其中： （ 3）初始化各臺(tái)發(fā)電機(jī)組的出力，即初始化 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 其中： 為負(fù)荷 在 時(shí)段的負(fù)荷量 個(gè)體調(diào)整方法 在進(jìn)行個(gè)體調(diào)整時(shí)按列向量的先后順序進(jìn)行。以個(gè)體 中 為例，具體調(diào)整措施如下： （ 1）根據(jù)機(jī)組組合問(wèn)題對(duì)精度的要求，對(duì) 列中的各個(gè)元素保留 （ 2）調(diào)整 列中的元素取值，使其滿足相應(yīng)發(fā)電機(jī)組出力范圍約束。其方法如下： （ 21） 其中： 為調(diào)整前發(fā)電機(jī)組 在 時(shí)段的發(fā)電出力 為調(diào)整后發(fā)電機(jī)組 在 時(shí)段的發(fā)電出力 為介于 0、 1 之間的常數(shù)，本文取 發(fā)電機(jī)組 最小穩(wěn)定運(yùn)行出力； 發(fā)電機(jī)組 最大出力； （ 3）調(diào)整 列中的元素取值，使其滿足相應(yīng)發(fā)電機(jī)組的增出力和降出力約束約束。具體如下： （ 22） 其中： 為前一步調(diào)整完成的發(fā)電機(jī)組 在 時(shí)段的發(fā)電出力 為此步調(diào)整后的發(fā)電機(jī)組 在 時(shí)段的發(fā)電出力 為機(jī)組 最大減出力 為機(jī)組 最大增出力 （ 4）調(diào)整發(fā)電機(jī)組啟停狀態(tài)使其滿足系統(tǒng)備用約束。具體調(diào)整方法如下： 當(dāng) 時(shí)，增開發(fā)電機(jī)組，令 新投入運(yùn)行的發(fā)電機(jī)組發(fā)電出力為其最小出力，直至滿足系統(tǒng)備用約束為止。其中， 為 時(shí)段系統(tǒng)備用要求 （ 5）經(jīng)過(guò)上述三步調(diào)整后， 列中所有元素的總和可能不等于 時(shí)段中的系統(tǒng)總負(fù)荷。因此要進(jìn)行負(fù)荷分配的調(diào)整。具體的調(diào)整辦法為：當(dāng) 時(shí)，通過(guò)增加運(yùn)行發(fā)電機(jī)組出力來(lái)滿足負(fù)荷平衡約束；反之，若 ，則降低運(yùn)行發(fā)電機(jī)組的出力。此步調(diào)整中，只能在發(fā)電機(jī)組的最大出力允許范圍內(nèi)進(jìn)行調(diào)整，不能改變機(jī)組的運(yùn)行狀態(tài)。 （ 6）算法趨于收斂時(shí)，若發(fā)電機(jī)組的出力過(guò)程不滿足最小運(yùn)行、停運(yùn)時(shí)間約束條件，則通過(guò)調(diào)整違反約束發(fā)電機(jī)組的運(yùn)行狀態(tài)滿足此項(xiàng)約束條件，即： 時(shí)，延長(zhǎng)發(fā)電機(jī)組 的運(yùn)行時(shí)間； 時(shí)，采用將發(fā)電機(jī)組 違反約束的全部停運(yùn)狀態(tài)轉(zhuǎn)變?yōu)檫\(yùn)行狀態(tài)的方式來(lái)滿足約束條件，并令相應(yīng)的出力為機(jī)組 的最小出力。 其中： 為機(jī)組 最小運(yùn)行時(shí)間； 為機(jī)組 最小停運(yùn)時(shí)間； 適度函數(shù)的選取 采用個(gè)體調(diào)整方法后，在求解的過(guò)程中只有發(fā)電機(jī)組的最小運(yùn)行、停運(yùn)時(shí)間約束條件可能得不到滿足。為了加快算法收斂，本文的適度函數(shù)采用如下形式： （ 23） 其中： 為發(fā)電機(jī)組 違反最小運(yùn)行或停運(yùn)時(shí)間約束條件時(shí)的懲罰量，本文取 為機(jī)組 的啟動(dòng)成本； 為懲罰因子，本文取 ； 為違反此項(xiàng)約束的次數(shù)； 為正常數(shù)，本文取 。其含義為：發(fā)電機(jī)組 違反 1 次最小運(yùn)行時(shí)間或停運(yùn)時(shí)間約束，便以機(jī)組 的 倍的啟動(dòng)成本 進(jìn)行懲罰。 選擇復(fù)制 （ 1）群體中各個(gè)體的選擇概率 選擇概率的計(jì)算公式為： （ 24） 其中： 為第 個(gè)體的選擇概率 為第 個(gè)個(gè)體，即本文中機(jī)組 各個(gè)時(shí)段的 發(fā)電出力 （ 2）賭輪選擇法 賭輪選擇法用下面的子過(guò)程來(lái)模擬： 在 區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù) ； 若 ,則染色體 被選中； 若 , 則染色體 被選中。 其中 稱為染色體 的積累概率 , 其計(jì)算公式為 （ 25） 交叉 通過(guò) 在父代中選擇交配個(gè)體后，將準(zhǔn)備進(jìn)行交叉操作的父代個(gè)體表示為 （ 26） 交叉操作產(chǎn)生的個(gè)體記為 、 ，保留到子代中的個(gè)體記為 、 。本文的交叉操作是在 2 個(gè)父代個(gè)體奇數(shù)列與 偶數(shù)列之間進(jìn)行的。具體操作過(guò)程為： （ 1）生成隨機(jī)數(shù) ；生成隨機(jī)交叉位 。 （ 2）交叉操作生成個(gè)體 、 ，其表達(dá)式為 （ 27） （ 3）對(duì)交叉生成的個(gè)體依照 個(gè)體調(diào)整方法進(jìn)行個(gè)體調(diào)整，然后計(jì)算出 、 的適度值。 （ 4）采用局部錦標(biāo)賽選擇法在父代個(gè)體和交叉產(chǎn)生的個(gè)體間進(jìn)行子代選擇，具體方法如下： （ 28） 變異 通過(guò) 個(gè)體交叉后，將準(zhǔn)備進(jìn)行變異的父代個(gè)體表示為 （ 29） 變異后產(chǎn)生的個(gè)體記為 、 ，保留到子代中的個(gè)體記為 、 。 本文只對(duì)某列進(jìn)行變異處理。具體操作過(guò)程為： （ 1） 生成隨機(jī)變異因子 ； 生成隨機(jī)變異時(shí)段 ； 生成隨機(jī)變異個(gè)體選擇因子 （ 2）變異后生成個(gè)體 、 ，其表達(dá)式為 （ 30） （ 3）對(duì)變異后生成的個(gè)體依照 個(gè)體調(diào)整方法進(jìn)行個(gè)體調(diào)整，然后計(jì)算出 、 的適度值。 （ 4）采用局部錦標(biāo)賽選擇法在父代個(gè)體和變異產(chǎn)生的個(gè)體間進(jìn)行子代選擇，具體方法如下： （ 31） 終止條件 遺傳算法的終止條件有兩類常 見條件： 第一類：采用設(shè)定最大遺傳代數(shù)的方法，一般可設(shè)為 50 代，此時(shí)就可能得出最優(yōu)解。 第二類：根據(jù)個(gè)體的差異來(lái)判斷，通過(guò)計(jì)算種群中基因多樣性測(cè)度，即所有基因位 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 相似程度來(lái)進(jìn)行控制。 本文采用第一類方法，將 、 個(gè)體依照 個(gè)體調(diào)整方法進(jìn)行個(gè)體調(diào)整，然后計(jì)算出對(duì)應(yīng)的適度值，直到第 代，循環(huán)迭代結(jié)束，輸出最優(yōu)解 Tc0。 3)模型求解 利用窮舉搜索法和遺傳算法可以分別求解問(wèn)題 1 和 2。 問(wèn)題 2 利用 C+程序?qū)ΩF舉搜索法進(jìn)行實(shí)現(xiàn)，然后求解，所得結(jié)果如表二所示。 表二 問(wèn)題二窮舉搜索法求解結(jié)果 機(jī)組 G1 機(jī)組 G2 小時(shí) 1 狀態(tài) 運(yùn)行 關(guān)機(jī) 出力 (MW) 100 0 備用 (MW) 100 0 2 狀態(tài) 運(yùn)行 運(yùn)行 出力 (MW) 110 20 備用 (MW) 90 80 3 狀態(tài) 運(yùn)行 運(yùn)行 出力 (MW) 110 60 備用 (MW) 90 40 4 狀態(tài) 運(yùn)行 運(yùn)行 出力 (MW) 100 40 備用 (MW) 100 60 總成本 (￥ ) 6820 利用 MATLAB 程序?qū)z傳進(jìn)行實(shí)現(xiàn)，然后求解。由于遺傳算法具有隨機(jī)性，所程序每次運(yùn)行所得的結(jié)果有略微差別，我們從多次運(yùn)行的解中選取總成本最小的一組機(jī)組組合計(jì)劃，結(jié)果如表三所示。 表三 問(wèn)題二遺傳算法求解結(jié)果 機(jī)組 G1 機(jī)組 G2 小時(shí) 1 狀態(tài) 運(yùn)行 關(guān)機(jī) 出力 (MW) 100 0 備用 (MW) 100 0 2 狀態(tài) 運(yùn)行 關(guān)機(jī) 出力 (MW) 130 0 備用 (MW) 70 0 3 狀態(tài) 運(yùn)行 運(yùn)行 出力 (MW) 150 20 備用 (MW) 50 80 4 狀態(tài) 運(yùn)行 運(yùn)行 出力 (MW) 120 20 備用 (MW) 80 80 總成本 (￥ ) 6780 從問(wèn)題 2 兩種算法的求解結(jié)果中我們可以發(fā)現(xiàn)，遺傳算法的求解結(jié)果優(yōu)于窮舉搜索法，但遺傳算法有一定的隨機(jī)性，有時(shí)需多運(yùn)行幾次才能得到最優(yōu)解。且遺傳算法比窮舉搜索法更容易實(shí)現(xiàn)。 問(wèn)題 3 利用窮舉搜索法和矩陣實(shí)數(shù)編碼遺傳算法分別求解問(wèn)題 3。 窮舉搜索法求解結(jié)果見附錄三。 由于矩陣實(shí)數(shù)編碼遺傳算法得到的成本最小值具有一定的隨機(jī)性，且隨算法中迭代次數(shù)的變化而變化，所程序每次運(yùn)行所得的結(jié)果有略微差別。為求得更為精確的結(jié)果，我們變換迭代次數(shù)，以判斷迭代多少次為最優(yōu)（這里取 30、 50、 100次的結(jié)果），見圖三、四、五，詳細(xì)結(jié)果見附錄四、五 圖三 迭代 30 次的運(yùn)行結(jié)果 圖四 迭代 50 次的運(yùn)行結(jié)果 圖五 迭代 100 次的運(yùn)行結(jié)果 我們從多次運(yùn)行的結(jié)果中選取最優(yōu)機(jī)組組合計(jì)劃，使用矩陣實(shí)數(shù)編碼遺傳算法求得的最優(yōu)解為迭代次數(shù)為 50 次（總成本、各小時(shí)各機(jī)組的狀態(tài)、 各小時(shí)各機(jī)組的發(fā)電出力和各小時(shí)提供的備用）見附錄五 從問(wèn)題 3 的求解結(jié)果中，通過(guò)不同迭代次數(shù)之間的比較以及窮舉搜索法與矩陣實(shí)數(shù)編碼遺傳算法的對(duì)比分析，看出矩陣實(shí)數(shù)編碼遺傳算法在進(jìn)行大規(guī)模機(jī)組組合問(wèn)題求解時(shí)，具有很強(qiáng)的適應(yīng)性和全局搜索能力，而且系統(tǒng)規(guī)模越大算法的優(yōu)化結(jié)果越理想。 因此，矩陣實(shí)數(shù)編碼遺傳算法的求解結(jié)果優(yōu)于窮舉搜索法，但矩陣實(shí)數(shù)編碼遺傳算法有一定的隨機(jī)性，需多運(yùn)行幾次才能得到最優(yōu)解。 六、模型的改進(jìn)及評(píng)價(jià) 6.1 模型的改進(jìn) 模型改進(jìn)一：機(jī)組組合優(yōu)化模型 I 與 II 的改進(jìn) 在機(jī)組組合優(yōu)化模型 I、 II 中，通 過(guò)二次函數(shù)對(duì)空載成本和增量成本曲線參數(shù)進(jìn)行擬合過(guò)程中，采用二次函數(shù)擬合誤差比較大（增量成本變化幅度比較小），特別是機(jī)組規(guī)模比較小的時(shí)候更是如此。 鑒于此種情況，當(dāng)機(jī)組規(guī)模比較大時(shí)，可以采取平滑曲線進(jìn)行擬合。如問(wèn)題三，可以利用二次函數(shù)進(jìn)行擬合，根據(jù)運(yùn)行結(jié)果可以看出誤差更小，機(jī)組啟停更合理，發(fā)電成本更小。 此外，當(dāng)機(jī)組規(guī)模相對(duì)較小時(shí)，可以不進(jìn)行曲線擬合，直接采取分段函數(shù)，編程求解。如問(wèn)題一和二，利用 C+編程，采取窮舉搜索法求解，精度會(huì)更高。 模型改進(jìn)二：基于矩陣實(shí)數(shù)編碼遺傳算法的改進(jìn) 在矩陣實(shí)數(shù)編碼遺傳算法步 驟中，根據(jù)實(shí)際情況（如機(jī)組規(guī)模，時(shí)段等問(wèn)題）可以對(duì)各步驟進(jìn)行優(yōu)化或改進(jìn)。如 變異，本文實(shí)在時(shí)段內(nèi)列向量進(jìn)行的，相當(dāng)于發(fā)電機(jī)組 在不同時(shí)段發(fā)電出力的重新調(diào)整。因此，還可以采用多窗口變異操作【 1】。此操作是在個(gè)體內(nèi)行向量間進(jìn)行的，相當(dāng)于在不同發(fā)電機(jī)組間進(jìn)行發(fā)電出力的重新調(diào)整。此法具有經(jīng)濟(jì)負(fù)荷分配的功能，并且，由于是同時(shí)進(jìn)行多個(gè)時(shí)段的負(fù)荷分配調(diào)整，故執(zhí)行效率較高。當(dāng)然，二者相結(jié)合，效果更佳。 6.2 模型的評(píng)價(jià) 優(yōu)點(diǎn)： 第一，提供了一種求解多變量、多約束的混合整數(shù)非線性規(guī)劃的機(jī)組組合優(yōu)化問(wèn)題的思路，此方法新穎可靠 易行，極具參考價(jià)值。 第二，采用 MRCGA 算法求解機(jī)組組合問(wèn)題的新方法。利用二維實(shí)數(shù)矩陣對(duì)發(fā)電計(jì)劃安排進(jìn)行編碼，將機(jī)組組合問(wèn)題轉(zhuǎn)化為單層優(yōu)化問(wèn)題進(jìn)行求解，因而降低了算法的時(shí)間復(fù)雜度。運(yùn)用個(gè)體調(diào)整方法處理各項(xiàng)約束條件，確保了優(yōu)化結(jié)果的可行性，使該算法更易于應(yīng)用實(shí)際。 第三， 矩陣實(shí)數(shù)編碼遺傳算法（ MRCGA）適合求解大規(guī)模機(jī)組組合問(wèn)題。通過(guò)MATLAB 仿真計(jì)算、不同迭代次數(shù)比較分析以及同其他方法（如窮舉法）的對(duì)比分析，驗(yàn)證了該方法在進(jìn)行大規(guī)模機(jī)組組合問(wèn)題求解時(shí)，具有很強(qiáng)的適應(yīng)性和全局搜索能力，而且系統(tǒng)規(guī)模越大 算法的優(yōu)化結(jié)果越理想。 缺點(diǎn)： 第一，采用二次函數(shù)對(duì)空載成本和增量成本曲線參數(shù)進(jìn)行擬合過(guò)程中，擬合誤差比較大。特別是機(jī)組規(guī)模比較小時(shí)更是如此。 第二， MRCGA 算法對(duì)小規(guī)模機(jī)組組合問(wèn)題求解結(jié)果精度不高，誤差大。 參考文獻(xiàn)： 1 劉瓊蓀，龔劬，何中市，傅鸝，任善強(qiáng)，數(shù)學(xué)實(shí)驗(yàn)，北京：高等教育出版社，2004 2 姜啟源，謝金星，葉俊，數(shù)學(xué)模型，北京：高等教育出版社， 2006 3 孫力勇，張焰，蔣傳文，基于矩陣實(shí)數(shù)編碼遺傳算法求解大規(guī)模機(jī)組組合問(wèn)題，中國(guó)機(jī)電工程學(xué)報(bào)，第 26 卷（ 2 期）， 2006 4 趙東方，數(shù)學(xué)模型與計(jì)算，北京：科學(xué)出版社， 2007 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 附錄 1 問(wèn)題 1 的 C+求解程序 #include #include using namespace std; double cost1(double x); double cost2(double x); int get_total_price(); void fun(int i); ofstream fout(11.doc); const int hour = 5; / 最大出力 int pmax2 = 200, 100; / 最大增出力 int pcmax2 = 30, 40; / 最大減出力 int pdmax2 = 50, 60; / 狀態(tài) int state2hour = 1, 0; / 負(fù)荷 int demand5 = 0, 100, 130, 170, 140; / 啟動(dòng)費(fèi)用 int start2 = 350, 100; / 機(jī)組各時(shí)段狀態(tài) int power25 = 100, 0; / 系統(tǒng)備用要求 int b_powerhour = 0, 20, 30, 50, 40; / 最小費(fèi)用 int minprice = 9999999; int main() fun(1); return 0; / 機(jī)組 1 成本 double cost1(double x) if (x price ? price: minprice); /cout 200) continue; / 機(jī)組 1 增出力和減出力約束 if ( (power0i-power0i-1) pcmax0) & (power0i power0i-1) | (power0i-1-power0i) pdmax0) & (power0i-1 power0i) continue; / 機(jī)組 2 / 負(fù)荷平衡約束 / 機(jī)組 1 狀態(tài) if (power0i 0) state0i = 1; else state0i = 0; / 機(jī)組 2 狀態(tài) if (power1i 0) state1i = 1; else state1i = 0; / 系統(tǒng)備用約束 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 int bei = 0; int k = 0; for ( k = 0; k 2; k+) bei += stateki * (pmaxk - powerki); if (bei b_poweri) continue; if (i = hour - 1) / cout get_total_price() ; / for (k = 0; k hour; k+) / / cout power0k - power1k ; / / cout endl; fout get_total_price() ; for (k = 0; k hour; k+) fout power0k - power1k ; fout endl; else / 繼續(xù)遞歸求解 fun(i + 1); 附錄 2 2.1 初始化個(gè)參數(shù) % IEEE118BusData 遺傳算法計(jì)算 %分段增量總發(fā)電量 54*5 rp = 10 15 20 25 30 10 15 20 25 30 10 15 20 25 30 180 210 240 270 300 140 180 220 260 300 14 18 22 26 30 40 55 70 85 100 10 15 20 25 30 10 15 20 25 30 140 180 220 260 300 150 200 250 300 350 12.4 16.8 21.2 25.6 30 12.4 16.8 21.2 25.6 30 40 55 70 85 100 12.4 16.8 21.2 25.6 30 40 55 70 85 100 12.4 16.8 21.2 25.6 30 12.4 16.8 21.2 25.6 30 40 55 70 85 100 90 130 170 210 250 90 130 170 210 250 40 55 70 85 100 40 55 70 85 100 80 110 140 170 200 80 110 140 170 200 40 55 70 85 100 164 228 292 356 420 164 228 292 356 420 124 168 212 256 300 40 50 60 70 80 14 18 22 26 30 10 15 20 25 30 8 11 14 17 20 40 55 70 85 100 40 55 70 85 100 180 210 240 270 300 40 55 70 85 100 14 18 22 26 30 140 180 220 260 300 80 110 140 170 200 10.4 12.8 15.2 17.6 20 26 32 38 44 50 140 180 220 260 300 140 180 220 260 300 140 180 220 260 300 10.4 12.8 15.2 17.6 20 40 55 70 85 100 40 55 70 85 100 10.4 12.8 15.2 17.6 20 30 35 40 45 50 40 55 70 85 100 40 55 70 85 100 40 55 70 85 100 30 35 40 45 50; % 分段增量總成本 54*5 cp = 26.94 27.985 28.682 29.379 30.075 26.94 27.985 28.682 29.379 30.075 26.94 27.985 28.682 29.379 30.075 14.845 17.129 17.781 18.434 19.086 14.41 16.368 17.238 18.108 18.978 27.219 28.473 29.03 29.588 30.145 18.332 19.036 19.42 19.804 20.188 26.94 27.985 28.682 29.379 30.075 26.94 27.985 28.682 29.379 30.075 14.41 16.368 17.238 18.108 18.978 11.21 11.81 12.11 12.41 12.71 27.108 28.278 28.891 29.504 30.117 27.108 28.278 28.891 29.504 30.117 18.332 19.036 19.42 19.804 20.188 27.108 28.278 28.891 29.504 30.117 18.332 19.036 19.42 19.804 20.188 27.108 28.278 28.891 29.504 30.117 27.108 28.278 28.891 29.504 30.117 18.332 19.036 19.42 19.804 20.188 12.546 12.858 13.05 13.242 13.435 12.546 12.858 13.05 13.242 13.435 18.332 19.036 19.42 19.804 20.188 18.332 19.036 19.42 19.804 20.188 13.642 14.126 14.39 14.654 14.918 13.642 14.126 14.39 14.654 14.918 18.332 19.036 19.42 19.804 20.188 10.076 12.491 13.846 15.202 16.557 10.076 12.491 13.846 15.202 16.557 14.236 16.063 17.02 17.977 18.934 17.308 19.604 20.522 21.441 22.359 27.219 28.473 29.03 29.588 30.145 26.94 27.985 28.682 29.379 30.075 37.923 38.235 38.404 38.574 38.744 18.332 19.036 19.42 19.804 20.188 18.332 19.036 19.42 19.804 20.188 14.845 17.129 17.781 18.434 19.086 18.332 19.036 19.42 19.804 20.188 27.219 28.473 29.03 29.588 30.145 11.18 11.72 11.96 12.2 12.44 13.758 14.954 15.606 16.259 16.911 37.991 38.353 38.489 38.625 38.761 23.196 23.509 23.626 23.744 23.861 14.41 16.368 17.238 18.108 18.978 14.41 16.368 17.238 18.108 18.978 14.41 16.368 17.238 18.108 18.978 37.991 38.353 38.489 38.625 38.761 18.332 19.036 19.42 19.804 20.188 18.332 19.036 19.42 19.804 20.188 37.991 38.353 38.489 38.625 38.761 23.235 23.578 23.675 23.773 23.871 18.332 19.036 19.42 19.804 20.188 18.332 19.036 19.42 19.804 20.188 18.332 19.036 19.42 19.804 20.188 23.235 23.578 23.675 23.773 23.871; % 發(fā)電機(jī)組的空載成本 54*1 load0 = 31.67 31.67 31.67 6.78 6.78 31.67 10.15 31.67 31.67 6.78 32.96 31.67 31.67 10.15 31.67 10.15 31.67 31.67 10.15 28 28 10.15 10.15 基于遺傳算法的機(jī)組組合問(wèn)題的建模與求解 39 39 10.15 64.16 64.16 6.78 74.33 31.67 31.67 17.95 10.15 10.15 6.78 10.15 31.67 32.96 6.78 17.95 58.81 6.78 6.78 6.78 17.95 10.15 10.15 17.95 58.81 10.15 10.15 10.15 58.81; %1*54 發(fā)電機(jī)組的最小出力 P_MIN=5 5 5 150 100 10 25 5 5 100 100 8 8 25 8 25 8 8 25 50 50 25 25 50 50 25 100 100 80 30 10 5 5 25 25 150 25 10 100 50 8 20 100 100 100 8 25 25 8 25 25 25 25 25; %1*54 發(fā)電機(jī)組的最大出力 P_MAX=30 30 30 300 300 30 100 30 30 300 350 30 30 100 30 100 30 30 100 250 250 100 100 200 200 100 420 420 300 80 30 30 20 100 100 300 100 30 300 200 20 50 300 300 300 20 100 100 20 50 100 100 100 50; % 發(fā)電機(jī)組的最大增出力 PCMAX = 15 15 15 150 150 15 50 15 15 150 175 15 15 50 15 50 15 15 50 125 125 50 50 100 100 50 210 210 150 40 15 15 10 50 50 150 50 15 150 100 10 25 150 150 150 10 50 50 10 25 50 50 50 25; %發(fā)電機(jī)組的最大減出力 PDMAX = 15 15 15 150 150 15 50 15 15 150 175 15 15 50 15 50 15 15 50 125 125 50 50 100 100 50 210 210 150 40 15 15 10 50 50 150 50 15 150 100 10 25 150 150 150 10 50 50 10 25 50 50 50 25; %發(fā)電機(jī)組的初始發(fā)電量 ini_power = 5 5 5 150 100 10 25 5 5 100 100 8 8 25 8 25 8 8 25 50 50 25 25 50 50 25 100 100 80 30 10 5 5 25 25 150 25 10 100 50 8 20 100 100 100 8 25 25 8 25 25 25 25 25; %發(fā)電機(jī)組的初始工作時(shí)間 ini_time = 1 1 1 8 8 1 5 1 1 8 8 1 1 5 1 5 1 1 5 8 8 5 5 10 10 5 10 10 10 4 1 1 1 5 510 5 1 10 10 1 1 8 8 8 1 5 5 1 2 5 5 5 2; %發(fā)電機(jī)組的最小運(yùn)行時(shí)間 min_r_time = 1 1 1 8 8 1 5 1 1 8 8 1 1 5 1 5 1 1 5 8 8 5 5 8 8 5 10 10 8 4 1 1 1 5 5 8 5 1 8 8 1 1 8 8 8 1 5 5 1 2 5 5 5 2; %發(fā)電機(jī)組的最小停運(yùn)時(shí)間 min_s_time = 1 1 1 8 8 1 5 1 1 8 8 1 1 5 1 5 1 1 58 8 5 5 8 8 5 10 10 8 4 1 1 1 5 5 8 5 1 8 8 1 1 8 8 8 1 5 5 1 2 5 5 5 2; %發(fā)電機(jī)組的啟動(dòng)成本 start_money = 40 40 40 440 110 40 50 40 40 100 100 40 40 50 40 50 40 40 59 100 100 50 50 100 100 50 250 250 100 4