張業(yè)清 李婧芳 胡鵬偉

摘? 要： 針對(duì)人工蜂群算法（ABC）容易陷入局部極值點(diǎn)、進(jìn)化后期收斂慢和優(yōu)化精度較差等缺點(diǎn)。把模擬退火技術(shù)（SA）引入到ABC算法中，提出了一種改進(jìn)的優(yōu)化算法。混合優(yōu)化算法在各溫度下依次進(jìn)行ABC和SA搜索，是一種兩層的串行結(jié)構(gòu)。由于ABC提供了并行搜索結(jié)構(gòu)，所以，混合優(yōu)化算法使SA轉(zhuǎn)化成并行SA算法。SA的概率突跳性保證了種群的多樣性，從而防止ABC算法陷入局部極小?；谀M退火的改進(jìn)人工蜂群算法保持了ABC算法簡單容易實(shí)現(xiàn)的特點(diǎn)，改善了算法的全局優(yōu)化能力，便于收斂的同時(shí)也可以防止算法陷入局部最優(yōu)解。

關(guān)鍵詞： 人工蜂群算法;模擬退火;局部最優(yōu)

中圖分類號(hào)： TP391 ???文獻(xiàn)標(biāo)識(shí)碼： A??? DOI：10.3969/j.issn.1003-6970.2020.07.003

本文著錄格式：張業(yè)清，李婧芳，胡鵬偉. 基于模擬退火思想的改進(jìn)人工蜂群算法[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年，土耳其學(xué)者Karaboga提出一種人工蜂群算法^[1]，這種算法主要依托了一種全新的群智能下的全局優(yōu)化算法，它靈感是從蜂群在進(jìn)行采蜜的行為中得到的。通過采蜜中的蜂群行為進(jìn)行效仿，來提出的一種優(yōu)化算法，采用該優(yōu)化算法只要求我們對(duì)問題本身的優(yōu)劣情況進(jìn)行對(duì)比，不需要去深入了解某些問題的特殊性，在蜂群中只需了解局部工蜂的優(yōu)化行為，來然后在整個(gè)蜂群中采用全局的優(yōu)化情況進(jìn)行對(duì)比，得出最優(yōu)情況并進(jìn)行突出表現(xiàn)，這樣的算法對(duì)于收斂的速度提高很多，這也可以說是它為集群智能思想的重要體現(xiàn)。

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

1 ?人工蜂群算法

1.1 ?人工蜂群算法

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

（1）該階段下，對(duì)于采集位置隨機(jī)分到各個(gè)工蜂之間，各個(gè)工蜂將對(duì)該負(fù)責(zé)位置的花蜜多少進(jìn)行測(cè)量，測(cè)量結(jié)束后各個(gè)工蜂回到蜂巢進(jìn)行蜜源信息額分享。

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

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

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

在該蜂群采蜜過程中，對(duì)于蜂群中進(jìn)行采蜜和觀察的蜜蜂數(shù)量基本保持為各自一半。同時(shí)對(duì)于每個(gè)位置只分配一個(gè)工蜂進(jìn)行采蜜。我們可以理解成實(shí)際蜜源的數(shù)量與進(jìn)行采蜜的數(shù)量是一樣的。當(dāng)出現(xiàn)在某一位置中的蜜源被進(jìn)行觀察和采蜜的工蜂采完后，此位置的采蜜蜂將會(huì)成為一個(gè)新的偵查蜜蜂隨機(jī)尋找新的蜜源。

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

在該算法當(dāng)中，對(duì)于優(yōu)化問題來講，該解可能是存在某一位置下的蜜源，而適應(yīng)度的函數(shù)值則對(duì)應(yīng)該位置下的花蜜量的數(shù)量。解為觀察或是進(jìn)行采蜜的工蜂的數(shù)量。該算法包含以下幾個(gè)步驟。

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

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

（3）對(duì)于進(jìn)行采蜜的蜜蜂來講，他通過本身的記憶信息對(duì)原位置進(jìn)行判定，得出一個(gè)限定區(qū)域，對(duì)候選的花蜜量進(jìn)行測(cè)量，依照貪婪準(zhǔn)則對(duì)蜜源的位置進(jìn)行選定。

對(duì)于一個(gè)位置內(nèi)的蜜源進(jìn)行選定的該概率情況進(jìn)行選定方式可以表示為：

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

ABC模型采用以下公式從就的蜜源位置中產(chǎn)生一個(gè)新的候選蜜源位置，即：

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

對(duì)于上式（2）我們可以得出，在位置處的波動(dòng)情況與和的參數(shù)差是正相關(guān)的。通過該原理，想要在蜜蜂進(jìn)行搜尋的區(qū)域內(nèi)短時(shí)間內(nèi)得到最優(yōu)解就要對(duì)步長進(jìn)行縮短的調(diào)整。

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

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

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

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

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

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

人工蜂群算法中，蜜蜂的采蜜行為和函數(shù)優(yōu)化問題的對(duì)應(yīng)關(guān)系如下表。

1.3 ?人工蜂群算法程序的實(shí)現(xiàn)步驟

1. 蜜蜂種群的初始化情況。在該程序的初始階段，所有的蜜蜂全部以偵查蜂的形式出現(xiàn)，對(duì)全局進(jìn)行搜索，因?yàn)樗麄儗?duì)于各區(qū)域沒有了解，依照所搜得到的蜜源來對(duì)花蜜進(jìn)行評(píng)估，也就是“收益度”。

對(duì)于種群參數(shù)而言，只要有以下三個(gè)參數(shù)：

（1）蜜蜂的總體數(shù)量N，一般情況下我們會(huì)將觀察蜂和進(jìn)行采蜜的蜜蜂分別認(rèn)為是N/2;

（2）對(duì)于某處蜜源的停留的最大搜索限制次數(shù)Limit;

（3）搜索過程中出現(xiàn)的最大迭代次數(shù);

2. 依照上步得到的“收益度”數(shù)值，蜂群將被劃分為兩類即：觀察蜂和采蜜蜂，得到收益度靠后的將變?yōu)橛^察蜂，而靠前的將變?yōu)椴擅鄯?。此時(shí)觀察蜂在舞蹈區(qū)進(jìn)行等待，通過采蜜蜂傳遞的信息來對(duì)該區(qū)域的花蜜信息有一個(gè)掌握，對(duì)于花蜜量含量高的區(qū)域召喚觀察蜂也會(huì)逐步增加，這是一個(gè)以概率形式來完成招募的過程。

3. 采蜜蜂將在原蜜源附近繼續(xù)搜索并開展采蜜工作，并對(duì)該區(qū)域的花蜜量進(jìn)行評(píng)估，依照貪婪法則對(duì)蜜源進(jìn)行選取，來獲得更多的花蜜。

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

5. 如果在該蜜源區(qū)域搜索的次數(shù)已經(jīng)超過了限定次數(shù)，但是還沒發(fā)現(xiàn)更好的蜜源，它們將會(huì)放棄此區(qū)域，同時(shí)蜜蜂的角色也會(huì)發(fā)生改變，即觀察蜂和采蜜蜂會(huì)變成偵查蜂，隨機(jī)前往一個(gè)新位置的蜜源。

6. 對(duì)當(dāng)前的所有蜜源進(jìn)行記錄，來找到全局的最優(yōu)解，并跳轉(zhuǎn)到第2步，循環(huán)此過程，結(jié)束的標(biāo)志為符合最大迭代次數(shù)或是小于優(yōu)化誤差，最后得到全局的最優(yōu)值。

2 ?建模過程實(shí)例

在該建模中建立人工蜂群算法的數(shù)學(xué)模型，同時(shí)該建模以典型的多峰值函數(shù)優(yōu)化問題為分析背景。

（1）對(duì)于n=0時(shí)刻，隨機(jī)生成個(gè)可行解，具體隨機(jī)產(chǎn)生的可行解為：

（7）一旦出現(xiàn)符合停止要求的情況出現(xiàn)，則停止計(jì)算過程并得出最優(yōu)適應(yīng)度值以及與其相關(guān)的參數(shù)值，否則在回到第2步進(jìn)行重新運(yùn)算。

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

3 ?基于模擬退火算法的改進(jìn)人工蜂群算法

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

模擬退火算法這種算法是以固體退火原理為基礎(chǔ)，在固體處于高溫環(huán)境下，其內(nèi)部的粒子在進(jìn)行快速的無規(guī)則運(yùn)動(dòng)，同時(shí)具有很大的內(nèi)能，但是在其處于常溫時(shí)起內(nèi)部的粒子最穩(wěn)定，內(nèi)能達(dá)到了最小，模擬退火算法也是根據(jù)這種原理進(jìn)行設(shè)計(jì)的。

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

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

這種計(jì)算方法是依靠統(tǒng)計(jì)力學(xué)進(jìn)行展開。在統(tǒng)計(jì)力學(xué)角度中分析，處于不同結(jié)構(gòu)下的粒子有不同能量。不同的溫度下，粒子能量不同，粒子的運(yùn)動(dòng)及排列形式也有所不同。當(dāng)系統(tǒng)從高溫條件下逐步的降低溫度，直至完全的冷卻，晶體最終會(huì)處于一種低能的狀態(tài)^[14-15]。

假如我們對(duì)于材料的狀態(tài)采用粒子自身的能力進(jìn)行定義，Metropolis算法可以認(rèn)為退火過程采用了一個(gè)簡單的數(shù)學(xué)模型進(jìn)行表達(dá)。。這時(shí)我們假設(shè)E（i）為材料處在i狀態(tài)下的能量，材料在處于T溫度時(shí)，對(duì)于從i狀態(tài)變?yōu)?em>j狀態(tài)則可以表示為以下規(guī)律：

（1）當(dāng)E（i）小于等于E（j）時(shí)，狀態(tài)的變化用下面概率呈現(xiàn)：

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

（2）當(dāng)E（i）大于等于E（j）時(shí)，這種狀態(tài)轉(zhuǎn)換將被認(rèn)可。

綜上所述在一定溫度下，材料進(jìn)行了充分的轉(zhuǎn)換后，會(huì)達(dá)到一種熱平衡狀態(tài)。如果出現(xiàn)溫度降低的很大情況時(shí)，材料會(huì)以很大概率進(jìn)入最小能量狀態(tài)。

假設(shè)目標(biāo)函數(shù)為：

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

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

在下，x（k）的狀態(tài)決定下一個(gè)新的狀態(tài)x（k+1），與前面的狀態(tài)情況時(shí)無關(guān)的，這是一個(gè)典型馬爾可夫過程。如果存在緩慢下降溫度但是每一狀態(tài)下溫度卻又經(jīng)過多次轉(zhuǎn)換，致使在每個(gè)溫度狀態(tài)下都實(shí)現(xiàn)熱平衡，這時(shí)將以概率1的形式進(jìn)行全局的最優(yōu)解表達(dá)。綜上所述全局最優(yōu)解可以通過模擬退火算法進(jìn)行獲取。

3.3? 轉(zhuǎn)移概率公式

容易看出其轉(zhuǎn)移概率函數(shù)為指數(shù)函數(shù)，其自變量越大概率越大。首先不考慮常數(shù)系數(shù)K，K的作用僅限于人為調(diào)節(jié)，分兩方面來考慮這一轉(zhuǎn)移概率函數(shù)。

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

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

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

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

對(duì)于智能算法而言，算法的前期搜索范圍極大，當(dāng)算法達(dá)到后期時(shí)，會(huì)慢慢進(jìn)入收斂狀態(tài)，即可能達(dá)到了全局或局部最優(yōu)解，為此，本文從局部最優(yōu)和全局最優(yōu)兩方面來考慮改進(jìn)方法。

（1）局部最優(yōu)解的搜索方法

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

（2）全局最優(yōu)解的搜索方法

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

（3）本文轉(zhuǎn)移概率公式

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;

}

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

4 ?實(shí)驗(yàn)結(jié)果及分析

由于ABC算法的貪心算法找到的是局部最優(yōu)解的情況，全局最優(yōu)則是通過模擬退火算法獲取。對(duì)于模擬退火算法來講，它的基礎(chǔ)是metropolis算法。Metropolis算法又稱為metropolis抽樣，其核心思想是當(dāng)能量增加的時(shí)候以一定的概率接納而非一味拒絕。基于此思想應(yīng)用于基礎(chǔ)的ABC算法上，經(jīng)實(shí)驗(yàn)證明去的了較好的效果。傳統(tǒng)的ABC算法在算法的任何階段對(duì)于新解的產(chǎn)生，改變的步長都是一定的，本文通過引入模擬退火思想，使ABC在算法初期能以較大步長尋找新解，便于跳出局部最優(yōu);在算法后期以小概率接受步長較長的新解，便于收斂的同時(shí)也可以防止算法陷入局部最優(yōu)解。為了驗(yàn)證基于模擬退火算法的人工蜂群算法的優(yōu)化結(jié)果，本文對(duì)原始的三種優(yōu)化算法以及我們的優(yōu)化算法分別在三個(gè)不同的目標(biāo)函數(shù)下進(jìn)行200次的迭代，得到了如下實(shí)驗(yàn)結(jié)果：

4.1 ?第一組實(shí)驗(yàn)（目標(biāo)函數(shù)為Rosenbroke函數(shù)）

（1）第一種原始的新解產(chǎn)生函數(shù)（設(shè)置pp_ debug = 1），運(yùn)行結(jié)果如下：

Means of 200 runs： 9.808269901650287892

平均運(yùn)行時(shí)間=： 0.055567155000000 second

Min val：0.176049980984729904

（2）第二種改進(jìn)方法（pp_debug = 2），此轉(zhuǎn)移方法在第一種的基礎(chǔ)上增加了全 局更新的思想，有利于達(dá)到全局最優(yōu)解，但會(huì)陷入局部最優(yōu)解，運(yùn)行結(jié)果如下：

Means of 200 runs： 27.444346569494861399

平均運(yùn)行時(shí)間=： 0.056990765000000 second

Min val：0.062116211823108072

（3）第三種轉(zhuǎn)移方法（pp_debug = 3），次方法結(jié)合第一種和第二種，沒有本質(zhì)改 進(jìn)，效果介于第一種和第二種之間，運(yùn)行結(jié)果如下：

Means of 200 runs： 15.291687887025133818

平均運(yùn)行時(shí)間=： 0.057119505000000 second

Min val：0.104958787969900436

（4）本文在引入模擬退火算法之后（即pp_ debug = 5）時(shí)，運(yùn)行結(jié)果如下：

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

平均運(yùn)行時(shí)間=： 0.057688065000000 second

Min val：0.011360413050712590

由運(yùn)行結(jié)果可見解的平均值大大降低

4.2 ?第二組實(shí)驗(yàn)（目標(biāo)函數(shù)為Griewank函數(shù)）

4.3 ?第三組實(shí)驗(yàn)（目標(biāo)函數(shù)為Rastrigin函數(shù)）

經(jīng)過以上三組實(shí)驗(yàn)結(jié)果可以看出，本文基于模擬退火算法的改進(jìn)對(duì)三種不同優(yōu)化目標(biāo)函數(shù)下的結(jié)果均優(yōu)于前三種算法且十分有效，在時(shí)間復(fù)雜度不增加的同時(shí)對(duì)平均結(jié)果和最優(yōu)解的提升效果很大。

5 ?結(jié)論

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

參考文獻(xiàn)

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]. 計(jì)算機(jī)應(yīng)用研究， 2018， 35（05）： 1281-1286.

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

14. 裴小兵， 賈定芳. 基于模擬退火算法的城市物流多目標(biāo)配送車輛路徑優(yōu)化研究[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)， 2016， 46（2）： 105-113.

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