一種改進(jìn)的人工魚群算法

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

一種改進(jìn)的人工魚群算法

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

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

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

1　引言

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

2　AFSA和CM-AFSA

2.1AFSA算法

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

2.1.1追尾行為

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

2.1.2覓食行為

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

2.1.3群聚行為

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

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

2.1.4隨機(jī)行為

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

3　云模型

3.1云模型定義

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

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

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

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

3.3云發(fā)生器

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

3.3.1正向云

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

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

3.3.2逆向云

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

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

4　基于云模型的魚群算法

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

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

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

CM-AFSA算法描述如下：

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

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

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

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

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

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

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

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

5　仿真實(shí)驗(yàn)與性能測(cè)試

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

（1）Rosenbrock函數(shù)

5.1固定收斂精度

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

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

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

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

5.2固定代數(shù)

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

表3　實(shí)驗(yàn)參數(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ù)一定的情況下，改進(jìn)后的魚群算法50次優(yōu)化均值和50次優(yōu)化結(jié)果的最優(yōu)值明顯的優(yōu)于基本魚群算法算法，相對(duì)于基本魚群算法，改進(jìn)后的魚群算法具有較強(qiáng)的全局搜索能力，結(jié)果更穩(wěn)定，魯棒性更強(qiáng)。

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

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

參考文獻(xiàn):

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

[2]李曉磊,錢積新.基于分解協(xié)調(diào)的人工蟻群優(yōu)化算法研究[J].電路與系統(tǒng)學(xué)報(bào),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ìn)研究[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2005,1(37):115-119.

崔麗英（1974-），女，碩士研究生，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù);

黃殿平（1989－），男，碩士研究生，主要研究方向?yàn)閳D形圖像處理；

宋曉(1987－)，女，碩士研究生，主要研究方向?yàn)閳D形圖像處理。

作者簡(jiǎn)介：