基于的退火演化算法和遺傳算法

1、實用標(biāo)準(zhǔn)文案基于退火演化算法和遺傳算法的機組優(yōu)化組合算法吳金華，吳耀武，熊信艮（華中科技大學(xué)電力工程系，湖北省武漢市 430074 ）摘 要：機組組合問題是編制短期發(fā)電計劃時首先要解決的問題， 合理的開停機方案將帶來很大的經(jīng)濟效益。 現(xiàn)代電力系統(tǒng)對機組優(yōu)化組合算法的收斂速度和解的質(zhì)量要求越來越高， 作者從改善傳統(tǒng)算法這兩方面著手， 根據(jù)退火演化算法和遺傳算法各自的特點， 提出了一種用于機組優(yōu)化組合的組合算法。 與傳統(tǒng)的一些優(yōu)化算法相比， 該組合算法具有搜索速度快， 收斂性好， 而且解的質(zhì)量相當(dāng)高。通過對實際系統(tǒng)的測算， 驗證了該方法的有效性和優(yōu)越性。 該方法具有良好的并行性，易于在并行計算機上

2、實現(xiàn)。關(guān)鍵詞 ：機組優(yōu)化組合；退火演化算法；遺傳算法；電力系統(tǒng)；并行計算1 引言電力系統(tǒng)的機組組合問題，就是在滿足系統(tǒng)負(fù)荷及備用要求和機組運行的技術(shù)條件約束的情況下， 確定未來一定期間內(nèi)各機組的開停機時間并在機組間分配負(fù)荷，使系統(tǒng)總的運行費用達(dá)到最小。合理的開停機方案能節(jié)省一次能源，延長機組使用壽命， 帶來巨大的經(jīng)濟效益。 據(jù)國外資料和國內(nèi)部分機組的實際測算表明，優(yōu)化組合是編制短期發(fā)電計劃首先要解決的問題，一般而言，其經(jīng)濟效益遠(yuǎn)大于負(fù)荷經(jīng)濟分配所得到效益。從數(shù)學(xué)的角度來講，機組組合問題是一個高維的、非凸的、離散的混合整數(shù)非線性優(yōu)化問題。 當(dāng)系統(tǒng)規(guī)模較大時， 很難找出理論上的最優(yōu)解。 由于它能夠

3、帶來顯著的經(jīng)濟效益，人們一直在積極研究和開發(fā)各種算法來解決這個問題，如優(yōu)先順序法、分支定界法、動態(tài)規(guī)劃法和拉格朗日松弛法等1-4。近年來，對專家系統(tǒng)法、遺傳算法、模擬退火法、人工神經(jīng)網(wǎng)絡(luò)及一些組合算法9 也進行了一些嘗試。在研究基本遺傳算法和退火演化算法的基礎(chǔ)上， 本文提出了一種適合于機組組合的組合算法 9 。在計算過程中，對遺傳算法的適應(yīng)度函數(shù)、 雜交及變異方式作了一些改進，有效地避免了簡單遺傳算法在機組組合問題中的早熟問題，并且提高了收斂速度。2 機組組合問題的數(shù)學(xué)模型設(shè)系統(tǒng)調(diào)度期間的時段數(shù)為 H，系統(tǒng)中機組或等效機組數(shù)為 G，各時段系統(tǒng)總負(fù)荷為 PDt ，則其數(shù)學(xué)描述如下（1）目標(biāo)函數(shù)精

4、彩文檔實用標(biāo)準(zhǔn)文案式中 Fit (Pit ) 為 t 時段 i 機組的運行費用； STi 為 i 機組的啟停費用； STi 為 i 機組的停運時間； Uit 為 i 機組在時段 t 內(nèi)的狀態(tài)， Uit =1 為運行狀態(tài)， Uit =1 為停運狀態(tài)； Pit 為機組 i 在時段 t 內(nèi)的有功功率。（2）機組組合的約束條件在機組組合的過程中，主要的約束條件為1）電力平衡約束2） 單機約束式(2)(4)t為系統(tǒng)在時間 t 的網(wǎng)損； Dt為時間 t 系統(tǒng)總負(fù)荷； k 為備用系中 CP為 i 機組的上、下限出數(shù)； i 為 i機組在計算周期內(nèi)允許啟停的次數(shù)；MOi 為 i 機組的最小運行時間；力； i 為

5、 i機組每時段可加減負(fù)荷的最大值；T為 i 機組的最小停運時間。本文中發(fā)電機組的運行費用采用發(fā)電功率的二次函數(shù)表示，即式中ai 、bi 、ci 為常數(shù)。機組的啟停費用有兩種模型（ 1）冷卻啟動式中K3 為壓火運行一小時的費用。本文中將網(wǎng)損作為常數(shù)處理，即按總負(fù)荷的一定比例（ 7）考慮。更詳細(xì)的模型應(yīng)包括線路潮流限制、 分區(qū)功率平衡、 機組的燃料限制和隨機停運的影響等，但本文模型未考慮這些因素。3 遺傳和退火演化組合算法及其改進3.1基本遺傳算法及其改進遺傳算法（ GA）是一種基于生物界自然選擇和自然遺傳機制的隨機化搜精彩文檔N 個點的初始群體出實用標(biāo)準(zhǔn)文案索算法。在隨機產(chǎn)生的一個初始解群中利用

6、適應(yīng)度函數(shù)衡量各個解的優(yōu)劣， 根據(jù)“優(yōu)勝劣汰” 的準(zhǔn)則選出父輩解群， 通過雜交和變異操作來實現(xiàn)群體內(nèi)個體結(jié)構(gòu)的重組，使群體內(nèi)個體一代一代得以優(yōu)化并逐漸逼近全局最優(yōu)解。本文所提出的算法， 在保留了 GA算法的基本步驟和特點的同時， 作了如下幾點改進。（1）適應(yīng)度函數(shù)比例變換為了避免遺傳算法在搜索初期易產(chǎn)生的“早熟”現(xiàn)象和搜索結(jié)束階段易產(chǎn)生的隨機漫游現(xiàn)象，本文對適應(yīng)度函數(shù)進行了指數(shù)比例變換式中F 為原適應(yīng)度函數(shù)； F' 為變換后的適應(yīng)度函數(shù)，為比例調(diào)整系數(shù)。系數(shù)的值決定選擇的強制性2 ，在搜索初期，賦給一個較小值，來縮小一些超常個體的函數(shù)值以降低異常個體的競爭力；在結(jié)束階段， 則賦給一個相

7、對較大值，來放大相應(yīng)的適應(yīng)度函數(shù)值來提高個體的競爭力。（ 2）雜交概率和變異概率可變在迭代前期，采用較大的雜交概率和較小的變異概率，以提高繁殖效率；在迭代后期， 解群中的碼鏈已趨于穩(wěn)定，此時交叉作用已經(jīng)減小， 雜交概率可降低，而為了防止收斂于局部最優(yōu)解，可增大變異概率。本文借鑒了文獻7 采用的雜交概率和變異概率變化公式（3）網(wǎng)絡(luò)式遺傳操作為了保證算法收斂的穩(wěn)定與快速，采用了一種網(wǎng)絡(luò)式遺傳操作，即在一個總的遺傳算法中采用了多個子遺傳操作。由于技術(shù)限制， 本文在算例中僅采用了兩個子遺傳操作， 在兩個子算法中分別采用不同的雜交、變異方式，形成兩個不同的新解群。3.2退火演化算法及其與遺傳算法結(jié)合退火

8、演化算法（ AEA）是模擬退火算法（ SA）的一種改進算法。為了改善搜索過程，避免落入局部最優(yōu)，基于群體和選擇的思想，退火演化算法（ AEA）采用了一種新的演化策略， 即通過變異和選擇不斷改善一個解的群體， 而不是象普通模擬退火算法那樣采取單點迭代方式，從而大大減小了陷入局部極小的概率，并且可導(dǎo)致快速收斂到全局極小值。本組合算法的基本思想就是：算法首先從一個包含發(fā)，在每個冷卻步上，用遺傳算法作為退火演化算法產(chǎn)生新解的規(guī)則，設(shè)有L個子遺傳操作用來產(chǎn)生新解，這些新解分別采用Metropolis接受準(zhǔn)則被接受或舍棄；經(jīng)過一個冷卻步后，群體規(guī)模則增加到包含NL 個點，按照與這些點的適應(yīng)值成比例的概率從

9、中選擇 N 個個體作為生存集；如果最好的點不在生存集中，則從 N個點中隨機舍棄一個點， 然后把最好的點加入其中， 算法再在一個降低的控制參數(shù)下重復(fù)上述過程。精彩文檔實用標(biāo)準(zhǔn)文案遺傳算法會在每一代中不斷產(chǎn)生新解，用退火演化算法對這些新解群進行檢驗和改善。 隨著計算次數(shù)的增加， 溫度逐漸降低， 接受惡化解的概率逐漸減小，遺傳算法尋優(yōu)朝著更有效的方向進行，由此大大改善了遺傳算法的收斂性。4 組合算法用于機組組合（1）編碼方法采用二進制碼表示機組對應(yīng)狀態(tài) Uit ，對于有 G臺機組，H個時段的情況，一個串長為 L=H G的串就表示了系統(tǒng)在一個調(diào)度周期內(nèi)的機組組合狀態(tài)，在各時段上進行負(fù)荷經(jīng)濟分配之后，得

10、到機組一天的運行情況。（2）約束處理對于功率平衡約束和旋轉(zhuǎn)備用約束，采用罰函數(shù)法以構(gòu)成增廣函數(shù)，適應(yīng)度函數(shù)取為增廣函數(shù)的倒數(shù)。而對各種單機約束則采用硬約束，即當(dāng)超出約束條件時，直接將適應(yīng)值置零。（3）收斂判據(jù)本文在算法迭代的結(jié)果滿足以下兩個條件之一時結(jié)束：1 ）適應(yīng)度最大值大于某一個值且連續(xù)若干代所獲得的最優(yōu)解沒有變化，則認(rèn)為解已成熟收斂；2 ）迭代次數(shù)超過某一個規(guī)定的限值。（4）算法流程1 ）讀入系統(tǒng)和機組的參數(shù)， 初始化 GA、AEA的參數(shù)，令迭代次數(shù)： k=0 ； 2 ）產(chǎn)生初始解群，計算各染色個體的適應(yīng)值；3 ）每一冷卻步， 利用 GA為 AEA產(chǎn)生 L 個新解，每個子 GA算法中分別

11、進行不同遺傳操作，采用 Metropolis 接受準(zhǔn)則對新解進行檢驗，保留優(yōu)良個體。若滿足了收斂判據(jù)，則轉(zhuǎn)入5），否則進入 4）；4 ）AEA算法改善整個解群。轉(zhuǎn)入4），改變控制參數(shù)；5 ）得到并輸出最優(yōu)解。5 算例結(jié)果及分析取控制參數(shù)：群體規(guī)模N；0.001；選擇策略：；=80=0.900R=E最大迭代次數(shù)： Max=100；初始溫度： T=1000K；溫度系數(shù)： ? =0.96 。對實際算例進行了測算，限于篇幅，算例原始數(shù)據(jù)未列出。算例 1：文獻 6 的 10 機系統(tǒng)，利用本組合算法測算，迭代 38 次，結(jié)果如表 1 所示，計算出運行耗量為 78673t 標(biāo)準(zhǔn)煤；啟動耗量為 260 t 標(biāo)

12、準(zhǔn)煤。總耗量為 78933t 標(biāo)準(zhǔn)煤。較文獻 6 利用拉格朗日松弛法測算結(jié)果節(jié)省2.834 （ 2305t 標(biāo)準(zhǔn)煤，其迭代 60 次）。較文獻 7 利用一般遺傳算法測算結(jié)果節(jié)省1.095 （ 874t 標(biāo)準(zhǔn)煤）。算例 2：文獻 8 的 61 機系統(tǒng)，其中 18 臺可調(diào)。利用本組合算法計算出總耗量 27100 t 標(biāo)準(zhǔn)煤，較文獻 5 和文獻 8 利用改進遺傳算法測算結(jié)果節(jié)省0.892 （ 244t 標(biāo)準(zhǔn)煤）。算例結(jié)果表明，本文所提出的組合方法是有效的，迭代次數(shù)少，進行機組優(yōu)化組合的解質(zhì)量也相當(dāng)高。 本文采用的退火演化算法， 采用解群迭代來替代單個點的迭代，明顯減少了陷入局部極小的概率，并且可快速

13、收斂到全局極小值，而且退火演化算法實際上可以視為模擬退火算法的并行執(zhí)行。本文采用的網(wǎng)絡(luò)式遺傳操作，使得該方法易于在并行計算機上應(yīng)用，可使優(yōu)化速度得到很大提高，可望應(yīng)用于實際電力系統(tǒng)的經(jīng)濟運行。精彩文檔實用標(biāo)準(zhǔn)文案參考文獻1 侯煦光，等（ Hou Xuguang et al ）電力系統(tǒng)最優(yōu)規(guī)劃 （Power system optimization ）M 武漢：華中理工大學(xué)出版社（ Huazhong University ofScience and Technology Press）， 19912 康立山，等（ Kang Lishan et al ） 非數(shù)值并行算法 , 第一分冊 , 模擬退火算法

14、（ Non-numerical parallel algorithms simulated annealing algorithm ）M. 北京 : 科學(xué)出版社（ Science Press ）， 19943 劉勇，等（ Liu Yong et al ）非數(shù)值并行算法，第二分冊，遺傳算法（ Non-numerical parallel algorithms genetic algorithm）M 北京：科學(xué)出版社（ Science Press ）， 19954 陳皓勇，王錫凡（ Chen Haoyong, WangXifan ）機組組合問題的優(yōu)化方法綜述（ A survey of optimi

15、zation-based methods for unit commitment） J 電力系統(tǒng)自動化（ Automation of Electric Power System ）， 1999，23(4) 5 韋柳濤，曾慶川，等（ Wei Liutao ，Zeng Qingchuan et al ）啟發(fā)式遺傳基因算法及其在電力系統(tǒng)機組組合優(yōu)化中的應(yīng)用（A new henristic geneticalgorithmand itsapplicationin solutionof the unitcommitment）J 中國電機工程學(xué)報（ Proceeding of the CSEE）， 199

16、4，14(2) 6 韓學(xué)山，等（ Han Xueshan et al ）考慮發(fā)電機組輸出功率速度限制的最優(yōu)機組組合（ Optimal unit commitment considering unit s ramp-ratelimits） J 電網(wǎng)技術(shù)（ Power System Technology ）， 1994，18(2) 7 蔡超豪，蔡元宇（ Cai Chaohao， Cai Yuanyu）機組優(yōu)化組合的遺傳算法（ Optimization of unit commitment by genetic algoritm）J 電網(wǎng)技術(shù)（ Power System Technology ）， 1997，21(1) 8 劉青松（Liu Qingsong）改進遺傳算法確定發(fā)電機組的優(yōu)化組合 （Optimalgen