人工魚群與微粒群混合優化算法

摘 要:針對人工魚群算法局部搜索不精確、微粒群優化算法易發生過早收斂等問題，提出一種新的人工魚群與微粒群混合優化算法。算法的主要思想是先利用人工魚群的全局收斂性快速尋找到滿意的解域，再利用粒子群算法進行快速的局部搜索，所得混合算法具有局部搜索速度快，而且具有全局收斂性能。最后，以五個標準函數和一個應用實例進行測試，測試結果表明，提出的算法在一定程度上避免了陷入局部極小，加快了收斂速度且提高了搜索精度。

關鍵詞:微粒群算法; 人工魚群算法; 混合算法; 測試函數

中圖分類號:TP183;TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2084-03

doi:10.3969/j.issn.1001-3695.2010.06.025

Hybrid algorithm with artificial fish swarm algorithm and PSO

YAO Xiang-guang1， ZHOU Yong-quan2， LI Yong-mei1

(1.College of Computer Electron Information， Guangxi University， Nanning 530004， China; 2. College of Mathematics Computer Science， Guangxi University for Nationalities， Nanning 530006， China )

Abstract:The artificial fish swarm algorithm (AFSA) has a stronger robustness， and has a imprecision of solution. The particle swarm optimization algorithm (PSO) is simple and effective， and is easy in premature convergence. This paper presented a new hybrid evolutionary algorithm with artificial fish swarm algorithm and particle swarm optimization. This algorithm has the advantages of both AFSA and PSO. First， algorithm looked for satisfactory solution space with AFSA， later its search exacted solution with PSO. By doing experiments on five benchmark functions and a applicable examples， the results show that the algorithm avoids trapping into local optimum in a certain extent and improves the precision of convergence.

Key words:particle swarm optimization; artificial fish swarm algorithm; hybrid algorithm; test functions

人工魚群算法[1](AFSA)由李曉磊等人于2002年提出，該算法具有克服局部極值、取得全局極值的良好能力，并具有對初值、參數選擇不敏感、魯棒性強、簡單、易實現等優點，已經在神經網絡、模式識別、參數估計、辨識方法等諸多方面得到了應用[2，3]。但是隨著優化問題復雜程度和規模的不斷擴大，AFSA在優化初期具有較快的收斂性，后期卻往往收斂較慢，算法很難得到精確的最優解，只能找到滿意的解域。

微粒群優化算法[4] (PSO)是由美國社會心理學家Kennedy 和電氣工程學家Eberhart在1995 年提出的一種群智能優化算法，它是一種基于種群搜索策略的自適應隨機優化算法，也是一種很好的優化工具，擅長于解決連續問題的優化。PSO具有算法簡單、易于實現、計算量小和計算效率高的優點，因而吸引了許多學者對其進行研究。PSO最早應用于人工神經網絡的訓練方法，而現在其應用領域已擴展到多目標優化、數據分類、數據聚類、模式識別、路由計算、生物系統建模、流程規劃、信號處理、機器人控制、決策支持以及仿真和系統辯識等方面，并取得了很好的效果[5～7]。由于微粒間快速的信息交互，PSO具有較快的收斂速度，但又由于粒子都向最優方向移動，使得粒子趨向同一化，在優化具有高維復雜地形的函數時，算法往往存在著容易陷入局部最優、后期易于震蕩引起顯著的早熟現象而導致進化停滯的問題。

本文在分析了AFSA和PSO各自優缺點的基礎上，提出一種人工魚群與微粒群混合優化算法。仿真實驗結果表明，該算法是一種有效的混合優化算法。

1 基本算法

1.1 人工魚群算法

人工魚群算法是一類基于群智能(swarm intelligence)的隨機優化算法，它從構造動物簡單的底層行為做起，通過各動物個體的局部尋優行為，最終在群體中使全局最優值突現出來。其數學模型描述如下[8]:假設在一個n維的目標搜索空間中，有N條人工魚組成一個群體，每條人工魚個體的狀態可表示為向量X=(x1，x2，…，xn)，其中xi(i=1，2，…，n)為欲尋優的變量;人工魚當前所在位置的食物濃度表示為Y=f(x)，其中Y為目標函數;人工魚個體之間的距離表示為di，j=||Xi-Xj||;visual表示人工魚的感知范圍;σ表示擁擠度因子;step表示人工魚移動的步長;trynumber表示人工魚每次覓食最大的試探次數。

1.1.1 人工魚的行為描述

在每次迭代過程中，人工魚主要是通過覓食行為、聚群行為和追尾行為等來更新自己，從而實現尋優。具體的行為描述如下:

a)覓食行為。它是指魚朝著食物多的地方游動的一種行為。人工魚Xi在其視野內隨機選擇一個狀態Xj，分別計算目標函數值并進行比較，如果Yi

b)聚群行為。魚在游動過程中為了保證自身的生存和躲避危害會自然地聚集成群。人工魚Xi搜索當前視野內的伙伴數目nf，若伙伴中心有較多的食物且不太擁擠，則Xi朝伙伴的中心位置向前一步，否則執行覓食行為。

c)追尾行為。當魚群中的一條或幾條魚發現食物時，其鄰近的伙伴會尾隨其快速到達食物點。人工魚Xi搜索其視野內狀態最優的伙伴Xmax，如果Xmax的附近有較多的食物且不太擁擠，則Xi朝此伙伴前進一步，否則執行覓食行為。

d)隨機行為。它是指人工魚會在其視野內隨機地移動，當發現食物時，會向食物逐漸增多的方向快速地移去。

e)公告板。它用來記錄最優人工魚個體的狀態。每條人工魚每次行動完畢，將自身當前狀態與公告板狀態進行比較，如果優于公告板中的狀態，則用自身狀態更新公告板中的狀態，否則公告板的狀態不變，這樣就使公告板記錄下歷史最優的狀態。

1.1.2 移動策略

根據所要解決的問題性質，每條人工魚對當前所處的環境進行評價，從而選擇一種合適的行為策略。可以按照進步最快的原則或者進步即可的原則來選擇，如先進行追尾行為，如果沒有進步再進行覓食行為。最終，大量人工魚會聚集在幾個局部極值的周圍，而值較優的極值區域周圍一般會聚集大量的人工魚，從而達到尋優的目的。

1.2 微粒群優化算法基本原理

基本PSO算法[9，10]與其他演化算法相似，也是基于群體的，它將每一個可能產生的解表述為D維搜索空間中的一個無質量無體積的微粒點。設在D維搜索空間中有m個沒有重量和體積的微粒組成的一個種群，第i個粒子的當前位置為Xi=(xi1，xi2，…，xid)，飛行速度為Vi=(vi1，vi2，…，vid)。通過評價各微粒的目標函數確定t時刻每個微粒所經過的最佳位置Pi=(pi1，pi2，…，pid)，也稱為pbest;在群體里所有微粒經歷過的最好位置的索引號用符號g表示，即Pg，也稱為gbest。則對于每一代，粒子狀態更新方程為

vij(t+1)=ωvij(t)+c1r1(pij(t)-xij(t))+c2r2(Pg(t)-xij(t))(1)

xij(t+1)=xij(t)+vij(t+1)(2)

其中:ω為慣性權重;i=1，2，…，m表示微粒個數，j=1，2，…，D表示搜索空間維數;c1和c2為加速系數，r1和r2為兩個在[0， 1]內變化的隨機函數。式(1)中第一部分由微粒先前速度的慣性引起，為“慣性”行為;第二部分為微粒的“認知”行為，表示微粒本身的思考能力;第三部分為微粒的“社會”行為，表示微粒之間的信息共享與相互合作。為了提高微粒的有效性，搜索時，微粒的位置被最大位置和最小位置限制，如果微粒在某維的位置超出該維的最大位置或最小位置，則該微粒的位置被限制為該維的最大或最小位置。同樣，微粒的速度也被最大速度和最小速度所限制。

2 人工魚群與微粒群混合優化算法

2.1 人工魚群與微粒群混合優化算法基本思想

人工魚群算法對初值、參數選擇不敏感，具有良好的克服局部極值、取得全局極值的能力，但后期收斂速度較慢，只能找到滿意的解的域，很難得到精確的最優解。微粒群優化算法中的各個微粒根據自身所經歷的最好位置pbest和群體所經歷的最好位置gbest，利用式(1)(2)動態地調整當前速度和當前位置，具有較快的收斂速度。然而在算法后期，由于粒子的同一化，使得算法很難跳出局部最優，引起顯著的早熟現象。

若將兩種算法有機地結合起來，根據算法結合中“取長補短”的思想，保留兩種算法的優點:先利用人工魚群的全局收斂性快速尋找到滿意的解域，再利用粒子群算法進行快速的局部搜索，使得混合后的算法不僅具有快速的局部搜索速度，而且保證具有全局收斂性能。

2.2 人工魚群與微粒群混合優化算法流程

a)在可行域內隨機初始化人工魚群規模N、每條人工魚的初始位置、視野visual、移動步長step、擁擠度因子δ、最大重復嘗試次數trynumber、粒子群的加速系數c1和c2、魚群迭代次數、微粒群迭代次數等。

b)計算每條人工魚的適應度，并與公告板的狀態比較，若較好，則將其賦給公告板。

c)每條人工魚體通過覓食、聚群、追尾和隨機行為更新自己的位置。

d)魚群終止條件。若達到預設進化代數，將最優值、最優位置更新于公告板，轉e)，否則轉b)。

e)重新初始化所有微粒的位置和速度，或者將魚群最大進化代數時粒子的信息對應賦值給微粒群粒子信息。

f)將公告板最優位置、最優值信息賦給pbest和gbest。

g)評價每個微粒的適應度。

h)對每個微粒，將其適應值與其經歷過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest。

i)對每個微粒，將其適應值與全局所經歷的最好位置gbest作比較，如果較好，則更新全局最好位置gbest。

j)根據式(1)(2)更新微粒的速度和位置。

k)檢查終止條件(通常為達到預設進化代數或足夠好的適應值)，如果滿足終止條件，則輸出最優解，算法終止;否則轉g)。

3 仿真實驗

為驗證本文算法的有效性，下面給出五個典型標準測試函數和一個應用實例，將其最優值結果與文獻[11，12]作比較，并將其收斂速度分別與基本PSO算法、AFSA作比較。參數設置為c1=c2=1.7，粒子數為30，人工魚群進化代數為15代。測試函數中前兩個是單峰函數，其他為復雜的多峰函數。函數均為求最小值，函數1)~3)的最優值為0，函數4)的最優值為-1.031 628，函數5)的最優值為3。

3.1 典型標準測試函數比較

1)Sphere函數，稱為球面模型，用于測試優化算法局部尋優能力。

f1(x)=∑ni=1x2i，x∈(-100，100)n

2)Rosenbrock函數，稱為香蕉函數。

f2(x)=∑ni=1(100(xi+1-x2i)2+(xi-1)2)，x∈(-2.048，2.048)n

3)Rastrigin 函數。

f3(x)=∑ni=1(x2i-10cos(2πxi)+10)，x∈(-5.12，5.12)n

4)Camel函數。該函數有六個局部極小點(1.607105，0.568651)、(-1.607105， -0.568651)、(1.703607，-0.796084)、(-1.703607，0.796084)、(-0.0898，0.7126)以及(0.0898，-0.7126)。其中(-0.0898，0.7126)和(0.0898，-0.7126)為兩個全局最小點，最小值為-1.031628。

f4(x)=(4-2.1x21+x413)x21+x1x2+(-4+4x22)x22，x∈(-5.12，5.12)n

5)Goldste in-Price’s函數。該函數有一個全局最小值3在(0，-1)點，另外有三個局部極小值。

f5(x)=g(x)h(x)

其中:g(x)=1+(x1+x2+1)2(19-14x1+3x21-14x2+6x1x2+3x22);h(x)=30+(2x1-3x2)2(18-32x1+12x21+48x2-36x1x2+27x22)，x∈(-2，2)n。

表1為本文算法與文獻[12]中兩種自適應PSO算法在最優值、最優點上的比較;表2為本文算法與文獻[11]中三種不同慣性權重算法在最優值上的比較;表3為本文算法與基本PSO算法和基本AFSA算法連續運行20次所得函數全局最小值的平均值和平均迭代次數的比較。圖1~4分別為Sphere函數、Rosenbrock函數、Camel函數、Goldste in-Price’s函數在前50次進化中應用三種算法(基本PSO算法、基本AFSA算法和AFSA與PSO混合進化優化算法)在尋優值和收斂速度上的比較。其中，實線為本文算法收斂曲線，虛線為PSO算法收斂曲線，帶*號的實線為AFSA算法收斂曲線。

表1 與文獻[12]中兩種自適應PSO算法的比較

函數 最優點 最優解

經典自適應PSO改進的自適應PSO本文算法

最優點 最優解最優點 最優解最優點 最優解

f1(x) (0.0，0.0) 0(0.000071，0.0000010.00012)(0.000001，0.0000000.000000)(0.000000，00.000000)

f2(x) (1.0，1.0) 0(0.0097，0.99980.0048)(0.77e-6，1-0.12e-6)(1.000000，01.000000)

f4(x)(0.0898，-0.7126)(-0.0898，0.7126)-1.031628(0.1120，-1.029734-0.7150)

(0.0893，-1.031615-0.7121)(0.08982517370650， -0.71264075113962)(-0.08986490960070，0.71265869965287)-1.03162833174535

表2 與文獻[11]中三種不同慣性權重算法的比較

函數

慣性權重

線性遞減線性遞增先增后減

本文算法

Sphere函數最優值9.96e-108.94e-145.6633e-070

Rosenbrock函數最優值16.79846.24810.93290

Rastrigin 函數最優值15.267721.267719.66390

表3 與基本PSO算法和基本AFSA算法比較

函數

基本PSO基本AFSA本文算法

迭代數平均值迭代數平均值迭代數平均值

f5(x)5373.000027083.000000-06455463873.000000-00000000

3.2 應用實例比較[13]

求解激發態氫原子3s電子徑向波函數的節點。氫原子是最簡單的原子，激發態氫原子3s電子的徑向波函數為

R(r)=c(27-18rα-210+2r2α-20)er3α-10

其中:r是電子離核的徑向距離;c是歸一化常數，α0=0.529×10-10;m為常數。令c=1，x=rα-10，則上式可轉換為函數f(x)=(27-18x+2x2)e-x3。該f(x)=0方程的解所在可行域為0≤x≤15，則求解該方程的根問題可以轉換為求此函數的最小值問題，取適應度函數為

F=11+|f(x)|G=|g(x)|

參數設置為:初始群體規模N=50，感知范圍visual=1.5，步長step=0.3，擁擠度因子δ=0.618，粒子群的加速度參數c1和c2分別取1.2。表4為本文算法所得的方程近似根與文獻[14]中的根的比較情況。

表4 與文獻[13]中三種算法的比較

算法方程的根精度

文獻[14]算法1.90 7.100.00001

文獻[15]算法1.90 7.100.00001

進化策略算法1.901956 7.0983970.000001

本文算法1.90192484233901 7.098073351082131.0e-12

由上述圖表中數據的比較可以得出:從最優值比較，人工魚群與微粒群混合進化優化算法的平均最優值明顯優于所比較文獻的平均最優值，搜索精度明顯提高;從收斂速度比較，本文算法比基本PSO算法和基本AFSA算法收斂速度有明顯改善，說明算法能夠有效快速跳出局部最優，搜索到理想的最優值，也說明兩種算法取長補短、混合進化的有效性。

4 結束語

本文提出了人工魚群與微粒群混合優化算法，利用人工魚群算法全局收斂性好和粒子群算法收斂速度快等優點，取長補短，通過傳遞兩種算法的信息得到問題最優解。魚群先利用有限的進化代數尋找到滿意的全局收斂域，再將其信息共享給粒子群，使算法快速找到最優值。通過五個典型測試函數和一個應用實例與參考文獻結果的比較表明，本文提出的算法在有效避免陷入局部極值點、提高算法的搜索效率、收斂精度以及算法的穩定性等方面有顯著成效。

參考文獻:

[1]李曉磊，邵之江，錢積新. 一種基于動物自治體的尋優模式:魚群算法[J].系統工程理論與實踐， 2002，22(11):32-38.

[2]黃光球，陸秋琴，劉冠. 基于魚群算法的通風巷道漏風點辨識方法研究[J].系統仿真學報，2007，19(12):2677-2682.

[3]馬建偉，張國立，謝宏，等. 利用人工魚群算法優化前向神經網絡[J].計算機應用，2004，24(10):21-23.

[4]KENNEDY J，EBERHART R C.Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks.Perth:IEEE Press，1995:1942-1948.

[5]王凌，劉波.微粒群優化與調度算法[M].北京:清華大學出版社，2008.

[6]RAY T，LIEW K M.A swarm metaphor for multiovjective design optimization[J]. Engineering Optimization，2002，34(2):141-153.

[7]高海兵，高亮，周馳，等. 基于粒子群優化的神經網絡訓練算法研究[J].電子學報，2004，32(9):1572-1574.

[8]高尚，楊靜宇.群智能算法及其應用[M].北京:中國水利水電出版社，2006.

[9]李曉梅， 何佳. 微粒群算法的發展及應用[J]. 電腦開發與應用， 2008，21(11):28-30.

[10]謝曉鋒， 張文俊， 楊之廉. 微粒群算法綜述[J]. 控制與決策， 2003，18(2):129-134.

[11]崔紅梅， 朱慶保. 微粒群算法的參數選擇及收斂性分析[J]. 計算機工程與應用， 2007，43(23):89-91.

[12]童瑿，吳智銘，童爭雄.一種自適應的微粒群算法[J].計算機科學，2007，34(9):198-199.

[13]郭德龍，周永權.改進進化策略求解復雜化學方程根的研究[J]. 計算機與應用化學，2008，25(3):289-292.

[14]GAO Shi-bo， ZHANG Yun-tao.Particle swarm optimization algorithm and its application in extracting roots of complicated chemical equations[J].Jilin Chemical Industry Institute Journal，2007，24(1):38-41.

[15]CLERE M. The swarm and the queen:towards a deterministic and adaptive particle swarm optimization[C]//Proc of Congress on Evolutionary Computation.Piscatway:IEEE Service Center，1999:1951-1957.