崔麗英,黃殿平,宋曉阜新市第一中等職業(yè)技術(shù)專(zhuān)業(yè)學(xué)校;遼寧工程技術(shù)大學(xué)
一種改進(jìn)的人工魚(yú)群算法
崔麗英1,黃殿平2,宋曉2
1阜新市第一中等職業(yè)技術(shù)專(zhuān)業(yè)學(xué)校;2遼寧工程技術(shù)大學(xué)
摘要:人工魚(yú)群算法是一種高效的群體智能尋優(yōu)算法。本文提出一種改進(jìn)智能魚(yú)群算法,引入云學(xué)習(xí)因子和云變異因子,使算法在尋優(yōu)過(guò)程中的學(xué)習(xí)能力有所提高,避免算法在尋優(yōu)過(guò)程中游動(dòng)行為的不確定性,提高了算法的尋優(yōu)能力。
關(guān)鍵詞:魚(yú)群算法;云模型;優(yōu)化
2002年,我國(guó)知名學(xué)者李曉磊[1-2]提出了人工魚(yú)群算法(Artifi?cial Fish-swarm Algorithm,AFSA)理論,AFSA主要是通過(guò)仿生魚(yú)的覓食、群聚、游弋和追尾行為,從單條人工魚(yú)的底層局部尋優(yōu)從而達(dá)到群體全局尋優(yōu)。由于AFSA魯棒性強(qiáng),算法簡(jiǎn)單且容易實(shí)現(xiàn),一經(jīng)提出就引起了廣泛關(guān)注[3]。本文為了解決魚(yú)群進(jìn)化過(guò)程中隨機(jī)性與傾向性的兼容問(wèn)題,采用云模型的思想,提出一種基于云的人工魚(yú)群算法(Cloudy Model-Artificial Fish-swarm Algorithm,CMAFSA)。
2.1AFSA算法
在AFSA算法中,N表示魚(yú)群容量,Visual代表可視域,Step代表步長(zhǎng),Try_number代表迭代次數(shù),δ為擁擠度因子,每個(gè)人工魚(yú)的狀態(tài)表示為X=(x1,x2,…,xn),其中xi(i=1,2,…,n)代表尋優(yōu)變量。Y=f(X )代表人工魚(yú)食物濃度,其中Y為目標(biāo)函數(shù)值,表示兩個(gè)人工魚(yú)個(gè)體之間的距離。
2.1.1追尾行為
設(shè)Xi為人工魚(yú)此刻的位置狀態(tài),在可視域范圍內(nèi)搜索此刻最優(yōu)的人工魚(yú)Xmax,當(dāng)Yi
2.1.2覓食行為
設(shè)Xi為人工魚(yú)此刻的位置狀態(tài),該人工魚(yú)在其可視域內(nèi)搜索,若發(fā)現(xiàn)有狀態(tài)Xj,且Xj所在位置的食物濃度Yj大于當(dāng)前狀態(tài)Xi的食物濃度,那么當(dāng)前人工魚(yú)將會(huì)朝該方向移動(dòng)一步;否則,如果Xj所在位置的食物濃度小于當(dāng)前食物濃度,那么在可視域內(nèi)隨機(jī)選擇下一個(gè)狀態(tài)再次與當(dāng)前狀態(tài)進(jìn)行比較。嘗試Try_number次后,如果在該可視域中無(wú)更優(yōu)狀態(tài),那么此人工魚(yú)隨意移動(dòng)一個(gè)步長(zhǎng)。
2.1.3群聚行為
設(shè)Xi為人工魚(yú)此刻的位置狀態(tài),其可視域內(nèi)所有人工魚(yú)的集合為S。
如果存在非空集合S,則表示此刻人工魚(yú)可視域內(nèi)存在其他人工魚(yú),其魚(yú)群容量Nf≥1,如果當(dāng)前狀態(tài)Yi
2.1.4隨機(jī)行為
人工魚(yú)的隨機(jī)行為是人工魚(yú)覓食行為的缺省行為之一,在此刻人工魚(yú)可視域范圍內(nèi)隨意選定其后一狀態(tài)并向此狀態(tài)前進(jìn)一個(gè)步長(zhǎng)。此行為為人工魚(yú)個(gè)體提供隨機(jī)游弋的機(jī)會(huì),可以提高種群多樣性,同時(shí)能夠跳出局部最優(yōu)以達(dá)到全局最優(yōu)。
3.1云模型定義
云模型是李德毅院士提出的一種定性定量轉(zhuǎn)換模型[4],可以實(shí)現(xiàn)定性與定量間的不確定性轉(zhuǎn)換。設(shè)U是一個(gè)普通集合表示的論域,C對(duì)應(yīng)論域U上相聯(lián)系的語(yǔ)言值,存在數(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上的分布稱(chēng)為云模型,簡(jiǎn)稱(chēng)云[5]。
3.2云模型的數(shù)字特征
云用期望Ex(Expected value)、熵En(Entropy)和超熵He(Hy?per entropy)三個(gè)數(shù)字特征來(lái)整體表征一個(gè)概念,多個(gè)數(shù)字特征的組合能夠體現(xiàn)云模型在全局中的特性[3]。
3.3云發(fā)生器
按云的產(chǎn)生機(jī)理和計(jì)算方向,有正向云和逆向云[6]。它是整個(gè)云模型的核心理論。
3.3.1正向云
正向云是依據(jù)云模型的數(shù)字特征將定性概念轉(zhuǎn)化為定量數(shù)值,其方法是通過(guò)云的數(shù)字特征(Ex,En,He)來(lái)生成云滴,此過(guò)程是直接前向的,如圖1所示。輸入定性概念的Ex、En以及He,根據(jù)對(duì)應(yīng)關(guān)系輸出云滴drop(xi,μi),其中xi代表定性概念在U中的位置,μi是隸屬度。
圖1 正向云發(fā)生器
3.3.2逆向云
逆向云實(shí)現(xiàn)定量值與定性概念之間過(guò)程轉(zhuǎn)換,該發(fā)生器能把數(shù)據(jù)轉(zhuǎn)換成具有數(shù)字特征(Ex,En,He)來(lái)進(jìn)行表達(dá)。如圖2所示,逆向云是于統(tǒng)計(jì)原理思想設(shè)計(jì)的。
圖2 逆向云發(fā)生器
針對(duì)AFSA后期收斂性差、易陷入局部最優(yōu)等缺點(diǎn),本文將云的概念引入到魚(yú)群算法中進(jìn)行建模,通過(guò)正太云實(shí)現(xiàn)人工魚(yú)的自適應(yīng)進(jìn)化,引入云變異的均衡概念,提出了一種基于云模型的人工魚(yú)群算法。CM-AFSA與其他AFSA改進(jìn)算法的區(qū)別在于增加了魚(yú)群的自主學(xué)習(xí)能力,對(duì)云參數(shù)進(jìn)行了自適應(yīng)處理。CM-AFSA引入云學(xué)習(xí)因子和云變異因子。
云學(xué)習(xí)因子是在魚(yú)群學(xué)習(xí)過(guò)程中,兩個(gè)適應(yīng)度不相同的個(gè)體人工魚(yú),通過(guò)正態(tài)云產(chǎn)生新人工魚(yú)的過(guò)程。設(shè)xf、xm為互相進(jìn)化的兩個(gè)人工魚(yú)的當(dāng)前狀態(tài),F(xiàn)f、Fm為兩個(gè)人工魚(yú)個(gè)體適應(yīng)度,則云學(xué)習(xí)因子的期望、熵、超熵為:
云變異因子是在魚(yú)群在學(xué)習(xí)過(guò)程中,人工魚(yú)通過(guò)自身攜帶的適應(yīng)度,再通過(guò)正態(tài)云產(chǎn)生新人工魚(yú)的過(guò)程。設(shè)xi是當(dāng)前某個(gè)人工魚(yú)狀態(tài),F(xiàn)i是此個(gè)個(gè)體的適應(yīng)度,則云變異因子的期望、熵、超熵分別為:
CM-AFSA算法描述如下:
(1)由適應(yīng)度函數(shù)定義,在U中隨機(jī)產(chǎn)生n個(gè)人工魚(yú)x1,x2,…,xn,初始化種群X={x1,x2,…} ,xn,步長(zhǎng)Step、可視域Visual、擁擠度δ和代數(shù)Try_number;
(2)計(jì)算每個(gè)人工魚(yú)適應(yīng)度f(wàn)(x),結(jié)果按升序排序,記錄最優(yōu)人工魚(yú)、最大、最小適應(yīng)度xbest、Fmax、Fmin;
(3)計(jì)數(shù)器i=1;
(4)對(duì)第i條魚(yú)進(jìn)行追尾行為,判斷當(dāng)前可視范圍內(nèi)最大人工魚(yú)的鄰域是否擁擠,若不擁擠執(zhí)行追尾行為,否則執(zhí)行(5);
(5)對(duì)于人工魚(yú)xi,當(dāng)i≤0.618n時(shí),啟動(dòng)云變異因子,對(duì)符合條件的人工魚(yú)個(gè)體進(jìn)行操作;否則啟動(dòng)云學(xué)習(xí)因子,對(duì)符合條件的人工魚(yú)個(gè)體進(jìn)行操作;
(6)比較(4)和(5)得到的結(jié)果,更新公告板;
(7)判斷是否處理完所有人工魚(yú),若滿足,則執(zhí)行(8),否則執(zhí)行(4);
(8)若滿足終止條件,算法優(yōu)化結(jié)束;否則執(zhí)行(3)。
為驗(yàn)證算法的性能,實(shí)驗(yàn)選用了4個(gè)經(jīng)典的測(cè)試函數(shù)。因?yàn)檫@4個(gè)函數(shù)都存在多極值點(diǎn)、震蕩性的特性,因此國(guó)內(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ù)為:魚(yú)群規(guī)模為50,代數(shù)為500,收斂精度為0.01%,步長(zhǎng)Step=0.7,可視域Visual=3,最大迭代次數(shù)Try_number=50,擁擠度δ=8。對(duì)4個(gè)函數(shù)分別獨(dú)立進(jìn)行100次運(yùn)行,實(shí)驗(yàn)結(jié)果見(jiàn)表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)魚(yú)群算法的平均代數(shù)從326次下降到181次,迭代時(shí)長(zhǎng)也由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ù)為:魚(yú)群規(guī)模50,Try_number=50,δ=8,代數(shù)為100,由于各函數(shù)的復(fù)雜度不同,對(duì)每個(gè)測(cè)試函數(shù)參數(shù)見(jiàn)表3,對(duì)函數(shù)分別采用基本AFSA和CM-AFSA獨(dú)立運(yùn)行50次,實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表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)后的魚(yú)群算法50次優(yōu)化均值和50次優(yōu)化結(jié)果的最優(yōu)值明顯的優(yōu)于基本魚(yú)群算法算法,相對(duì)于基本魚(yú)群算法,改進(jìn)后的魚(yú)群算法具有較強(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ú)群算法的優(yōu)化曲線,實(shí)線代表改進(jìn)后的魚(yú)群算法的優(yōu)化曲線,橫坐標(biāo)為代數(shù),縱坐標(biāo)為函數(shù)適應(yīng)值的對(duì)數(shù)。對(duì)比圖3~圖6可得,CM-AFSA算法能較快的收斂于全局最優(yōu),收斂性更優(yōu),如圖3所示,基本魚(yú)群算法在收斂后期陷入了局部最優(yōu)值0.0019,而改進(jìn)后的魚(yú)群算法成功收斂到全局最優(yōu)2.78×10-10。實(shí)驗(yàn)結(jié)果表明,CM-AFSA算法的明顯提高了函數(shù)優(yōu)化的收斂精度。
結(jié)束語(yǔ):CM-AFSA通過(guò)引入云學(xué)習(xí)因子和云變異因子的概念,增強(qiáng)了魚(yú)群算法的全局搜索能力,使魚(yú)群算法的尋優(yōu)精度更加精確,也有效的避免了基本魚(yú)群算法容易陷入局部最優(yōu)。將CMAFSA算法應(yīng)用到復(fù)雜函數(shù)的尋優(yōu)中,通過(guò)仿真測(cè)試可明顯看出,基于云模型的人工魚(yú)群算法相對(duì)于AFSA算法的性能在各方面都有顯著的改善,尤其在跳出局部極值方面有表現(xiàn)優(yōu)秀,但在處理高維函數(shù)時(shí),由于云的引入使魚(yú)群算法的算法復(fù)雜度更強(qiáng),如何降低算法的復(fù)雜度提高效率需要進(jìn)一步研究。
參考文獻(xiàn):
[1]李曉磊,邵之江,錢(qián)積新.一種基于動(dòng)物自治體的尋優(yōu)模式:魚(yú)群算法[J].系統(tǒng)工程理論與實(shí)踐,2002,22(11):32-38.
[2]李曉磊,錢(qián)積新.基于分解協(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].中國(guó)工程科學(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)介: