求解機(jī)組組合問題的改進(jìn)型人工魚群算法研究

翟軍臣，杜廷松，，李德宜，李文武

1.三峽大學(xué)非線性與復(fù)雜系統(tǒng)研究所，湖北宜昌 443002

2.武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430081

3.三峽大學(xué)電氣與新能源學(xué)院，湖北宜昌 443002

◎工程與應(yīng)用◎

求解機(jī)組組合問題的改進(jìn)型人工魚群算法研究

翟軍臣1，杜廷松1，2，李德宜2，李文武3

1.三峽大學(xué)非線性與復(fù)雜系統(tǒng)研究所，湖北宜昌 443002

2.武漢科技大學(xué)冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430081

3.三峽大學(xué)電氣與新能源學(xué)院，湖北宜昌 443002

提出了改進(jìn)型人工魚群算法。采用線性遞減的函數(shù)取代標(biāo)準(zhǔn)人工魚群算法（BAFSA）中的固定視野；在覓食行為中，利用粒子群算法（PSO）中的慣性權(quán)重線性遞減的視野來加速算法的收斂速度；同時(shí)用混沌現(xiàn)象代替BAFSA中的隨機(jī)現(xiàn)象。給出了算法的全局收斂性證明，并將算法應(yīng)用于求解電力系統(tǒng)機(jī)組組合問題，分別對(duì)基準(zhǔn)測(cè)試函數(shù)、三機(jī)組和十機(jī)組系統(tǒng)進(jìn)行仿真計(jì)算，結(jié)果均表明新算法能有效跳出局部極值，收斂速度快且具有更高的精度。因此，改進(jìn)型算法可以作為求解機(jī)組組合問題的有效算法。

機(jī)組組合；人工魚群；線性遞減；混沌搜索

1 引言

電力系統(tǒng)的中大規(guī)模機(jī)組組合（UC）問題是一個(gè)高維、離散、非線性的工程優(yōu)化問題[1]。其機(jī)組調(diào)度的目的是在一個(gè)周期內(nèi)滿足各種約束的條件下動(dòng)態(tài)地決策機(jī)組的啟停和安排機(jī)組出力，使得機(jī)組總耗量最小。當(dāng)系統(tǒng)的規(guī)模較大時(shí)，要從理論上求得精確的最優(yōu)解已相當(dāng)困難。由于傳統(tǒng)的優(yōu)化算法在求解UC問題過程中都或多或少地存在一些缺陷，往往得不到較理想的全局最優(yōu)解；而現(xiàn)代智能優(yōu)化算法因處理約束方便、全局搜索能力強(qiáng)而倍受眾多學(xué)者關(guān)注。這些現(xiàn)代智能優(yōu)化算法如PSO、遺傳算法[2]（GA）、人工神經(jīng)網(wǎng)絡(luò)[3]（NN）、禁忌搜索（TS）、模擬退火[4]（SA）、模糊優(yōu)化等方法已成功應(yīng)用于這類問題的求解。

BAFSA是一類基于動(dòng)物行為的群體智能優(yōu)化算法[5]。該算法具有簡(jiǎn)單易實(shí)現(xiàn)、收斂速度快、計(jì)算效率較高等優(yōu)點(diǎn)，其對(duì)初值與參數(shù)選擇不敏感，具有較強(qiáng)的魯棒性和較好的收斂性能，但是尋優(yōu)結(jié)果精度低且易陷入局部最優(yōu)，出現(xiàn)早熟現(xiàn)象。因此，學(xué)者們從不同的方面對(duì)人工魚群算法進(jìn)行了改進(jìn)。文獻(xiàn)[6]引入生存機(jī)制和競(jìng)爭(zhēng)機(jī)制對(duì)算法進(jìn)行改進(jìn)，所給算法的收斂速度和搜索效率得到一定程度的提高；文獻(xiàn)[7]引入魚的吞食行為，以減少算法的運(yùn)算量，提高運(yùn)算速度，并提高算法跳出局部極值的能力；文獻(xiàn)[8]采用最優(yōu)個(gè)體保留策略對(duì)魚群算法的覓食行為進(jìn)行改進(jìn)，給出加速個(gè)體局部搜索方法。這些改進(jìn)算法在一定程度上改善了BAFSA的優(yōu)化性能，但算法運(yùn)行后期搜索的盲目性較大、易陷入局部最優(yōu)和尋優(yōu)結(jié)果精度低等問題沒有得到很好地解決。

本文提出了一種改進(jìn)的人工魚群算法（IAFSA），采用線性遞減的函數(shù)來代替不變的視野值；在覓食行為中引入慣性權(quán)重線性遞減的視野；同時(shí)引入混沌行為代替隨機(jī)行為。新算法可保證快速地收斂到最優(yōu)解，并且避免陷入局部極值而出現(xiàn)早熟現(xiàn)象。

2 BAFSA基本框架

在一片水域中，魚往往能自行或尾隨其他魚找到營養(yǎng)物質(zhì)多的地方，因而魚生存數(shù)目最多的地方一般就是本水域中營養(yǎng)物質(zhì)最多的地方。BAFSA就是根據(jù)這一特點(diǎn)，通過構(gòu)造人工魚來模擬魚群的覓食、聚群、追尾及隨機(jī)行為，從而實(shí)現(xiàn)尋優(yōu)[9-10]。

2.1 相關(guān)定義

人工魚個(gè)體的狀態(tài)可以表示為向量X=(x1，x2，…，xn)，xi(i=1，2，…，n)為欲尋優(yōu)的變量；人工魚當(dāng)前所在位置的食物濃度可以表示為Y=F(X)，其中Y為目標(biāo)函數(shù)值；人工魚個(gè)體i，j之間的距離為dij=‖Xi-Xj‖；step表示人工魚移動(dòng)的最大步長；Visual表示人工魚視野；try_number表示嘗試次數(shù)；δ表示擁擠度因子；N表示人工魚總數(shù)。

2.2 行為描述

（1）覓食行為

這是人工魚的一種基本行為，也就是趨向食物的一種活動(dòng)。設(shè)人工魚i當(dāng)前狀態(tài)為Xi，在其感知范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xk：

式中，Rand()是一個(gè)介于0和1之間的隨機(jī)數(shù)，如果在求極大值問題中，Yi＜Yj，則向該方向前進(jìn)一步：

否則，再重新隨機(jī)選擇狀態(tài)Xk，判斷是否滿足前進(jìn)條件。這樣反復(fù)嘗試try_number次后，如果仍不滿足前進(jìn)條件，則執(zhí)行隨機(jī)行為。

（2）聚群行為

否則，執(zhí)行覓食行為。

（3）追尾行為

否則，執(zhí)行覓食行為。

（4）隨機(jī)行為

隨機(jī)行為的實(shí)現(xiàn)較簡(jiǎn)單，就是在視野中選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)，其實(shí)，它是覓食行為的一個(gè)缺省行為，即Xi的下一個(gè)位置為：

3 改進(jìn)型人工魚群算法

3.1 改進(jìn)措施

（1）一般來講，當(dāng)視野范圍較小時(shí)，人工魚群的覓食行為和隨機(jī)游動(dòng)比較突出，可能導(dǎo)致算法陷入局部最優(yōu)解；視野范圍較大時(shí)，人工魚的追尾行為和聚群行為將變得較突出，較容易發(fā)現(xiàn)全局極值并收斂，而人工魚在比較大的區(qū)域內(nèi)執(zhí)行覓食行為和隨機(jī)行為，不利于全局極值附近的人工魚發(fā)現(xiàn)鄰近范圍內(nèi)的全局極值點(diǎn)。故對(duì)人工魚的視野進(jìn)行適當(dāng)?shù)母淖儯涸谒惴ǖ某跏茧A段，每條人工魚以一個(gè)大的視野尋找解，這樣能擴(kuò)大尋優(yōu)的范圍。隨著算法進(jìn)化代數(shù)的增加，魚群的視野將適當(dāng)?shù)販p小以加快收斂速度，提高算法的優(yōu)化性能。因此，采用線性遞減的視野，定義視野的變化函數(shù)為：

其中，gen為當(dāng)前進(jìn)化代數(shù)，V(gen)為gen代人工魚視野值，Vmax，Vmin分別是視野的上下限，MAXGEN為最大進(jìn)化代數(shù)。算法初期人工魚的視野越大，就越容易發(fā)現(xiàn)全局最優(yōu)值并收斂，隨著進(jìn)化程度的不斷加深，視野不斷地減小，算法越有利于局部搜索。

（2）對(duì)覓食行為中人工魚的視野作進(jìn)一步改進(jìn)，當(dāng)人工魚在其感知范圍內(nèi)隨機(jī)選擇下一個(gè)狀態(tài)時(shí)，利用PSO中慣性權(quán)重線性遞減的視野代替原來的視野[11]，加速算法的收斂速度。具體如下：

其中，V(k)為一次迭代中覓食行為第k次嘗試的視野；k和try_number分別表示當(dāng)前嘗試次數(shù)和最大嘗試次數(shù)；是當(dāng)前狀態(tài)，X為下一個(gè)狀態(tài)。隨著嘗試次數(shù)的增加，慣性權(quán)重不斷減小，感知范圍的半徑也隨著不斷的減小，保證了算法能夠快速地收斂到最優(yōu)解。

（3）混沌運(yùn)動(dòng)具有遍歷性隨機(jī)性等特性，能夠在一定的范圍內(nèi)按其自身規(guī)律不重復(fù)遍歷所有狀態(tài)[12]。因此，在BAFSA中的隨機(jī)行為將混沌搜索引入其中，即用混沌現(xiàn)象代替隨機(jī)現(xiàn)象。

其中，CXi為混沌變量，u為控制參數(shù)，Xmax、Xmin分別為Xi的最大值和最小值，是當(dāng)前狀態(tài)，X為下一個(gè)狀態(tài)。混沌現(xiàn)象執(zhí)行簡(jiǎn)單并且能夠避免陷入局部極值。

混沌映射式（10）為Logistic映射，取控制參數(shù)u=4時(shí)，式（10）處于混沌狀態(tài)，也就是說除（0，0.25，0.5，0.75，1）這幾個(gè)點(diǎn)外，其他點(diǎn)都是通過迭代公式產(chǎn)生的，它們都處于0和1之間。因?yàn)榛煦绗F(xiàn)象的軌跡對(duì)初始值非常敏感，如果n個(gè)決策變量的初始值不同，就可以得到n個(gè)不同的混沌軌跡。

IAFSA步驟如下：

步驟1初始化設(shè)置，包括人工魚群的個(gè)數(shù)N、每條人工魚的初始值位置、人工魚移動(dòng)的最大步長(Step)、人工魚的初始視野(Visual)，最大進(jìn)化代數(shù)(MAXGEN)、重試次數(shù)(try_number)和擁擠度因子(δ)。

步驟2利用公式（6）計(jì)算人工魚當(dāng)前的視野值，計(jì)算每條人工魚的適應(yīng)度值，并記錄全局最優(yōu)的人工魚的狀態(tài)。

步驟3對(duì)每條人工魚進(jìn)行評(píng)價(jià)，對(duì)其要執(zhí)行的行為進(jìn)行選擇，包括覓食行為、聚群行為、追尾行為和隨機(jī)行為。

步驟4執(zhí)行人工魚選擇的行為，四種行為分別對(duì)應(yīng)于公式（8）、（3）、（4）、（10），根據(jù)對(duì)應(yīng)公式計(jì)算每條人工魚的適應(yīng)度值，更新每條人工魚的位置信息。

步驟5更新全局最優(yōu)人工魚的狀態(tài)。

步驟6判斷是否滿足終止條件，若滿足，則輸出結(jié)果，否則，跳轉(zhuǎn)到步驟2。

3.2 算法的應(yīng)用

在實(shí)際情況中，汽輪機(jī)進(jìn)氣閥突然開啟時(shí)會(huì)產(chǎn)生閥點(diǎn)效應(yīng)，該效應(yīng)對(duì)于最優(yōu)分配的求解影響明顯[13]。文中研究的是一個(gè)靜態(tài)計(jì)及閥點(diǎn)效應(yīng)的機(jī)組組合優(yōu)化問題，模型中對(duì)負(fù)荷平衡、機(jī)組技術(shù)出力等實(shí)際情況進(jìn)行約束，建立了追求發(fā)電成本最小的機(jī)組組合優(yōu)化數(shù)學(xué)模型。

考慮閥點(diǎn)效應(yīng)后的耗電特性為：

其中，F(xiàn)i為第i臺(tái)發(fā)電機(jī)的發(fā)電費(fèi)用，Pi為第i臺(tái)發(fā)電機(jī)的有功功率，ai、bi、ci為第i臺(tái)發(fā)電機(jī)的運(yùn)行特性參數(shù)，ei，fi為第i臺(tái)發(fā)電機(jī)的閥點(diǎn)效應(yīng)系數(shù)，Pimin為第i臺(tái)發(fā)電機(jī)的最小出力。

綜上所述，計(jì)及閥點(diǎn)效應(yīng)的機(jī)組優(yōu)化數(shù)學(xué)模型如下：

其中，F(xiàn)為總的發(fā)電費(fèi)用，N為系統(tǒng)內(nèi)發(fā)電機(jī)的總數(shù)，PL為系統(tǒng)負(fù)荷，PD為系統(tǒng)網(wǎng)損，Pimin，Pimax分別是機(jī)組出力的最小值和最大值。當(dāng)電力系統(tǒng)網(wǎng)絡(luò)覆蓋密集時(shí)可以忽略網(wǎng)損，文中在計(jì)算時(shí)忽略了系統(tǒng)網(wǎng)損。

BAFSA是通過迭代搜尋最優(yōu)解的，在每次迭代的過程中，人工魚都通過覓食、聚群、追尾和隨機(jī)等行為來更新自己。根據(jù)機(jī)組發(fā)電功率的最大值和最小值產(chǎn)生初始的人工魚群：

其中，ub和lb分別是機(jī)組發(fā)電功率的最大值和最小值；X為初始的人工魚群狀態(tài)。引進(jìn)懲罰因子，將UC的目標(biāo)函數(shù)轉(zhuǎn)化為：

其中，λ為懲罰因子。設(shè)人工魚當(dāng)前狀態(tài)為Xi，探索當(dāng)前領(lǐng)域內(nèi)(dij≤Visual)的伙伴數(shù)目nf及中心狀態(tài)Xc。若Yc/nf≥δYi，人工魚執(zhí)行聚群、追尾等行為。否則，執(zhí)行覓食行為（8）：

若Xj不在感知范圍內(nèi)，則執(zhí)行改進(jìn)后的隨機(jī)行為式（10）：

本次循環(huán)結(jié)束后，自動(dòng)更新人工魚的當(dāng)前狀態(tài)X和當(dāng)前位置的食物濃度Y。當(dāng)進(jìn)化代數(shù)大于等于最大進(jìn)化代數(shù)(gen≥MAXGEN)的時(shí)候，則停止運(yùn)算并求出仿真計(jì)算中的全局近似最優(yōu)解（機(jī)組總耗量最?。?/p>

4 收斂性分析

4.1 概念及引理

其中，F(xiàn)(a)為目標(biāo)函數(shù)；gi(a)為第i個(gè)約束條件；M為約束條件個(gè)數(shù)；a為n維未知變量；Z為搜索空間。當(dāng)問題規(guī)模為n時(shí)，搜索空間Z為機(jī)組的組合變量空間，是一個(gè)離散的狀態(tài)空間，狀態(tài)數(shù)一共有|Z|=2n。令Y={F(a)|a∈Z}，則有Y={F(a)|a∈Z}，|Y|＜|Z|。設(shè)|Y|=N，將Y具體化為：

定義人工魚的食物濃度為：Energy(a)=F(a)，a∈Z；令XZ為所有人工魚集合，?x∈XZ，有YN≤Energy(X)≤Y1，將集合XZ劃分為非空子集：

令Xi，j(i=1，2，…，N，j=1，2，…，|表示中第j個(gè)人工魚的位置狀態(tài)。在人工魚的行為過程中，從一個(gè)狀態(tài)轉(zhuǎn)移到另外的狀態(tài)可表示為Xi，j→Xk，l，則從Xi，j到Xk，l的轉(zhuǎn)移概率為pij，kl，從Xi，j到X中任一人工魚位置狀態(tài)的轉(zhuǎn)移概率為pij，k，從X中任一人工魚位置狀態(tài)到中任一人工魚位置狀態(tài)的轉(zhuǎn)移概率為pi，k，則有[14]：

P′∞為一個(gè)穩(wěn)定的隨機(jī)矩陣，且P′∞=1′P′∞，P′∞= P′0P′∞唯一確定并且與初始分布無關(guān)，P′∞滿足如下條件：

4.2 全局收斂性證明

定理1在改進(jìn)型人工魚群算法中，對(duì)于?Xi，j?，i=1，2，…，N，j=1，2，…，|X|滿足：

證明設(shè)Xi，j為第t次迭代后的人工魚，記為Xt，設(shè)在Xt中能量最高的人工魚為bestt=X*，其中，bestt為n維矢量，則有F(bestt)=Y1。在BAFSA中，每次迭代過程中對(duì)當(dāng)前人工魚最優(yōu)狀態(tài)的更新可知：

式（18）得證。

對(duì)于式（19），由BAFSA中對(duì)每個(gè)人工魚探索其當(dāng)前所處的環(huán)境狀況，選擇一種行為（覓食、聚群或者追尾），設(shè)bestt+1為Xt+1中最優(yōu)人工魚。采取線性遞減的函數(shù)值代替固定的視野，只改變?nèi)斯~選擇行為的概率值，僅對(duì)收斂速度產(chǎn)生影響，而不影響算法的收斂性。以下分情況進(jìn)行分析：

情況1如果人工魚選擇聚群行為或追尾行為，即選擇聚群行為概率ps＞0或選擇追尾行為概率pf＞0，則有F(bestt+1)＞F(bestt)，結(jié)論顯然成立。

情況2如果當(dāng)前人工魚選擇覓食行為，說明此時(shí)當(dāng)前人工魚在鄰域內(nèi)為最優(yōu)，則此時(shí)人工魚選擇此種行為的概率pp=1-ps-pf，此時(shí)人工魚探索感知范圍隨機(jī)選擇狀態(tài)，有兩種情況：

（1）選擇的狀態(tài)位置食物濃度高于當(dāng)前食物濃度，設(shè)此種情況的概率為ppy，命題得證。

（2）選擇狀態(tài)位置食物濃度低于當(dāng)前人工魚位置食物濃度，設(shè)此種情況的概率為ppn=1-ppy，此時(shí)重新選擇，反復(fù)嘗試try_number次，則其概率為(ppn)try_number；如果仍不滿足，則隨機(jī)移動(dòng)，設(shè)隨機(jī)移動(dòng)的概率為prandom，注意到用混沌現(xiàn)象代替隨機(jī)現(xiàn)象不會(huì)影響隨機(jī)運(yùn)動(dòng)的概率。隨機(jī)移動(dòng)后狀態(tài)位置濃度高于當(dāng)前人工魚位置食物濃度的概率為pbetter=(1/2)(1-(ppn)try_number× prandom)≥0；如果pbetter＞0，命題得證；如果pbetter=0，說明此時(shí)人工魚已經(jīng)到達(dá)局部極值。此時(shí)通過設(shè)置較小的try_number可以使其隨機(jī)移動(dòng)，跳出局部極值。

表1 10維函數(shù)BAFSA、GAFSA和IAFSA算法結(jié)果比較

由基本人工魚群算法可知，人工魚選擇一種行為的總概率為1，即ps+pf+pp=1，綜合上述兩種情況可得，?k＜i，pik＞0，證畢。

定理2改進(jìn)型人工魚群算法具有全局收斂性。

根據(jù)定理1中式（19）結(jié)論得：

由以上可知，轉(zhuǎn)移矩陣P′是n階可歸約隨機(jī)矩陣，滿足上述引理1中條件，所以，下式成立：

該矩陣是穩(wěn)定的隨機(jī)矩陣，故可得：

其中，F(xiàn)best為最優(yōu)目標(biāo)函數(shù)值，即Fbest=f(Xt)。因此，改進(jìn)型人工魚群算法具有全局收斂性，證畢。

5 仿真實(shí)驗(yàn)

5.1 典型函數(shù)仿真實(shí)驗(yàn)

為驗(yàn)證IAFSA的有效性，采用如下三個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真計(jì)算，并與BAFSA和文獻(xiàn)[16]提出的全局版人工魚群算法（GAFSA）進(jìn)行比較。

上述三個(gè)多維函數(shù)，理論最小值均為0。

設(shè)定參數(shù)如下：人工魚數(shù)目N=40，最多嘗試次數(shù)try_number=9，視野半徑visual=1，擁擠度因子δ= 0.618，步長step=0.5，上述三個(gè)函數(shù)變量取10維，用BAFSA、GAFSA和IAFSA分別對(duì)三個(gè)典型函數(shù)求m in，最大進(jìn)化代數(shù)設(shè)置為1 500次，連續(xù)運(yùn)行50次，將所得的函數(shù)全局平均最小值(Amin)、函數(shù)全局最小值(Gmin)和標(biāo)準(zhǔn)差(σ)作為算法性能的衡量指標(biāo)，所得結(jié)果如表1。

圖1～3是10維函數(shù)f1，f2，f3采用BAFSA、GAFSA和IAFSA運(yùn)行50次后得到的平均最小值進(jìn)化曲線，圖中縱坐標(biāo)用函數(shù)最優(yōu)平均值的自然對(duì)數(shù)表示。

圖1 函數(shù)f1平均最小值的進(jìn)化曲線

從實(shí)驗(yàn)的結(jié)果可以看出，IAFSA的平均優(yōu)化結(jié)果和最優(yōu)結(jié)果明顯好于GAFSA和BAFSA，并且優(yōu)化結(jié)果的精度遠(yuǎn)大于GAFSA和BAFSA，同時(shí)通過標(biāo)準(zhǔn)差的對(duì)比可以看出，IAFSA的穩(wěn)定性比GAFSA和BAFSA都要好一些。

圖2 函數(shù)f2平均最小值的進(jìn)化曲線

圖3 函數(shù)f3平均最小值的進(jìn)化曲線

表2 三機(jī)組系統(tǒng)BAFSA和IAFSA算法結(jié)果比較

表3 十機(jī)組系統(tǒng)BAFSA和IAFSA算法結(jié)果比較

圖4 三機(jī)組系統(tǒng)BAFSA和IAFSA算法收斂曲線

圖5 十機(jī)組系統(tǒng)BAFSA和IAFSA算法收斂曲線

5.2 機(jī)組組合系統(tǒng)仿真

為進(jìn)一步驗(yàn)證文中提出的算法的有效性，分別對(duì)三機(jī)組和十機(jī)組系統(tǒng)進(jìn)行仿真分析，機(jī)組參數(shù)、負(fù)荷需求等數(shù)據(jù)引用于文獻(xiàn)[17-18]中。算法參數(shù)取：人工魚數(shù)目N=200，最大進(jìn)化代數(shù)MAXGEN=300，最多嘗試次數(shù)try_number=100，視野半徑visual=25，擁擠度因子δ=9，步長step=8。

5.2.1 三機(jī)組系統(tǒng)

對(duì)三機(jī)組系統(tǒng)用本文提出的IAFSA進(jìn)行仿真計(jì)算，將得到的結(jié)果與BAFSA進(jìn)行比較，對(duì)改進(jìn)后的程序運(yùn)行30次取平均值，結(jié)果見表2。

從表2可以看出，IAFSA與BAFSA相比，效果較好，新型算法在精度上有了較大的提高，并且收斂速度也更快。BAFSA計(jì)算得到的近似最優(yōu)解為5 122.347$，平均耗時(shí)90.472 5 s；而IAFSA計(jì)算得到的近似最優(yōu)解為5 095.705$，平均耗時(shí)15.922 6 s。IAFSA在精度方面提高了0.5%，平均耗時(shí)方面提高了82.4%。

5.2.2 十機(jī)組系統(tǒng)

用本文提出的IAFSA進(jìn)行仿真計(jì)算，將得到的結(jié)果與BAFSA進(jìn)行比較，對(duì)改進(jìn)后的程序運(yùn)行30次取平均值，結(jié)果見表3。

從表3可以看出，對(duì)于十機(jī)組系統(tǒng)IAFSA與BAFSA相比，效果較好，改進(jìn)的算法在精度上有了很大的提高。

5.2.3 結(jié)果分析

為驗(yàn)證算法改進(jìn)的作用，將三機(jī)組和十機(jī)組系統(tǒng)BAFSA和IAFSA算法收斂過程的收斂特性作對(duì)比，收斂曲線如圖4和圖5所示。

從圖4和圖5可以看出，BAFSA容易陷入局部最優(yōu)解，出現(xiàn)早熟的現(xiàn)象。IAFSA能夠有效地跳出局部極值，經(jīng)過不斷迭代尋優(yōu)，最終趨于穩(wěn)定。

6 結(jié)束語

本文評(píng)述了BAFSA的規(guī)則和特點(diǎn)，提出了改進(jìn)型人工魚群算法，并將其用于求基準(zhǔn)測(cè)試函數(shù)的最小值和求解電力系統(tǒng)機(jī)組組合問題。采用線性遞減的視野函數(shù)，保證算法快速跳出局部極值區(qū)域，加快了該算法的收斂速度；當(dāng)人工魚在其感知范圍內(nèi)隨機(jī)選擇下一個(gè)狀態(tài)時(shí)，利用PSO中的慣性權(quán)重線性遞減來加速算法的收斂速度；用混沌現(xiàn)象代替BAFSA中的隨機(jī)現(xiàn)象，避免了算法丟失最優(yōu)解而陷入搜索停滯即出現(xiàn)早熟的現(xiàn)象?；鶞?zhǔn)測(cè)試函數(shù)、三機(jī)組和十機(jī)組系統(tǒng)的仿真計(jì)算結(jié)果均表明改進(jìn)型算法是求解機(jī)組組合問題的有效算法。

[1]陳皓勇，王錫凡.機(jī)組組合問題的優(yōu)化方法綜述[J].電力系統(tǒng)自動(dòng)化，1999，23（4）：51-56.

[2]朱宗斌，杜中軍.基于改進(jìn)GA的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（5）：77-80.

[3]楊靜俐，杜廷松.求解線性約束的二次規(guī)劃神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)新算法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（24）：37-39.

[4]李梓，于海濤，賈美娟.基于改進(jìn)模擬退火的優(yōu)化k-means算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（24）：77-80.

[5]Ma Jun.Research on the fish behavior simulation based on swarm intelligence[J].Procedia Engineering，2002，43：547-551.

[6]李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實(shí)踐，2002，22（11）：32-38.

[7]Cheng Y M，Jiang M Y，Yuan D F.Novel clustering algorithms based on improved artificial fish sw arm algorithm[C]//Proceedings of the 6th International Conference on Fuzzy Systems and Know ledge，2009：141-145.

[8]范玉軍，王冬冬，孫明明.改進(jìn)的人工魚群算法[J].重慶師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，24（3）：23-26.

[9]Jiang Jingqing，Bo Yuling，Song Chuyi，et al.Hybrid algorithm based on particle sw arm optimization and artificial fish swarm algorithm[J].Lecture Notes in Computer Science，2012，7367：607-614.

[10]Tsai Hsing-Chih，Lin Yong-Huang.Modification of the fish swarm algorithm with particle swarm optimization formulation and communication behavior[J].Applied Soft Computing，2011，11（8）：5367-5374.

[11]Simon S P，Padhy N P，Anand R S.An ant colony system approach for unit comm itment problem[J].Electrical Power and Energy Systems，2006，28：315-323.

[12]Yuan Xiaofang，Yang Yim in，Wang Hui.Improved parallel chaos optimization algorithm[J].Applied Mathematics and Computation，2012，219（8）：3590-3599.

[13]蔣秀潔，龔學(xué)會(huì)，李滄.基于MATLAB的計(jì)及閥點(diǎn)效應(yīng)的有功功率經(jīng)濟(jì)分配[J].電力學(xué)報(bào)，2008，23（6）：467-469.

[14]黃光球，劉嘉飛，姚玉霞.人工魚群算法的全局收斂性證明[J].計(jì)算機(jī)工程，2012，38（2）：204-206.

[15]Iosifescu M.Finite Markov processes and their applications[M].New York：John W iley Sons，1980.

[16]王聯(lián)國，洪毅，施秋紅.全局版人工魚群算法[J].系統(tǒng)仿真學(xué)報(bào)，2009，21（23）：7483-7486.

[17]Liao Daqian，Du Tingsong.Improvement on particle swarm optimization method solving unit comm itment dispatch in the power system considering the valve-point effect[C]// Proceedings of 2012 the 3rd International Conference on Mechanic Automation and Control Engineering. USA：IEEE Press，2012：323-326.

[18]吳月萍，杜奕.改進(jìn)的人工魚群算法的參數(shù)分析[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（13）：48-52.

ZHAI Junchen1,DU Tingsong1，2,LI Deyi2,LI Wenwu3

1.Institute of Nonlinear and Complex Systems, China Three Gorges University, Yichang, Hubei 443002, China
2.Hubei Province Key Laboratory of System Science in Metallurgical Process, Wuhan University of Science and Technology,Wuhan 430081, China
3.College of Electrical Engineering and Reusable Energy, China Three Gorges University, Yichang, Hubei 443002, China

An improved artificial fish swarm algorithm is proposed. The new algorithm uses the linear decreasing function instead of a fixed visual, uses linear decreasing inertia weight as the Particle Swarm Optimization（PSO）to accelerate the convergence speed of the algorithm, and uses chaos phenomenon instead of random phenomena of BAFSA. It presents the global convergence proof and carries on the simulation experiment with the test function and the systems of three units and ten units. The results show that the improved algorithm can escape from the local extremum effectively, and has higher convergence speed and precision. So it can be used as an effective algorithm for combined allocation problem.

unit commitment; Artificial Fish Swarm Algorithm（AFSA）; linear decreasing; chaos search

ZHAI Junchen, DU Tingsong, LI Deyi, et al. Improved artificial fish swarm algorithm for combined allocation problem. Computer Engineering and Applications, 2014, 50（17）：223-229.

A

TP301

10.3778/j.issn.1002-8331.1310-0198

國家自然科學(xué)基金（No.61174216，No.61374028）；湖北省自然科學(xué)基金（No.2013CFA 131）；冶金工業(yè)過程系統(tǒng)科學(xué)湖北省重點(diǎn)實(shí)驗(yàn)室（武漢科技大學(xué)）開放基金（No.z201402）。

翟軍臣（1988—），男，碩士研究生，主要研究領(lǐng)域?yàn)槿斯ぶ悄茉陔娏ο到y(tǒng)中的應(yīng)用、數(shù)值計(jì)算；杜廷松（1969—），男，通訊作者，教授，主要研究領(lǐng)域?yàn)樽顑?yōu)化理論與算法、智能計(jì)算；李德宜（1962—），男，教授，主要研究領(lǐng)域?yàn)橥贵w理論與控制理論；李文武（1975—），男，副教授，主要研究領(lǐng)域?yàn)殡娏ο到y(tǒng)信息安全、水電站仿真與控制及配電網(wǎng)分析。E-mail：tingsongdu@ctgu.edu.cn

2013-10-17

2013-11-25

1002-8331（2014）17-0223-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-03-12,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1310-0198.htm l