求解機組組合問題的改進型人工魚群算法研究

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

1.三峽大學非線性與復雜系統研究所，湖北宜昌 443002

2.武漢科技大學冶金工業過程系統科學湖北省重點實驗室，武漢 430081

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

◎工程與應用◎

求解機組組合問題的改進型人工魚群算法研究

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

1.三峽大學非線性與復雜系統研究所，湖北宜昌 443002

2.武漢科技大學冶金工業過程系統科學湖北省重點實驗室，武漢 430081

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

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

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

1 引言

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

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

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

2 BAFSA基本框架

在一片水域中，魚往往能自行或尾隨其他魚找到營養物質多的地方，因而魚生存數目最多的地方一般就是本水域中營養物質最多的地方。BAFSA就是根據這一特點，通過構造人工魚來模擬魚群的覓食、聚群、追尾及隨機行為，從而實現尋優[9-10]。

2.1 相關定義

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

2.2 行為描述

（1）覓食行為

這是人工魚的一種基本行為，也就是趨向食物的一種活動。設人工魚i當前狀態為Xi，在其感知范圍內隨機選擇一個狀態Xk：

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

否則，再重新隨機選擇狀態Xk，判斷是否滿足前進條件。這樣反復嘗試try_number次后，如果仍不滿足前進條件，則執行隨機行為。

（2）聚群行為

否則，執行覓食行為。

（3）追尾行為

否則，執行覓食行為。

（4）隨機行為

隨機行為的實現較簡單，就是在視野中選擇一個狀態，然后向該方向移動，其實，它是覓食行為的一個缺省行為，即Xi的下一個位置為：

3 改進型人工魚群算法

3.1 改進措施

（1）一般來講，當視野范圍較小時，人工魚群的覓食行為和隨機游動比較突出，可能導致算法陷入局部最優解；視野范圍較大時，人工魚的追尾行為和聚群行為將變得較突出，較容易發現全局極值并收斂，而人工魚在比較大的區域內執行覓食行為和隨機行為，不利于全局極值附近的人工魚發現鄰近范圍內的全局極值點。故對人工魚的視野進行適當的改變：在算法的初始階段，每條人工魚以一個大的視野尋找解，這樣能擴大尋優的范圍。隨著算法進化代數的增加，魚群的視野將適當地減小以加快收斂速度，提高算法的優化性能。因此，采用線性遞減的視野，定義視野的變化函數為：

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

（2）對覓食行為中人工魚的視野作進一步改進，當人工魚在其感知范圍內隨機選擇下一個狀態時，利用PSO中慣性權重線性遞減的視野代替原來的視野[11]，加速算法的收斂速度。具體如下：

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

（3）混沌運動具有遍歷性隨機性等特性，能夠在一定的范圍內按其自身規律不重復遍歷所有狀態[12]。因此，在BAFSA中的隨機行為將混沌搜索引入其中，即用混沌現象代替隨機現象。

其中，CXi為混沌變量，u為控制參數，Xmax、Xmin分別為Xi的最大值和最小值，是當前狀態，X為下一個狀態?；煦绗F象執行簡單并且能夠避免陷入局部極值。

混沌映射式（10）為Logistic映射，取控制參數u=4時，式（10）處于混沌狀態，也就是說除（0，0.25，0.5，0.75，1）這幾個點外，其他點都是通過迭代公式產生的，它們都處于0和1之間。因為混沌現象的軌跡對初始值非常敏感，如果n個決策變量的初始值不同，就可以得到n個不同的混沌軌跡。

IAFSA步驟如下：

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

步驟2利用公式（6）計算人工魚當前的視野值，計算每條人工魚的適應度值，并記錄全局最優的人工魚的狀態。

步驟3對每條人工魚進行評價，對其要執行的行為進行選擇，包括覓食行為、聚群行為、追尾行為和隨機行為。

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

步驟5更新全局最優人工魚的狀態。

步驟6判斷是否滿足終止條件，若滿足，則輸出結果，否則，跳轉到步驟2。

3.2 算法的應用

在實際情況中，汽輪機進氣閥突然開啟時會產生閥點效應，該效應對于最優分配的求解影響明顯[13]。文中研究的是一個靜態計及閥點效應的機組組合優化問題，模型中對負荷平衡、機組技術出力等實際情況進行約束，建立了追求發電成本最小的機組組合優化數學模型。

考慮閥點效應后的耗電特性為：

其中，Fi為第i臺發電機的發電費用，Pi為第i臺發電機的有功功率，ai、bi、ci為第i臺發電機的運行特性參數，ei，fi為第i臺發電機的閥點效應系數，Pimin為第i臺發電機的最小出力。

綜上所述，計及閥點效應的機組優化數學模型如下：

其中，F為總的發電費用，N為系統內發電機的總數，PL為系統負荷，PD為系統網損，Pimin，Pimax分別是機組出力的最小值和最大值。當電力系統網絡覆蓋密集時可以忽略網損，文中在計算時忽略了系統網損。

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

其中，ub和lb分別是機組發電功率的最大值和最小值；X為初始的人工魚群狀態。引進懲罰因子，將UC的目標函數轉化為：

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

若Xj不在感知范圍內，則執行改進后的隨機行為式（10）：

本次循環結束后，自動更新人工魚的當前狀態X和當前位置的食物濃度Y。當進化代數大于等于最大進化代數(gen≥MAXGEN)的時候，則停止運算并求出仿真計算中的全局近似最優解（機組總耗量最?。?/p>

4 收斂性分析

4.1 概念及引理

其中，F(a)為目標函數；gi(a)為第i個約束條件；M為約束條件個數；a為n維未知變量；Z為搜索空間。當問題規模為n時，搜索空間Z為機組的組合變量空間，是一個離散的狀態空間，狀態數一共有|Z|=2n。令Y={F(a)|a∈Z}，則有Y={F(a)|a∈Z}，|Y|＜|Z|。設|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個人工魚的位置狀態。在人工魚的行為過程中，從一個狀態轉移到另外的狀態可表示為Xi，j→Xk，l，則從Xi，j到Xk，l的轉移概率為pij，kl，從Xi，j到X中任一人工魚位置狀態的轉移概率為pij，k，從X中任一人工魚位置狀態到中任一人工魚位置狀態的轉移概率為pi，k，則有[14]：

P′∞為一個穩定的隨機矩陣，且P′∞=1′P′∞，P′∞= P′0P′∞唯一確定并且與初始分布無關，P′∞滿足如下條件：

4.2 全局收斂性證明

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

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

式（18）得證。

對于式（19），由BAFSA中對每個人工魚探索其當前所處的環境狀況，選擇一種行為（覓食、聚群或者追尾），設bestt+1為Xt+1中最優人工魚。采取線性遞減的函數值代替固定的視野，只改變人工魚選擇行為的概率值，僅對收斂速度產生影響，而不影響算法的收斂性。以下分情況進行分析：

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

情況2如果當前人工魚選擇覓食行為，說明此時當前人工魚在鄰域內為最優，則此時人工魚選擇此種行為的概率pp=1-ps-pf，此時人工魚探索感知范圍隨機選擇狀態，有兩種情況：

（1）選擇的狀態位置食物濃度高于當前食物濃度，設此種情況的概率為ppy，命題得證。

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

表1 10維函數BAFSA、GAFSA和IAFSA算法結果比較

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

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

根據定理1中式（19）結論得：

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

該矩陣是穩定的隨機矩陣，故可得：

其中，Fbest為最優目標函數值，即Fbest=f(Xt)。因此，改進型人工魚群算法具有全局收斂性，證畢。

5 仿真實驗

5.1 典型函數仿真實驗

為驗證IAFSA的有效性，采用如下三個基準測試函數進行仿真計算，并與BAFSA和文獻[16]提出的全局版人工魚群算法（GAFSA）進行比較。

上述三個多維函數，理論最小值均為0。

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

圖1～3是10維函數f1，f2，f3采用BAFSA、GAFSA和IAFSA運行50次后得到的平均最小值進化曲線，圖中縱坐標用函數最優平均值的自然對數表示。

圖1 函數f1平均最小值的進化曲線

從實驗的結果可以看出，IAFSA的平均優化結果和最優結果明顯好于GAFSA和BAFSA，并且優化結果的精度遠大于GAFSA和BAFSA，同時通過標準差的對比可以看出，IAFSA的穩定性比GAFSA和BAFSA都要好一些。

圖2 函數f2平均最小值的進化曲線

圖3 函數f3平均最小值的進化曲線

表2 三機組系統BAFSA和IAFSA算法結果比較

表3 十機組系統BAFSA和IAFSA算法結果比較

圖4 三機組系統BAFSA和IAFSA算法收斂曲線

圖5 十機組系統BAFSA和IAFSA算法收斂曲線

5.2 機組組合系統仿真

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

5.2.1 三機組系統

對三機組系統用本文提出的IAFSA進行仿真計算，將得到的結果與BAFSA進行比較，對改進后的程序運行30次取平均值，結果見表2。

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

5.2.2 十機組系統

用本文提出的IAFSA進行仿真計算，將得到的結果與BAFSA進行比較，對改進后的程序運行30次取平均值，結果見表3。

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

5.2.3 結果分析

為驗證算法改進的作用，將三機組和十機組系統BAFSA和IAFSA算法收斂過程的收斂特性作對比，收斂曲線如圖4和圖5所示。

從圖4和圖5可以看出，BAFSA容易陷入局部最優解，出現早熟的現象。IAFSA能夠有效地跳出局部極值，經過不斷迭代尋優，最終趨于穩定。

6 結束語

本文評述了BAFSA的規則和特點，提出了改進型人工魚群算法，并將其用于求基準測試函數的最小值和求解電力系統機組組合問題。采用線性遞減的視野函數，保證算法快速跳出局部極值區域，加快了該算法的收斂速度；當人工魚在其感知范圍內隨機選擇下一個狀態時，利用PSO中的慣性權重線性遞減來加速算法的收斂速度；用混沌現象代替BAFSA中的隨機現象，避免了算法丟失最優解而陷入搜索停滯即出現早熟的現象?；鶞蕼y試函數、三機組和十機組系統的仿真計算結果均表明改進型算法是求解機組組合問題的有效算法。

[1]陳皓勇，王錫凡.機組組合問題的優化方法綜述[J].電力系統自動化，1999，23（4）：51-56.

[2]朱宗斌，杜中軍.基于改進GA的云計算任務調度算法[J].計算機工程與應用，2013，49（5）：77-80.

[3]楊靜俐，杜廷松.求解線性約束的二次規劃神經網絡學習新算法[J].計算機工程與應用，2010，46（24）：37-39.

[4]李梓，于海濤，賈美娟.基于改進模擬退火的優化k-means算法[J].計算機工程與應用，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]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優模式：魚群算法[J].系統工程理論與實踐，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].重慶師范大學學報：自然科學版，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]蔣秀潔，龔學會，李滄.基于MATLAB的計及閥點效應的有功功率經濟分配[J].電力學報，2008，23（6）：467-469.

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

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

[16]王聯國，洪毅，施秋紅.全局版人工魚群算法[J].系統仿真學報，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].計算機工程與應用，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

國家自然科學基金（No.61174216，No.61374028）；湖北省自然科學基金（No.2013CFA 131）；冶金工業過程系統科學湖北省重點實驗室（武漢科技大學）開放基金（No.z201402）。

翟軍臣（1988—），男，碩士研究生，主要研究領域為人工智能在電力系統中的應用、數值計算；杜廷松（1969—），男，通訊作者，教授，主要研究領域為最優化理論與算法、智能計算；李德宜（1962—），男，教授，主要研究領域為凸體理論與控制理論；李文武（1975—），男，副教授，主要研究領域為電力系統信息安全、水電站仿真與控制及配電網分析。E-mail：tingsongdu@ctgu.edu.cn

2013-10-17

2013-11-25

1002-8331（2014）17-0223-07

CNKI網絡優先出版：2014-03-12,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1310-0198.htm l