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

1、基于退火演化算法和遺傳算法基于退火演化算法和遺傳算法的機(jī)組優(yōu)化組合算法的機(jī)組優(yōu)化組合算法吳金華，吳耀武，熊信艮吳金華，吳耀武，熊信艮（華中科技大學(xué)電力工程系，湖北省（華中科技大學(xué)電力工程系，湖北省武漢市武漢市430074430074）摘要：機(jī)組組合問題是編制短期發(fā)電計(jì)劃時(shí)首先要解決的問題，合理的開停機(jī)方案將帶來很大的經(jīng)濟(jì)效益?，F(xiàn)代電力系統(tǒng)對機(jī)組優(yōu)化組合算法的收斂速度和解的質(zhì)量要求越來越高，作者從改善傳統(tǒng)算法這兩方面著手，根據(jù)退火演化算法

2、和遺傳算法各自的特點(diǎn)，提出了一種用于機(jī)組優(yōu)化組合的組合算法。與傳統(tǒng)的一些優(yōu)化算法相比，該組合算法具有搜索速度快，收斂性好，而且解的質(zhì)量相當(dāng)高。通過對實(shí)際系統(tǒng)的測算，驗(yàn)證了該方法的有效性和優(yōu)越性。該方法具有良好的并行性，易于在并行計(jì)算機(jī)上實(shí)現(xiàn)。關(guān)鍵詞關(guān)鍵詞：機(jī)組優(yōu)化組合；退火演化算法；遺傳算法；電力系統(tǒng)；并行計(jì)算1引言引言電力系統(tǒng)的機(jī)組組合問題，就是在滿足系統(tǒng)負(fù)荷及備用要求和機(jī)組運(yùn)行的技術(shù)條件約束的情況下，確定未來一定期間內(nèi)各機(jī)組的開停機(jī)

3、時(shí)間并在機(jī)組間分配負(fù)荷，使系統(tǒng)總的運(yùn)行費(fèi)用達(dá)到最小。合理的開停機(jī)方案能節(jié)省一次能源，延長機(jī)組使用壽命，帶來巨大的經(jīng)濟(jì)效益。據(jù)國外資料和國內(nèi)部分機(jī)組的實(shí)際測算表明，優(yōu)化組合是編制短期發(fā)電計(jì)劃首先要解決的問題，一般而言，其經(jīng)濟(jì)效益遠(yuǎn)大于負(fù)荷經(jīng)濟(jì)分配所得到效益。從數(shù)學(xué)的角度來講，機(jī)組組合問題是一個(gè)高維的、非凸的、離散的混合整數(shù)非線性優(yōu)化問題。當(dāng)系統(tǒng)規(guī)模較大時(shí)，很難找出理論上的最優(yōu)解。由于它能夠帶來顯著的經(jīng)濟(jì)效益，人們一直在積極研究和開發(fā)各種算

4、法來解決這個(gè)問題，如優(yōu)先順序法、分支定界法、動(dòng)態(tài)規(guī)劃法和拉格朗日松弛法等[14]。近年來，對專家系統(tǒng)法、遺傳算法、模擬退火法、人工神經(jīng)網(wǎng)絡(luò)及一些組合算法[9]也進(jìn)行了一些嘗試。在研究基本遺傳算法和退火演化算法的基礎(chǔ)上，本文提出了一種適合于機(jī)組組合的組合算法[9]。在計(jì)算過程中，對遺傳算法的適應(yīng)度函數(shù)、雜交及變異方式作了一些改進(jìn)，有效地避免了簡單遺傳算法在機(jī)組組合問題中的早熟問題，并且提高了收斂速度。2機(jī)組組合問題的數(shù)學(xué)模型機(jī)組組合問題的

5、數(shù)學(xué)模型設(shè)系統(tǒng)調(diào)度期間的時(shí)段數(shù)為H，系統(tǒng)中機(jī)組或等效機(jī)組數(shù)為G，各時(shí)段系統(tǒng)總負(fù)荷為PDt，則其數(shù)學(xué)描述如下（1）目標(biāo)函數(shù)“優(yōu)勝劣汰”的準(zhǔn)則選出父輩解群，通過雜交和變異操作來實(shí)現(xiàn)群體內(nèi)個(gè)體結(jié)構(gòu)的重組，使群體內(nèi)個(gè)體一代一代得以優(yōu)化并逐漸逼近全局最優(yōu)解。本文所提出的算法，在保留了GA算法的基本步驟和特點(diǎn)的同時(shí)，作了如下幾點(diǎn)改進(jìn)。（1）適應(yīng)度函數(shù)比例變換為了避免遺傳算法在搜索初期易產(chǎn)生的“早熟”現(xiàn)象和搜索結(jié)束階段易產(chǎn)生的隨機(jī)漫游現(xiàn)象，本文對適應(yīng)

6、度函數(shù)進(jìn)行了指數(shù)比例變換式中F為原適應(yīng)度函數(shù)；F為變換后的適應(yīng)度函數(shù)，β為比例調(diào)整系數(shù)。系數(shù)β的值決定選擇的強(qiáng)制性[2]，在搜索初期，賦給β一個(gè)較小值，來縮小一些超常個(gè)體的函數(shù)值以降低異常個(gè)體的競爭力；在結(jié)束階段，則賦給β一個(gè)相對較大值，來放大相應(yīng)的適應(yīng)度函數(shù)值來提高個(gè)體的競爭力。（2）雜交概率和變異概率可變在迭代前期，采用較大的雜交概率和較小的變異概率，以提高繁殖效率；在迭代后期，解群中的碼鏈已趨于穩(wěn)定，此時(shí)交叉作用已經(jīng)減小，雜交概率

7、可降低，而為了防止收斂于局部最優(yōu)解，可增大變異概率。本文借鑒了文獻(xiàn)[7]采用的雜交概率和變異概率變化公式（3）網(wǎng)絡(luò)式遺傳操作為了保證算法收斂的穩(wěn)定與快速，采用了一種網(wǎng)絡(luò)式遺傳操作，即在一個(gè)總的遺傳算法中采用了多個(gè)子遺傳操作。由于技術(shù)限制，本文在算例中僅采用了兩個(gè)子遺傳操作，在兩個(gè)子算法中分別采用不同的雜交、變異方式，形成兩個(gè)不同的新解群。3.23.2退火演化算法及其與遺傳算法結(jié)合退火演化算法及其與遺傳算法結(jié)合退火演化算法（AEA）是模擬

8、退火算法（SA）的一種改進(jìn)算法。為了改善搜索過程，避免落入局部最優(yōu)，基于群體和選擇的思想，退火演化算法（AEA）采用了一種新的演化策略，即通過變異和選擇不斷改善一個(gè)解的群體，而不是象普通模擬退火算法那樣采取單點(diǎn)迭代方式，從而大大減小了陷入局部極小的概率，并且可導(dǎo)致快速收斂到全局極小值。本組合算法的基本思想就是：算法首先從一個(gè)包含N個(gè)點(diǎn)的初始群體出發(fā)，在每個(gè)冷卻步上，用遺傳算法作為退火演化算法產(chǎn)生新解的規(guī)則，設(shè)有L個(gè)子遺傳操作用來產(chǎn)生新解