基于遺傳算法的機(jī)組組合問題的建模與求解論文

1、基于遺傳算法的機(jī)組組合問題的建模與求解-論文基于遺傳算法的機(jī)組組合問題的建模與求解本文針對當(dāng)前科技水平不足以有效存儲電力的情況下產(chǎn)生的發(fā)電機(jī)機(jī)組組合的問題，考慮負(fù)荷平衡、輸電線傳輸容量限制等實(shí)際情況產(chǎn)生的約束條件，建立機(jī)組組合優(yōu)化模型，追求發(fā)電成本最小。同時(shí)采用矩陣實(shí)數(shù)編碼遺傳算法（MRCGA）和窮舉搜索算法，利用MATLAB 7.0.1和C+編程，分別對模型進(jìn)行求解，并對所得結(jié)果進(jìn)行分析比較，以此來幫助電力部門制定機(jī)組啟停計(jì)劃。首先，建立發(fā)電成本最小目標(biāo)函數(shù)和各項(xiàng)約束條件的數(shù)學(xué)表達(dá)式。其中機(jī)組空載成本和增量成本之和隨該機(jī)組發(fā)電出力增長呈折線關(guān)系，在分析計(jì)算時(shí)為了簡便，本文采用一條平滑的二次曲

2、線來近似代替。對于問題1，選取相應(yīng)的約束條件對目標(biāo)函數(shù)進(jìn)行約束，從而給出優(yōu)化模型。由于問題1的求解規(guī)模很小，所以采用窮舉搜索算法，利用C+編程求解，得到了3母線系統(tǒng)4小時(shí)的最優(yōu)機(jī)組組合計(jì)劃（見表一）。對于問題2，在優(yōu)化模型的基礎(chǔ)上，增加最小穩(wěn)定運(yùn)行出力約束、機(jī)組啟動和停運(yùn)時(shí)的出力約束以及機(jī)組最小運(yùn)行時(shí)間和最小停運(yùn)時(shí)間約束這三個約束條件，建立了優(yōu)化模型II。同時(shí)采用遺傳算法和窮舉搜索算法，利用MATLAB和C+編程，分別對模型進(jìn)行求解，部分結(jié)果如下：發(fā)電總成本（單位：元）矩陣實(shí)數(shù)編碼遺傳算法6780窮舉搜索算法6820在對所得結(jié)果進(jìn)行了分析比較，重新制定了3母線系統(tǒng)4小時(shí)最優(yōu)機(jī)組組合計(jì)劃（見表三

3、）。對于問題3，用IEEE118系統(tǒng)對優(yōu)化模型II進(jìn)行測試。由于求解規(guī)模巨大，同樣采用遺傳算法和窮舉搜索算法，利用MATLAB和C+編程，分別對模型進(jìn)行求解，部分結(jié)果如下：發(fā)電總成本（單位：百萬）矩陣實(shí)數(shù)編碼遺傳算法2.034窮舉搜索算法2.135在對所得結(jié)果進(jìn)行比較時(shí)發(fā)現(xiàn)對于大規(guī)模問題，遺傳算法優(yōu)勢明顯，將其求解結(jié)果作為24小時(shí)的最優(yōu)機(jī)組組合計(jì)劃（見附錄）。最后，我們就模型存在的不足之處提出了改進(jìn)方案，并對優(yōu)缺點(diǎn)進(jìn)行了分析。關(guān)鍵字 機(jī)組組合優(yōu)化模型 矩陣實(shí)數(shù)編碼遺傳算法 窮舉搜索算法一、問題的提出當(dāng)前的科學(xué)技術(shù)還不能有效地存儲電力，所以電力生產(chǎn)和消費(fèi)在任何時(shí)刻都要相等，否則就會威脅電力系統(tǒng)安

4、全運(yùn)行。為了能夠?qū)崟r(shí)平衡變化劇烈的電力負(fù)荷，電力部門往往需要根據(jù)預(yù)測的未來電力負(fù)荷安排發(fā)電機(jī)組起停計(jì)劃，在滿足電力系統(tǒng)安全運(yùn)行條件下，追求發(fā)電成本最小。在沒有電力負(fù)荷損耗以及一個小時(shí)之內(nèi)的電力負(fù)荷和發(fā)電機(jī)出力均不變的前提下，假定所有發(fā)電機(jī)組的發(fā)電成本都是由3部分組成:1.啟動成本（Startup Cost），2.空載成本（No load cost），3.增量成本（Incremental Cost）。需要考慮的約束有: 1負(fù)荷平衡約束2系統(tǒng)備用約束3輸電線路傳輸容量約束4發(fā)電機(jī)組出力范圍約束5機(jī)組增出力約束6機(jī)組降出力約束。問題1：3母線系統(tǒng)有一個3母線系統(tǒng)，其中有2臺機(jī)組、1個負(fù)荷和3條輸電線

5、路，已知4個小時(shí)的負(fù)荷和系統(tǒng)備用要求。請求出這4個小時(shí)的最優(yōu)機(jī)組組合計(jì)劃。最終結(jié)果應(yīng)該包括總成本、各小時(shí)各機(jī)組的狀態(tài)、各小時(shí)各機(jī)組的發(fā)電出力和各小時(shí)各機(jī)組提供的備用。 問題2：3母線系統(tǒng)在問題1的基礎(chǔ)上，考慮發(fā)電機(jī)組的下列物理特性約束:1.發(fā)電機(jī)組的穩(wěn)定出力范圍約束2.機(jī)組啟動時(shí)的出力約束3.機(jī)組停運(yùn)時(shí)的出力約束4.機(jī)組最小運(yùn)行時(shí)間約束5.機(jī)組最小停運(yùn)時(shí)間約束。重新制定最優(yōu)機(jī)組組合計(jì)劃。問題3：IEEE 118系統(tǒng)用IEEE118節(jié)點(diǎn)的電力系統(tǒng)對問題2的求解模型進(jìn)行測試，試求出24個小時(shí)的最優(yōu)機(jī)組組合計(jì)劃。最終結(jié)果應(yīng)該包括總成本、各小時(shí)各機(jī)組的狀態(tài)、各小時(shí)各機(jī)組的發(fā)電出力和各小時(shí)各機(jī)組提供的備

6、用。 二、問題的分析機(jī)組優(yōu)化組合和優(yōu)化啟停就是要在滿足約束條件的情況下，優(yōu)化地選定各時(shí)段參加運(yùn)行的機(jī)組，求出機(jī)組的最佳運(yùn)行方案，實(shí)現(xiàn)發(fā)電成本最小。然而，機(jī)組組合問題是一個多變量、多約束的混合整數(shù)非線性規(guī)劃問題。針對此類問題的求解，數(shù)學(xué)類優(yōu)化方法如線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等，都存在明顯不足之處。而采用智能優(yōu)化算法對此問題的研究較多，主要包括遺傳算法、模擬退火算法、禁忌搜索、人工神經(jīng)網(wǎng)絡(luò)、模糊優(yōu)化等算法。其中模擬退火算法收斂速度慢、禁忌搜索算法對初始解依賴性較強(qiáng)、人工神經(jīng)網(wǎng)絡(luò)算法存在網(wǎng)絡(luò)合適的隱含層數(shù)目和節(jié)點(diǎn)數(shù)目難以確定、模糊優(yōu)化方法的隸屬函數(shù)和模糊推理規(guī)則的確定較困難。鑒于遺傳算法作為一種

7、新的全局 優(yōu)化搜索算法，以其簡單通用、魯棒性強(qiáng)、適于并行處理及應(yīng)用范圍廣等顯著特點(diǎn)，本文采用基于矩陣實(shí)數(shù)編碼遺傳算法來解決機(jī)組組合問題?？梢詫⒄麄€問題分為以下兩個任務(wù)來完成：一、建立機(jī)組組合問題的數(shù)學(xué)模型二、采用窮舉搜索法和遺傳算法，利用C+或者M(jìn)ATLAB編程，求解模型，得到最優(yōu)機(jī)組組合計(jì)劃由于題目中的三個問題所考慮的約束條件復(fù)雜程度不同，發(fā)電機(jī)組數(shù)與負(fù)荷情況也不相同，本文將三個問題逐一建立模型并求解：問題1根據(jù)負(fù)荷平衡、系統(tǒng)備用、輸電線路傳輸容量、發(fā)電機(jī)組出力范圍、機(jī)組增出力、機(jī)組降出力等約束建立優(yōu)化模型I，采用窮舉搜索算法，利用C+編程進(jìn)行求解。問題2和問題3在問題1的基礎(chǔ)上，增加機(jī)組啟

8、動和停運(yùn)時(shí)的出力、機(jī)組最小運(yùn)行時(shí)間和最小停運(yùn)時(shí)間約束條件，建立了優(yōu)化模型II，采用窮舉搜索法和遺傳算法，分別利用C+和MATLAB編程進(jìn)行求解。三、模型假設(shè)和符號系統(tǒng)3.1 模型假設(shè)1. 假設(shè)系統(tǒng)不存在電力負(fù)荷損耗2. 假設(shè)一個小時(shí)之內(nèi)的電力負(fù)荷和發(fā)電機(jī)出力均不變3. 假設(shè)參加交叉運(yùn)算的染色體個數(shù)占全體染色體總數(shù)的比例為0.40.994. 假設(shè)發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例為0.00010.13.2 符號系統(tǒng)為機(jī)組 在 時(shí)段的運(yùn)行狀態(tài)， 為機(jī)組 的啟動成本為機(jī)組 在 時(shí)段的發(fā)電成本為機(jī)組 在 時(shí)段的出力；為負(fù)荷 在 時(shí)段的負(fù)荷量；為發(fā)電機(jī)組 的最大出力；810基于遺傳算法的

9、機(jī)組組合問題的建模與求解為 時(shí)段系統(tǒng)備用要求；為線路 上流過的電能；為第 根輸電線路第 條母線的線性傳輸因子；為母線 上的注入功率；為第根輸電線路的最大傳輸容量；發(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ā)電出力增長走勢圖在分析計(jì)算時(shí)為了簡便，通常用一條平滑曲線來近似代替有起伏的部分成本特性，如圖一中平畫曲線所示。當(dāng)n段直線近似

10、表示時(shí)，部分成本特性可表示為 （1）2)啟動成本 （2）其中： 為機(jī)組 在 時(shí)段的運(yùn)行狀態(tài)， 為機(jī)組 的啟動成本3)目標(biāo)函數(shù)機(jī)組組合的目的是針對在指定的周期內(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ī)組臺數(shù)為 ，則該問題的目標(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í)段的

11、出力；為負(fù)荷 在 時(shí)段的負(fù)荷量；2)系統(tǒng)備用約束任何時(shí)段，發(fā)電機(jī)的備用容量之和必須大于系統(tǒng)備用要求。 （5）其中： 為發(fā)電機(jī)組 的最大出力；為 時(shí)段系統(tǒng)備用要求；3)輸電線路傳輸容量約束線路傳輸?shù)碾娔鼙仨氃谒膫鬏斎萘糠秶鷥?nèi)。 （6）其中： 為線路 上流過的電能；為第 根輸電線路第 條母線的線性傳輸因子；為母線 上的注入功率；為第根輸電線路的最大傳輸容量；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í)，增加出力的速度要小于其最

12、大增出力；發(fā)電機(jī)組在減少發(fā)電出力時(shí)，減少出力的速度要小于其最大減出力。 （8）其中： 為機(jī)組 最大減出力；為機(jī)組 最大增出力；6)機(jī)組啟動和停運(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ī)組每次啟動后，連續(xù)運(yùn)行時(shí)間至少為該臺機(jī)組的最小運(yùn)行時(shí)間。機(jī)組每次停運(yùn)后，連續(xù)停運(yùn)時(shí)間至少為該臺機(jī)組的最小停運(yùn)時(shí)間。 （10） （11）其中： 為機(jī)組 最小運(yùn)行時(shí)間；為機(jī)組 最小停運(yùn)時(shí)間；4.2模型及其求解問題11）優(yōu)化模型問題1中的3

13、母線系統(tǒng)僅考慮負(fù)荷平衡約束 系統(tǒng)備用約束、輸電線路傳輸容量約束、發(fā)電機(jī)組出力范圍約束與穩(wěn)定出力范圍約束和機(jī)組增降出力約束，所建優(yōu)化方程模型如下。 （12） （13）其中： 為機(jī)組 在 時(shí)段的發(fā)電成本； 為機(jī)組 的啟動成本；2)優(yōu)化模型的求解算法機(jī)組組合問題在數(shù)學(xué)規(guī)劃上屬于NP完全問題，任何NP完全問題只有通過列舉所有可能的組合，才能得到最優(yōu)解，即采用窮舉搜索法。由于問題1的求解規(guī)模不大，所以該問題將采用窮舉搜索法對模型進(jìn)行求解。我們設(shè)置一計(jì)數(shù)器 （ ）用以記錄機(jī)組已運(yùn)行的時(shí)間。 讀取各機(jī)組和負(fù)荷的原始數(shù)據(jù)。另 。 設(shè)置機(jī)組1的第 小時(shí)的出力大?。◤男〉酱笠来嗡阉?，跨度為1），使其出力大小的變化

14、滿足增出力約束和降出力約束。 判斷機(jī)組1是否滿足其出力范圍約束。若滿足則繼續(xù)下一步，否則，重復(fù)基于遺傳算法的機(jī)組組合問題的建模與求解步驟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，若是則輸出該種情況下兩臺機(jī)組各時(shí)段出力大 小，否則重復(fù)步驟2、3、4、5、

15、6、7，另 。直到所有的情況搜索完畢為止。執(zhí)行完該算法，可以得到一最優(yōu)機(jī)組組合計(jì)劃。3)模型求解與分析我們根據(jù)上面的算法步驟，我們編C+程序（附錄1），并代入各機(jī)組和負(fù)荷的初始數(shù)據(jù)?？梢缘玫揭豢偝杀緸?580￥的最優(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)1000備用(MW)10002狀態(tài)運(yùn)行關(guān)機(jī)出力(MW)1300備用(MW)7003狀態(tài)運(yùn)行運(yùn)行出力(MW)13040備用(MW)70604狀態(tài)運(yùn)行關(guān)機(jī)出力(MW)1400備用(MW)600總成本(￥)6580使用窮舉搜索法對該問題雖然能得出結(jié)果，但其運(yùn)行效率太低，不能用于求解大

16、規(guī)模問題，且編程實(shí)現(xiàn)較復(fù)雜，不是一種優(yōu)良的算法。問題2和問題31）優(yōu)化模型問題2和問題3的優(yōu)化模型為 （14） （15）2）求解算法對于問題2和3，我們同時(shí)采用窮舉搜索法和遺傳算法兩種算法進(jìn)行求解，并將求得結(jié)果進(jìn)行比較，以比較兩種算法的優(yōu)劣。窮舉搜索法的算法思想與問題1的求解算法思想一致。遺傳算法的流程圖如圖二所示。 圖二 遺傳算法流程圖矩陣實(shí)數(shù)編碼遺傳算法的描述： 針對機(jī)組組合問題的矩陣實(shí)數(shù)編碼本文以要安排發(fā)電機(jī)組起停計(jì)劃作為遺傳算法中的個體，采用實(shí)數(shù)矩陣形式進(jìn)行編碼。其具體形式為 （16）其中： 為遺傳種群中的第 個個體為編碼矩陣中的第 行第 列元素，含義為發(fā)電機(jī)組 在 時(shí)段的發(fā)電出力為編

17、碼矩陣中的第 個列向量，含義為 時(shí)段內(nèi)發(fā)電機(jī)組間的負(fù)荷分配情況為編碼矩陣中的第 個行向量，含義為發(fā)電機(jī)組 在發(fā)電計(jì)劃制定周期內(nèi)的出力過程發(fā)電機(jī)組的運(yùn)行狀態(tài)取決于矩陣中元素的具體取值，即根據(jù)機(jī)組在某時(shí)段中的出力大小來確定啟停狀態(tài)，具體表達(dá)式為 （17） 遺傳種群初始化遺傳種群初始化時(shí)，按編碼矩陣中列向量的順序進(jìn)行。以 中 為例，初始過程如下：（1）生成服從均勻分布的隨機(jī)數(shù)數(shù)組 （18）其中： 為在發(fā)電機(jī)組 最大最小出力之間隨機(jī)生成的正數(shù)（2）計(jì)算百分比系數(shù)數(shù)組 （19）其中： （3）初始化各臺發(fā)電機(jī)組的出力，即初始化 基于遺傳算法的機(jī)組組合問題的建模與求解其中： 為負(fù)荷 在 時(shí)段的負(fù)荷量 個體調(diào)

18、整方法在進(jìn)行個體調(diào)整時(shí)按列向量的先后順序進(jìn)行。以個體 中 為例，具體調(diào)整措施如下：（1）根據(jù)機(jī)組組合問題對精度的要求，對 列中的各個元素保留（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ī)組

19、最大增出力（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)過上述三步調(diào)整后， 列中所有元素的總和可能不等于 時(shí)段中的系統(tǒng)總負(fù)荷。因此要進(jìn)行負(fù)荷分配的調(diào)整。具體的調(diào)整辦法為：當(dāng) 時(shí)，通過增加運(yùn)行發(fā)電機(jī)組出力來滿足負(fù)荷平衡約束；反之，若 ，則降低運(yùn)行發(fā)電機(jī)組的出力。此步調(diào)整中，只能在發(fā)電機(jī)組的最大出力允許范圍內(nèi)進(jìn)行調(diào)整，不能改變機(jī)組的運(yùn)行狀態(tài)。（6）算法趨于收斂時(shí)，若發(fā)電機(jī)組的出力過程不滿足最小運(yùn)行、停運(yùn)時(shí)間約束條件，則通過調(diào)整違反約束發(fā)電機(jī)組的運(yùn)行狀態(tài)

20、滿足此項(xiàng)約束條件，即： 時(shí)，延長發(fā)電機(jī)組 的運(yùn)行時(shí)間； 時(shí)，采用將發(fā)電機(jī)組 違反約束的全部停運(yùn)狀態(tài)轉(zhuǎn)變?yōu)檫\(yùn)行狀態(tài)的方式來滿足約束條件，并令相應(yīng)的出力為機(jī)組 的最小出力。其中： 為機(jī)組 最小運(yùn)行時(shí)間；為機(jī)組 最小停運(yùn)時(shí)間； 適度函數(shù)的選取采用個體調(diào)整方法后，在求解的過程中只有發(fā)電機(jī)組的最小運(yùn)行、停運(yùn)時(shí)間約束條件可能得不到滿足。為了加快算法收斂，本文的適度函數(shù)采用如下形式： （23）其中： 為發(fā)電機(jī)組 違反最小運(yùn)行或停運(yùn)時(shí)間約束條件時(shí)的懲罰量，本文取 為機(jī)組 的啟動成本； 為懲罰因子，本文取 ； 為違反此項(xiàng)約束的次數(shù)； 為正常數(shù)，本文取 。其含義為：發(fā)電機(jī)組 違反1次最小運(yùn)行時(shí)間或停運(yùn)時(shí)間約束，便

21、以機(jī)組 的 倍的啟動成本 進(jìn)行懲罰。 選擇復(fù)制（1）群體中各個體的選擇概率選擇概率的計(jì)算公式為： （24）其中： 為第 個體的選擇概率為第 個個體，即本文中機(jī)組 各個時(shí)段的發(fā)電出力（2）賭輪選擇法賭輪選擇法用下面的子過程來模擬： 在 區(qū)間內(nèi)產(chǎn)生一個均勻分布的隨機(jī)數(shù) ； 若 ,則染色體 被選中； 若 , 則染色體 被選中。其中 稱為染色體 的積累概率, 其計(jì)算公式為 （25） 交叉通過 在父代中選擇交配個體后，將準(zhǔn)備進(jìn)行交叉操作的父代個體表示為 （26）交叉操作產(chǎn)生的個體記為 、 ，保留到子代中的個體記為 、 。本文的交叉操作是在2個父代個體奇數(shù)列與偶數(shù)列之間進(jìn)行的。具體操作過程為：（1）生成隨

22、機(jī)數(shù) ；生成隨機(jī)交叉位 。（2）交叉操作生成個體 、 ，其表達(dá)式為 （27）（3）對交叉生成的個體依照 個體調(diào)整方法進(jìn)行個體調(diào)整，然后計(jì)算出 、 的適度值。（4）采用局部錦標(biāo)賽選擇法在父代個體和交叉產(chǎn)生的個體間進(jìn)行子代選擇，具體方法如下： （28） 變異通過 個體交叉后，將準(zhǔn)備進(jìn)行變異的父代個體表示為 （29）變異后產(chǎn)生的個體記為 、 ，保留到子代中的個體記為 、 。本文只對某列進(jìn)行變異處理。具體操作過程為：（1） 生成隨機(jī)變異因子 ；生成隨機(jī)變異時(shí)段 ；生成隨機(jī)變異個體選擇因子 （2）變異后生成個體 、 ，其表達(dá)式為 （30）（3）對變異后生成的個體依照 個體調(diào)整方法進(jìn)行個體調(diào)整，然后計(jì)算出

23、 、 的適度值。（4）采用局部錦標(biāo)賽選擇法在父代個體和變異產(chǎn)生的個體間進(jìn)行子代選擇，具體方法如下： （31） 終止條件遺傳算法的終止條件有兩類常見條件：第一類：采用設(shè)定最大遺傳代數(shù)的方法，一般可設(shè)為50代，此時(shí)就可能得出最優(yōu)解。第二類：根據(jù)個體的差異來判斷，通過計(jì)算種群中基因多樣性測度，即所有基因位基于遺傳算法的機(jī)組組合問題的建模與求解相似程度來進(jìn)行控制。本文采用第一類方法，將 、 個體依照 個體調(diào)整方法進(jìn)行個體調(diào)整，然后計(jì)算出對應(yīng)的適度值，直到第 代，循環(huán)迭代結(jié)束，輸出最優(yōu)解Tc0。3)模型求解利用窮舉搜索法和遺傳算法可以分別求解問題1和2。問題2利用C+程序?qū)ΩF舉搜索法進(jìn)行實(shí)現(xiàn)，然后求解，

24、所得結(jié)果如表二所示。表二 問題二窮舉搜索法求解結(jié)果機(jī)組G1機(jī)組G2小時(shí)1狀態(tài)運(yùn)行關(guān)機(jī)出力(MW)1000備用(MW)10002狀態(tài)運(yùn)行運(yùn)行出力(MW)11020備用(MW)90803狀態(tài)運(yùn)行運(yùn)行出力(MW)11060備用(MW)90404狀態(tài)運(yùn)行運(yùn)行出力(MW)10040備用(MW)10060總成本(￥)6820利用MATLAB程序?qū)z傳進(jìn)行實(shí)現(xiàn)，然后求解。由于遺傳算法具有隨機(jī)性，所程序每次運(yùn)行所得的結(jié)果有略微差別，我們從多次運(yùn)行的解中選取總成本最小的一組機(jī)組組合計(jì)劃，結(jié)果如表三所示。表三 問題二遺傳算法求解結(jié)果機(jī)組G1機(jī)組G2小時(shí)1狀態(tài)運(yùn)行關(guān)機(jī)出力(MW)1000備用(MW)10002狀態(tài)運(yùn)

25、行關(guān)機(jī)出力(MW)1300備用(MW)7003狀態(tài)運(yùn)行運(yùn)行出力(MW)15020備用(MW)50804狀態(tài)運(yùn)行運(yùn)行出力(MW)12020備用(MW)8080總成本(￥)6780從問題2兩種算法的求解結(jié)果中我們可以發(fā)現(xiàn)，遺傳算法的求解結(jié)果優(yōu)于窮舉搜索法，但遺傳算法有一定的隨機(jī)性，有時(shí)需多運(yùn)行幾次才能得到最優(yōu)解。且遺傳算法比窮舉搜索法更容易實(shí)現(xiàn)。問題3利用窮舉搜索法和矩陣實(shí)數(shù)編碼遺傳算法分別求解問題3。窮舉搜索法求解結(jié)果見附錄三。由于矩陣實(shí)數(shù)編碼遺傳算法得到的成本最小值具有一定的隨機(jī)性，且隨算法中迭代次數(shù)的變化而變化，所程序每次運(yùn)行所得的結(jié)果有略微差別。為求得更為精確的結(jié)果，我們變換迭代次數(shù)，以判

26、斷迭代多少次為最優(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í)提供的備用）見附錄五從問題3的求解結(jié)果中，通過不同迭代次數(shù)之間的比較以及窮舉搜索法與矩陣實(shí)數(shù)編碼遺傳算法的對比分析，看出矩陣實(shí)數(shù)編碼遺傳算法在進(jìn)行大規(guī)模機(jī)組組合問題求解時(shí)，具有很強(qiáng)的適應(yīng)性和全局搜索能力，而且系統(tǒng)規(guī)模越大算法的優(yōu)化結(jié)果越理想。因此，矩陣實(shí)數(shù)編碼遺傳算

27、法的求解結(jié)果優(yōu)于窮舉搜索法，但矩陣實(shí)數(shù)編碼遺傳算法有一定的隨機(jī)性，需多運(yùn)行幾次才能得到最優(yōu)解。六、模型的改進(jìn)及評價(jià)6.1模型的改進(jìn)模型改進(jìn)一：機(jī)組組合優(yōu)化模型I與II的改進(jìn)在機(jī)組組合優(yōu)化模型I、II中，通過二次函數(shù)對空載成本和增量成本曲線參數(shù)進(jìn)行擬合過程中，采用二次函數(shù)擬合誤差比較大（增量成本變化幅度比較?。?，特別是機(jī)組規(guī)模比較小的時(shí)候更是如此。鑒于此種情況，當(dāng)機(jī)組規(guī)模比較大時(shí)，可以采取平滑曲線進(jìn)行擬合。如問題三，可以利用二次函數(shù)進(jìn)行擬合，根據(jù)運(yùn)行結(jié)果可以看出誤差更小，機(jī)組啟停更合理，發(fā)電成本更小。此外，當(dāng)機(jī)組規(guī)模相對較小時(shí)，可以不進(jìn)行曲線擬合，直接采取分段函數(shù)，編程求解。如問題一和二，利用C

28、+編程，采取窮舉搜索法求解，精度會更高。模型改進(jìn)二：基于矩陣實(shí)數(shù)編碼遺傳算法的改進(jìn)在矩陣實(shí)數(shù)編碼遺傳算法步驟中，根據(jù)實(shí)際情況（如機(jī)組規(guī)模，時(shí)段等問題）可以對各步驟進(jìn)行優(yōu)化或改進(jìn)。如 變異，本文實(shí)在時(shí)段內(nèi)列向量進(jìn)行的，相當(dāng)于發(fā)電機(jī)組 在不同時(shí)段發(fā)電出力的重新調(diào)整。因此，還可以采用多窗口變異操作【1】。此操作是在個體內(nèi)行向量間進(jìn)行的，相當(dāng)于在不同發(fā)電機(jī)組間進(jìn)行發(fā)電出力的重新調(diào)整。此法具有經(jīng)濟(jì)負(fù)荷分配的功能，并且，由于是同時(shí)進(jìn)行多個時(shí)段的負(fù)荷分配調(diào)整，故執(zhí)行效率較高。當(dāng)然，二者相結(jié)合，效果更佳。6.2模型的評價(jià)優(yōu)點(diǎn)：第一，提供了一種求解多變量、多約束的混合整數(shù)非線性規(guī)劃的機(jī)組組合優(yōu)化問題的思路，此方

29、法新穎可靠易行，極具參考價(jià)值。第二，采用MRCGA算法求解機(jī)組組合問題的新方法。利用二維實(shí)數(shù)矩陣對發(fā)電計(jì)劃安排進(jìn)行編碼，將機(jī)組組合問題轉(zhuǎn)化為單層優(yōu)化問題進(jìn)行求解，因而降低了算法的時(shí)間復(fù)雜度。運(yùn)用個體調(diào)整方法處理各項(xiàng)約束條件，確保了優(yōu)化結(jié)果的可行性，使該算法更易于應(yīng)用實(shí)際。第三， 矩陣實(shí)數(shù)編碼遺傳算法（MRCGA）適合求解大規(guī)模機(jī)組組合問題。通過MATLAB仿真計(jì)算、不同迭代次數(shù)比較分析以及同其他方法（如窮舉法）的對比分析，驗(yàn)證了該方法在進(jìn)行大規(guī)模機(jī)組組合問題求解時(shí)，具有很強(qiáng)的適應(yīng)性和全局搜索能力，而且系統(tǒng)規(guī)模越大算法的優(yōu)化結(jié)果越理想。缺點(diǎn)：第一，采用二次函數(shù)對空載成本和增量成本曲線參數(shù)進(jìn)行擬合

30、過程中，擬合誤差比較大。特別是機(jī)組規(guī)模比較小時(shí)更是如此。第二，MRCGA算法對小規(guī)模機(jī)組組合問題求解結(jié)果精度不高，誤差大。參考文獻(xiàn)：1 劉瓊蓀，龔劬，何中市，傅鸝，任善強(qiáng)，數(shù)學(xué)實(shí)驗(yàn)，北京：高等教育出版社，20042 姜啟源，謝金星，葉俊，數(shù)學(xué)模型，北京：高等教育出版社，20063 孫力勇，張焰，蔣傳文，基于矩陣實(shí)數(shù)編碼遺傳算法求解大規(guī)模機(jī)組組合問題，中國機(jī)電工程學(xué)報(bào)，第26卷（2期），20064 趙東方，數(shù)學(xué)模型與計(jì)算，北京：科學(xué)出版社，2007基于遺傳算法的機(jī)組組合問題的建模與求解附錄1 問題1的C+求解程序#include #include using namespace std;doub

31、le 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;/ 啟動費(fèi)用int start2 = 350, 100;/ 機(jī)組

32、各時(shí)段狀態(tài)int power25 = 100, 0;/ 系統(tǒng)備用要求int b_powerhour = 0, 20, 30, 50, 40;/ 最小費(fèi)用int minprice = ;int main()fun(1);return 0;/ 機(jī)組1成本double cost1(double x)if (x = 100)return 100 + 10*x;elsereturn 14*x - 300;/ 機(jī)組2成本double cost2(double x)if (x = 60)return 12*x + 200;elsereturn 15*x + 20;/ 總成本int get_total_pri

33、ce()int i = 0, j;double price = 0;for (j = 1; j hour; j+)price += stateij*cost1(powerij)+ stateij*(1-stateij-1)*starti;i = 1;for (j = 1; j price ? price: minprice);/cout minprice ;fout minprice ;return price;void fun(int i)for (int j = -50; j = 30; j+= 1)/ 機(jī)組1power0i = power0i-1 + j;/ 機(jī)組1出力范圍約束if (p

34、ower0i 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;elsestate0i = 0;/ 機(jī)組2狀態(tài)if (power1i 0)state1i = 1;elsestate1i = 0;/ 系統(tǒng)備用約束基于遺傳算法的機(jī)組組合問題的建模與求解int bei = 0;i

35、nt 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

36、2.1 初始化個參數(shù)% IEEE118BusData 遺傳算法計(jì)算%分段增量總發(fā)電量 54*5rp = 10 15 20 25 3010 15 20 25 3010 15 20 25 30180 210 240 270 300140 180 220 260 30014 18 22 26 3040 55 70 85 10010 15 20 25 3010 15 20 25 30140 180 220 260 300150 200 250 300 35012.4 16.8 21.2 25.6 3012.4 16.8 21.2 25.6 3040 55 70 85 10012.4 16.8 21.2

37、 25.6 3040 55 70 85 10012.4 16.8 21.2 25.6 3012.4 16.8 21.2 25.6 3040 55 70 85 10090 130 170 210 25090 130 170 210 25040 55 70 85 10040 55 70 85 10080 110 140 170 20080 110 140 170 20040 55 70 85 100164 228 292 356 420164 228 292 356 420124 168 212 256 30040 50 60 70 8014 18 22 26 3010 15 20 25 308

38、11 14 17 2040 55 70 85 10040 55 70 85 100180 210 240 270 30040 55 70 85 10014 18 22 26 30140 180 220 260 30080 110 140 170 20010.4 12.8 15.2 17.6 2026 32 38 44 50140 180 220 260 300140 180 220 260 300140 180 220 260 30010.4 12.8 15.2 17.6 2040 55 70 85 10040 55 70 85 10010.4 12.8 15.2 17.6 2030 35 4

39、0 45 5040 55 70 85 10040 55 70 85 10040 55 70 85 10030 35 40 45 50;% 分段增量總成本 54*5cp = 26.94 27.985 28.682 29.379 30.07526.94 27.985 28.682 29.379 30.07526.94 27.985 28.682 29.379 30.07514.845 17.129 17.781 18.434 19.08614.41 16.368 17.238 18.108 18.97827.219 28.473 29.03 29.588 30.14518.332 19.036 1

40、9.42 19.804 20.18826.94 27.985 28.682 29.379 30.07526.94 27.985 28.682 29.379 30.07514.41 16.368 17.238 18.108 18.97811.21 11.81 12.11 12.41 12.7127.108 28.278 28.891 29.504 30.11727.108 28.278 28.891 29.504 30.11718.332 19.036 19.42 19.804 20.18827.108 28.278 28.891 29.504 30.11718.332 19.036 19.42

41、 19.804 20.18827.108 28.278 28.891 29.504 30.11727.108 28.278 28.891 29.504 30.11718.332 19.036 19.42 19.804 20.18812.546 12.858 13.05 13.242 13.43512.546 12.858 13.05 13.242 13.43518.332 19.036 19.42 19.804 20.18818.332 19.036 19.42 19.804 20.18813.642 14.126 14.39 14.654 14.91813.642 14.126 14.39

42、14.654 14.91818.332 19.036 19.42 19.804 20.18810.076 12.491 13.846 15.202 16.55710.076 12.491 13.846 15.202 16.55714.236 16.063 17.02 17.977 18.93417.308 19.604 20.522 21.441 22.35927.219 28.473 29.03 29.588 30.14526.94 27.985 28.682 29.379 30.07537.923 38.235 38.404 38.574 38.74418.332 19.036 19.42

43、 19.804 20.18818.332 19.036 19.42 19.804 20.18814.845 17.129 17.781 18.434 19.08618.332 19.036 19.42 19.804 20.18827.219 28.473 29.03 29.588 30.14511.18 11.72 11.96 12.2 12.4413.758 14.954 15.606 16.259 16.91137.991 38.353 38.489 38.625 38.76123.196 23.509 23.626 23.744 23.86114.41 16.368 17.238 18.

44、108 18.97814.41 16.368 17.238 18.108 18.97814.41 16.368 17.238 18.108 18.97837.991 38.353 38.489 38.625 38.76118.332 19.036 19.42 19.804 20.18818.332 19.036 19.42 19.804 20.18837.991 38.353 38.489 38.625 38.76123.235 23.578 23.675 23.773 23.87118.332 19.036 19.42 19.804 20.18818.332 19.036 19.42 19.

45、804 20.18818.332 19.036 19.42 19.804 20.18823.235 23.578 23.675 23.773 23.871;% 發(fā)電機(jī)組的空載成本 54*1load0 = 31.6731.6731.676.786.7831.6710.1531.6731.676.7832.9631.6731.6710.1531.6710.1531.6731.6710.15282810.1510.15基于遺傳算法的機(jī)組組合問題的建模與求解393910.1564.1664.166.7874.3331.6731.6717.9510.1510.156.7810.1531.6732.966

46、.7817.9558.816.786.786.7817.9510.1510.1517.9558.8110.1510.1510.1558.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

47、 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