一種改進(jìn)的群搜索優(yōu)化算法

安曉偉， 蘇宏升

(蘭州交通大學(xué) 自動(dòng)化與電氣工程學(xué)院，甘肅 蘭州 730070)

一種改進(jìn)的群搜索優(yōu)化算法

安曉偉， 蘇宏升

(蘭州交通大學(xué) 自動(dòng)化與電氣工程學(xué)院，甘肅 蘭州 730070)

摘要：群搜索優(yōu)化算法是建立在群居動(dòng)物覓食行為基礎(chǔ)上的新型啟發(fā)式算法，具有算法簡單、易于實(shí)現(xiàn)的特點(diǎn).標(biāo)準(zhǔn)群搜索優(yōu)化算法(GSO)基于發(fā)現(xiàn)-追隨的尋優(yōu)策略，由于追隨者搜索模式過于單一，從而容易陷入局部最優(yōu).為了提高標(biāo)準(zhǔn)GSO算法的收斂速度與收斂精度，提出一種改進(jìn)群搜索優(yōu)化算法(IGSO).在該算法中，發(fā)現(xiàn)者保持原有的尋優(yōu)方式，追隨者執(zhí)行魚群算法的尋優(yōu)模式，通過引入魚群算法的覓食、追尾、聚群與隨機(jī)行為，使搜索方式多樣化，可以同時(shí)考慮種群的個(gè)體最優(yōu)與群體最優(yōu)，從而有效避免陷入局部最優(yōu).通過6個(gè)基準(zhǔn)測試函數(shù)對兩種算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的群搜索優(yōu)化算法優(yōu)于標(biāo)準(zhǔn)群搜索優(yōu)化算法.

關(guān)鍵詞：群搜索優(yōu)化算法；函數(shù)優(yōu)化；人工魚群算法

0引言

啟發(fā)式算法由于其運(yùn)行方式受到自然運(yùn)行規(guī)律啟發(fā)而得到應(yīng)用，其特點(diǎn)是通過模擬動(dòng)物組織的群體行為進(jìn)行尋優(yōu)，如蜂群、鳥群等.群搜索優(yōu)化算法(GSO)是一種常見的啟發(fā)式算法.

GSO是基于一般動(dòng)物群體的覓食模式的原理，即發(fā)現(xiàn)-搜尋(PS)模式[1-2]，將種群個(gè)體分為發(fā)現(xiàn)者，追隨者與游蕩者.目前群搜索優(yōu)化算法已在解決實(shí)際問題的應(yīng)用中得到實(shí)現(xiàn).Wu等人提出了一種多發(fā)現(xiàn)者的群搜索優(yōu)化算法(GSOMP)，該方法在柔性交流輸電系統(tǒng)的多目標(biāo)優(yōu)化問題中得到應(yīng)用[3].He和Li利用經(jīng)過GSO算法訓(xùn)練的人工神經(jīng)網(wǎng)絡(luò)進(jìn)行機(jī)器設(shè)備的在線狀態(tài)監(jiān)測[4].Yan和Shi提出結(jié)合了PSO和GSO優(yōu)點(diǎn)的混合算法(GSPSO)[5].

傳統(tǒng)GSO算法的搜索方式是種群中的最優(yōu)個(gè)體(發(fā)現(xiàn)者)進(jìn)行隨機(jī)搜索，并將最優(yōu)食物位置信息傳遞給種群中的其余個(gè)體.然而，該方法依賴于追隨者的搜索速度與精度，從而容易陷入局部最優(yōu)解.筆者提出一種改進(jìn)的群搜索優(yōu)化算法(IGSO)，將魚群算法的行為策略融入追隨者的搜尋行為，在該算法中，發(fā)現(xiàn)者保持標(biāo)準(zhǔn)GSO算法搜索程序，而追隨者將執(zhí)行魚群算法的尋優(yōu)程序.該算法特點(diǎn)在于不僅考慮種群的先前信息，而且通過引入魚群算法的擁擠度因子與視覺參數(shù)來評估當(dāng)前種群的個(gè)體情況，從而改變了追隨者以往隨機(jī)搜索的方式，增加了搜索方式的多樣性，從而使優(yōu)化算法的收斂速度和精度提高.

1標(biāo)準(zhǔn)群搜索優(yōu)化算法

GSO算法是一種融合了動(dòng)物覓食搜索行為與群居理論的仿生算法，該算法采用發(fā)現(xiàn)-追尋模式作為算法的基本框架，以群居動(dòng)物的社會(huì)覓食策略作為算法尋優(yōu)的基本策略.將群體中的個(gè)體按照覓食行為中的角色分為發(fā)現(xiàn)者、追隨者與游蕩者.

(1)

在GSO算法的迭代過程中，選取每一次迭代中具有最佳個(gè)體適應(yīng)度值的個(gè)體作為發(fā)現(xiàn)者，其余的個(gè)體作為追隨者與游蕩者.發(fā)現(xiàn)者從0°開始，然后隨機(jī)搜索3個(gè)方向(分別為初始點(diǎn)的前方，右方和左方)，若搜索到適應(yīng)度值更佳的位置，則發(fā)現(xiàn)者前進(jìn)至該位置；反之，發(fā)現(xiàn)者停留在當(dāng)前位置，并轉(zhuǎn)換搜索角度，繼續(xù)搜尋.若發(fā)現(xiàn)者歷經(jīng)多次迭代無法找到比當(dāng)前適應(yīng)度值更優(yōu)的位置，則返回初始點(diǎn).

發(fā)現(xiàn)者位置迭代公式為

前方區(qū)域

(2)

右側(cè)區(qū)域

(3)

左側(cè)區(qū)域

(4)

表示發(fā)現(xiàn)者從0°處開始搜索，并分別搜索0°的前、右，左3個(gè)方向.

轉(zhuǎn)向角度

φk+1=φk+r2αmax,

(5)

式中：r1是均值為0,方差為1的正態(tài)分布的隨機(jī)數(shù);r2為[0,1]間均勻分布的隨機(jī)數(shù);lmax與αmax是最大搜索距離與最大轉(zhuǎn)向角.

除發(fā)現(xiàn)者外，在種群中隨機(jī)選擇一部分個(gè)體作為追隨者，追隨者沿著發(fā)現(xiàn)者的路徑進(jìn)行追尋搜索.并在適當(dāng)時(shí)機(jī)與發(fā)現(xiàn)者相互轉(zhuǎn)換，轉(zhuǎn)換公式為

式中：r3為[0,1]間均勻分布的隨機(jī)數(shù).

此外，種群中的剩余成員被選為游蕩者，游蕩者在搜索區(qū)域隨機(jī)搜索如式(6)所示

φk+1=φk+r2αmax，

(6)

式中：αmax是最大轉(zhuǎn)向角；r2為[0,1]間均勻分布的隨機(jī)數(shù)。

在追隨者和游蕩者的尋優(yōu)過程中，若找到某位置比當(dāng)前發(fā)現(xiàn)者及其剩余個(gè)體的位置更優(yōu)，則在下次迭代時(shí)該個(gè)體將轉(zhuǎn)換為發(fā)現(xiàn)者.

2人工魚群算法

人工魚群算法是一種基于魚群群體智能的仿生算法[6-7].其模型建立在魚群覓食過程中會(huì)向著食物濃度高的區(qū)域進(jìn)行游動(dòng)這一行為.搜索過程是通過構(gòu)建魚群中個(gè)體的底層行為，以局部尋優(yōu)來實(shí)現(xiàn)全局最優(yōu).不同于傳統(tǒng)優(yōu)化算法，其同時(shí)考慮了個(gè)體最優(yōu)和群體最優(yōu)，不僅考慮每只魚的當(dāng)前狀態(tài)而且考慮種群中相鄰魚的狀態(tài).

算法可以表述為在一個(gè)n維的目標(biāo)搜索空間中存在由N條人工魚組成的一個(gè)群體.第i條人工魚的狀態(tài)可表示為向量Xi=(xi1,xi2,…,xiQ)，其中i=1,2,…,N.目標(biāo)函數(shù)的適應(yīng)度值Y=f(X)，將Xi帶入其中求得Yi.相鄰兩條魚的距離可以表示為

在人工魚群算法中，人工魚群中的個(gè)體具有彼此不同的移動(dòng)方向.根據(jù)魚群個(gè)體的當(dāng)前狀態(tài)將行為分為四類.

(1) 覓食行為

覓食行為反映了魚具有向食物富集區(qū)域移動(dòng)的能力.設(shè)人工魚當(dāng)前處于狀態(tài)為Xi，適應(yīng)值為Yi，在其視野范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，并計(jì)算Yj，若Yj

(7)

Xj=Xi+Visual·rand().

(8)

試探trynumber次后，如果仍不能找到更好的食物聚集位置，則執(zhí)行隨機(jī)行為

Leap(Xi)=Xi+rand()step.

(9)

(2) 追尾行為

設(shè)第i條人工魚的當(dāng)前狀態(tài)為Xi，其適應(yīng)值為Yi.探索當(dāng)前鄰域內(nèi)(Dij

Yp1,

(9)

則按式(10)向Xp移動(dòng)一步，否則執(zhí)行覓食行為,

(10)

(3) 聚群行為

聚群行為反映了魚的個(gè)體在避免過分擁擠的條件下向鄰近的伙伴中心靠近的行為.設(shè)第i條人工魚當(dāng)前狀態(tài)為Xi，適應(yīng)值為Yi，以自身為中心向周圍區(qū)域探索，搜索到鄰域的伙伴數(shù)目為nf，形成集合Si，

Si={Xi‖Xj-Xi‖≤Visual,j=1,2,…i-1,i+1,…,N}.

如果Si非空，則該集合中心位置為

計(jì)算該中心適應(yīng)度值，如果滿足

Ycentre1,

(11)

則表明伙伴中心有較多的食物并且不太擁擠，則按式(12)向中心位置前進(jìn)一步，否則執(zhí)行覓食行為.

(12)

(4) 隨機(jī)行為

指魚的個(gè)體執(zhí)行隨機(jī)移動(dòng)的行為，可表示為

Leap(Xi)=Xi+rand()step.

3改進(jìn)的群搜索優(yōu)化算法

通過采用人工魚群算法的搜索模式改變了標(biāo)準(zhǔn)GSO算法中追隨者的搜索過程.在此算法中，發(fā)現(xiàn)者-追隨者模型仍然被沿用，追隨者執(zhí)行人工魚群算法的尋優(yōu)策略，分為覓食、追尾、聚群與隨機(jī)行為.

追隨者的行為選擇方式為先進(jìn)行各種行為試探，如追尾、聚群等行為，選擇向最優(yōu)方向前進(jìn)最快的行為，然后選擇執(zhí)行操作后狀態(tài)較優(yōu)的行為來實(shí)際執(zhí)行，缺省的行為為覓食行為.也就是選擇各行為中使得人工魚的下一個(gè)狀態(tài)最優(yōu)的行為，若無最優(yōu)行為，則采取隨機(jī)行為.

追尾行為被應(yīng)用于追隨者追尋發(fā)現(xiàn)者的尋優(yōu)過程中，其位置變換公式如式(13)所示.r1是均值為0,方差為1正態(tài)分布的隨機(jī)數(shù).函數(shù)rand()表示返回(0,1)區(qū)間中的一個(gè)任意數(shù)，

(13)

采用聚群行為對追隨者尋優(yōu)方式進(jìn)行優(yōu)化，此方式利用魚群中的個(gè)體靠近鄰近伙伴中心的特點(diǎn)，使追隨者充分獲得種群中其他個(gè)體的位置信息，提高了種群間的信息交流，從而綜合考慮了群體最優(yōu)與個(gè)體最優(yōu)，使尋優(yōu)方式得以優(yōu)化.其位置更新公式如式(14)所示,

對于覓食行為，追隨者在自己可見的區(qū)域去尋找一個(gè)更好的位置.如果經(jīng)過最大試探次數(shù)trynumber獲得成功，追隨者會(huì)執(zhí)行公式(15)進(jìn)行位置更新,

(15)

如果追隨者經(jīng)過經(jīng)過最大試探次數(shù)trynumber仍然無法找到更好的個(gè)體適應(yīng)值，追隨者將隨機(jī)移動(dòng)見公式(16).r1是均值為0,方差為1正態(tài)分布的隨機(jī)數(shù).函數(shù)rand()表示返回(0,1)區(qū)間中的一個(gè)任意數(shù),

(16)

發(fā)現(xiàn)者和游蕩者的搜索方式與標(biāo)準(zhǔn)GSO算法相同.

綜上所述，改進(jìn)的群搜索優(yōu)化算法步驟如下：① 確定種群數(shù)量，進(jìn)行初始化操作;② 求出所有成員的個(gè)體適應(yīng)度值，選取適應(yīng)度值最優(yōu)的個(gè)體成為發(fā)現(xiàn)者;③ 根據(jù)式(2)～式(5)更新發(fā)現(xiàn)者的尋優(yōu)行為;④ 選剩余成員的80%成為追隨者，按式(13)～式(16)更新追隨者的行為;⑤ 根據(jù)式(6)更新游蕩者的行為;⑥ 若滿足終止條件，則輸出當(dāng)前發(fā)現(xiàn)者的適應(yīng)度值,否則，返回步驟(2).

4實(shí)驗(yàn)與仿真分析

為了驗(yàn)證該算法的性能，筆者將IGSO算法與標(biāo)準(zhǔn)GSO算法作比較.驗(yàn)證過程是在MATLAB7.6的環(huán)境下進(jìn)行的.算法的性能由以下6個(gè)測試函數(shù)所衡量，參數(shù)見表1.

球體模型

廣義Rosenbrock函數(shù)

廣義Schwefel函數(shù)

廣義Rastrigin函數(shù)

Ackley函數(shù)

廣義Griewank函數(shù)

為了便于比較，IGSO中的參數(shù)設(shè)定與文獻(xiàn)[1]中的一致，即初始搜索角度φ0為π/4，常數(shù)a

從圖1(a)中可以看出，標(biāo)準(zhǔn)GSO出現(xiàn)了不收斂的情況，而IGSO在1 500次迭代之后就開始穩(wěn)定的收斂，逐漸趨近于全局最優(yōu)值.由圖(b)和(c)可以看出，標(biāo)準(zhǔn)GSO迭代初期有較大的斜率，表明該算法有持續(xù)的快速收斂能力，但在搜索進(jìn)行過程中陷入局部極值，此時(shí)人工魚群搜索策略的引入使得改進(jìn)群搜索優(yōu)化算法快速跳出局部極值，開始分組尋優(yōu)，繼續(xù)向全局最優(yōu)解的方向搜索，雖耗時(shí)略長，但是收斂值明顯優(yōu)于標(biāo)準(zhǔn)GSO算法，顯示出較高的精度.從(d)圖中可以看出標(biāo)準(zhǔn)GSO收斂較快，迭代次數(shù)較少，但是水平部分的線段表明搜索過早進(jìn)入停滯階段，易陷入早熟，尋優(yōu)精度不如引入改進(jìn)后的群搜索優(yōu)化算法.從圖(e)、(f)的優(yōu)化曲線可以看出，改進(jìn)的群搜索優(yōu)化算法在搜索后期表現(xiàn)出較強(qiáng)的優(yōu)勢，而標(biāo)準(zhǔn)GSO算法則陷入局部最優(yōu).

從表2中所知：改進(jìn)的群搜索優(yōu)化算法(IGSO)的測試平均值的優(yōu)化結(jié)果優(yōu)于標(biāo)準(zhǔn)GSO算法.

5結(jié)論

對標(biāo)準(zhǔn)GSO算法進(jìn)行改進(jìn)，將人工魚群算法中人工魚個(gè)體的聚群、追尾、覓食行為引入追隨者的搜索策略之中，從而較大程度地提高算法的收斂速度.而在文獻(xiàn)[8-10]中，針對發(fā)現(xiàn)者的行為作出一些改進(jìn)，并且是算法的收斂速度得到一定程度的提升.接下來的進(jìn)一步的研究工作是嘗試將本文針對追隨者的改進(jìn)方法與上述文獻(xiàn)中針對發(fā)現(xiàn)者的改進(jìn)方法進(jìn)行有機(jī)結(jié)合，進(jìn)一步提高算法的效率.

參考文獻(xiàn)：

[1]張雯雰,滕少華,李麗娟.改進(jìn)的群搜索優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(4):48-52.

[2]HE S,WU Q H,SUNDERS J R.Group search optimizer:an optimization algorithm inspired by animal searching behavior[J].Evolutionary Computation,2009,13(5):973-990.

[3]KANG Q,LAN T,YAN Y,et al.Group search optimizer based optimal location and capacity of distributed generations[J]. Neuro Computing,2012,78(1):55-63.

[4]CHEN Y,ZHU Q,XU H.Finding rough set reducts with fish swarm algorithm[J].Knowledge Based Systems,2015(2):74-77.

[5]XIE H B,LIU F,LI L J,et al.Research on topology optimization of truss structures based on the improved group search optimizer[J].Neuro Computing, 2013,12 (11):707-712.

[6]劉憲林,喬云飛.基于人工魚群算法的電力系統(tǒng)穩(wěn)定器參數(shù)優(yōu)化研究[J].鄭州大學(xué)學(xué)報(bào):工學(xué)版,2013,34(5):68-72．

[7]劉鋒,覃廣,李麗娟.快速被動(dòng)群搜索優(yōu)化算法及其在空間結(jié)構(gòu)中的應(yīng)用[J].工程設(shè)計(jì)學(xué)報(bào),2010,17(6):420-425.

[8]李鵬.基于群搜索優(yōu)化算法的配電網(wǎng)重構(gòu)[J].電網(wǎng)技術(shù),2012,6(28):43-47.

[9]房娟艷.混合群搜索優(yōu)化算法及其應(yīng)用研究[D].太原:太原科技大學(xué)機(jī)電學(xué)院,2010.

[10]姚健.群搜索算法與二次插值法的混合算法及其應(yīng)用研究[D].太原:太原科技大學(xué)機(jī)電學(xué)院,2010.

An Improved Group Search Optimization Algorithm

AN Xiao-wei1, SU Hong-sheng2

(1.School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China; 2.School of Automation and Electrical Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

Abstract:Group Search Optimization (GSO) is a swarm intelligence approach inspired by animal searching behavior and group living theory. It is simple and efficient, and easy to implement. The searching mode of the scrounger is oversimplified, so it falls into local optimum easily. In order to enhance its convergence speed and precision, the improved Group Search Optimization (IGSO) is proposed. Inheriting the strategy of producer-scrounger of GSO, IGSO introduces the strategy of the Artificial Fish Swarm (AFS) algorithm to the behavior of the scrounger. By introducing prey, fellow, swarm and leap of the AFS algorithm, searching forms is diversified, as well as the best individuals of group and best groups of population can be considered, IGSO can effectively avoid the local optimum. Six benchmark functions are used to evaluate the performance of two algorithms. Experimental results show that IGSO is able to achieve better results than standard GSO.

Key words:group searching optimization; function optimization; artificial fish swarm algorithm

中圖分類號：TM301.6

文獻(xiàn)標(biāo)志碼：A

doi:10.3969/j.issn.1671-6833.2015.02.023

文章編號:1671-6833(2015)02-0105-05

作者簡介：安曉偉 (1987-)，男，新疆烏魯木齊人，碩士研究生，主要從事人工智能算法在電力系統(tǒng)中的應(yīng)用相關(guān)研究，E-mail:neuqauto@126.com.

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61263004);甘肅省自然科學(xué)基金資助項(xiàng)目(1212RJZA071)

收稿日期:2014-10-12；

修訂日期：2014-12-03