用GTS算法解決機(jī)組組合問題

1、用GTS算法解決機(jī)組組合問題概論概論機(jī)組組合問題 為了實(shí)現(xiàn)電力供需的平衡，并最合理的利用發(fā)電資源，預(yù)先對(duì)發(fā)電機(jī)組的啟停和出力進(jìn)行調(diào)度安排就是非常必要的。機(jī)組優(yōu)化組合和優(yōu)化啟停就是要在滿足約束條件的情況下，優(yōu)化地選定各時(shí)段參加運(yùn)行的機(jī)組，求出機(jī)組的最佳運(yùn)行方案，實(shí)現(xiàn)發(fā)電成本最小。經(jīng)濟(jì)調(diào)度問題 在滿足負(fù)載需求以及功率平衡方程和機(jī)組運(yùn)行限制的前提下，以一種最優(yōu)的分配方案分配機(jī)組的運(yùn)行方案。遺傳算法 從代表問題中可能存在的一個(gè)解集的一個(gè)種群開始逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。在本文

2、的UCP問題中，我們以機(jī)組運(yùn)行狀態(tài)的二進(jìn)制編碼作為問題的解集，以目標(biāo)函數(shù)即成本以及引入約束的罰函數(shù)的和作為算法中的適應(yīng)方程。本文的算法核心就是基于遺傳算法。 禁忌搜索 Tabu搜索是一種強(qiáng)有力的優(yōu)化搜索算法，核心在于對(duì)搜索過程進(jìn)行短期記憶和中長(zhǎng)期記憶。以令搜索具有廣泛性和集中性，基本思想是搜索基本的解空間，在當(dāng)解空間的領(lǐng)域中找到另一個(gè)更好的解時(shí)，更新解空間。但是為了跳出局部極值和避免循環(huán)，搜索中設(shè)置了禁止表，當(dāng)搜索解在禁止表中時(shí)，則放棄該解。搜索過程可以靈活使用禁止表記錄搜索過程，從而使搜索過程能夠找到局部最優(yōu)解，又能跳出局部極值找到更優(yōu)的解。本文中主要用該算法構(gòu)造種群中的新成員。模擬退火法

3、是一種通用概率演算法，用來在一個(gè)大的搜尋空間內(nèi)找尋命題的最優(yōu)解。將搜尋空間內(nèi)每一點(diǎn)想像成空氣內(nèi)的分子；分子的能量，就是它本身的動(dòng)能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對(duì)命題的合適程度。演算法先以搜尋空間內(nèi)一個(gè)任意點(diǎn)作起始：每一步先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。當(dāng)溫度不斷下降至0時(shí)，最終以概率為1穩(wěn)定在其“能量”的全局最小點(diǎn)上。本文中用模擬退火法對(duì)由遺傳算法得到的解集進(jìn)行逐個(gè)實(shí)驗(yàn)，以更新算法解集進(jìn)行下一輪迭代。2.模型的建立模型的建立Uit機(jī)組i在t時(shí)段的運(yùn)行狀態(tài)（ON=1，OFF=0）Vit機(jī)組i在t時(shí)段的開，關(guān)狀態(tài)Pit機(jī)組i在t時(shí)段的

4、發(fā)電出力Fit(Pit)機(jī)組i在t時(shí)段的產(chǎn)出花費(fèi)Sit機(jī)組i的啟動(dòng)成本Soi機(jī)組i的冷開機(jī)成本PDt系統(tǒng)在t時(shí)段內(nèi)負(fù)載需求的峰值Rtt時(shí)段的旋轉(zhuǎn)備用符號(hào)的約定Pmaxi Pmini機(jī)組i的最大，發(fā)電出力Toni Toffi機(jī)組i的運(yùn)行與關(guān)閉時(shí)間Tupi Tdowni機(jī)組i的開機(jī)與關(guān)機(jī)時(shí)間idownioffiiiitiitiitiititTtNiitititititTETTDSoSCPBPAPFSVPFUF )/exp(1i)(t)(211啟動(dòng)成本的目標(biāo)函數(shù)：機(jī)組函數(shù)：時(shí)段內(nèi)產(chǎn)出花費(fèi)的目標(biāo)發(fā)電成本目標(biāo)函數(shù)：調(diào)度時(shí)間內(nèi)所有機(jī)組的目標(biāo)函數(shù)tTTtTTtiUPPPUtRPDPUtPDPUupionid

5、ownioffiitiitiitNittiitNititit;:,;:;)(:;:maxmin1max1最小開關(guān)機(jī)時(shí)間約束運(yùn)行約束旋轉(zhuǎn)備用約束負(fù)載約束約束條件3.構(gòu)造算法構(gòu)造算法綜述 本文用遺傳算法(GA)，禁忌搜索(TS)和模擬退火法(SA)來解決UCP問題中的機(jī)組運(yùn)行狀態(tài)的組合優(yōu)化問題。以二進(jìn)制碼來表示機(jī)組的狀態(tài)變量Uit，再經(jīng)由GTS算法，求解使得在滿足發(fā)電約束同時(shí)成本最低的機(jī)組調(diào)度問題。 算法步驟如下: 隨機(jī)選擇一系列可行解(染色體)，定義其為初始種群(由若干個(gè)染色體串組成，每個(gè)串對(duì)應(yīng)一個(gè)自變量值)。 以解決調(diào)度問題來求出每個(gè)染色體的數(shù)值。 根據(jù)適應(yīng)函數(shù)，計(jì)算種群中每個(gè)染色體的適應(yīng)度。

6、 用遺傳算法(GA)構(gòu)造新的種群: (1).挑選適應(yīng)度最好的解決方案(染色體)，復(fù)制到新種群中。 (2).對(duì)現(xiàn)有的種群隨機(jī)選取一部分方案用禁忌搜索(TS)在新的種群中構(gòu)造新的成員。 (3).用交叉的操作來完成新種群中新成員的構(gòu)造。 (4).用變異操作來對(duì)新種群進(jìn)行完善。 用模擬退火法(SA)對(duì)新種群的成員進(jìn)行測(cè)試。終止準(zhǔn)則 我們將停止算法如果下面兩個(gè)條件有一個(gè)滿足:l 最好方案的執(zhí)行迭代數(shù)大于預(yù)先設(shè)定的最大迭代數(shù)。l 最大允許的迭代次數(shù)已經(jīng)達(dá)到算法流程圖4.GTS算法中的算法中的GA算法算法解決方案的編碼 UCP的解決方案可以由一個(gè)二進(jìn)制矩陣來表示出來，我們的編碼方法是用二進(jìn)制數(shù)來對(duì)解決方案中

7、的十進(jìn)制數(shù)進(jìn)行轉(zhuǎn)換。矩陣中每一個(gè)長(zhǎng)度為T的列向量代表著機(jī)組在不同時(shí)間段下的運(yùn)行狀態(tài)，經(jīng)過對(duì)這些列向量的二進(jìn)制數(shù)的解碼，我們可以得到N個(gè)十進(jìn)制數(shù)U1，U2，.,UN。 范圍從0到2N-1。下面給出一些圖助于理解適應(yīng)度函數(shù) 遺傳算法在進(jìn)化搜索過程中基本不利于外部信息，僅以適應(yīng)度函數(shù)為依據(jù)。一般情況下適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的。對(duì)目標(biāo)函數(shù)的某種映射稱為適應(yīng)度的尺度轉(zhuǎn)換。交叉 交叉操作是發(fā)生在染色體的十進(jìn)制碼中的，具體可以分為以下兩個(gè)步驟。第一步是將新選擇產(chǎn)生的匹配池中的染色體由輪盤賭規(guī)則兩兩隨機(jī)進(jìn)行匹配。 第二步則是進(jìn)行交叉繁殖：通過父輩染色體的十進(jìn)制碼的串的交換產(chǎn)生出新的孩子。(串的選擇規(guī)則

8、可以擬定)兩個(gè)父輩染色體產(chǎn)生兩個(gè)孩子染色體，種群中染色體數(shù)量不發(fā)生改變。變異 以一種很小的概率隨機(jī)的選擇一個(gè)染色體，選擇的染色體被解碼成二進(jìn)制數(shù)，隨機(jī)選擇一個(gè)機(jī)組以及時(shí)間段，改變其二進(jìn)制的值(由1變?yōu)?，由0變?yōu)?)。5.GTS算法中的算法中的TS算法算法TS算法在GTS算法的作用 用來對(duì)GA算法隨機(jī)選中的種群的成員構(gòu)造新的相鄰成員。增加了算法的廣泛性。TS算法的具體實(shí)現(xiàn) UCP問題中的禁忌表(TL)被構(gòu)造為一個(gè)Z*N維的矩陣，Z為TL的長(zhǎng)度，N為機(jī)組的數(shù)量。每一個(gè)TL矩陣的列向量表示了一個(gè)機(jī)組的TL。列向量i的每一個(gè)十進(jìn)制數(shù)記錄了機(jī)組i的狀態(tài)的搜尋方案。經(jīng)由這種方式我們以最小的記憶需求記錄了

9、所有的搜尋方案中機(jī)組的狀態(tài)信息。算法流程圖禁忌表與搜尋方案6.GTS算法中的算法中的SA算法算法SA算法步驟 給出SA算法的第k次迭代步驟 step(1):構(gòu)造新的溫度Cpk=Cp0()k,01。 step(2):在溫度Cpk下對(duì)GA算法構(gòu)成的種群成員一個(gè)一個(gè)的做退火實(shí)驗(yàn)。 step(3):退火實(shí)驗(yàn):計(jì)算增量t=C(xj)-C(xi)，其中C(x)為評(píng)價(jià)函數(shù) 。 若t=U(0,1),使xi=xj。跳轉(zhuǎn)到step(2)，其他，跳轉(zhuǎn)step(2)。 其中xi是SA算法的現(xiàn)行方案，xj為GA算法的現(xiàn)行種群成員。 step(4):如果所有種群中的成員都經(jīng)過了退火實(shí)驗(yàn)，跳轉(zhuǎn)到主算法的下一個(gè)步驟。如果還有

10、成員沒有實(shí)驗(yàn)，跳轉(zhuǎn)到step(2)。 為了方便理解，下引入算法流程圖來對(duì)算法進(jìn)行進(jìn)一步的解釋。SA算法流程圖7.例子例子為了體現(xiàn)出GTS算法的優(yōu)越性，我們用三個(gè)例子以拉格朗日松弛算法，整數(shù)規(guī)劃來對(duì)GTS算法進(jìn)行比較，在調(diào)度的24小時(shí)時(shí)間內(nèi)例子1和2包括了10個(gè)運(yùn)行機(jī)組，例子3則有26個(gè)機(jī)組。比較例子的仿真圖我們可以看出，GTS算法的優(yōu)越性比較明顯，GTS的參數(shù)選擇具體如下：種群大小為50，交叉率為0.8，變異率 為0.3，精英復(fù)制 為2，最大種群成員數(shù)為1000, 禁忌表大小為7，初始溫度為5000，=0.9。仿真圖8.總結(jié)總結(jié)本文用到了一種新的算法(GTS)來解決機(jī)組組合問題，該算法結(jié)合了三種算法，在GA算法的基礎(chǔ)上，引用TS算法來構(gòu)造GA算法的種群中的新成員，用SA算法來加速GA算法的收斂速度。本文用的GTS算法與一般的GA算法的不同在于三點(diǎn)：第一：這種算法的解決方案用二進(jìn)制與十進(jìn)制混合編碼表示