尹雅麗，　熊小峰，　郭肇祿

（江西理工大學(xué)理學(xué)院，江西贛州341000）

基于轉(zhuǎn)軸法的導(dǎo)向人工蜂群算法

尹雅麗，熊小峰，郭肇祿

（江西理工大學(xué)理學(xué)院，江西贛州341000）

針對人工蜂群算法在求解復(fù)雜多峰問題時容易出現(xiàn)收斂速度慢、開采能力不足的問題，提出了基于轉(zhuǎn)軸法的導(dǎo)向人工蜂群算法（RDABC）.在RDABC算法的搜索過程中，利用方向引導(dǎo)信息來指導(dǎo)個體朝更優(yōu)方向搜索，并對當前最優(yōu)解執(zhí)行轉(zhuǎn)軸法局部搜索，以加快收斂速度.在8個標準測試函數(shù)上進行了比較實驗，實驗結(jié)果表明RDABC算法的求解精度更高，收斂速度更快.

人工蜂群算法；方向引導(dǎo)信息；轉(zhuǎn)軸法；局部搜索

0　引言

人工蜂群算法［1］（artificial bee colony，ABC）是土耳其學(xué)者Karaboga于2005年提出的一種群智能算法，它通過模擬蜜蜂覓食過程中的智能尋優(yōu)機制來尋找最優(yōu)解.自ABC算法提出以來，許多研究人員對其進行了研究，并將其與PSO、ED、PS-EA、EA、GA等演化算法進行了比較，實驗結(jié)果表明ABC算法具有較好的全局尋優(yōu)能力，是求解高維、多峰問題的一種有效方法［2-3］.由于ABC算法具有操作簡單、易于實現(xiàn)、控制參數(shù)少、搜索精度高、魯棒性較強等優(yōu)點［4-5］，這使得ABC及其改進算法被不斷應(yīng)用于各種優(yōu)化問題中，如：Xu等［6］為了避免算法“早熟”和收斂速度慢等問題，將混沌機制引入ABC中用于求解無人作戰(zhàn)機的路徑規(guī)劃問題；Dos等［7］為了提高算法的開采能力和收斂速度，在ABC算法的雇傭蜂和觀察蜂階段采用高斯分布的隨機數(shù)代替均勻分布隨機數(shù)，用于求解螺線管的基準問題；王慧穎等［8］利用全局最優(yōu)解和個體極值信息提高算法的局部搜索能力以平衡算法的勘探和開采能力，并提高了解的精度；Akay等［9］將其用于計算最大類間方差和熵從而求解多閾值分割問題，提高了求解精度；周文越等［10］在ABC中引入禁忌搜索提高算法搜索效率用于計算環(huán)網(wǎng)斷點集；Pan等［11］將離散機制引入至ABC的種群表達和更新操作中用于求解批量流水線調(diào)度問題，并且在雇傭蜂階段采用了最優(yōu)解鄰域值替換較差個體的機制，較好的平衡了算法的勘探和開采能力；阮羚［12］等通過對每次迭代中的最優(yōu)解進行混沌算子處理形成混沌池，提高算法的局部搜索能力的同時不限制其搜索的全局性，減小“早熟”收斂的可能性用于土壤分層電阻率計算；Mansouri［13］將求解區(qū)間不斷進行二等分縮小的方法引入至ABC中用于求解非線性函數(shù)的不動點，提高了解的精度.

在工程實踐中發(fā)現(xiàn)，與許多演化算法類似［14-15］，ABC也存在著一定的局限性.如求解單峰問題時，觀察蜂階段只進行單一維度更新，導(dǎo)致進化后期收斂速度慢；求解多峰問題時，進化過程中種群相似度過高，導(dǎo)致算法容易出現(xiàn)“早熟”、易陷入局部最優(yōu)；求解精度要求較高的工程問題時，求解精度達不到要求等.針對標準ABC算法在求解復(fù)雜多峰問題時容易出現(xiàn)收斂速度慢、開采能力不足、求解精度不高的問題，提出了一種基于轉(zhuǎn)軸法的導(dǎo)向人工蜂群算法（RDABC），該算法在進化過程中引入了方向引導(dǎo)信息用于指導(dǎo)個體維度上的數(shù)值朝著更優(yōu)方向進行更新，擴大搜索范圍的同時提高算法收斂速度，并在進化過程中針對最優(yōu)解使用轉(zhuǎn)軸法進行局部搜索，提高求解精度.

1　ABC算法

ABC算法通過模擬蜜蜂采蜜過程中的智能機制處理函數(shù)優(yōu)化問題，其將蜂群劃分為雇傭蜂、觀察蜂、偵查蜂三類進行進化，且雇傭蜂、觀察蜂、蜜源數(shù)目相等，蜜源質(zhì)量即對應(yīng)優(yōu)化問題的適應(yīng)度值［1］.

在算法的初始階段，通過式（1）產(chǎn)生含SN個個體的初始蜜源，得到初始種群［1］：

其中i=1，…，SN，j=1，…，D，每個個體表示為Xi=（xi1，xi2，…，xiD）.xminj、xmaxj分別表示個體在第j維上的下界和上界，rand∈［0，1］為0～1之間服從均勻分布的隨機數(shù).

產(chǎn)生初始種群后，通過式（2）計算蜜源的質(zhì)量［1］：其中fiti為蜜源的適應(yīng)值，適應(yīng)值越大表示該蜜源質(zhì)量越優(yōu)，fi為蜜源i的目標函數(shù)值.

在演化過程中，ABC通過依次執(zhí)行雇傭蜂操作、觀察蜂操作、偵查蜂操作來使得種群不斷向最優(yōu)解逼近，各操作過程敘述如下.

1.1雇傭蜂操作

在雇傭蜂操作過程中，雇傭蜂根據(jù)式（3）對每個蜜源進行一次鄰域搜索，產(chǎn)生新蜜源Vi=（vi1，vi2，…，viD）［1］：

其中φij∈［-1，1］，k∈ ｛1，…，SN｝，j∈｛1，…，D｝為隨機數(shù)，在每次鄰域搜索過程中隨機更新一個維度上的數(shù)值，然后計算新蜜源Vi的質(zhì)量，當新蜜源Vi優(yōu)于蜜源Xi時，則蜜源Xi由Vi替代.

1.2觀察蜂操作

雇傭蜂操作執(zhí)行結(jié)束后，ABC算法開始執(zhí)行觀察蜂操作.在觀察蜂操作中，雇傭蜂先將蜜源信息共享給觀察蜂，然后觀察蜂根據(jù)蜜源質(zhì)量，按貪婪法選擇蜜源進行開采，每個蜜源的選擇概率計算方式如下［1］：

Pi表示蜜源i的選擇概率，當蜜源被選中之后，觀察蜂將按式（3）對所選中的蜜源進行鄰域搜索.

1.3偵查蜂操作

在偵查蜂操作過程中，挑選出未被更新次數(shù)最大的蜜源，當這些蜜源未被更新的次數(shù)大于事先給定的限制次數(shù)“l(fā)imit”時，這些蜜源將按式（1）重新隨機產(chǎn)生.

2　基于轉(zhuǎn)軸法的導(dǎo)向ABC算法（RDABC）

標準ABC算法在求解復(fù)雜多峰問題時，在個體更新過程中采用隨機的方式對某一維度上的數(shù)值進行更新，這種機制使得算法在進化后期收斂速度慢.針對這種不足，引入方向引導(dǎo)信息（Directed information）來指導(dǎo)個體朝著更優(yōu)的方向搜索，從而提高算法的收斂速度.為了提高算法的開采能力，融合改進的轉(zhuǎn)軸法來進行局部搜索，不僅能提高算法的收斂速度，也使得求解精度得以提高.

2.1RDABC的操作算子

基本ABC在求解復(fù)雜多峰問題時，在雇傭蜂和觀察蜂階段中，對每個個體的任一維度進行更新，維度的選取通過隨機的方式產(chǎn)生，當更新得到的個體優(yōu)于原個體時，新個體將取代原個體，但這種隨機選擇更新的機制未記錄該個體上此維度的更新方向，即在下次迭代中，若此個體的同一維度被再次選中進行更新時，其更新方向的隨機性可能使個體更靠近最優(yōu)解，也可能使其偏離最優(yōu)解，這種隨機性降低了算法的收斂速度.方向信息指導(dǎo)策略［16］能有效指導(dǎo)個體朝著更優(yōu)的方向搜索，因此在RDABC中引入方向信息能有效地提高算法的收斂速度.方向信息指導(dǎo)策略為：針對第i個個體在第j維的方向信息設(shè)置為diij，其取值為0，1或-1，即個體將朝著三個可能的方向進行更新，但最終個體只選擇更具優(yōu)勢的方向進行更新.RDABC在雇傭蜂和觀察蜂操作過程中根據(jù)方向信息按式（5）進行鄰域搜索［16］：

其中diij表示蜜源i在第 j維上的方向信息，φij∈［-1，1］、rij∈［0，1］為隨機數(shù)，在更新初始階段設(shè)置diij=0，當更新得到的解不優(yōu)于原解時置diij=0；當更新得到的解優(yōu)于原解時，若更新解在j維上的值比原解在j維上的值大則置diij=-1，否則置diij=1.

雖然利用了方向指導(dǎo)策略來加速ABC算法的收斂速度，但在求解一些復(fù)雜工程優(yōu)化問題時，ABC算法容易出現(xiàn)勘探和開采搜索能力不平衡的問題.為了進一步提高其開采能力，利用改進的轉(zhuǎn)軸法（RM）［17］來進行局部搜索是一種提高算法開采能力的有效方法.在改進的RM［17］中，采用了一種基于等級的適應(yīng)值計算方法，并限制指定方向上個體的更新次數(shù)，同時要求每個方向上的更新效果達到一定的精度，隨著更新次數(shù)的增加，最小步長δmin的限制條件也作出動態(tài)調(diào)整.改進的RM算法流程如下所示：

step1.輸入初始點x0，初始搜索方向d，初始更新步長δj，步長調(diào)整因子α，β，終止條件a，nl，ε1，ε2，方向更新次數(shù)k=0，外部更新次數(shù)k2=0

step 2.while k2＜2nlandδmin≥1.0e-（a+nRM）do

step 3.置x=xk，k1=0，z=x

step 4.while k1＜nldo

step 5.for j=1 to Ddo

step 6.y=x+δjdj

step 7.if y優(yōu)于x then set，x=y，δj=αδj；else

δj=βδj

step 8.end for

step10.k1=k1+1

step11.end while

step12.if f（x）＜f（xk）andδmin≥1.0e-（a+nRM） then set k=k+1，xk=x，更新搜索方向d

step13.end while

其中δ1，δ2，…，δD為每個維度上的搜索步長，a為常數(shù)，nRM表示調(diào)用RM的次數(shù).

2.2RDABC的總體框架

RDABC算法在ABC的雇傭蜂和觀察蜂階段中引入方向指導(dǎo)策略，通過對每個個體的每個維度都設(shè)置一個方向信息來指導(dǎo)個體朝著更具優(yōu)勢的方向進行搜索，為了提高算法的開采能力，針對最優(yōu)個體引入了轉(zhuǎn)軸法（RM）用于局部搜索.轉(zhuǎn)軸法，是求解最優(yōu)值處于狹小、彎曲的“山谷”內(nèi)的一種有效方法，其通過在某一方向上進行步長調(diào)整來指導(dǎo)個體在此方向上向最優(yōu)解靠近，當此方向無法使個體得到改進時，則重新調(diào)整方向并以當前獲得的最優(yōu)個體作為初始點繼續(xù)通過調(diào)整步長的方式進行個體更新，這種搜索方法可以使個體快速向最優(yōu)解逼近［18］.引入方向信息和RM局部搜索的RDABC算法在提高收斂速度的同時提高算法的求解精度和開采能力，其算法流程如下所示：

step 1.初始化種群Xi，i=1，…，NS，iter=1

step 2.計算各個體的函數(shù)值及適應(yīng)值，并保存最優(yōu)個體xbest.

step 3.計算改進RM中的初始步長δj

step 4.將xbest作為改進RM的初始點調(diào)用RM，獲得最優(yōu)個體x′best

step 5.if f（x′best）＜f（xbest）then用x′best替換種群中間位置的個體，xbest=x′best.

step 6.while終止條件不滿足時do

step 7.雇傭蜂階段：按式（5）對蜜源進行更新、計算函數(shù)值和適應(yīng)值

step 8.按式（4）計算選擇概率Pi

step 9.觀察蜂階段：按貪婪選擇機制選擇蜜源并按式（5）進行更新

step10.偵查蜂階段：對于要丟棄的蜜源，按式（1）重新產(chǎn)生

step11.保存當前最優(yōu)個體xbest

step12.if m od（iter，nc）==0 then

step13.計算步長δj，并將xbest作為初始點調(diào)用改進RM

step14.if f（x′best）＜f（xbest）then用 x′best替換種群中間位置的個體，xbest=x′best.

step15.iter=iter+1

step16.end while

其中nc為常數(shù)，一般設(shè)置為nc=k×D［16］.

3　實驗

為了驗證RDABC算法的有效性，采用函數(shù)優(yōu)化領(lǐng)域中被廣泛采用的8個標準測試函數(shù)［19］進行了實驗.實驗在 Pentium（R）Dual-Core CPU: E5400、4 GB內(nèi)存、2.70 GHz主頻的計算機上實現(xiàn)，程序采用Matlab7.10.0語言實現(xiàn).

3.1實驗設(shè)置

實驗中采用的8個標準測試函數(shù)［19］的定義和取值范圍如表1所示，8個測試函數(shù)的理論最優(yōu)值都是0，其中函數(shù)F1～F3為單峰函數(shù)，F(xiàn)4～F5為多峰函數(shù).

表1　標準測試函數(shù)表

為了公平地比較各算法的性能，實驗公共參數(shù)都作如下統(tǒng)一設(shè)定：問題的維度為D=40，種群規(guī)模為NS=40，最大評價次數(shù)為max Cyeld=1000，控制參數(shù)limit=NS×D.其中改進的RM部分的參數(shù)作如下設(shè)置［17］：內(nèi)部控制參數(shù)，nl=15；a=20終止參數(shù)ε1= 1.0e-150，ε2=1.0e-4；進行局部搜索的控制參數(shù)nc= 5×D.為了分析RDABC的性能，將RDABC與標準ABC、dABC［16］和RABC［17］算法進行比較分析，其中dABC算法在ABC的雇傭蜂和觀察蜂階段引入了方向引導(dǎo)機制，是最近提出的一種改進算法，比很多其他的改進算法表現(xiàn)更優(yōu)，RABC算法在ABC的基礎(chǔ)上針對當前最優(yōu)個體引入了RM局部搜索策略.

3.2實驗結(jié)果與分析

Best，Worst，Mean和Std分別為算法獨立實驗30次的最好值、最差值、平均值和標準差.Best和Worst反映了解的質(zhì)量；Mean顯示了在給定函數(shù)評價次數(shù)下算法所能達到的精度，反映了算法的收斂速度；Std反映了算法的穩(wěn)定性.結(jié)果如表2所示，每個函數(shù)的最優(yōu)結(jié)果標記為黑體.

從表 2中可以看出，RDABC算法在求解Sphere、SumSquare、Zakharov及Griewank函數(shù)時，比標準ABC算法的求解質(zhì)量提高了1.0e-26至1.0e-41，求解精度提高了1.0e-27至1.0e-40；相比于dABC算法，解的質(zhì)量提高了1.0e-26至1.0e-37，解的精度提高了1.0e-27至1.0e-34.求解復(fù)雜的多峰函數(shù)Ackley和Bohachevsky時，RDABC相比于標準ABC算法，解的質(zhì)量提高了1.0e-8至1.0e-10，解的精度提高了1.0e-9至1.0e-10，且在Bohachevsky上獲得了理論最優(yōu)值；相比于dABC算法，解的質(zhì)量提高了1.0e-6至1.0e-7，精度提高了1.0e-7.RDABC相比于RABC算法，在最好值上針對所有的函數(shù)都取得了優(yōu)于或等于RABC的結(jié)果，對于Sphere、SumSquare、Rastrigin、Griewank、Bohachevsky函數(shù)，RDABC比RABC在解的精度提高了1.0e-1至1.0e-7，說明相比標準ABC、dABC、RABC，RDABC的收斂速度得到了提高.在反應(yīng)算法的穩(wěn)定性的方差指標上，除函數(shù)Zakharov和NCRastrigin外 ，RDABC算 法 在 求 解 Sphere、SumSquare、Griewank時，相比標準ABC算法提高了1.0e-32至 1.0e-40；相比dABC算法提高了1.0e-26至1.0e-34，相比RABC提高了1.0e-1至1.0e-7.在求解函數(shù)Rastrigin、Ackley、Bohachevsky時，相比標準ABC算法提高了1.0e-1至1.0e-10；相比dABC算法提高了 1.0e-1至1.0e-7，相比RABC提高了1.0e-1至1.0e-3，說明在這些函數(shù)上RDABC表現(xiàn)出了優(yōu)于上述3種算法的穩(wěn)定性.

實驗結(jié)果表明，針對這些測試函數(shù)，RDABC的性能在多數(shù)函數(shù)上要優(yōu)于ABC、dABC、RABC算法，解的質(zhì)量和精度得到進一步的提高，求解結(jié)果也更接近理論最優(yōu)值.特別是30次獨立運行后反應(yīng)結(jié)果的精度的均值普遍要比RABC的結(jié)果均值更優(yōu)，優(yōu)化最高數(shù)量級為1.0e-7，說明RDABC算法在這些優(yōu)化問題的求解過程中很好的結(jié)合了方向引導(dǎo)信息策略和RM局部搜索方法，增強了RDABC算法的尋優(yōu)能力.

表2　算法最優(yōu)、最差、均值、方差實驗結(jié)果表

表3　顯著性水平的t檢驗表

為了從統(tǒng)計學(xué)意義上分析RDABC算法的有效性，對其進行顯著性水平為p=0.05的t—檢驗，檢驗結(jié)果如表3所示.

從表3可知，RDABC算法在6個函數(shù)上顯著優(yōu)于ABC算法和dABC算法，在5個函數(shù)上顯著優(yōu)于RABC算法.從統(tǒng)計意義上表明了，RDABC算法更好的結(jié)合了方向指導(dǎo)信息和RM局部搜索策略，使得其在絕大多數(shù)測試函數(shù)上的求解精度更高，性能更優(yōu).

4　結(jié)論

針對標準ABC算法在求解復(fù)雜多峰問題時容易出現(xiàn)收斂速度慢、開采能力不足、求解精度低的缺點，提出一種改進的RDABC算法用于數(shù)值優(yōu)化問題.由于RDABC算法在雇傭蜂和觀察蜂階段引入方向指導(dǎo)策略，使得個體維度上的數(shù)值朝著更優(yōu)的方向進行搜索.針對當前最優(yōu)個體進行了轉(zhuǎn)軸法局部搜索，使得當前最優(yōu)個體能快速而有效的得到優(yōu)化更新，同時為了避免局部搜索過程可能使算法陷入局部最優(yōu)，進行了有選擇性的調(diào)用RM局部搜索，這些改進使得RDABC算法相比ABC、dABC、RABC算法具有更高的求解精度，更快的收斂速度.初始種群的多樣性及雇傭蜂和觀察蜂階段的選擇策略對算法的性能也有一定的影響，進一步的研究可以從這兩個方面開展，從而使得算法性能更優(yōu)，能更好的用于工程優(yōu)化問題.

［1］Karaboga D.An idea based on honey bee swarm for numerical optimization［R］.Kayseri:Erciyes University，2005.

［2］Dervis Karaboga，Bahriye Basturk.Apowerful and efficient algorithm for numerical function optimization:artificial bee colony（ABC）algorithm ［J］.Journal of Global Optimization，2007，39（3）: 459-471.

［3］Karaboga D，Basturk B.On the performance of artificial bee colony（ABC）algorithm［J］.Applied Soft Computing，2008，8（1）:687-697.

［4］秦全德，程適，李麗，等.人工蜂群算法研究綜述［J］.智能系統(tǒng)學(xué)報，2014，9（2）:127-135.

［5］陳阿慧，李艷娟，郭繼峰.人工蜂群算法綜述［J］.智能計算機與應(yīng)用，2014（6）:20-24.

［6］Xu C，Duan H，Liu F.Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle（UCAV）path planning［J］. Aerospace Science&Technology，2010，14（8）:535-541.

［7］Coelho L D S，Alotto P.Gaussian artificial bee colony algorithm approach applied to Loney’s solenoid benchmark problem［J］. Magnetics，IEEE Transactions on，2011，47（5）:1326-1329.

［8］王慧穎，劉建軍，王全洲.改進的人工蜂群算法在函數(shù)優(yōu)化問題中的應(yīng)用［J］.計算機工程與應(yīng)用，2012，48（19）:36-39.

［9］Akay B.A study on particle swarm optimization and artificial bee colony algorithms for multilevel thresholding［J］.Applied Soft Computing，2013，13（6）:3066-3091.

［10］周文越，呂飛鵬，廖小君.基于人工蜂群算法的環(huán)網(wǎng)方向保護配合最小斷點集計算［J］.電力系統(tǒng)保護與控制，2013（6）:77-81.

［11］Pan Q K，Wang L，Li JQ，et al.A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespanminimisation［J］.Omega，2014，45（2）:42-56.

［12］阮羚，徐碧川，全江濤，等.用于土壤分層電阻率模型反演的人工蜂群結(jié)合混沌搜索算子及混沌算法 ［J］.高電壓技術(shù)，2015，41（1）:42-48.

［13］Mansouri P，Asady B，Gupta N.The Bisection-Artificial Bee Colony algorithm to solve fixed point problems［J］.AppliedSoft Computing，2015（26）:143-148.

［14］郭肇祿，吳志健，汪靖，等.一種基于精英云變異的差分演化算法［J］.武漢大學(xué)學(xué)報（理學(xué)版），2013，59（2）:117-122.

［15］郭肇祿，吳志健，董曉健，等.一種基于分量熱力學(xué)遷移策略的并行多種群 GEP［J］.四川大學(xué)學(xué)報（工程科學(xué)版），2012，44（2）: 83-90.

［16］K I ran M S，F(xiàn)IndIk O.A directed artificial bee colony algorithm［J］. Applied Soft Computing，2015，26:454-462.

［17］Kang F，Li J，Ma Z.Rosenbrock artificial bee colony algorithm for accurateglobal optimizationof numerical functions［J］. Information Sciences，2011，181（16）:3508-3531.

［18］陳寶林.最優(yōu)化理論與算法［M］.2版.北京：清華大學(xué)出版社，2005.

［19］Yao X，Liu Y，Lin G.Evolutionary programming made faster［J］. IEEE Transactions on Evolutionary Computation，1999，3（2）:82-102.

Rosenbrock artificial bee colony algorithm with directed information

YIN Yali，XIONG Xiaofeng，GUO Zhaolu

（Faculty of Science，Jiangxi University of Science and Technology，Ganzhou 341000，China）

Artificial bee colony（ABC）algorithm has slow convergence for complexmultimodal problems，and is good at exploration but poor at exploitation.The study proposes animprovedABCalgorithmcalled Rosenbrock-directed ABC（RDABC）by adding the Rosenbrock's rotational direction method for the local search tool and directional information to ABC.The performance of the proposed approach was examined on well-known eight benchmark functions.The experimental results show that the proposed approach is more effective andmore successful in terms of solution quality，and convergence to global optimum.

artificial bee colony algorithm；directional information；Rosenbrockmethod；local search technique

TP391

A

2095-3046（2015）05-0098-06

10.13265/j.cnki.jxlgdxxb.2015.05.017

2015-04-30

國家自然科學(xué)基金項目（11401267，11461032）

尹雅麗（1989-），女，碩士研究生，主要從事建模與優(yōu)化算法應(yīng)用等方面的研究，E-mail:1071712763@qq.com.

熊小峰（1965-），男，教授，主要從事建模與應(yīng)用數(shù)理統(tǒng)計等方面的研究，E-mail:xxf_gz@163.com.