機(jī)組優(yōu)化組合問題的隨機(jī)tabu搜索算法
吳金華，吳耀武，熊信艮, 鐘德惠
（華中科技大學(xué)電氣工程學(xué)院，湖北省 武漢市 430074）
摘 要：針對機(jī)組組合問題的特點(diǎn)，作者對tabu搜索策略和模擬退火算法（SA）的組合算法-隨機(jī)tabu搜索策略的編碼方式、移動規(guī)則和tabu表的構(gòu)造等作了適應(yīng)性的改進(jìn)，并對實(shí)際機(jī)組組合算例進(jìn)行了求解。仿真結(jié)果表明，tabu－SA組合算法有效地結(jié)合了SA算法的大規(guī)模尋優(yōu)特性和tabu搜索的局部搜索能力強(qiáng)的特點(diǎn)，能快速搜索到高質(zhì)量的系統(tǒng)優(yōu)化解。而且隨機(jī)tabu搜索算法具有框架性算法不易陷入局部最優(yōu)的特點(diǎn)，易于與其他算法結(jié)合來構(gòu)造新的高效組合算法。
關(guān)鍵詞：機(jī)組組合；Tabu搜索；模擬退火算法；隨機(jī)搜索
1 引言
機(jī)組組合是電力系統(tǒng)短期經(jīng)濟(jì)調(diào)度的一項(xiàng)重要任務(wù)。在數(shù)學(xué)規(guī)劃上，機(jī)組組合問題屬于NP完備（NP-Complete）問題，當(dāng)系統(tǒng)規(guī)模較大時，幾乎無法找出理論上的最優(yōu)解。但由于它能夠帶來顯著的經(jīng)濟(jì)效益，人們一直在積極研究和開發(fā)了各種算法來解決這個問題。例如：優(yōu)先順序法簡單且計(jì)算速度快，但難于找到全局最優(yōu)解；動態(tài)規(guī)劃法、分支定界法理論上能找到最優(yōu)解，但易陷入“維數(shù)災(zāi)”；拉格朗日松弛法運(yùn)用靈活且成功地解決了大系統(tǒng)的機(jī)組組合問題，避免了“維數(shù)災(zāi)”，但需模型連續(xù)可導(dǎo)且具有凸性，等等。近年來，隨著計(jì)算機(jī)、人工智能技術(shù)的發(fā)展和仿生優(yōu)化算法的出現(xiàn)，一些新的優(yōu)化算法迅速發(fā)展并在機(jī)組組合問題領(lǐng)域內(nèi)取得了富有成效的應(yīng)用，如遺傳算法[1,2]、模擬退火法[3]、tabu搜索[4]和人工神經(jīng)網(wǎng)絡(luò)法[5]等。但由于各算法都各具優(yōu)點(diǎn)和不足，如遺傳算法對大規(guī)模系統(tǒng)尋優(yōu)效果較差；模擬退火算法計(jì)算相當(dāng)費(fèi)時；tabu搜索的大規(guī)模尋優(yōu)特性稍弱；而人工神經(jīng)網(wǎng)絡(luò)則對計(jì)算初值依賴較強(qiáng)等。如何對各算法進(jìn)行改進(jìn)，對它們的確良優(yōu)缺點(diǎn)進(jìn)行有效的取舍便成了今后各算法應(yīng)用研究的熱點(diǎn)。
針對機(jī)組組合問題的混合離散優(yōu)化等特點(diǎn)，本文對tabu搜索和SA算法的組合算法——隨機(jī)tabu搜索策略的數(shù)據(jù)編碼、移動規(guī)則和tabu表作了適應(yīng)性的構(gòu)造，并運(yùn)用其對機(jī)組組合問題進(jìn)行求解，取得了很好的效果。算例仿真證明了其有效性。
2 隨機(jī)tabu搜索的基本原理
Tabu搜索的基本思想是由F.Glover在20世紀(jì)60年代末提出來的，近年來逐步形成為一套系統(tǒng)的優(yōu)化理論。Tabu搜索策略本質(zhì)上是各類局部搜索法和啟發(fā)式迭代法的一般框架，其主要特征是適應(yīng)記憶（adaptive memory）和響應(yīng)探索（responsive exploration），并因此而具備了智能特色。由于其構(gòu)造實(shí)施的多樣性和在許多最優(yōu)化問題中的成功應(yīng)用，研究結(jié)果表明，在解的優(yōu)劣程度相當(dāng)?shù)臈l件下，tabu搜索的速度一般快于SA和遺傳算法（GA），使之成為離散優(yōu)化領(lǐng)域內(nèi)又一研究熱點(diǎn)。
Tabu搜索主要由移動（move）、tabu表（tabu list）和釋放水平（aspiration level）構(gòu)成。首先利用隨機(jī)方法或與問題有關(guān)的啟發(fā)式方法產(chǎn)生一個當(dāng)前解X（即初始解，n維向量）之后，按一定的規(guī)則，采用一組“移動”對X進(jìn)行操作，產(chǎn)生一組試驗(yàn)解。選擇其中的最好解令為當(dāng)前解，重復(fù)迭代，求出系統(tǒng)最優(yōu)解。為了防止搜索過程返回到已經(jīng)訪問過的局部最優(yōu)點(diǎn)，tabu搜索采用了適應(yīng)記憶策略。將最近若干次所實(shí)現(xiàn)的移動的反方向記錄到tabu表中，凡是tabu表中的移動一般不可作為下一步的搜索方向，從而防止產(chǎn)生循環(huán)，避免了局部最優(yōu)。同時，為了盡可能不錯過產(chǎn)生最優(yōu)解的“移動”，tabu搜索對tabu表中的“移動”都賦予一個釋放準(zhǔn)則，當(dāng)其達(dá)到了釋放準(zhǔn)則，則該“移動”將從tabu表中釋放出來而不再被限制。
模擬退火算法（SA）也是一種適合于求解大型組合優(yōu)化問題的技術(shù)，其核心在于模擬熱力學(xué)中液體的凍結(jié)與結(jié)晶或金屬溶液的冷卻與退火過程。模擬退火算法是將Metropoplis接受準(zhǔn)則引入到局部迭代改進(jìn)算法中，一定程度上具有了脫離局部最優(yōu)“陷阱”的能力。隨機(jī)tabu搜索策略則是將SA算法的Metropolis接受準(zhǔn)則嵌入到一般tabu搜索框架中，即在tabu搜索的每步局部迭代中，除采用tabu表來限制下一步的搜索方向，還通過Metropolis接受準(zhǔn)則來決定局部優(yōu)化解的接受。因此，與普通tabu搜索策略相比，它具備更高的全局尋優(yōu)能力；與模擬退火算法相比，隨機(jī)tabu搜索策略的解生成過程由于其搜索的方向性和搜索范圍的不斷調(diào)整而更有效。文獻(xiàn)[6]對隨機(jī)tabu搜索的全局收斂性進(jìn)行了分析與證明。
3 隨機(jī)tabu搜索在機(jī)組組合中的應(yīng)用
3.1 機(jī)組組合問題的數(shù)學(xué)模型 設(shè)系統(tǒng)調(diào)度期間的時段數(shù)為H，系統(tǒng)中機(jī)組或等效機(jī)組數(shù)為G，各時段系統(tǒng)總負(fù)荷為PDt，則目標(biāo)函數(shù)和主要約束條件的數(shù)學(xué)描述如下
式中 Fit (Pit)為t時段i機(jī)組的運(yùn)行費(fèi)用；STi和SDi為i機(jī)組的啟停費(fèi)用，一般視為常數(shù)或?yàn)閱⑼r間的函數(shù)；Uit為i機(jī)組在時段t的狀態(tài)，Uit=1或0分別表示為運(yùn)行或停運(yùn)狀態(tài)；Pit為機(jī)組i在時段t的出力。約束條件中，Ct為時段t系統(tǒng)的網(wǎng)損；PDt為時段t系統(tǒng)總負(fù)荷；k為備用系數(shù)；Mi為i機(jī)組在計(jì)算周期內(nèi)允許啟停次數(shù)；Pimax和Pimin為i機(jī)組的上、下限出力；RURi和RDRi分別為機(jī)組i的升、降功率速度約束；MUi，MDi則為機(jī)組i的最小運(yùn)行和最小停運(yùn)時間。
機(jī)組的運(yùn)行費(fèi)用模型采用發(fā)電功率的函數(shù)表示，即
網(wǎng)損可作常數(shù)處理，即按總負(fù)荷的一定比例（7%）考慮。更詳細(xì)的模型應(yīng)包括線路潮流限制、分區(qū)功率平衡、機(jī)組的燃料限制和隨機(jī)停運(yùn)的影響等。
3.2 優(yōu)化目標(biāo)函數(shù)的建立與數(shù)據(jù)編碼 對于除機(jī)組容量約束外的其他約束，采用罰函數(shù)法處理，以構(gòu)成系統(tǒng)優(yōu)化目標(biāo)函數(shù)
式中 Cf為罰參數(shù)；R為約束形式，
常規(guī)求解機(jī)組組合問題時，一般將其分為機(jī)組組合和負(fù)荷經(jīng)濟(jì)分配兩個子問題，即在每一運(yùn)算步上，首先確定各機(jī)組在各時段的組合運(yùn)行狀態(tài)，然后再進(jìn)行負(fù)荷經(jīng)濟(jì)分配運(yùn)算，這使得計(jì)算量相當(dāng)大，十分費(fèi)時。為此本文采用了一種新的二進(jìn)制與浮點(diǎn)數(shù)混合編碼方式，即以串X={U11,
3.3 移動設(shè)計(jì)、tabu表與釋放準(zhǔn)則
tabu搜索的搜索過程由“移動”來實(shí)現(xiàn)。本文由于采用了二進(jìn)制與浮點(diǎn)數(shù)混合編碼策略，因此對碼串中的U，P分量構(gòu)造了不同的移動方式。
（1）對U分量，隨機(jī)選取碼串的某一位或幾位U分量進(jìn)行取反操作。
（2）對P分量，隨機(jī)選取碼串中P分量的一位或幾位根據(jù)式
為保證搜索均在可行解中進(jìn)行，算法對每組“移動”操作所產(chǎn)生的試驗(yàn)解群作如下檢驗(yàn)和修正：
tabu表是tabu搜索策略的關(guān)鍵。在一般tabu算法實(shí)現(xiàn)中，tabu表中記錄的是最近若干代迭代過程中的所實(shí)現(xiàn)的移動的反方向。本文將最近若干次迭代過程中所得局部優(yōu)化解的碼串記錄到tabu表中。凡是處于
