基于復數編碼的多策略人工蜂群算法

單 嫻,杜學東

(1.中國石油大學(華東)理學院,山東青島266580;2.山東科技大學信息科學與工程學院,山東青島266510)

1 引 言

隨著社會經濟和科學技術的不斷發展,在工程技術、國防科技、經濟管理和制造業等多個領域中涌現出大量的復雜優化問題.由于這些實際問題往往具有數據規模大、信息不確定等特點,在有限的時間內運用傳統的精確優化方法已經難以解決.因此,設計高效、實用的優化算法成為科研工作人員研究的熱點.通過模擬自然界中生物行為特征而衍生出的啟發式優化算法應運而生.

目前常用的啟發式優化智能算法包括以遺傳算法[1]、差分進化算法[2]和分布估計算法[3]為代表的進化算法,和模擬動物行為特征的粒子群算法[4]、蟻群算法[5]、魚群算法[6]、猴群算法[7]和人工蜂群算法[8]等群體智能算法.近年來,涌現出一批新的模擬人類行為特征的群體智能算法,如SBA算法[9]、TLBA算法[10]和JOA算法[11]等.由于這些智能算法不需要梯度信息,而且不要求優化函數必須滿足凸條件,因而在復雜優化問題的求解中顯示出強大的優勢.如何通過對各種智能算法進行改進改善其解決優化問題的能力,成為研究者們廣泛關注的問題.

人工蜂群算法(artificial bee colony algorithm,ABC)是2005年由Karaboga[8,12]基于蜜蜂采蜜過程中的分工機制和群體智能行為提出的一種啟發式群體智能算法.該算法是一種并行直接搜索方法,計算過程中不需要任何梯度信息,算法結構簡單,易于在計算機上實現,控制參數較少,具有較好的收斂性和穩定性.因此,自提出以來便被廣泛應用至參數優化[13]、聚類分析[14]與生產調度[15]等多個領域,解決了國內外現代工程領域的多種復雜優化問題[16].

國內外學者針對人工蜂群算法展開多個角度的研究,研究的內容主要分為兩個方面.

1)通過改進搜索策略提高算法搜索效率.

人工蜂群算法主要由雇傭蜂搜索、觀察蜂搜索和偵察蜂搜索三個階段完成.算法性能的優劣依賴于各個階段的搜索方程.Zhu等[17]將全局最優解的信息融入搜索方程,提出受gbest引導的ABC算法(GABC).Banharnsakun等[18]考慮將目前最優解(best-so-far)設置為引導項,提出改進的ABC算法.Gao等[19]受DE/best/1和DE/best/2兩種變異策略的啟發,運用最優解的信息,提出ABC/best/1和ABC/best/2兩種改進的搜索策略,有效地提高了算法的開發能力,但與ABC/rand/1相比,則顯得探索能力不足.為此,Gao等[20]考慮將ABC/rand/1和ABC/best/1結合,并引入參數M,將兩種搜索策略優勢互補,更好地平衡了探索能力和開發能力.Li等[21]受PSO算法的啟示,在搜索方程中加入由適應度值確定的慣性權重和加速系數.Gao等[22]對搜索公式進行改進,將正交學習策略引入搜索過程,提出CABC算法.Gao等[23]將種群劃分為多個子種群,運用各個子種群內部及子種群之間的信息交換進行搜索,提出基于信息學習的改進ABC算法.

從標準ABC算法和上述改進算法中可以看出,不同的引導向量和搜索方程能夠對搜索方向產生不同的影響,進而影響算法的收斂速度和計算精度.各種搜索策略在不同類型優化問題中的表現各異,即使對應同一類型優化問題,對于不同規模和不同求解階段求解效率也略有不同.

2)將人工蜂群算法與其他優化算法相結合改善算法性能.

Kang等[24-26]將Nelder-Mead單形搜索機制、Rosenbrock方法和Hooke-Jeeves方法引入ABC算法,提出混合的單形ABC算法、Rosenbrock-ABC算法和HABC算法.Gao等[27]運用傳統的Powell方法作為局部搜索算子對ABC算法進行改進,提高了ABC算法的整體性能.Chen等[28]將模擬退火算法嵌入搜索過程,改善了算法的搜索能力.Mustafa等[29]提出基于PSO和ABC的混合算法.上述算法的改進過程中,運用其他優化算法的特點,將局部搜索與全局搜索有機結合,實現開發能力與勘探能力的均衡.

盡管上述改進方法在一定程度上改善了ABC算法的性能,但這些算法在提高精度,改進效率和避免過早收斂等方面仍具有較大的改進空間.目前對蜂群算法的研究中,普遍考慮采用一種搜索策略展開尋優,而不同的搜索策略在不同問題的各個求解階段尋優效果存在明顯差異,現有研究尚不能為不同優化問題如何選擇最佳策略提供有價值的參考.

為此,本文考慮種群個體編碼方式和搜索策略對算法效率的影響,提出基于復數編碼的多策略人工蜂群算法.利用復數編碼方法維持解集的多樣性,增強種群個體信息容量.并建立搜索策略知識庫,在搜索過程中由種群個體依據自身獲取信息自適應選擇搜索策略,進而提高算法的搜索能力.最后,采用測試函數對算法性能進行比較和分析.

2 基本人工蜂群算法

人工蜂群由雇傭蜂、觀察蜂和偵察蜂三部分構成.其中,雇傭蜂負責搜索食物源,并將獲取的食物源信息以搖擺舞的形式傳遞給觀察蜂;觀察蜂以一定的概率選擇食物源,或者在食物源附近繼續搜索新的食物源;若某個雇傭蜂獲得的食物源經過若干次搜索后仍然沒有得到改善,則該雇傭蜂會放棄該食物源,并轉化為偵察蜂重新進行搜索.

食物源的數目與雇傭蜂的數目相同,即等于種群規模SN.一個食物源的位置代表優化問題的一個候選解,稱為種群個體,用Xi=(xi1,xi2,...,xiD)表示,其中D為優化問題的維數,i=1,2,...,SN.食物源的花蜜量對應解的適應度值.

根據蜂群的構成,將整個搜索過程分為四個階段:

1)種群個體初始化階段

初始食物源在各分量邊界范圍內由式(1)隨機產生

其中j=1,2,...,D,xij為第i個食物源的第j個分量,表示第j個分量的下界和上界,?為[0,1]之間的隨機數.

2)雇傭蜂搜索階段

雇傭蜂在食物源位置附近隨機產生新的食物源Vi=(vi1,vi2,...,viD),搜索方程為

其中j和k是隨機選擇的下標,滿足j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.φij為[-1,1]之間的隨機數.

3)觀察蜂選擇階段

觀察蜂從雇傭蜂處獲取食物源信息,運用適應度函數f對第i個食物源進行評估,并根據輪盤賭和貪婪策略選擇食物源.當選擇概率pi＞s時,觀察蜂選擇該食物源;否則,根據式(2)重新搜索新的食物源,并對新食物源進行評估.其中s為[0,1]之間的隨機數,選擇概率

其中fitnessi為第i個食物源的適應度值.

4)偵察蜂搜索階段

若某個食物源經過limit次循環后仍然未被更新,則該食物源將被放棄,發現該食物源的雇傭蜂轉化為偵察蜂,并且由式(1)隨機產生一個新的食物源.

3 改進的人工蜂群算法

3.1 基于復數編碼的人工蜂群算法

傳統智能優化算法中,種群個體的編碼采用二進制編碼或者實數編碼,這使得每個種群個體包含的信息在一定程度上受到限制.受神經網絡權值表達的復數編碼方法啟示[30],考慮用雙倍體表示每個食物源個體,從而將個體信息量翻倍,增加了種群的多樣性,更加充分地利用到搜索空間的信息.

對于D維的優化問題,食物源個體Y的第j個分量對應一個復數,

其中i是虛數單位,j=1,2,...,D,Rj表示第j個分量的實部,Ij表示第j個分量的虛部.

3.1.1 種群個體的初始化

設優化問題第j個分量的取值范圍為[Aj,Bj],隨機產生D個模和D個幅角

第i個個體的第j個分量對應的雙倍體為(Rj,Ij).由于

可得

由此產生SN×D個雙倍體,即SN個食物源個體,每個個體包含D個雙倍體.

3.1.2 種群個體的更新

與傳統編碼方式不同的是,復數編碼個體的更新需要對實部和虛部并行進行,從而在增加種群多樣性的同時,還可以提高算法的運行效率.

1)復數編碼的實部更新

其中j和k是隨機選擇的下標,滿足j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.Rij為第i個個體第j個分量的實部,φij為[-1,1]之間的隨機數.

2)復數編碼的虛部更新

其中j和k是隨機選擇的下標,滿足j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.Iij為第i個個體的第j個分量的虛部,φij為[-1,1]之間的隨機數.

3.1.3 適應度函數的計算方法

由于每個個體的各個分量都是由實部和虛部構成,需要先將各個分量的編碼由二維空間確定的復數轉化到一維空間確定的實數,然后再計算相應的適應度.具體的操作過程可以描述為

1)由復數的模確定實數值

2)由幅角確定實數變量

其中xij表示轉換后的實數自變量.然后得到新個體的適應度值,并對其進行評價,若優于當前個體的適應度值,則進行替換,否則進行下一次迭代.

3.2 多策略人工蜂群算法

已有的人工蜂群算法中,對雇傭蜂和觀察蜂均采用某一種搜索策略獲取食物源.僅采用一種搜索策略,

每次只產生一個新的個體,無法兼顧搜索的多樣性.而且,某一種搜索策略可能適用于一類或幾類優化問題,而對其他的優化問題則無法得到理想的求解結果.不同的搜索策略對于同一優化問題,獲得的結果也可能存在較大的差異.為解決單一搜索策略可能造成的不足,考慮采用多種搜索策略自適應選擇的方式對食物源進行搜索.

論文設計一種自適應搜索策略調整方法.首先建立產生食物源個體的搜索策略知識庫,然后對應每一次搜索,從知識庫中選取三種搜索策略產生三個新的個體,并從三個候選個體中選取適應度最優者進入下一代種群.

策略1個體Xi從自身鄰域范圍內選取個體Xk,根據自身信息和個體Xk的信息進行更新,搜索方程為

其中j和k是隨機選擇的下標,j∈{1,2,...,D},k∈{1,2,...,SN},且k≠i.

策略2個體Xi從自身鄰域范圍內選取兩個個體Xk1和Xk2,根據自身信息和個體Xk1、Xk2的信息進行更新,搜索方程為

其中j,k1和k2是隨機選擇的下標,j∈{1,2,...,D},k1∈{1,2,...,SN},k2∈{1,2,...,SN},且k1?=i,k2?=i,k1?=k2.

策略3個體Xi從自身鄰域范圍內選取兩個個體Xk1和Xk2,根據當前種群中最優個體Xbest的信息和個體Xk1,Xk2的信息進行更新,搜索方程為

其中j,k1和k2是隨機選擇的下標,j∈{1,2,...,D},k1∈{1,2,...,SN},k2∈{1,2,...,SN},k1?=i,k2?=i,k1?=k2.

其中策略1適用于搜索范圍較小,食物源分布較為密集的情形;策略2在策略1的基礎上,局部搜索能力有所改善;策略3適用于搜索范圍較大,食物源分布較為分散的情形.

3.3 改進人工蜂群算法流程

基于復數編碼方式和多種搜索策略,提出改進的人工蜂群算法(簡稱CCABC算法).算法流程如下:

步驟1參數設定.設置種群個體的數量SN、個體更新限制次數limit和最大迭代次數MaxCycle;

步驟2初始化種群.采用復數編碼方法產生初始種群,并計算種群個體的適應度值,記錄當前最優個體Xbest的相關信息;

步驟3雇傭蜂運用式(10)、式(11)和式(14)～式(16)對個體Xi進行更新,產生新個體的實部和虛部,并根據式(12)和式(13)轉換為相應實數,得到備選個體V1,V2和V3.計算三個個體的適應度值,選擇最優個體Vi.若f(Vi)＜f(Xi),則Xi←Vi,triali←0;否則,triali←triali+1;

步驟4按照式(3)計算個體的選擇概率.觀察蜂依據輪盤賭方法選擇個體Xi,并利用式(10)～式(16)進行更新,得到備選個體V1、V2和V3.計算三個個體的適應度值,選擇最優個體Vi.將Vi與Xi進行比較,保留較優個體;

步驟5若triali＞limit,雇傭蜂轉化為偵察蜂,并依據復數編碼方法產生新個體Sol取代原個體Xi.

步驟6計算當前種群的適應度值,并記錄最優個體Xbest的相關信息.迭代次數iter←iter+1;

步驟7判斷是否達到終止條件或最大迭代次數,若滿足,則返回最優個體和最優解,停止迭代;否則,繼續執行步驟3.

4 實驗仿真與分析

4.1 算法測試環境

為驗證算法的有效性,對15個基準測試函數[19,20]進行仿真實驗.其中f1～f6是單峰函數,f7是不連續的階梯函數,f8～f12是多峰多極值函數,f13～f15是轉移的多峰多極值函數.表1給出了15個測試函數的名稱、維數、搜索空間范圍和最優值.

表1 測試函數說明Table 1 Benchmark functions used in experiments

對所有的測試函數,維數D和種群規模SN分別設置為30和50,最大迭代次數MaxCycle=1 000,閾值limit=1 000.為了說明算法的有效性和優越性,運用MATLAB編程并進行仿真.將算法的計算結果與單一搜索策略ABC/rand/1和ABC/best/1進行比較,每個測試函數在不同算法上均獨立運行30次,統計其最優值運算結果的均值Mean和標準方差SD.均值能夠反映算法所能達到的精度,標準方差則可以反映算法的穩定性.結果如表2所示.

表2 CCABC算法,ABC/rand/1算法和ABC/best/1算法性能比較Table 2 Result comparisons of CCABC,ABC/rand/1 and ABC/best/1

從表2中可以看出,CCABC算法在15個函數上的性能都要明顯優于實數編碼單一策略的ABC算法.具體而言,在f6,f7和f12～f15上,CCABC算法和ABC/best/1均取得全局最優值;而在函數f8上,僅有CCABC算法取得了全局最優值.對于函數f1～f5和f9～f11,CCABC算法的計算精度與ABC/rand/1算法、ABC/best/1算法相比均有提高.因此,與實數編碼單一策略的ABC/rand/1算法和ABC/best/1算法相比,CCABC在性能上具有明顯的改善,能夠獲取更高的數值精度.

為了進一步直觀展示出CCABC算法的尋優效果,將ABC/best/1算法和CCABC算法對兩種測試函數的收斂曲線進行比較,如圖1和圖2所示.

在函數f3的進化過程中,算法均以較快的速度收斂.由函數f9進化過程曲線可以看出,在CCABC算法的運行前期,算法的搜索速度較快,每一代的最優值隨迭代次數增加下降較為明顯;隨著進化的進行,適應度函數曲線變化逐漸平緩,種群個體函數最優值向測試函數的最優解靠近.與ABC/best/1算法相比,CCABC算法在算法的計算精度和收斂速度上均有大幅度的提高.

圖1 函數f3收斂性能比較Fig.1 Convergence performance of different ABCs on f3

圖2 函數f9收斂性能比較Fig.2 Convergence performance of different ABCs on f9

表3 CCABC算法與MPEDE算法、HCLPSO算法和JOA算法的性能比較Table 3 Result comparisons of CCABC,MPEDE,HCLPSO and JOA

為評估CCABC算法在求解全局優化問題上的性能,選取10個測試函數,將CCABC算法與近期相關文獻提出的三種優化算法(MPEDE算法[31],HCLPSO算法[32]和JOA算法[11])的計算結果進行對比.表3給出每種算法在每個測試函數上的最優解的均值和標準方差.從表3中可以看出,CCABC算法在8個測試函數上取得了最佳性能.在函數f9上得到的最優值略差于MPEDE算法,但具有相同的數量級,且優于HCLPSO算法和JOA算法.僅在函數f4上,CCABC算法的表現遜于其他三種算法.通過與其他算法的對比可以看出,CCABC算法在全局優化問題上能夠取得相對滿意的優化效果.

5 結束語

優化問題廣泛存在于社會經濟、科學技術與工業制造等多個領域.智能算法為優化問題的求解提供了新的思路和方法.人工蜂群算法是繼遺傳算法、粒子群算法等方法之后提出的一種群體智能優化算法,在解決優化問題方面表現出良好的性能.基本人工蜂群算法計算精度較低,要提高求解精度,可以從解的編碼方式、搜索策略和參數設置等多個方面進行改進.本文提出基于復數編碼的多策略人工蜂群算法.該算法運用復數編碼方法產生多樣性好的解集,并建立策略知識庫,在搜索過程中自適應選擇搜索策略對解集進行更新.選取15個測試函數進行仿真實驗,并將實驗結果與其他人工蜂群算法、MPEDE算法、HCLPSO算法和JOA算法進行比較.數值計算結果證明了CCABC算法的有效性.該算法在解決全局優化問題上與其他算法相比具有一定的優越性.對于如何將其應用到其他類型優化問題及實際工程領域中,將是下一步研究的方向.