溫陽(yáng)東， 殷運(yùn)鵬， 朱 楊

（合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院，安徽 合肥 230009）

0 引 言

系統(tǒng)的尋優(yōu)問(wèn)題是指在一定的資源環(huán)境約束條件下尋找系統(tǒng)的最佳設(shè)計(jì)方案，現(xiàn)代意義上的系統(tǒng)優(yōu)化問(wèn)題實(shí)質(zhì)上是計(jì)算機(jī)技術(shù)同數(shù)學(xué)規(guī)劃的統(tǒng)一。

對(duì)于一個(gè)實(shí)際問(wèn)題而言，在一定指標(biāo)的約束下如何使投資最小、取得的經(jīng)濟(jì)收益最大，是每個(gè)工程都需要考慮的重要問(wèn)題［1］。而復(fù)雜的非線性系統(tǒng)不是簡(jiǎn)單的串、并聯(lián)單元的結(jié)合，其目標(biāo)函數(shù)與約束函數(shù)多為非線性、非凸、不連續(xù)、不可微，甚至有多重極值，這些問(wèn)題導(dǎo)致很難用一般的解析方法對(duì)其進(jìn)行尋優(yōu)。

復(fù)雜的非線性系統(tǒng)的尋優(yōu)問(wèn)題發(fā)展至今，可用的方法仍然不多，并且沒(méi)有哪一種方法被證明是優(yōu)于其他方法的。從20世紀(jì)50年代開(kāi)始，在自然科學(xué)不斷發(fā)展的同時(shí)，很多人從大自然生態(tài)系統(tǒng)中得到靈感創(chuàng)新出具有啟發(fā)式的仿生優(yōu)化算法，并被用于復(fù)雜系統(tǒng)的尋優(yōu)。但是這些方法在解決實(shí)際問(wèn)題中仍然存在許多不足，例如最優(yōu)值不精確、算法繁瑣、無(wú)法逃出局部最優(yōu)值等。因此，復(fù)雜非線性系統(tǒng)的尋優(yōu)仍然是一個(gè)需要人們努力研究的問(wèn)題，對(duì)此本文提出了一種改進(jìn)的AFSA 算法［2］。

1 算法的基本原理

人工魚(yú)群算法（artificial fish school algorithm，AFSA）是文獻(xiàn)［3］于2002年提出的，該算法求全局極值的能力良好，并具有對(duì)初值、參數(shù)選擇不敏感等優(yōu)點(diǎn)，已在系統(tǒng)最優(yōu)化、神經(jīng)網(wǎng)絡(luò)、模式識(shí)別、參數(shù)估計(jì)、辨識(shí)方法等方面得以應(yīng)用［4］。

1.1 傳統(tǒng)的AFSA算法

AFSA算法是一種群體智能（swarm intelligence）優(yōu)化算法。在自然界，一片水域養(yǎng)魚(yú)，剛開(kāi)始魚(yú)隨機(jī)地被放養(yǎng)到這片水域中，但是一段時(shí)間后，魚(yú)往往能自行或者尾隨其他魚(yú)找到這片水域中食物最多的地方，因而一般情況下，魚(yú)集中的地方也就是這片水域中營(yíng)養(yǎng)物質(zhì)最豐富的地方。AFSA算法就是根據(jù)這一特點(diǎn)，構(gòu)造出理想的人工魚(yú)模仿魚(yú)群覓食來(lái)達(dá)到尋優(yōu)的目的。

AFSA模型的建立如下：在n維的可供搜索的空間內(nèi)模擬出N條人工魚(yú)，用多維向量表示為X＝（x1，x2，x3，…，xn），其中xi（i＝1，2，…，n）為尋優(yōu)目標(biāo)；每條人工魚(yú)所處水面位置的食物濃度為y＝f（X）；每2條人工魚(yú)之間的距離為dij＝｜xi－xj｜；每條人工魚(yú)每次移動(dòng)的步長(zhǎng)為Step；每條人工魚(yú)的視野范圍為Visual，即表示魚(yú)的感知范圍；某個(gè)區(qū)域內(nèi)判斷人工魚(yú)是否過(guò)于擁擠的擁擠因子為δ；尋優(yōu)的迭代次數(shù)為Num［5］。

1.1.1 人工魚(yú)的行為描述

在人工魚(yú)群的尋優(yōu)過(guò)程中，每次位置的更新都是通過(guò)覓食、聚群、追尾、隨機(jī)行為來(lái)進(jìn)行的。具體描述如下［6］：

（1）覓食行為。人工魚(yú)的當(dāng)前狀態(tài)為Xi，在它的感知范圍Visual內(nèi)，隨機(jī)選擇一個(gè)狀態(tài)Xj，如果yj＞yi，則向該方向前進(jìn)一個(gè)步長(zhǎng)Step，否則重新選擇狀態(tài)Xj，重復(fù)Num次后若無(wú)yj＞yi，則隨機(jī)移動(dòng)一個(gè)步長(zhǎng)Step。

（2）聚群行為。人工魚(yú)的當(dāng)前狀態(tài)為Xi，在它的感知范圍Visual內(nèi)搜尋伙伴們的數(shù)目np與中心位置Xc，如果yc／np＞δyi則表明區(qū)域內(nèi)不是很擁擠，向Xc的方向前進(jìn)一個(gè)Step，反之則繼續(xù)執(zhí)行覓食行為。

（3）追尾行為。人工魚(yú)的當(dāng)前狀態(tài)為Xi，在它的感知范圍Visual內(nèi)，yj濃度下最大的伙伴為Xj，如果yj／np＞δyi，表明伙伴Xj處有較大的食物濃度，且伙伴數(shù)量較少，則向伙伴Xj位置處移動(dòng)一個(gè)Step。

（4）隨機(jī)行為。即某條人工魚(yú)在Visual范圍內(nèi)，隨機(jī)選擇一個(gè)位置移動(dòng)，也是為了更大范圍地尋找伙伴或食物。

1.1.2 人工魚(yú)的行為選擇與特點(diǎn)

人工魚(yú)在進(jìn)行行為選擇時(shí)，總是遵循每一步都選擇向最優(yōu)化方向移動(dòng)最大的行為，即下一個(gè)狀態(tài)一定優(yōu)于當(dāng)前狀態(tài)，否則就進(jìn)行隨機(jī)行為。

綜上所述，傳統(tǒng)的人工魚(yú)群算法模型為：

其中，X為當(dāng)前魚(yú)的狀態(tài)；XV為Visual內(nèi)的某一狀態(tài)；Visual為魚(yú)的感知范圍；behaven為魚(yú)的行為選擇；Step為移動(dòng)1次的步長(zhǎng)；Xnext為迭代下一次的魚(yú)的狀態(tài)［7］。

1.1.3 傳統(tǒng)AFSA算法的局限性

AFSA算法解決了很多問(wèn)題，也具備了很多優(yōu)點(diǎn)。但當(dāng)傳統(tǒng)的AFSA算法被用于工程計(jì)算、優(yōu)化控制等實(shí)際工程中，會(huì)發(fā)現(xiàn)有明顯的不足之處［8］：① 前期收斂的速度很快，可是到了迭代后期速度明顯下降；② 精確度的獲取能力不足，只能得到最優(yōu)解域；③ 當(dāng)搜尋區(qū)域較大、處于變化平坦的區(qū)域時(shí)，收斂到全局最優(yōu)解的速度變慢，搜索效果不好。

1.2 改進(jìn)的雙空間自適應(yīng)嵌套AFSA算法

針對(duì)傳統(tǒng)AFSA算法在復(fù)雜非線性系統(tǒng)中的局限性，本文采取了雙空間二次迭代的改進(jìn)。

1.2.1 改進(jìn)思路

本文采取的改進(jìn)思路如下：

（1）第1次尋優(yōu)，采取稍大的Visual與稍大的Step開(kāi)始，并在迭代過(guò)程中隨著迭代次數(shù)的增大，快速地在整個(gè)水域里找尋出最優(yōu)解域。

（2）第2次尋優(yōu)以第1次搜尋出的最優(yōu)解域作為整個(gè)水域，以第1次最優(yōu)解域內(nèi)的人工魚(yú)默認(rèn)為產(chǎn)出子代的人工魚(yú)，子代人工魚(yú)的視野與步長(zhǎng)均做出相應(yīng)的調(diào)整，并在不斷的迭代中自適應(yīng)做出調(diào)整，即可在一代最優(yōu)域的基礎(chǔ)上精確尋優(yōu)。由于空間的變化，擁擠因子也做出相應(yīng)調(diào)整。

1.2.2 雙空間自適應(yīng)嵌套AFSA算法模型

第1次全空間搜索的模型為：

第2次最優(yōu)域空間內(nèi)搜索的子代魚(yú)模型為：

其中，Visual0為初始最大的視野；Step0為初始最大的步長(zhǎng)；iter為當(dāng)前迭代的次數(shù)；Num為總迭代次數(shù)。上標(biāo)1、2分別為一代魚(yú)和二代魚(yú)（即子代魚(yú)）。

從公式上看第2次與第1次迭代差不多，但是其子代魚(yú)的水域、視野、步長(zhǎng)、擁擠因子都根據(jù)水域的變化而不同，并會(huì)在迭代中自適應(yīng)調(diào)整。

2 算法對(duì)復(fù)雜系統(tǒng)尋優(yōu)的實(shí)現(xiàn)

所謂復(fù)雜的非線性系統(tǒng)是因?yàn)槠鋫鬟f函數(shù)、目標(biāo)函數(shù)、約束函數(shù)的非線性與復(fù)雜性，使其難以設(shè)計(jì)尋優(yōu)方案，或者尋優(yōu)的結(jié)果不理想。而實(shí)際工作中的系統(tǒng)較多為復(fù)雜非線性系統(tǒng)，因此面對(duì)復(fù)雜非線性函數(shù)的尋優(yōu)常常十分困難［9］。

按照改進(jìn)的算法，復(fù)雜非線性系統(tǒng)尋優(yōu)的實(shí)現(xiàn)分為第1次全空間搜索和第2次最優(yōu)域空間內(nèi)搜索。

第1次全空間搜索步驟如下：

（1）根據(jù)實(shí)驗(yàn)經(jīng)驗(yàn)選取合適的人工魚(yú)數(shù)目N、初始視野Visual0、初始步長(zhǎng)Step0、最大迭代次數(shù)Num、擁擠因子δ。因?yàn)槭堑?次搜索，Visual0與Step0可適當(dāng)選擇較大值，以便快速找到全局的最優(yōu)域。

（2）當(dāng)前迭代次數(shù)iter＝0，隨機(jī)生成N條人工魚(yú)，魚(yú)群初始化完成。

（3）計(jì)算每條魚(yú)位置處的食物濃度FD，將最大的FD值寫(xiě)入公告板中，即在系統(tǒng)約束條件下計(jì)算該系統(tǒng)的最優(yōu)解，F(xiàn)D值為最優(yōu)解的相反數(shù)。

（4）按照（3）式和（4）式的模型，人工魚(yú)進(jìn)行行為選擇并不停地尋優(yōu)，直至到達(dá)最大迭代次數(shù)時(shí)結(jié)束。

第1次全空間搜索的目的是為了快速得到最優(yōu)解域，因此其迭代次數(shù)不需要過(guò)大，否則會(huì)增加許多不必要的計(jì)算。

第2次最優(yōu)域空間內(nèi)搜索步驟如下：

（1）把第1次尋優(yōu)的最優(yōu)域空間B作為本次尋優(yōu)的全空間，第1次尋優(yōu)結(jié)束時(shí)B空間內(nèi)有Nb條人工魚(yú)，默認(rèn)這Nb條魚(yú)產(chǎn)下子代魚(yú)后死亡。

（2）子代魚(yú)的初始視野與初始步長(zhǎng)均為一代魚(yú)的1／2，該空間內(nèi)可能存在擁擠的情況，因而根據(jù)實(shí)驗(yàn)變動(dòng)Num和擁擠因子δ，求極大值可使δ適當(dāng)減小。

（3）視野與步長(zhǎng)按照（5）式和（6）式的自適應(yīng)方式在每一次迭代中進(jìn)行不斷的自適應(yīng)，從而選擇出相應(yīng)的行為進(jìn)行迭代。

（4）當(dāng)連續(xù)n次的尋優(yōu)結(jié)果的均方差小于停止因子γ時(shí)，可視為尋優(yōu)完成，停止迭代。

在雙空間自適應(yīng)嵌套尋優(yōu)過(guò)程中可能會(huì)出現(xiàn)人工魚(yú)某一狀態(tài)不滿足約束條件，則在該人工魚(yú)ε鄰域內(nèi)隨機(jī)選取一個(gè)值判斷是否滿足約束條件，若不滿足則重新選取直至滿足為止。

3 改進(jìn)算法的測(cè)試

3.1 測(cè)試復(fù)雜非線性系統(tǒng)函數(shù)

具有普遍性的3個(gè)測(cè)試系統(tǒng)如下：?

測(cè)試系統(tǒng)的函數(shù)圖形如圖1所示。

圖1 3個(gè)測(cè)試系統(tǒng)的函數(shù)圖像

由圖1可知，f1有5個(gè)非等高極值，且全局最優(yōu)值為0.908 3；f2為二維多峰函數(shù)，有3個(gè)極值，全局最優(yōu)解為10.007 0；f3為Schaffer函數(shù)，該函數(shù)只有1個(gè)全局最大值1，在該最小谷值周圍有多個(gè)圈脊，形成無(wú)數(shù)個(gè)局部最大值，在尋優(yōu)過(guò)程中很容易停留在圈脊帶上。

3.2.3 種算法尋優(yōu)對(duì)比

對(duì)上述3個(gè)復(fù)雜非線性系統(tǒng)函數(shù)運(yùn)用遺傳算法［10］（GA）、傳統(tǒng) AFSA算法、本文改進(jìn)的 AFSA算法進(jìn)行尋優(yōu)對(duì)比。GA算法采用Matlab遺傳算法工具箱［11］，種群規(guī)模為N＝30，交叉概率為Pc＝0.92，變異概率為pm＝0.08，迭代次數(shù)為100。傳統(tǒng)AFSA對(duì)應(yīng)3個(gè)系統(tǒng)的Visual分別為0.26、4.06、0.26，Step分別為0.12、1.90、1.90，擁擠因子δ為0.103，魚(yú)群數(shù)目為50。本文改進(jìn)的AFSA算法第1空間的Visual和Step采用傳統(tǒng)AFSA算法參數(shù)的120%，δ為0.103；第2空間的Visual和Step為第1空間參數(shù)的1／2，δ降為0.086。

3種算法在相同的PC平臺(tái)上運(yùn)行25次，平均尋優(yōu)結(jié)果對(duì)比見(jiàn)表1所列，其中t為每次計(jì)算時(shí)魚(yú)群首次找到最優(yōu)解的所用時(shí)間。測(cè)試平臺(tái)參數(shù)如下：Pentium（R）Dual－Core CPU 2.2GHz，RAM 2.0GB，32位系統(tǒng)。

表1 3種算法平均尋優(yōu)結(jié)果對(duì)比

測(cè)試結(jié)果分析如下：

（1）f1與f2系統(tǒng)中，本文改進(jìn)的AFSA算法的平均最優(yōu)解的精度和找到最優(yōu)解的速度比傳統(tǒng)AFSA算法與GA算法都有一定程度的提升。

（2）從圖1中可以看出，f3系統(tǒng)眾多的局部極值與全局極值非常接近，因此3種算法尋優(yōu)效果較為接近。

4 實(shí)際算例分析探討

大規(guī)模輸電電網(wǎng)的規(guī)劃是一個(gè)容易陷入局部極值的尋優(yōu)問(wèn)題。選擇被廣泛采用的IEEE Garver－18點(diǎn)系統(tǒng)對(duì)本文AFSA算法進(jìn)行測(cè)試。系統(tǒng)如圖2所示，其中實(shí)線表示原有網(wǎng)絡(luò)，虛線表示可擴(kuò)建的線路［12］。

圖2 Garver－18點(diǎn)系統(tǒng)

運(yùn)用本文AFSA算法，經(jīng)調(diào)試，取人工魚(yú)數(shù)目N＝25；2次空間的最大迭代次數(shù)分別為Num1＝50，Num2＝150，一代魚(yú)的Visual為6，二代魚(yú)的Visual為2；2次空間的擁擠因子分別為0.4和0.2；過(guò)負(fù)荷檢驗(yàn)采用直流潮流。計(jì)算得出的規(guī)劃結(jié)果見(jiàn)表2所列。

表2 Garver－18點(diǎn)系統(tǒng)規(guī)劃方案

為了評(píng)價(jià)該算法的性能，分別采用GA算法、傳統(tǒng)AFSA算法和本文AFSA算法在同一個(gè)PC平臺(tái)上對(duì)18節(jié)點(diǎn)系統(tǒng)進(jìn)行優(yōu)化，各計(jì)算50次，算法對(duì)比結(jié)果見(jiàn)表3所列。

表3 算法對(duì)比結(jié)果

由表3可以看出，本文改進(jìn)后的AFSA算法具有穩(wěn)定的收斂性能且用時(shí)較短。

通過(guò)輸電網(wǎng)規(guī)劃的Garver－18點(diǎn)系統(tǒng)算例可以看出，相比于傳統(tǒng)AFSA算法，改進(jìn)后的算法在電力系統(tǒng)規(guī)劃、多級(jí)階梯物流中轉(zhuǎn)運(yùn)輸系統(tǒng)的優(yōu)化等多極值復(fù)雜系統(tǒng)尋優(yōu)中具有收斂穩(wěn)定、用時(shí)較短等技術(shù)優(yōu)勢(shì)。

5 結(jié)束語(yǔ)

本文改進(jìn)人工魚(yú)群算法，提出了雙空間自適應(yīng)嵌套AFSA算法。通過(guò)理論分析測(cè)試、實(shí)際算例檢驗(yàn)，證明了該算法具有穩(wěn)定的收斂性，不會(huì)陷入局部最優(yōu)點(diǎn)，并相對(duì)提高了部分復(fù)雜非線性系統(tǒng)的尋優(yōu)能力。

由于AFSA算法的研究尚處于初期，還有許多問(wèn)題，如算法的靈敏度和適用域?qū)挾取⒗碚摰耐茝V等有待進(jìn)一步研究。

［1］ 王華偉，高 軍.復(fù)雜系統(tǒng)可靠性分析與評(píng)估［M］.北京：科學(xué)出版社，2013：5－9.

［2］ 高 尚，楊靜寧.群智能算法及其應(yīng)用［M］.北京：中國(guó)水利水電出版社，2006：3－7.

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

［4］ 江銘炎，袁東風(fēng).人工魚(yú)群算法及其應(yīng)用［M］.北京：科學(xué)出版社，2012：112－124.

［5］ 李曉磊，薛云燦，路 飛.基于人工魚(yú)群算法的參數(shù)估計(jì)方法［J］.山東大學(xué)學(xué)報(bào)：工學(xué)版，2004，34（3）：84－87.

［6］ 李曉磊，錢(qián)積新.基于分解協(xié)調(diào)的人工魚(yú)群優(yōu)化算法研究［J］.電路與系統(tǒng)學(xué)報(bào)，2003，8（1）：1－6.

［7］ Carvalho D R，F(xiàn)reitas A A.A genetic algorithm for discovering small disjunct rules in data mining［J］.Applied Soft Computing，2002，2（2）：75－88.

［8］ Wang Z，Z W，Wang Z，et al.Classification rule mining with an improved ant colony algorithm［J］.Lecture Notes in Computer Science，2005，3339：357－367.

［9］ 倪 健，馬昌鳳.解非線性方程的一種新的全局快速算法［J］.合 肥 工 業(yè) 大 學(xué) 學(xué) 報(bào)：自 然 科 學(xué) 版，2011，34（4）：620－622.

［10］ 張梅鳳.人工魚(yú)群智能優(yōu)化算法的改進(jìn)及應(yīng)用研究［D］.大連：大連理工大學(xué)，2008.

［11］ 雷英杰.MATLAB遺傳算法工具箱及應(yīng)用［M］.西安：西安電子科技大學(xué)出版社，2008：34－45.

［12］ 金義雄，程浩忠.改進(jìn)粒子群算法及其在輸電網(wǎng)規(guī)劃中的應(yīng)用［J］.中國(guó)電機(jī)工程學(xué)報(bào)，2005，25（2）：46－50.