一種改進的人工魚群算法

崔麗英，黃殿平，宋曉阜新市第一中等職業技術專業學校；遼寧工程技術大學

一種改進的人工魚群算法

崔麗英1，黃殿平2，宋曉2
1阜新市第一中等職業技術專業學校；2遼寧工程技術大學

摘要：人工魚群算法是一種高效的群體智能尋優算法。本文提出一種改進智能魚群算法，引入云學習因子和云變異因子，使算法在尋優過程中的學習能力有所提高，避免算法在尋優過程中游動行為的不確定性，提高了算法的尋優能力。

關鍵詞：魚群算法；云模型；優化

1　引言

2002年，我國知名學者李曉磊[1-2]提出了人工魚群算法（Artifi?cial Fish-swarm Algorithm,AFSA）理論，AFSA主要是通過仿生魚的覓食、群聚、游弋和追尾行為，從單條人工魚的底層局部尋優從而達到群體全局尋優。由于AFSA魯棒性強，算法簡單且容易實現，一經提出就引起了廣泛關注[3]。本文為了解決魚群進化過程中隨機性與傾向性的兼容問題，采用云模型的思想，提出一種基于云的人工魚群算法（Cloudy Model-Artificial Fish-swarm Algorithm，CMAFSA）。

2　AFSA和CM-AFSA

2.1AFSA算法

在AFSA算法中，N表示魚群容量，Visual代表可視域，Step代表步長，Try_number代表迭代次數，δ為擁擠度因子，每個人工魚的狀態表示為X=(x1,x2,…,xn)，其中xi(i=1,2,…,n)代表尋優變量。Y=f(X )代表人工魚食物濃度，其中Y為目標函數值，表示兩個人工魚個體之間的距離。

2.1.1追尾行為

設Xi為人工魚此刻的位置狀態，在可視域范圍內搜索此刻最優的人工魚Xmax，當Yi

2.1.2覓食行為

設Xi為人工魚此刻的位置狀態，該人工魚在其可視域內搜索，若發現有狀態Xj，且Xj所在位置的食物濃度Yj大于當前狀態Xi的食物濃度，那么當前人工魚將會朝該方向移動一步；否則，如果Xj所在位置的食物濃度小于當前食物濃度，那么在可視域內隨機選擇下一個狀態再次與當前狀態進行比較。嘗試Try_number次后，如果在該可視域中無更優狀態，那么此人工魚隨意移動一個步長。

2.1.3群聚行為

設Xi為人工魚此刻的位置狀態，其可視域內所有人工魚的集合為S。

如果存在非空集合S，則表示此刻人工魚可視域內存在其他人工魚，其魚群容量Nf≥1，如果當前狀態Yi

2.1.4隨機行為

人工魚的隨機行為是人工魚覓食行為的缺省行為之一，在此刻人工魚可視域范圍內隨意選定其后一狀態并向此狀態前進一個步長。此行為為人工魚個體提供隨機游弋的機會，可以提高種群多樣性，同時能夠跳出局部最優以達到全局最優。

3　云模型

3.1云模型定義

云模型是李德毅院士提出的一種定性定量轉換模型[4]，可以實現定性與定量間的不確定性轉換。設U是一個普通集合表示的論域，C對應論域U上相聯系的語言值，存在數值x∈U，滿足x～N(Ex,)是C的一次隨機實現，其中En1～N(En,)，數值x對C的確定度μ(x)∈[0,1]是具有穩定傾向的隨機數。若

則x在論域U上的分布稱為云模型，簡稱云[5]。

3.2云模型的數字特征

云用期望Ex（Expected value）、熵En（Entropy）和超熵He（Hy?per entropy）三個數字特征來整體表征一個概念，多個數字特征的組合能夠體現云模型在全局中的特性[3]。

3.3云發生器

按云的產生機理和計算方向，有正向云和逆向云[6]。它是整個云模型的核心理論。

3.3.1正向云

正向云是依據云模型的數字特征將定性概念轉化為定量數值，其方法是通過云的數字特征（Ex,En,He）來生成云滴，此過程是直接前向的，如圖1所示。輸入定性概念的Ex、En以及He，根據對應關系輸出云滴drop(xi,μi)，其中xi代表定性概念在U中的位置，μi是隸屬度。

圖1　正向云發生器

3.3.2逆向云

逆向云實現定量值與定性概念之間過程轉換，該發生器能把數據轉換成具有數字特征(Ex,En,He)來進行表達。如圖2所示，逆向云是于統計原理思想設計的。

圖2　逆向云發生器

4　基于云模型的魚群算法

針對AFSA后期收斂性差、易陷入局部最優等缺點，本文將云的概念引入到魚群算法中進行建模，通過正太云實現人工魚的自適應進化，引入云變異的均衡概念，提出了一種基于云模型的人工魚群算法。CM-AFSA與其他AFSA改進算法的區別在于增加了魚群的自主學習能力，對云參數進行了自適應處理。CM-AFSA引入云學習因子和云變異因子。

云學習因子是在魚群學習過程中，兩個適應度不相同的個體人工魚，通過正態云產生新人工魚的過程。設xf、xm為互相進化的兩個人工魚的當前狀態，Ff、Fm為兩個人工魚個體適應度，則云學習因子的期望、熵、超熵為：

云變異因子是在魚群在學習過程中，人工魚通過自身攜帶的適應度，再通過正態云產生新人工魚的過程。設xi是當前某個人工魚狀態，Fi是此個個體的適應度，則云變異因子的期望、熵、超熵分別為：

CM-AFSA算法描述如下：

（1）由適應度函數定義，在U中隨機產生n個人工魚x1,x2,…,xn，初始化種群X={x1,x2,…} ,xn，步長Step、可視域Visual、擁擠度δ和代數Try_number；

（2）計算每個人工魚適應度f(x)，結果按升序排序，記錄最優人工魚、最大、最小適應度xbest、Fmax、Fmin；

（3）計數器i=1；

（4）對第i條魚進行追尾行為，判斷當前可視范圍內最大人工魚的鄰域是否擁擠，若不擁擠執行追尾行為，否則執行（5）；

（5）對于人工魚xi，當i≤0.618n時，啟動云變異因子，對符合條件的人工魚個體進行操作；否則啟動云學習因子，對符合條件的人工魚個體進行操作；

（6）比較（4）和（5）得到的結果，更新公告板；

（7）判斷是否處理完所有人工魚，若滿足，則執行（8），否則執行（4）；

（8）若滿足終止條件，算法優化結束；否則執行（3）。

5　仿真實驗與性能測試

為驗證算法的性能，實驗選用了4個經典的測試函數。因為這4個函數都存在多極值點、震蕩性的特性，因此國內外學者用這幾個函數做實驗對象。本次實驗環境為Windows7系統、Intel CoreI3處理器，編譯工具采用Matlab7.0，測試函數如下：

（1）Rosenbrock函數

5.1固定收斂精度

實驗參數為：魚群規模為50，代數為500，收斂精度為0.01％，步長Step=0.7，可視域Visual=3，最大迭代次數Try_number=50，擁擠度δ=8。對4個函數分別獨立進行100次運行，實驗結果見表1和表2。

對比表1和表2可以得出，對于多極值點、震蕩性的函數尋優測試結果，相對于AFSA算法，CM-AFSA算法的平均代數和所用時間有了顯著的降低，尤其是使用Rastrigin函數進行測試時，改進魚群算法的平均代數從326次下降到181次，迭代時長也由24.075s下降到9.614s，進一步證明了CM-AFSA算法具有較強的尋優能力。

表1　固定收斂精度時AFSA算法優化代數

表2　固定收斂精度時CM-AFSA算法優化代數

5.2固定代數

實驗參數為：魚群規模50，Try_number=50，δ=8，代數為100，由于各函數的復雜度不同，對每個測試函數參數見表3，對函數分別采用基本AFSA和CM-AFSA獨立運行50次，實驗數據見表4，收斂曲線如圖3～圖6所示。

表3　實驗參數設置

表4　相同代數下函數求解最優值表

Rastrigin Dejong's f6 CM-AFSA AFSA CM-AFSA AFSA CM-AFSA 1.239403E-008 4.387534E-004 5.723462E-008 6.325362E-011 0 0.00375632 0.389327 3.374859E-006 0.427223 2.836542E-010 4.298762E-004 0.0974563 1.230092E-007 5.342881E-003 9.372537E-12

從表4可以看出，在代數一定的情況下，改進后的魚群算法50次優化均值和50次優化結果的最優值明顯的優于基本魚群算法算法，相對于基本魚群算法，改進后的魚群算法具有較強的全局搜索能力，結果更穩定，魯棒性更強。

圖3　Rosenbrock函數優化曲線

圖4　Griewank函數優化曲線

圖5　Rastrigin函數優化曲線

圖6　Dejong’sf6函數優化曲線

在圖3～圖6中，虛線代表基本魚群算法的優化曲線，實線代表改進后的魚群算法的優化曲線，橫坐標為代數，縱坐標為函數適應值的對數。對比圖3～圖6可得，CM-AFSA算法能較快的收斂于全局最優，收斂性更優，如圖3所示，基本魚群算法在收斂后期陷入了局部最優值0.0019，而改進后的魚群算法成功收斂到全局最優2.78×10-10。實驗結果表明，CM-AFSA算法的明顯提高了函數優化的收斂精度。

結束語：CM-AFSA通過引入云學習因子和云變異因子的概念，增強了魚群算法的全局搜索能力，使魚群算法的尋優精度更加精確，也有效的避免了基本魚群算法容易陷入局部最優。將CMAFSA算法應用到復雜函數的尋優中，通過仿真測試可明顯看出，基于云模型的人工魚群算法相對于AFSA算法的性能在各方面都有顯著的改善，尤其在跳出局部極值方面有表現優秀，但在處理高維函數時，由于云的引入使魚群算法的算法復雜度更強，如何降低算法的復雜度提高效率需要進一步研究。

參考文獻:

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

[2]李曉磊,錢積新.基于分解協調的人工蟻群優化算法研究[J].電路與系統學報,2003,8(1):1-6.

[3]宋曉.基于云模型人工算法的應用研究[D].遼寧工程技術大學,2015.

[4]李德毅,劉常昱.論正太云模型的普適性[J].中國工程科學,2004,6(8):28-34.

[5]Li D,Liu C,Gan W.A new cognitive model:cloud model[J].International Journal of Intelligent Systems,2009,24(3):357-375.

[6]段海濱,王道波,于秀芬等.基于云模型理論的蟻群算法改進研究[J].哈爾濱工業大學學報,2005,1(37):115-119.

崔麗英（1974-），女，碩士研究生，主要研究方向為計算機網絡技術;

黃殿平（1989－），男，碩士研究生，主要研究方向為圖形圖像處理；

宋曉(1987－)，女，碩士研究生，主要研究方向為圖形圖像處理。

作者簡介：