安曉偉， 蘇宏升

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

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

安曉偉， 蘇宏升

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

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

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

0引言

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

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

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

1標準群搜索優(yōu)化算法

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

(1)

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

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

前方區(qū)域

(2)

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

(3)

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

(4)

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

轉(zhuǎn)向角度

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

(5)

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

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

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

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

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

(6)

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

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

2人工魚群算法

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

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

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

(1) 覓食行為

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

(7)

Xj=Xi+Visual·rand().

(8)

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

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

(9)

(2) 追尾行為

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

Yp1,

(9)

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

(10)

(3) 聚群行為

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

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

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

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

Ycentre1,

(11)

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

(12)

(4) 隨機行為

指魚的個體執(zhí)行隨機移動的行為，可表示為

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

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

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

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

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

(13)

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

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

(15)

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

(16)

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

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

4實驗與仿真分析

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

球體模型

廣義Rosenbrock函數(shù)

廣義Schwefel函數(shù)

廣義Rastrigin函數(shù)

Ackley函數(shù)

廣義Griewank函數(shù)

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

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

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

5結(jié)論

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

參考文獻：

[1]張雯雰,滕少華,李麗娟.改進的群搜索優(yōu)化算法[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é)報:工學(xué)版,2013,34(5):68-72．

[7]劉鋒,覃廣,李麗娟.快速被動群搜索優(yōu)化算法及其在空間結(jié)構(gòu)中的應(yīng)用[J].工程設(shè)計學(xué)報,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é)機電學(xué)院,2010.

[10]姚健.群搜索算法與二次插值法的混合算法及其應(yīng)用研究[D].太原:太原科技大學(xué)機電學(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

文獻標志碼：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.

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

收稿日期:2014-10-12；

修訂日期：2014-12-03