自適應隨機優化策略的改進人工蜂群算法

劉 鑫,楊霄鵬,姚 昆,蘇子萱,張衡陽

1(空軍工程大學 信息與導航學院,西安 710077) 2(中國人民解放軍 94042部隊，陜西 咸陽 713800)

1 引 言

隨著科學技術的進步,最優化問題被廣泛運用到數學規劃、計算機技術以及工程實踐中.通過對生物群體行為進行仿真和建模,并以此解決最優化問題已成為當前一個熱門研究領域[1].其中在該領域中較為成熟是Dorgo等人提出的蟻群算法(Ant Colony Optimization,ACO)[2]和Kennedy等人提出的粒子群算法(Particle Swarm Optimization,PSO)[3].

近年來,由Karaboga提出的人工蜂群算法(Artificial Bee Colony,ABC)作為一種新的隨機型搜索方法已成功應用于函數的優化問題[4].該算法主要通過模擬蜂群中不同類型的蜜蜂,根據其各自分工不同進行智能采蜜,同時在不同種群之間交換蜜源信息直到找到最優蜜源.文獻[5]和[6]通過五個基本函數對ABC算法的性能進行了驗證分析,實驗結果表明ABC算法與遺傳算法(Genetic Algorithm,GA)、粒子群算法(Particle Swarm Optimization,PSO)以及差分進化算法(Differential Evolutionary,DE)一樣具有良好的優化能力.但是,實驗中也暴露了ABC算法存在收斂速度慢和容易陷入“早熟”的不足.針對這一問題,文獻[1]通過將ABC算法與DE算法算法相結合,并在迭代中引入淘汰規則的方法克服了ABC算法的“早熟”現象;文獻[7]運用Nelder-Mean法使ABC算法的局部搜索能力得到了改進,并將其應用在混凝土重力壩動力材料參數識別問題,在建立基于不完全模態測試數據動力材料參數識別優化反演模型中取得了較好的效果.文獻[8,9]在ABC算法中加入混沌思想,利用混沌運動的隨機性、遍歷性等特點提高了算法的全局搜索能力.

為提高ABC算法的收斂速度以及解決在算法后期容易陷入局部最優解的問題,本文在重點參考文獻[1]及文獻[10,11]的基礎上,提出了一種基于自適應隨機優化策略的改進算法,通過利用自適應思想與雙向隨機優化機制以期改善算法的局部搜索能力,同時將粒子群算法引入到改進算法的初始階段以期提高算法的收斂速度.

2 人工蜂群算法原理

人工蜂群算法是基于蜂群迭代來完成尋優過程的一種隨機搜索算法[4].在ABC算法中,人工蜂群根據各自分工可分為采蜜蜂、觀察蜂和偵查蜂三種類型.通常采蜜蜂和觀察蜂各占蜂群總數的一半,每一個采蜜蜂僅對應一個蜜源工作,且蜜源Xi為Q維向量.算法初始化時首先隨機生成M個初始解,之后進行對最優解的搜索,其具體搜索過程如下:1)采蜜蜂對蜜源進行搜索并記憶蜜源的花蜜量,即問題解的質量(適應度);2)采蜜蜂將蜜源信息傳遞給觀察蜂,觀察蜂根據獲得的蜜源信息通過判斷收益率對蜜源進行選擇,進而改變記憶位置;3)當蜜源因蜂蜜開采完而被放棄時,產生偵查蜂并且由其搜索新的蜜源來替代舊蜜源.

在算法中,為了根據記憶位置Xi產生一個候選位置Vi,采用下式進行更新:

(1)

(2)

其中S為蜜源總數,Xi為第i個蜜源,fit(Xi)表示蜜源Xi的適應度值,i∈P{1,2,…,S}.

假設采蜜蜂和觀察蜂經過limit次循環搜索更新之后仍不能改進蜜源Xi的適應度,那么該該位置的采蜜蜂成為偵查蜂,同時蜜源Xi的位置將被改變.limit作為搜索次數,是ABC算法中一個非常重要的控制參數,用來控制偵查蜂的選擇.偵查蜂發現新位置并對Xi進行替換的操作如下:

(3)

其中n為Q維向量的某個分量.

由于ABC算法中蜜源Xi的位置無法隨著算法的進行而發生改變,而是當解的質量無法得到優化時經過limit次循環搜索之后才能對個別蜜源位置進行更新,存在算法效率低和收斂速度慢的缺陷.此外,算法依靠不同類型蜜蜂之間的交流合作來進行尋優,并且蜜蜂擔任的角色只有在特定的條件下才會發生轉變.假如其中任意一種類型的蜜蜂的活動受到限制,使其角色發生轉變的條件將無法滿足,進而造成算法陷入局部最優解.因此,針對人工蜂群算法存在的以上兩點缺陷對其進行改進.

3 改進人工蜂群算法

為提高ABC算法的收斂速度以及解決在算法后期容易陷入局部最優解的問題,在上述人工蜂群算法原理的基礎上,提出了一種基于自適應隨機優化策略的人工蜂群改進算法.該策略將加權粒子群算法與ABC算法進行融合,利用自適應思想及雙向隨機優化機制對算法的收斂速度和局部搜索能力加以改善,以期提高該算法的尋優性能.

3.1 粒子群算法

Kennedy和Eberhart[10]在1995年提出了基本的粒子群算法后,Yuhui Shi和Eberhart[11]在基本粒子群算法的基礎上添加了一個慣性因子w,式(4)和式(5)就是標準PSO算法的更新公式.

(4)

(5)

其中v表示粒子的速度,x表示粒子的位置,i表示第i個粒子,w表示慣性因子,c1和c2都是正的加速因子,而r1,r2都是[0,1]之間均勻分布的隨機數,Pi表示單個粒子在歷史上已經尋到的最優位置,Pg表示整個種群所已尋到的最優位置,t表示第t次迭代.

文獻[11]中提出的粒子群算法的具體尋優過程的基本流程如下:

Step1.對粒子群進行初始化,完成對m個粒子的初始位置和初始速度的隨機設定,并計算出所有m個粒子的適應度值;

Step2.對每個粒子,將它的當前位置的適應度值和它經歷過的最好位置Pi的適應度值Pibest進行比較,如果當前位置比Pibest好,更新Pi和Pibest,否則保持Pibest不變;

Step3.將每個粒子當前位置的適應度值與群體中所有粒子經歷過的最好位置Pg的適應度值Pgbest進行比較,如果當前位置比Pgbest好,更新Pg和Pgbest,否則保持Pgbest不變;

Step4.根據式(4)和式(5)調整粒子的速度和位置;

Step5.如果達到結束條件,則結束;否則轉到Step 2.

3.2 自適應隨機優化策略

3.2.1 自適應蜂群位置更新公式

在利用公式(1)進行蜜源Xi位置更新時,φij的取值越大越有利于算法跳出局部極小值點,同理,φij的取值越小算法的收斂速度越快[12].在全局搜索過程中,通過在算法的初期取較大的φij值以提高算法的探索能力,進而得到較優的蜜源,使其搜索精度得到提高;而在算法后期取較小的φij值,在提高算法的局部搜索能力的同時使其收斂速度加快.因此將φij設計為迭代次數的函數,且取值隨著迭代次數的增加逐漸減小,將φij定義如下:

(6)

其中,k的含義與公式(1)相同,wmax為初始權重、wmin為終止權重,Cmax為最大迭代次數,C為當前迭代次數.則公式(1)重新定義為

(7)

由此可以達到引導蜜源位置的搜索趨勢的目的,并針對算法本身隨機性強、收斂速度慢的缺陷進行了改進.

3.2.2 雙向隨機優化機制

在ABC算法計算蜜源的適應度值時,觀察蜂在對Xi周圍的蜜源進行比較之后后選擇其中一個蜜源,選擇的臨近蜜源位置的計算公式如下:

Xi(C+1)=Xi(C)+Δi(C)

(8)

其中Δi(C)是Xi附近隨機產生的遞進步長,C表示當前的迭代次數,若經過適應度值計算后得到fit(Xi(C+1))>fit(Xi(C)),則觀察蜂選擇Xi(C+1);否則維持不變.若在限定循環次數后蜜源質量仍沒有提高,則放棄該位置,采蜜蜂根據式(3)變成偵查蜂.

采用上述方法存在一定的缺陷,即每次循環僅對單一方向的蜜源進行搜索,觀察蜂的活動僅在鄰域內的一個方向上進行,同時也使其他類型蜜蜂的活動受到了限制,無法達到使角色發生轉變的條件,因此容易陷入局部最優解的情況.文獻[13]在研究動態網絡環境下搜索命中率及搜索成功率的過程中提出了一種雙向隨機漫步搜索機制,有效的提高了網絡的搜索特性.受到這一思想的啟發,本文將該機制改進后引入到本文對搜索蜜源的方向加以改進:設l為搜索步長,若

fit(Xi+l)

(9)

則

Xi=Xi+l

(10)

若

fit(Xi-l)

(11)

則

Xi=Xi-l

(12)

否則Xi保持不變.

改進后的蜜源搜索機制下,觀察蜂可對當前蜜源Xi臨近位置的其他蜜源進行雙向搜索,通過比較Xi與Xi+l、Xi與Xi-l的適應度值的大小關系對蜜源進行重新選擇.該種搜索機制不僅大大提高了算法的搜索效率,同時去除了對蜜蜂活動方向和范圍的限制,使不同類型蜜蜂間的交流合作更加密切,克服了傳統算法后期容易陷入局部最優解的問題.

3.2.3 粒子群算法實現算法初始化

在傳統蜂群算法中存在收斂速度較慢的缺點,而粒子群算法則具有較收斂速度快的特點,利用這一特性,本文將粒子群算法引入到改進算法的初始化階段,即首先利用粒子群算法通過較少次數的迭代產生出全局最優解,而后根據這一全局最優解在該解附近隨機產生初始蜜源位置,之后再進行人工蜂群算法蜜源位置的尋優過程.不論粒子群產生的是全局最優解還是局部最優解,都通過改進的ABC算法進行雙向鄰域搜索,當蜜源Xi的位置不發生改變時改進的人工蜂群算法切換為粒子群進行二次初始化.

改進后ABC算法的初始化蜜源位置如下:

(13)

因粒子群算法和傳統人工蜂群算法均存在易收斂于局部最優解的缺陷,故將兩種算法進行融合,有效地平衡了全局搜索和局部搜索.

人工蜂群算法通過位置信息進行搜索,并最終得到最優蜜源,因此蜜源的初始位置、領域搜索的范圍和搜索機制就顯得格外關鍵.利用粒子群算法收斂速度快的特性對算法進行初始化,通過較少的迭代得到全局最優解作為初始蜜源位置.

StartStep1．人工蜂群算法與粒子群算法的相關初始參數進行設置，根據式(4)和式(5)隨機生成M個粒子的初始速度和初始位置；Step2．通過計算每個粒子的適應度值并比較，在循環次數c內確定最優解Pg，best；Step3．采蜜蜂按式(6)和(7)搜索一個新的蜜源，并對該蜜源位置的適應度進行計算，如果新位置的適應度值優于原來的位置，則用新位置替換原位置；Step4．觀察蜂根據蜜源的花蜜量依概率公式(2)選擇一個蜜源位置，并根據雙向隨機優化機制隨機產生一個新的位置，并對該位置進行評價；Step5．若存在放棄的蜜源，該處的采蜜蜂根據式(3)變成偵查蜂；Step6．記錄當前的最優位置及適應度值．End

若粒子群算法在迭代過程中產生局部最優解,則將該最優解作為新增鄰域點,從而加速了偵查蜂的搜索,在該鄰域內采用雙向隨機優化機制以l為步長進行搜索,若蜜源Xi保持保持不變,則跳出該鄰域,再對人工蜂群算法進行初始化,進而最終使得蜂群以最快速度找到最優蜜源.

4 仿真實驗

本文合理選擇三個基準函數作為樣本,通過實驗分別驗證了算法的有效性、普遍適用性以及相應的性能指標,并且將實驗結果同傳統ABC算法進行比較,文獻[1]提出的混合人工蜂群算法(HABC)性能進行比較.

1)Rastrigin函數

2)Griewank函數

3)Sphere函數

本文算法的參數設置如下:對本文改進算法SRABC算法,種群規模S=60,limit=60,粒子群數為60,粒子群算法循環次數c=100;將傳統人工蜂群算法的種群規模S和循環搜索次數limit設置為60,規定算法做多完成2500此迭代,且每個算法都獨立且完整實現30次.表1至表3分別表示Rastrigin函數、Griewank函數和Sphere函數在維數等于30和60的情況下,且依據以上參數設定在30次運行后所得到的平均值、方差.最大值和最小值,并在表中對結果進行了對比.

對表1和表2數據進行對比可知,改進后的SRABC算法在不同維數下仿真精度都要明顯優于ABC算法及HABC算法對這兩個函數的仿真精度.尤其在維數等于60時,針對Rastrigin函數算法可以快速收斂到0.根據表3數據可知,對于單峰函數Sphere,SRABC算法在不同維數下對此函數的優化結果雖然沒有很大程度的提高,但仍優于標準ABC算法及HABC算法的優化結果.因此,改進算法不僅保持了原有算法的特性,在計算精度和穩定性方面較傳統算法以及HABC算法都有明顯提高.

表1 Rastrigin函數的測試結果
Table 1 Test results of Rastrigin function

算法維數平均值方差最大值最小值ABCHABCSRABC302．58239E?0091．03788E?0085．65922E?0081．13687E?0121．13687E?0121．64169E?0128．15703E?0121．12578E?0151．32635E?0141．78719E?145．68434E?0140ABCHABCSRABC600．1678950．4582411．990331．72463E?0104．56788E?0081．53871E?0078．25186E?0071．3074E?0111．21393E?0102．62695E?0101．2559E?0091．7053E?013

表2 Griewank函數的測試結果
Table 2 Test results of Griewank function

算法維數平均值方差最大值最小值ABCHABCSRABC 302．18149E?0129．27583E?0124．90501E?0119．99201E?0164．08007E?0149．89653E?0144．99267E?0134．44089E?0166，25426E0161．41953E?0157．54952E?0150ABCHABCSRABC602．79554E?0138．89572E?0134．85578E?0122．77556E?0151．4011E?0132．87342E?0131．20581E?0122．33147E?0151．72825E?0151．94662E?0158．54872E?0151．11022E?016

表3 Sphere函數的測試結果
Table 3 Test results of Sphere function

算法維數平均值方差最大值最小值ABCHABCSRABC301．13714E?0152．97144E?0161．79207E?0155．46909E?0165．55572E?0169．00306E0177．23074E?0164．09377E?0162．95155E?0165．79213E?174．61564E?0161．80046E?016ABCHABCSRABC602．34037E?0141．82907E?0147．64184E?0144．13668E?0153．6088E?0151．45665E?0158．65843E?0151．87149E?0158．15309E?0161．32347E?0169．89696E?0164．72298E?016

圖1 Rastrigin函數不同維數對比Fig.1 Comparison of different dimensions for Rastrigin function

圖1至圖3則分別給出了每個函數的維數為30和60時對ABC算法、HABC算法以及SRABC算法尋優迭代過程曲線圖,為了更清晰地顯示結果,x軸表示迭代次數,y軸采用對數坐標表示最優值.

圖2 Griewank函數不同維數對比Fig.2 Comparison of different dimensions for Griewank function

由圖1～圖3可知,在迭代次數不發生變化時,在不同維數下,三個基準函數對于傳統人工蜂群算法的最優解在迭代次數較大是表現出趨向于不發生變化,HABC算法相比較ABC算法有一定的改善,而SRABC算法在尋優過程中性能改善較為明顯.根據圖1、圖2可知,改進后的算法通過自適應隨機優化策略可以在迭代次數不發生改變的情況下,能夠使Rastrigin函數和Griewank函數在算法的初始階段近似地依線性快速收斂至最優解,且收斂速度明顯由于其他兩種算法.由圖3可看出Sphere函數作為基準函數時SRABC算法能夠快速遞減收斂到最優解,由于在算法初期采用了粒子群算法初步尋優的結果作為SRABC算法的初始值,而使搜索空間大大縮小,進而提高了算法的收斂速度.

圖3 Sphere函數不同維數對比Fig.3 Comparison of different dimensions for Sphere function

由此可知,改進后的人工蜂群算法能夠依據自適應隨機優化策略和雙向搜索機制使算法實現快速收斂,提高全過程的尋優能力,極大地改善了算法的結果精度,使算法能夠有效地避免“早熟”現象的產生.

6 結 語

經過改進之后的人工蜂群算法是一種先進的群體智能優化算法,算法易于實現且具有操作簡單的特點,同時減少了控制參數.本文針對ABC算法局部搜索能力較弱、搜索精度不高及收斂速度較慢的缺點,在算法開始階段引入粒子群算法對蜂群進行初始化,同時在自適應思想及雙向隨機優化機制的基礎上,提出了基于雙向隨機優化策略的改進算法,有效的改善了尋優過程中隨機性過強及搜索方向單一的缺陷,在一定程度上避免了算法陷入局部最優的問題.通過對比傳統算法、文獻[1]提出的HABC算法及本文改進算法,并通過三個不同基準函數對算法性能進行驗證,結果表明本文算法具有普遍有效性,同時在提高算法收斂速度的基礎上,有效的改善了算法的尋優能力.

[1] Gao Wei-feng,Liu San-yang,Jiang Fei,et al.Hybrid artificial bee colony algorithm[J].Systems Engineering and Electronics,2011,33(5):1167-1171.

[2] Dorgo M,Maniezzo V,Golorni A.The ants system:optimization by a colony of cooperating agants [J].IEEE Transactions on System,Man and Cybernetics PartB:Cybernetics,1996,26(1):29-41.

[3] Kennedy J,Ebethart R.Particle swarm optimization [C].Proceeding of IEEE International Conference on Neural Networks,Piscataway,NJ:IEEE Computer Scoiety,1995:1942-1948.

[4] Karaboga D.An idea based on honey bee swarm for numerical optimization,technical report-TR06 [R].Computer Engineering Department,Engineering Faculty,Erciyes University,2005.

[5] Karaboga D,Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm [J].Journal of Global Optimization,2007,39(3):459-471.

[6] Karaboga D,Basturk B.On the performance of artificial bee colony(ABC)algorithm [J].Applied Soft Computing,2008,8(1):687-697.

[7] Kang Fei,Li Jun-jie,Xu Qing.Hybrid simplex artificial bee colony algorithm and its application in material dynamic parameter back analysis of concrete dams [J].Journal of Hydraulic Engineer,2009,40(6):736-742.

[8] Alatas B.Chaotic Bee colony algorithms for global numerical optimization [J].Expert Systems with Applications,2010,37(8):535-541.

[9] Xu C F,Dun H B,Liu F.Chaotic artificial bee colony approach to uninhabited combat air vehicle path planning [J].Aerospace Science and Technology,2010,14(8):535-541.

[10] Kennedy J,Eberhart R C.Particle swarm optimization [C].Proc.of IEEE International Conference on Neural Networks,Perth,Australia,1995:1942-1948.

[11] Shi Y,Eberhart R C.A modified particle swarm optimizer [C].Proc.of IEEE World Congress on Evolutionary Computation,Anchorage,Alaska,USA,May,1998:69-73.

[12] Lei Xiu-juan,Huang Xu,Zhang Ai-dong.Improved artificial bee colony algorithm and its application in data clustering [C].Proc.of 2010 IEEE Fifth International Conference on Bio-Inspired Computing:Theories and Applications,2010:514-521.

[13] Ma Wen-ming,Meng Xiang-wu,Zhang Yu-jie.Bidirectional random walk search mechanism for unseructured P2P network[J].Journal of Software,2012,23(4):894-911.

[14] Yang Sheng-pei,Li Zhong-yang,Cheng Zhong-yang.Particle swarm optimization algorithm based on chaotic searching and people crossover operator[J].Computer Simulation,2016,33(6):218-222.

[15] Ma Can,Liu Jian,Yu Fang-ping.Research on cuckoo algorithm with simulated annealing[J].Journal of Chinese Computer Systems,2016,37(9):2029-2034.

[16] Li Yan-cang,Peng Yang.Improved artificial bee colony algorithm based on information entropy[J].Control and Decision,2015,30(6):1121-1125.

[17] Zhu Bing-lian,Zhu Fang-fang,Duan Qing-yan,et al.An improved spectrum allocation algorithm using multi-strategy discrete artificial bee colony technology[J].Journal of Xi′an Jiaotong University,2016,50(2):20-25.

[18] Naeem M,Anpalagan A,Jaseeemuddin M,et al.Resource allocation techniques in cooperative cognitive radio networks[J].IEEE Communications Surveys & Tutorials,2014,16(3):729-744.

[19] Ren Kai-jun,Deng Ke-feng,Liu Shao-wei,et al.Adaptive artificial bee colony optimization for parameter estimation of chaotic systems[J].Journal of National Univ-ersity of Defense Technology,2015,37(5):135-140.

[20] Ouyang A,Tang Z,Li L,et al.Estimating parameters of muskingum model using an adaptive hybrid P-SO algorithm[J].International Journal of Pattern Recogniti-on and Artificial Intelligence,2014,28(1):1-29.

附中文參考文獻：

[1] 高衛峰,劉三陽,姜 飛,等.混合人工蜂群算法[J].系統工程與電子技術,2011,33(5):1167-1171.

[7] 康 飛,李俊杰,許 青.混合蜂群算法及其在混凝土壩動力材料參數反演中的應用[J].水利學報,2009,40(6):736-742.

[13] 馬文明,孟祥武,張玉潔.面向非結構化P2P網絡的雙向隨機漫步搜索機制[J].軟件學報,2012,23(4):894-911.

[14] 楊勝培,李仲陽,陳中樣.基于混沌搜索與種群交叉的粒子群優化算法[J].計算機仿真,2016,33(6):218-222.

[15] 馬 燦,劉 堅,余方平,等.混合模擬退火的布谷鳥算法研究[J].小型微型計算機系統,2016,37(9):2029-2034.

[16] 李彥蒼,彭 陽.基于信息熵的改進人工蜂群算法[J].控制與決策,2015,30(6):1121-1125.

[17] 朱冰蓮,朱方方,段青言,等.采用多策略離散人工蜂群的改進頻譜分配算法[J].西安交通大學學報,2016,50(2):20-25.

[19] 任開軍,鄧科峰,劉少偉,等.自適應人工蜂群優化的混沌系統參數估計[J].國防科技大學學報,2015,37(5):135-140.