一種改進的人工魚群算法

崔麗英，黃殿平，宋曉阜新市第一中等職業(yè)技術(shù)專業(yè)學(xué)校；遼寧工程技術(shù)大學(xué)

一種改進的人工魚群算法

崔麗英1，黃殿平2，宋曉2
1阜新市第一中等職業(yè)技術(shù)專業(yè)學(xué)校；2遼寧工程技術(shù)大學(xué)

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

關(guān)鍵詞：魚群算法；云模型；優(yōu)化

1　引言

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

2　AFSA和CM-AFSA

2.1AFSA算法

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

2.1.1追尾行為

設(shè)Xi為人工魚此刻的位置狀態(tài)，在可視域范圍內(nèi)搜索此刻最優(yōu)的人工魚Xmax，當Yi

2.1.2覓食行為

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

2.1.3群聚行為

設(shè)Xi為人工魚此刻的位置狀態(tài)，其可視域內(nèi)所有人工魚的集合為S。

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

2.1.4隨機行為

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

3　云模型

3.1云模型定義

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

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

3.2云模型的數(shù)字特征

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

3.3云發(fā)生器

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

3.3.1正向云

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

圖1　正向云發(fā)生器

3.3.2逆向云

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

圖2　逆向云發(fā)生器

4　基于云模型的魚群算法

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

云學(xué)習(xí)因子是在魚群學(xué)習(xí)過程中，兩個適應(yīng)度不相同的個體人工魚，通過正態(tài)云產(chǎn)生新人工魚的過程。設(shè)xf、xm為互相進化的兩個人工魚的當前狀態(tài)，F(xiàn)f、Fm為兩個人工魚個體適應(yīng)度，則云學(xué)習(xí)因子的期望、熵、超熵為：

云變異因子是在魚群在學(xué)習(xí)過程中，人工魚通過自身攜帶的適應(yīng)度，再通過正態(tài)云產(chǎn)生新人工魚的過程。設(shè)xi是當前某個人工魚狀態(tài)，F(xiàn)i是此個個體的適應(yīng)度，則云變異因子的期望、熵、超熵分別為：

CM-AFSA算法描述如下：

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

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

（3）計數(shù)器i=1；

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

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

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

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

（8）若滿足終止條件，算法優(yōu)化結(jié)束；否則執(zhí)行（3）。

5　仿真實驗與性能測試

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

（1）Rosenbrock函數(shù)

5.1固定收斂精度

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

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

表1　固定收斂精度時AFSA算法優(yōu)化代數(shù)

表2　固定收斂精度時CM-AFSA算法優(yōu)化代數(shù)

5.2固定代數(shù)

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

表3　實驗參數(shù)設(shè)置

表4　相同代數(shù)下函數(shù)求解最優(yōu)值表

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可以看出，在代數(shù)一定的情況下，改進后的魚群算法50次優(yōu)化均值和50次優(yōu)化結(jié)果的最優(yōu)值明顯的優(yōu)于基本魚群算法算法，相對于基本魚群算法，改進后的魚群算法具有較強的全局搜索能力，結(jié)果更穩(wěn)定，魯棒性更強。

圖3　Rosenbrock函數(shù)優(yōu)化曲線

圖4　Griewank函數(shù)優(yōu)化曲線

圖5　Rastrigin函數(shù)優(yōu)化曲線

圖6　Dejong’sf6函數(shù)優(yōu)化曲線

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

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

參考文獻:

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

[2]李曉磊,錢積新.基于分解協(xié)調(diào)的人工蟻群優(yōu)化算法研究[J].電路與系統(tǒng)學(xué)報,2003,8(1):1-6.

[3]宋曉.基于云模型人工算法的應(yīng)用研究[D].遼寧工程技術(shù)大學(xué),2015.

[4]李德毅,劉常昱.論正太云模型的普適性[J].中國工程科學(xué),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].哈爾濱工業(yè)大學(xué)學(xué)報,2005,1(37):115-119.

崔麗英（1974-），女，碩士研究生，主要研究方向為計算機網(wǎng)絡(luò)技術(shù);

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

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

作者簡介：