基于模擬退火思想的改進人工蜂群算法

張業清 李婧芳 胡鵬偉

摘? 要： 針對人工蜂群算法（ABC）容易陷入局部極值點、進化后期收斂慢和優化精度較差等缺點。把模擬退火技術（SA）引入到ABC算法中，提出了一種改進的優化算法?；旌蟽灮惴ㄔ诟鳒囟认乱来芜M行ABC和SA搜索，是一種兩層的串行結構。由于ABC提供了并行搜索結構，所以，混合優化算法使SA轉化成并行SA算法。SA的概率突跳性保證了種群的多樣性，從而防止ABC算法陷入局部極小?；谀M退火的改進人工蜂群算法保持了ABC算法簡單容易實現的特點，改善了算法的全局優化能力，便于收斂的同時也可以防止算法陷入局部最優解。

關鍵詞： 人工蜂群算法;模擬退火;局部最優

中圖分類號： TP391 ???文獻標識碼： A??? DOI：10.3969/j.issn.1003-6970.2020.07.003

本文著錄格式：張業清，李婧芳，胡鵬偉. 基于模擬退火思想的改進人工蜂群算法[J]. 軟件，2020，41（07）：15-21

Improved Artificial Bee Colony Algorithm Based on Simulated Annealing

ZHANG Ye-qing¹， LI Jing-fang¹， HU Peng-wei²

（1. College of Information Science and Technology， Gansu Agricultural University， Lanzhou 730070， China;2. College of Mechanical and Vehicle Engineering， Changchun University， Changchun 130022， China）

【Abstract】： Aiming at the shortcomings of artificial bee colony algorithm （ABC） easy to fall into local extreme point， slow convergence in late evolution and poor optimization accuracy. Simulated annealing technology （SA） is introduced into the ABC algorithm， and an improved optimization algorithm is proposed. The hybrid optimization algorithm performs ABC and SA search in sequence at each temperature and is a two-layer serial structure. Since ABC provides a parallel search structure， a hybrid optimization algorithm transforms SA into a parallel SA algorithm. The probabilistic suddenness of SA ensures the diversity of the population， thus preventing the ABC algorithm from falling into a local minimum. The improved artificial bee colony algorithm based on simulated annealing maintains the characteristics of the ABC algorithm that is simple and easy to implement， improves the algorithm's global optimization ability， facilitates convergence， and prevents the algorithm from falling into the local optimal solution.

【Key words】： Artificial bee colony algorithm; Simulated annealing; Local optimal

0? 引言

2005年，土耳其學者Karaboga提出一種人工蜂群算法^[1]，這種算法主要依托了一種全新的群智能下的全局優化算法，它靈感是從蜂群在進行采蜜的行為中得到的。通過采蜜中的蜂群行為進行效仿，來提出的一種優化算法，采用該優化算法只要求我們對問題本身的優劣情況進行對比，不需要去深入了解某些問題的特殊性，在蜂群中只需了解局部工蜂的優化行為，來然后在整個蜂群中采用全局的優化情況進行對比，得出最優情況并進行突出表現，這樣的算法對于收斂的速度提高很多，這也可以說是它為集群智能思想的重要體現。

作為一種新的集群智能優化算法，人工蜂群算法理論研究和應用已經成為新的研究熱點，由于它在很多方面的優良性能，已經成為仿生智能計算機領域的一種重要優化算法?？墒菍τ谶@種最基本的蜂群算法來講，存在一定的弊端，它很容易陷入一定的局部優化現象和進化后期收斂速度較慢等缺點^[2]，但是本文從防止其陷入局部最優解方面進行了改進，來提高該算法的性能，經過試驗可以看出改進后的人工蜂群算法可以很好地預防模型陷入局部最優^[1]。

1 ?人工蜂群算法

1.1 ?人工蜂群算法

在人工蜂群算法中，每次搜尋過程包括三個階段內容^[3-10]：

（1）該階段下，對于采集位置隨機分到各個工蜂之間，各個工蜂將對該負責位置的花蜜多少進行測量，測量結束后各個工蜂回到蜂巢進行蜜源信息額分享。

（2）完成各自信息揮匯報之后，蜜蜂在回到他們之前到達的地方，依照各自的視覺情況對采集位置進行排查，再去周圍尋找一個新的位置下的蜜源。

（3）這時每個觀察的蜂蜜將對工蜂分享的花蜜信息進行選擇，如果該位置的蜜源才存在的花蜜量越大則此處的蜜源被選擇到的概率就越大。

此時得到高蜜源信息的觀察蜂召喚的蜜蜂就會有更多的花蜜量。在蜜蜂到達了其選定的位置后，基于蜜源位置的對比，進行采蜜的工蜂會依照其先前的自身的記憶在之前的位置進行新的選擇，得到一個新的蜜源，當有一個位置的花蜜被采蜜蜂進行舍棄后，將有新的觀察蜂對蜜源進行選定，來對舍棄的位置進行替換。在這個采蜜過程中，每次外出時只要求一致觀察蜂去搜查新位置下的蜜源，同時要求進行觀察的蜜蜂數量與進行采蜜工蜂的數量是一致的。

在該蜂群采蜜過程中，對于蜂群中進行采蜜和觀察的蜜蜂數量基本保持為各自一半。同時對于每個位置只分配一個工蜂進行采蜜。我們可以理解成實際蜜源的數量與進行采蜜的數量是一樣的。當出現在某一位置中的蜜源被進行觀察和采蜜的工蜂采完后，此位置的采蜜蜂將會成為一個新的偵查蜜蜂隨機尋找新的蜜源。

三種蜜蜂在不同的條件下可以相互轉換，如下圖。

在該算法當中，對于優化問題來講，該解可能是存在某一位置下的蜜源，而適應度的函數值則對應該位置下的花蜜量的數量。解為觀察或是進行采蜜的工蜂的數量。該算法包含以下幾個步驟。

（1）在該算法下，有N個偵查蜂進行偵查任務，這也可以認為是該算法的可行解，同時N也代表了進行采蜜工作的工蜂的數量，也可代表著尋找到的蜜源的數量值。該算法中每個解（i=1，2，…，N）都可以認為是D維的向量，其中D也可以認為是參量的個數值。每一個蜜源吸引一個采蜜蜂，N個蜜源吸引N個采蜜蜂，采蜜蜂的位置即為蜜源的位置。

（2）在該算法進行完初始化之后，針對于蜜源的問題的最優解會通過三種蜜蜂進行尋找后得出，觀察蜂或是進行采蜜的工蜂依照自身獲得的信息內容在現有的特定區域下進行尋找來進一步獲得新的蜜源的位置，并對該位置的花蜜量多少進行相應的測量，該測量值也可以認為是適應度函數對應的數值。通常在蜜蜂進行真實采蜜下，它們會對改位置中的蜜源多少進行判定并進一步得出此處的新蜜源的產值。在該計算模型中同樣依靠這一原理。但是在此模型中，是不會對信息進行深一步的比較，一般是對蜜源進行隨機的選定，同時依靠記憶來選定一個區域，依據下面的公式（2）進行分析，按照貪婪準則，如果一個區域中的蜜源高于另一個區域蜜源，他們會對蜜源較低的區域進行舍棄，并對區域進行記憶。完成所有區域的信息搜索后，他們會回到指定位置與觀察的蜜蜂進行蜜源信息的分享，每一個觀察蜂都會對其觀察的蜜源量進行信息評估，并根據評估結果作為蜜源選擇的依據。蜜源的收益度越高，吸引觀察蜂的概率越大。

（3）對于進行采蜜的蜜蜂來講，他通過本身的記憶信息對原位置進行判定，得出一個限定區域，對候選的花蜜量進行測量，依照貪婪準則對蜜源的位置進行選定。

對于一個位置內的蜜源進行選定的該概率情況進行選定方式可以表示為：

在上面的（1）式中，第i個解所對應適應度函數數值可以用進行表示，該數值與第i個位置下蜜源的實際數量也是成正相關的;蜜源的實際數量我們采用N進行表示，這與進行采蜜的蜜蜂的數量是一致的。觀察蜂與進行采蜜的蜜蜂采用這種方式來完成信息的交匯。

ABC模型采用以下公式從就的蜜源位置中產生一個新的候選蜜源位置，即：

式（2）中，與在集合中進行隨機的選取，并且，rand（）在此式中代表了[-1，1]中的隨機數值，蜜源在限定范圍的實際產量有它來影響，同時對于限定區域它可以對工蜂獲得的并且可以進行比較的區域進行代替。

對于上式（2）我們可以得出，在位置處的波動情況與和的參數差是正相關的。通過該原理，想要在蜜蜂進行搜尋的區域內短時間內得到最優解就要對步長進行縮短的調整。

每個候選蜜源位置產生后，其花蜜量與進行比較。如果出現了更好的蜜源位置，依照貪婪法則，舊的蜜源位置將會被替換。同時某未知的蜜源量在經過有限次搜索后蜜源含量任然么有改善，自該蜜源將會被放棄。

1.2 ?人工蜂群算法的四種選取過程

（1）全局形式的選擇過程：觀察蜂在一般情況下會采用這種方法，它們通過這種方式來對花蜜量最多的區域進行判定及選取，這也是對最優解的區域進行選取。見上式（1）所示。

（2）隨機形式的選擇過程：這種方法通常偵察蜂采用。

（3）區域形式的選擇過程：這種方法可以同時被進行采蜜和觀察的蜜蜂選取，依照該區域中的線管蜜源信息對記憶位置周圍區域的蜜源量進行測定，見上式（2）所示。

（4）貪婪選擇形式的過程：任何進行采蜜工作的蜜蜂均使用該方式，如果存在花蜜量更高的蜜源，蜜蜂將在其記憶中替代原有的花蜜量較少的蜜源，如果不存在將不會進行替換。

人工蜂群算法中，蜜蜂的采蜜行為和函數優化問題的對應關系如下表。

1.3 ?人工蜂群算法程序的實現步驟

1. 蜜蜂種群的初始化情況。在該程序的初始階段，所有的蜜蜂全部以偵查蜂的形式出現，對全局進行搜索，因為他們對于各區域沒有了解，依照所搜得到的蜜源來對花蜜進行評估，也就是“收益度”。

對于種群參數而言，只要有以下三個參數：

（1）蜜蜂的總體數量N，一般情況下我們會將觀察蜂和進行采蜜的蜜蜂分別認為是N/2;

（2）對于某處蜜源的停留的最大搜索限制次數Limit;

（3）搜索過程中出現的最大迭代次數;

2. 依照上步得到的“收益度”數值，蜂群將被劃分為兩類即：觀察蜂和采蜜蜂，得到收益度靠后的將變為觀察蜂，而靠前的將變為采蜜蜂。此時觀察蜂在舞蹈區進行等待，通過采蜜蜂傳遞的信息來對該區域的花蜜信息有一個掌握，對于花蜜量含量高的區域召喚觀察蜂也會逐步增加，這是一個以概率形式來完成招募的過程。

3. 采蜜蜂將在原蜜源附近繼續搜索并開展采蜜工作，并對該區域的花蜜量進行評估，依照貪婪法則對蜜源進行選取，來獲得更多的花蜜。

4. 對于觀察蜂而言，他們對于蜜源的選取是依據適應度進行概率性分配，在蜜源周圍進行采蜜及蜜源尋找，在進行蜜源尋找過程中，同樣遵循貪婪原則。

5. 如果在該蜜源區域搜索的次數已經超過了限定次數，但是還沒發現更好的蜜源，它們將會放棄此區域，同時蜜蜂的角色也會發生改變，即觀察蜂和采蜜蜂會變成偵查蜂，隨機前往一個新位置的蜜源。

6. 對當前的所有蜜源進行記錄，來找到全局的最優解，并跳轉到第2步，循環此過程，結束的標志為符合最大迭代次數或是小于優化誤差，最后得到全局的最優值。

2 ?建模過程實例

在該建模中建立人工蜂群算法的數學模型，同時該建模以典型的多峰值函數優化問題為分析背景。

（1）對于n=0時刻，隨機生成個可行解，具體隨機產生的可行解為：

（7）一旦出現符合停止要求的情況出現，則停止計算過程并得出最優適應度值以及與其相關的參數值，否則在回到第2步進行重新運算。

其中第（6）步主要是為了增強種群的多樣性，防止種群陷入局部最優值，這一步驟可使種群搜索到最優值的概率得到提高。

3 ?基于模擬退火算法的改進人工蜂群算法

3.1 ?模擬退火算法原理分析

模擬退火算法這種算法是以固體退火原理為基礎，在固體處于高溫環境下，其內部的粒子在進行快速的無規則運動，同時具有很大的內能，但是在其處于常溫時起內部的粒子最穩定，內能達到了最小，模擬退火算法也是根據這種原理進行設計的。

模擬退火算法通過概率統計展開隨機性的迭代求解^[11]，該方法模擬固體物質退火，進一步的解決了在算法進優化時易陷入局部最優解這一難題，同時在進行組合問題優化時可不過分依賴目標函數的初始值。對于該算法進行優化的目標函數來講，它是對固體的內能進行了模擬求全部的解由固體的內能值進行表示，我們得到的最小內能值就是代表問題的最優解。讓金屬逐漸的冷卻才能得到最低的內能值，這也是組合優化的重要前提。對于退火算法進行模擬式主要包含3個內容即：冷卻、等溫及加溫過程^[12]。在金屬溫度為T時，處于固體內部的粒子會處在一個相對平衡的狀態，假設在該溫度下固體的被能為E，該變量為，則這時固體內部的粒子處于平衡狀態下的概率可用來進行表示。但是隨著溫度的降低，其中的內能也最終將達到一個最低值^[13]。

3.2 ?模擬退火思想尋找最小值問題

這種計算方法是依靠統計力學進行展開。在統計力學角度中分析，處于不同結構下的粒子有不同能量。不同的溫度下，粒子能量不同，粒子的運動及排列形式也有所不同。當系統從高溫條件下逐步的降低溫度，直至完全的冷卻，晶體最終會處于一種低能的狀態^[14-15]。

假如我們對于材料的狀態采用粒子自身的能力進行定義，Metropolis算法可以認為退火過程采用了一個簡單的數學模型進行表達。。這時我們假設E（i）為材料處在i狀態下的能量，材料在處于T溫度時，對于從i狀態變為j狀態則可以表示為以下規律：

（1）當E（i）小于等于E（j）時，狀態的變化用下面概率呈現：

上式中，材料溫度用T表示，而K代表波爾茲曼常數。

（2）當E（i）大于等于E（j）時，這種狀態轉換將被認可。

綜上所述在一定溫度下，材料進行了充分的轉換后，會達到一種熱平衡狀態。如果出現溫度降低的很大情況時，材料會以很大概率進入最小能量狀態。

假設目標函數為：

要求得最優解，就要設定初始溫度，同時對其進行初始化得到解x（0），通過x（0）得到解x?，分析x?是否接受成為新解x（1）依賴于一個概率密度函數（接受新解的概率），若新解大于舊解則以概率1接受新解，若新解小于舊解這個概率則以概率密度函數計算值接受，通常為小于1的情況。

在溫度下，對于新得到的解x?可以通過優化問題的解x（k）得到，分析接受x?成為新解x（k+1）是一定的概率問題。對溫度進行多次溫度降低的轉換后，得出。在的情況下對上述操作進行重復。整個過程可以認為逐漸的進行新解尋找和逐漸降低溫度的過程，最后我們得到解就是該分析問題的最優解。

在下，x（k）的狀態決定下一個新的狀態x（k+1），與前面的狀態情況時無關的，這是一個典型馬爾可夫過程。如果存在緩慢下降溫度但是每一狀態下溫度卻又經過多次轉換，致使在每個溫度狀態下都實現熱平衡，這時將以概率1的形式進行全局的最優解表達。綜上所述全局最優解可以通過模擬退火算法進行獲取。

3.3? 轉移概率公式

容易看出其轉移概率函數為指數函數，其自變量越大概率越大。首先不考慮常數系數K，K的作用僅限于人為調節，分兩方面來考慮這一轉移概率函數。

（1）解的差值不變，溫度改變

當解的差值不變時，其自變量的分子不變，分母越大，自變量越小，其負值越大，其因變量值越大，越接近1，其圖像如圖3所示。表明同一差值下，溫度越高就越容易接受新的差解。

（2）溫度不變，解的差值改變

當溫度不變時，其自變量的分母不變，差值越大分子越大，其負數越小，其因變量越小，越接近0，其圖像如圖4所示。表明同一溫度下，差值越小就越容易接受新的差解。

對于智能算法而言，算法的前期搜索范圍極大，當算法達到后期時，會慢慢進入收斂狀態，即可能達到了全局或局部最優解，為此，本文從局部最優和全局最優兩方面來考慮改進方法。

（1）局部最優解的搜索方法

本文方法的思想可以使解不斷向解空間的最優解靠攏，可以有效的加快局部搜索的速度，使一個解空間可以以最快的速度達到局部最優解。

（2）全局最優解的搜索方法

由于智能算法的隨機性，不能保證種群覆蓋到全部的解集，很容易陷入局部最優解，同時在解的前期其移動步長過短，后期移動步長過長，故本文借助模擬退火算法的思想，引入“溫度”，“接受概率”等概念來解決此問題。

（3）本文轉移概率公式

Double delta = x_old-x_nei

Double cr = exp（delta/（1/process*100））

If （rdft（）

X_new = x_old+（x_old-x_nei）*（rdft（）-0.5）* 2+（x_glo-x_old）*0.5*（rdft（））;

}else{

X_new=x_old+（x_old-x_nei）*（rdft（）-0.5）*2;

}

本優化方法以SA為思想，取K=100，t=1/process，process為算法運行的當前代數，當前鄰居解與舊解的差值為分子。即：當運行代數較小時，1/process較大，溫度較高，cr值較大，算法更容易向局部最優解靠攏。當運行代數較大時，1/process較小，溫度較低，cr值較小，算法更容易擾亂原解，脫離局部最優解。

4 ?實驗結果及分析

由于ABC算法的貪心算法找到的是局部最優解的情況，全局最優則是通過模擬退火算法獲取。對于模擬退火算法來講，它的基礎是metropolis算法。Metropolis算法又稱為metropolis抽樣，其核心思想是當能量增加的時候以一定的概率接納而非一味拒絕?；诖怂枷霊糜诨A的ABC算法上，經實驗證明去的了較好的效果。傳統的ABC算法在算法的任何階段對于新解的產生，改變的步長都是一定的，本文通過引入模擬退火思想，使ABC在算法初期能以較大步長尋找新解，便于跳出局部最優;在算法后期以小概率接受步長較長的新解，便于收斂的同時也可以防止算法陷入局部最優解。為了驗證基于模擬退火算法的人工蜂群算法的優化結果，本文對原始的三種優化算法以及我們的優化算法分別在三個不同的目標函數下進行200次的迭代，得到了如下實驗結果：

4.1 ?第一組實驗（目標函數為Rosenbroke函數）

（1）第一種原始的新解產生函數（設置pp_ debug = 1），運行結果如下：

Means of 200 runs： 9.808269901650287892

平均運行時間=： 0.055567155000000 second

Min val：0.176049980984729904

（2）第二種改進方法（pp_debug = 2），此轉移方法在第一種的基礎上增加了全 局更新的思想，有利于達到全局最優解，但會陷入局部最優解，運行結果如下：

Means of 200 runs： 27.444346569494861399

平均運行時間=： 0.056990765000000 second

Min val：0.062116211823108072

（3）第三種轉移方法（pp_debug = 3），次方法結合第一種和第二種，沒有本質改 進，效果介于第一種和第二種之間，運行結果如下：

Means of 200 runs： 15.291687887025133818

平均運行時間=： 0.057119505000000 second

Min val：0.104958787969900436

（4）本文在引入模擬退火算法之后（即pp_ debug = 5）時，運行結果如下：

Double delta = x_old-x_nei

Double cr = exp（delta/（1/process*100））

If （rdft（）

X_new = x_old+（x_old-x_nei）*（rdft（）-0.5）* 2+（x_glo-x_old）*0.5*（rdft（））;

}else{

X_new=x_old+（x_old-x_nei）*（rdft（）-0.5）*2;

}

Means of 200 runs： 9.417805958074286110

平均運行時間=： 0.057688065000000 second

Min val：0.011360413050712590

由運行結果可見解的平均值大大降低

4.2 ?第二組實驗（目標函數為Griewank函數）

4.3 ?第三組實驗（目標函數為Rastrigin函數）

經過以上三組實驗結果可以看出，本文基于模擬退火算法的改進對三種不同優化目標函數下的結果均優于前三種算法且十分有效，在時間復雜度不增加的同時對平均結果和最優解的提升效果很大。

5 ?結論

本文將ABC和SA相結合，得到了一種改進后的的人工蜂群計算方法。這種方法不但保留基本人工蜂群算法具有的簡單容易實現的優勢，而且利用SA的概率突跳性，保證了群體的多樣性，同時增強了收斂精度以及對于空間的探索能力，避免了原始方法的缺點。它不僅僅是算法上的改進，同時也體現了進化以及搜索形式的互補。能夠很好地解決對于復雜問題的優化難題。這種改進的人工蜂群算法不論在性能還是優化效率層面，可以通過計算機仿真結果得出是明顯優于基本ABC算法。

參考文獻

1. An Idea Based On Honey Bee Swarm For Numerical Optimization. Karaboga. D. Technical Report-TR06. 2005

2. Abachizadeh M， Yazdi M， Yousefi-Koma A. Optimal tuning of pid controllers using artificial bee colony algorithm[C]// 2010 IEEE/ASME International Conference on Advanced Intelligent Mechatronics（AIM）， 2010： 379-384.

3. Tereshko V. Reaction-diffusion model of a honeybee colonys foraging behavior[C]. Parallel Problem Solving from Nature PPSN VI. Springer Berlin Heidelberg， 2000： 807-816.

4. Tereshko V， Lee T. How information-mapping patterns determine foraging behaviour of a honey bee colony[J]. Open Systems & Information Dynamics， 2002， 9（02）： 181-193.

5. Lucic P， Teodorovic D. Bee system： modeling combinatorial optimization transportation engineering problems by swarm intelligence[C]. Preprints of the TRISTAN IV triennial symposium on transportation analysis. 2001： 441-445.

6. Teodorovi?D， DellOrco M. Bee colony optimization-a cooperative learning approach to complex transportation problems[C]. Advanced OR and AI Methods in Transportation： Proceedings of 16th Mini-EURO Conference and 10th Meeting of EWGT （13-16 September 2005）. Poznan： Publishing House of the Polish Operational and System Research. 2005： 51-60.

7. Yang X S. Engineering optimizations via nature-inspired virtual bee algorithms[M]. Artificial Intelligence and Knowledge Engineering Applications： A Bioinspired Approach. Springer Berlin Heidelberg， 2005： 317-323.

8. Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical report-tr06， Erciyes University， engineering faculty， computer engineering department， 2005.

9. Karaboga D， Akay B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation， 2009， 214（1）： 108-132.

10. Karaboga D， Akay B. A survey： algorithms simulating bee swarm intelligence[J]. Artificial Intelligence Review， 2009， 31（1-4）： 61-85.

11. Karaboga D.An idea based on honey bee swarm for numerical optimization， TR06[R].Kayseri，Turkey： Erciyes University， 2005.

12. 何堯， 劉建華， 楊榮華. 人工蜂群算法研究綜述[J]. 計算機應用研究， 2018， 35（05）： 1281-1286.

13. 陶重犇， 雷祝兵， 李春光， 等. 基于改進模擬退火算法的搬運機器人路徑規劃[J]. 計算機測量與控制， 2018， 26（7）： 182-185.

14. 裴小兵， 賈定芳. 基于模擬退火算法的城市物流多目標配送車輛路徑優化研究[J]. 數學的實踐與認識， 2016， 46（2）： 105-113.

15. 張磊. 基于模擬退火算法的糧食調撥路徑規劃[J]. 糧食加工， 2019， 44（04）： 7-9.