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

曾 超，李 娜，王 維，陳朝陽，3

（1．中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南長沙 410083;2．中南大學(xué) 湘雅三醫(yī)院，湖南 長沙 410083;3．Department of Biomedical Engineering，Wayne State University，Detroit，MI 48201，USA）

0 引言

工程領(lǐng)域的許多問題都可以轉(zhuǎn)化為參數(shù)的最優(yōu)化問題，解決最優(yōu)化問題的優(yōu)化方法可分為經(jīng)典優(yōu)化算法和啟發(fā)式優(yōu)化算法。經(jīng)典優(yōu)化算法通常無法避免局部極小問題，而受大自然運行規(guī)律啟發(fā)得到的啟發(fā)式優(yōu)化算法得到了越來越多的關(guān)注和重視。其中，最為成功的是基于“優(yōu)勝劣汰”進化理論的進化算法。進化算法主要包括:遺傳算法、遺傳規(guī)劃、進化規(guī)劃、進化策略。

近年來產(chǎn)生的群智能算法是一類新的進化算法，該類算法在解決工程和金融領(lǐng)域的問題中極具應(yīng)用前景。其中，最著名的是蟻群算法和粒子群算法。蟻群算法［1］以真實螞蟻的行為為基礎(chǔ)，采用人工螞蟻的協(xié)作方式尋找離散優(yōu)化問題中的最優(yōu)解。粒子群算法［2］模擬鳥群捕食的行為，通過各個成員之間的集體協(xié)作使群體達到最優(yōu)。

最近，受動物在自然界搜尋食物過程的啟發(fā)，He S等人［3，4］提出了群搜索優(yōu)化（GSO）方法。與遺傳算法、粒子群算法、進化規(guī)劃和進化策略等優(yōu)化方法相比，在23個基準測試函數(shù)中，GSO方法取得了15個最佳結(jié)果。目前，GSO方法在工程領(lǐng)域已有較多的應(yīng)用，并在解決分布式電源配置［5］、平面框架結(jié)構(gòu)［6］、彈簧設(shè)計和壓力容器設(shè)計［7］等問題中也取得了很好的效果。為了進一步提高GSO方法的性能，文獻［5～8］對其進行了改進，并且，這些改進方法的性能在具體問題中或通過部分標(biāo)準測試函數(shù)中進行了驗證。

在GSO方法中，發(fā)現(xiàn)者的行為是影響收斂速度和精度最重要的因素。本文主要針對發(fā)現(xiàn)者的行為進行了改進。最大下降方向策略的加入，使得在不增加目標(biāo)函數(shù)計算次數(shù)的同時，優(yōu)化方法的收斂速度和精度得到提高。本文為了區(qū)別起見，將He S提出的GSO方法稱為標(biāo)準GSO方法，本文在此基礎(chǔ)上改進的群搜索算法稱為改進的GSO（iGSO）方法。

1 標(biāo)準GSO方法

GSO方法中，一個群里包含3種類型的成員:發(fā)現(xiàn)者（producer）、追隨者（scroungers）和游蕩者（dispersed members）。在每次迭代中，群成員中適應(yīng)度最大的一個為發(fā)現(xiàn)者。設(shè)在第k次迭代中的發(fā)現(xiàn)者位置為，搜索角度為，發(fā)現(xiàn)者的行為如下:

1）發(fā)現(xiàn)者分別對當(dāng)前位置的前方、左側(cè)和右側(cè)某處的位置進行掃描，并計算這3個位置的適應(yīng)度，3個位置按下

2）計算上述3個位置的適應(yīng)度，并選取其中的最優(yōu)值與當(dāng)前適應(yīng)度比較，若這個最優(yōu)值優(yōu)于當(dāng)前適應(yīng)度，則發(fā)現(xiàn)者移動到上述3個位置中具有最優(yōu)適應(yīng)度的位置;否則，此輪迭代中的發(fā)現(xiàn)者不移動位置，僅依據(jù)下式改變方向

式中amax是最大轉(zhuǎn)移角度，為一標(biāo)量。

3）經(jīng)過連續(xù)a次迭代后，發(fā)現(xiàn)者均沒有找到更好的位置，發(fā)現(xiàn)者的搜索角度將變?yōu)?/p>

式中 α是一個常數(shù)。

除了發(fā)現(xiàn)者以外，群中的其他成員以一定概率隨機地成為追隨者或游蕩者，例如:可選任意一個成員成為追隨者的概率為0．8，成為游蕩者的概率為0．2。在第k輪迭代中，若位置為，搜索角度為的成員i為追隨者，則它將向著此輪迭代中發(fā)現(xiàn)者的位置隨機移動一定距離，到達新的位置

式中r3∈in為一個在區(qū)間（0，1）均勻分布的隨機序列，o為Hadamard積。同時，追隨者的搜索角度將根據(jù)式（5）更新。若成員i為游蕩者，則其搜尋角度將按式（5）進行更新，并隨機選擇一個距離

從而移動到新的位置

經(jīng)過若干輪迭代后，計算中止，此時發(fā)現(xiàn)者的適應(yīng)度值就認為是目標(biāo)函數(shù)的最優(yōu)值，發(fā)現(xiàn)者所在的位置被認為是所求優(yōu)化問題的最優(yōu)解。

2 iGSO方法

在GSO中，“發(fā)現(xiàn)者—追隨者—游蕩者”框架是其全局收斂的重要保證，而發(fā)現(xiàn)者的行為是影響收斂速度和精度最重要的因素。在保證全局收斂能力的前提下，為了加快其收斂速度和精度，本文保留了GSO的基本框架，并對其發(fā)現(xiàn)者行為作出了改進，形成了iGSO方法。發(fā)現(xiàn)者行為改進如下:

1）在第k次迭代中，當(dāng)發(fā)現(xiàn)者、追隨者和游蕩者完成其行為后，保存每個成員在此輪迭代和此前若干輪（本文取此前2輪）迭代中的位置和適應(yīng)度，即保存

若X=X2時，取得

則方向

為發(fā)現(xiàn)者與所有成員在此前3輪迭代的位置中，下降速率最大的方向，同時求出其搜索角度φ2。

3）式（2）～式（4）和式（14）～式（16）共確定了6個位置，計算這6個位置的適應(yīng)度值

由這6個位置的適應(yīng)度值和式（5）和式（6）確定發(fā)現(xiàn)者的行為。

綜上所述，改進的群搜索優(yōu)化方法計算步驟如下:

1）確定搜索空間的上下界，初始化種群中每個成員的位置和初始角度;

2）計算每個成員的適應(yīng)度值，并根據(jù)適應(yīng)度值找出其中的發(fā)現(xiàn)者，同時在種群中隨機選擇追隨者和游蕩者;

3）根據(jù)式（2）～式（4）和式（14）～ 式（16），以及式（5）～（6）確定發(fā)現(xiàn)者行為;

4）根據(jù)式（7）和式（9）分別確定追隨者和游蕩者的行為;

5）根據(jù)式（10）更新所保存的位置和適應(yīng)度值矩陣;

6）判斷中止條件是否滿足，若滿足，則中止，輸出當(dāng)前發(fā)現(xiàn)者的位置及其適應(yīng)度值，否則，返回步驟（2）。

3 仿真結(jié)果與分析

3．1 測試函數(shù)

為了全面比較GSO和iGSO的性能，采用23個基準測試函數(shù)對2種優(yōu)化方法進行測試。這23個基準測試函數(shù)可分為三類:第一類為單模函數(shù)，包括f1～f7;第二類為具有較多局部極值的多模函數(shù)，包括f8～f13;第三類為具有較少局部極值的多模函數(shù)，包括f14～f23。關(guān)于這23個基準測試函數(shù)的解析式和搜索域請參考文獻［3］。本文所用的23個基準測試函數(shù)搜索空間的維數(shù)見表1。

表1 23個基準測試函數(shù)的維數(shù)Tab 1 Dimensions of 23 benchmark testing functions

3．2 參數(shù)設(shè)置

其中，Li和Ui是搜索空間第i維向量的下界和上界。在iGSO中，種群規(guī)模設(shè)置為45。這樣使得在每次迭代過程中，GSO與iGSO方法對目標(biāo)函數(shù)的計算次數(shù)一致。

采用iGSO對23個測試函數(shù)尋優(yōu)的過程中，目標(biāo)函數(shù)計算次數(shù)如表2所示。

表2 目標(biāo)函數(shù)的計算次數(shù)Tab 2 Computatioal numbers of target function

3．3 測試結(jié)果

采用23個基準測試函數(shù)對iGSO進行50次測試，得到的測試結(jié)果平均值如表3所示。表3中給出的GSO的測試結(jié)果來自文獻［3］，表3同時給出了各測試函數(shù)在搜索域中的最小值。

表3 測試函數(shù)的最小值和GSO與iGSO結(jié)果比較Tab 3 Minimum value of test function and result comparison of GSO and iGSO

從上表可知，iGSO對13測試函數(shù)的優(yōu)化精度優(yōu)于GSO，僅對5個測試函數(shù)的優(yōu)化精度遜于GSO，在其余5個函數(shù)中，2種方法的表現(xiàn)相當(dāng)。整體來說，iGSO的性能優(yōu)于GSO的性能。

4 結(jié)論

本文主要針對GSO框架中的發(fā)現(xiàn)者行為進行了改進，結(jié)果顯示，本文的改進方法提高了算法的精度。而在文獻［5～8］，針對追隨者的行為作出了一些改進，并顯示出良好的效果。若將本文的改進方法和上述文獻的改進方法有機結(jié)合，GSO的搜索能力將有可能得到進一步提高。

［1］ Bonabeau E，Dorigo M，Theraulaz G．Inspiration for optimization from social insect behaviour［J］．Nature，2000，406:39 －42．

［2］ Eberhat R，Kennedy J．A new optimizer using particle swarm theory［C］∥Proc of the 6th Int’l Symposium on Micro-Machine and Human Science，Nagoya，1995:39 －43．

［3］ He S，Wu Q H，Saunders J R．Group search optimizer:An optimization algorithm inspired by animal searching behavior［J］．IEEE Transactions on Evolutionary Computation，2009，13（5）:973 －990．

［4］ He S，Wu Q H，Saunders J R．A novel group search optimizer inspired by animal behavioral ecology［C］∥Proc of 2006 IEEE Congress on Evolutionary Computation，Vancouver，2006:1272 －1278．

［5］ Qi K，Tian L，Yong Y，et al．Group search optimizer based optimal location and capacity of distributed generations［J］．Neurocomputing，2012，78:55 －63．

［6］ 張雯雰，滕少華，李麗娟．改進的群搜索優(yōu)化算法［J］．計算機工程與應(yīng)用，2009，45（4）:48 －52．

［7］ Shen H，Zhu Y，Niu B，et al．An improved group search optimizer for mechanical design optimization problems［J］．Progress in Natural Science，2009，19:91 －97．

［8］ 劉 鋒，覃 廣，李麗娟．快速群搜索優(yōu)化算法及其應(yīng)用研究［J］．工程力學(xué)，2010，27（7）:38 －44．