基于調節算子的多目標人工蜂群算法

趙新秋, 段思雨, 馬學敏

(燕山大學,河北秦皇島 066004)

1 引 言

隨著工業生產能力的進步以及科學工藝的發展,在優化此類問題中往往需要多目標優化算法對多個沖突的目標同時進行優化,來獲得一組權衡的解集.目前,多目標進化算法(MOEAs)[1?4]相繼提出去解決復雜的非線性多目標優化問題,現已應用于參數優化[5?8]、車間調度[9]和數據挖掘[10,11]等領域,并取得了良好的效果.

人工蜂群算法(artificial bee colony algorithm)是一種仿生學群智能算法,該算法通過模擬蜜蜂采蜜的一系列過程,來解決現實中的復雜優化問題[12,13].由于其結構簡單、易于實現且擁有較快的收斂速度,最初廣泛應用于數值優化問題.目前,國內外學者對人工蜂群算法的改進主要包括加快算法收斂速度以及提高算法的多樣性和分布性.

1)提高算法多樣性和分布性.

單嫻等[14]通過種群個體在搜索過程中自適應選擇最佳搜索方式,提出一種復數編碼的多策略人工蜂群算法,改善了種群的多樣性;Akay[15]利用支配關系和非支配排序方法提出S-MOABC算法,結果表明算法能夠獲得一組分布性良好的解集;Yi 等[16]利用多重模型和動態信息交換策略,提出了一種動態多群體多目標人工蜂群算法.在此基礎上提出一種基于分解的人工蜂群算法[17],將分解的思想引入蜂群算法中,對比其他算法能夠取得一組分布性更好的解集;Luo 等[18]提出了一種基于評價指標的多目標人工蜂群算法,利用支配關系和偏好信息將每一代產生的非支配解加入到外部檔案,在處理復雜多目標問題時可以保證良好的分布性;Zhang 等[19]提出一種基于多種群和區間可信度的多目標優化方法,在外部檔案中利用精英學習策略,獲得一組分布性優越的解集;Beheshti[20]將二進制編碼方式引入算法,提出一種二進制鄰域蜂群算法,改善算法的開發能力.

2)加快算法收斂速度.

Gao 等[21]根據差分進化算法的啟發,通過混沌算子和反向學習方法對種群初始化,使用兩種不同的搜索方式來解決但目標問題,提出IABC 算法;Akbari 等[22]提出的多目標蜂群算法,具有里程碑的意義,該算法采用自適應網格的方法對外部檔案進行維護, 并利用精英蜂引導種群進化, 加快算法收斂速度; Xiang等[23]引入一種新的搜索方式,加入參數擾動平衡算法搜索和開發能力的同時,加快了算法的收斂速度;Liu等[24]將knee points 的概念引入蜂群算法,提高收斂速度的同時,保持了良好的分布性.

基于以上分析,本文提出了一種基于調節算子的多目標人工蜂群算法(multi-objective artificial bee colony algorithm based on regulation operators,RMOABC).為了改善算法開發能力弱的問題,在引領蜂階段,根據蜜源動態的調節進化方向,平衡了算法的局部搜索和全局搜索能力;在跟隨蜂階段,提出了一種根據種群分布的概率計算方式,合理利用多樣性個體對種群進行更新;在外部檔案維護階段,算法將外部檔案中的解進行維度融合,保證外部檔案的多樣性,并將其作為最后的輸出結果.通過與其他4種算法在基準測試函數進行仿真比較,驗證了本文算法的在收斂速度以及分布性上有一定提升.

2 標準人工蜂群算法

人工蜂群(artificial of bee colony,ABC)算法是一種新興的群體智能模型,是通過模擬自然界中蜂群尋找蜜源過程的仿生智能算法.在整個過程中,每個蜜源代表尋優過程中的可行解,并且根據不同的分工,蜂群被分為三類: 引領蜂(employed foragers)、跟隨蜂(onlookers)和偵查蜂(scouts).三類蜜蜂在整個過程中,相互分享信息,促進整個群體進化,完成整個尋優的過程.

使用ABC 算法求解問題時,首先,需要對種群進行初始化操作

其次,對引領蜂位置進行更新進化

其中k=1,2,...,N/2 且,j=1,2,...,D,rij ∈(?1,+1),vij為新產生的候選解的第j維分量.

在整個搜索過程中,跟隨蜂通過引領蜂分享的信息,根據蜜源質量使用輪盤賭策略選擇一個合適的蜜源進行開采,蜜源選擇概率為pi=其中Fi為適應度值.

以最小化問題為例

其中fi為第i個解的優化目標函數值.

選擇優異的蜜源后,跟隨蜂按照式(2)對蜜源進行深度開發.在引領蜂和跟隨蜂完成更新過程后,通過對適應度進行貪婪選擇,確定是否保留新產生的解.最后,若某個個體循環更新次數達到閾值(Limit),其解的質量還沒有得到改善,則放棄該蜜源,引領蜂轉化為偵查蜂,按照式(1)對蜜源進行重新初始化,產生一個新個體替代原有個體.

3 基于調節算子的多目標人工蜂群算法

3.1 基于個體閾值的更新公式

標準人工蜂群算法存在精于搜索,疏于開發的問題.在通過ABC 算法求解多目標優化問題時,由于同時存在多個互不支配的解,種群中個體通過信息交流搜索新蜜源,整個過程隨機性大,ABC 算法雖然具有較強的全局搜索能力,但并沒有通過充足的開發來找到一組最優解,算法局部搜索能力較差,當逐步接近Pareto前沿時開發效率明顯降低,導致算法整體搜索能力強開發能力弱.在蜜源開發末期,如果繼續使用式(2)對蜜源進行開發,蜜源質量基本得不到改善,整體多樣性缺失.在搜索過程中,為了進一步控制搜索進度,以平衡人工蜂群算法中全局“搜索”和局部“開發”的能力,引入了兩種調節算子: 局部調節算子和全局調節算子.針對蜂群算法在進化前期,在精英個體的引導下易陷入局部最優,通過加強當前食物源與鄰域內食物源進行信息交流共享,提高算法的尋優特性.針對人工蜂群算法收斂速度慢的缺陷,通過在進化中期加強精英解對種群的引導作用,使種群能夠快速收斂到近似Pareto 前沿.在進化后期,為避免丟失種群多樣性,通過與鄰域內個體充分交流,以保證在收斂到Pareto 前沿時具有良好的分布性.將引領蜂階段新的位置進行更新,即

其中k= 1,2,...,N/2 且k=i,j= 1,2,...,D,μ ∈[?Φ,+Φ],υ ∈[?Ψ,+Ψ],Ψ= sin(πti/Limit),Φ=|cos(πti/Limit)|,r ∈[1,1.75](通過設計重復性實驗確定最優取值范圍,由于篇幅所限,沒有列出詳細的實驗過程),e是外部檔案中隨機選擇的一個解,ti是蜜源i當前開發的閾值,Limit 是蜜源開采最大閾值.

調節算子和閾值曲線如圖1 所示.

圖1 調節算子和閾值曲線圖Fig.1 The curve of regulation operators and limit

由圖1 可以看出,在算法前期優化過程中,局部調節算子Φ大于全局搜索算子Ψ,蜜源更注重于局部開發;但在個體蜜源進化過程中,隨著蜜源自身閾值的增加,全局搜索算子Ψ變大,精英解對蜜源的影響變大,加速收斂進程;最后,算法重新側重于對局部開發的能力,保證在進化后期種群具有良好的分布性,以達到整個進化過程中局部搜索和全局開發能力的平衡.

3.2 基于個體分布的概率選擇公式

在單目標優化問題中,在跟隨蜂階段只需要根據個體的函數值就可以計算蜜源的適應度值.但在多目標問題中,僅僅考慮個體的函數值,在一定程度上很難判斷解的優異性,在進化過程中難以保證種群的分布性和收斂性.從圖2 可以看出,由于A 點不支配任何個體,一旦蜜源A 在開發過程中被淘汰或因達到自身開發閾值被重新初始化時,種群的多樣性將被破壞,將這種具有保障種群整體分布性的蜜源稱為多樣性個體.因此,本文提出一種基于種群個體分布的概率選擇公式,通過充分考慮種群中個體的分布性,賦予多樣性個體更高的適應度值,最后利用輪盤賭選擇解引導種群進化,以獲得一組收斂性和分布性良好的Pareto 最優解集.改進后的蜜源i的選擇概率

圖2 多樣性點示意圖Fig.2 The picture of diversity point

其中F(i)為蜜源i的的適應度值,F(i) = (Riexp(2mi/N))?1,Ri表示蜜源i的支配等級,mi為蜜源i支配蜜源的數量,N為蜜源總數.

為了保持算法中種群的多樣性,在式中將蜜源支配解的數量考慮到蜜源適應度的計算中.由式(4)可以看出,蜜源A 為非支配個體且mi為0 時,蜜源的適應度值為1.對于非支配個體,當蜜源支配解得數量越多時,其被賦予的適應度值越小,則其被選擇引導進化的概率也就越小.而對于支配個體,由于其蜜源本身是被支配的,導致其具有先天性的劣勢,其適應度值被限制在(0,1/Ri].通過考慮蜜源的分布性和支配等級分配蜜源適應度值的方式,在跟隨蜂階段多樣性個體會有更高的概率被選擇去引導蜜源進化,以保證整體算法的分布性,有利于改善算法的多樣性和收斂性.

算法在跟隨蜂階段蜜源位置更新方法為

其中k=1,2,...,N/2 且k=i,j=1,2,...,D,r ∈[1,1.75],μ的計算方式同引領蜂階段計算方式一致.

3.3 改進的外部檔案維護策略

精英解即搜索過程中產生的非支配解,通過將精英解保存到外部檔案中,并利用其信息引導種群進化,提高種群的收斂速度.一般條件下,外部檔案具有固定大小(見圖3).當外部檔案為空時,將進化過程中產生的非支配解加入外部檔案.當外部檔案存儲解的數量達到最大時,將個體的擁擠距離作為評判標準,將擁擠距離最小的個體刪除,直到迭代結束獲得一組滿足數量的解(見圖4).由圖4 可以看出,根據傳統的外部檔案維護策略,E 點將會被刪除,這樣的做法將會造成D 點和G 點環境之間多樣性的缺失,破壞了多樣性.為了解決此問題,本文提出一種新的外部檔案維護策略,當外部存檔容量大于最大值時,將擁擠距離最小的E 點和距離其最近的F 點兩者進行維度混合,重新生成一個新的個體,更新位置為xi= (xm+xn)/2,其中xm為將被刪除的擁有最小擁擠距離的個體,xn為距離具有最小擁擠距離個體最近的點.

圖3 外部檔案Fig.3 External arhcive

圖4 截斷后外部檔案Fig.4 External arhcive after truncation

3.4 利用多樣性點的重新初始化方式

為了充分利用多樣性個體的信息,當蜜源達到開發閾值Limit 時,利用下式對蜜源進行初始化,

如果不存在多樣性個體,則利用非支配個體的信息進行初始化,其中xi為重新初始化產生的新個體,xD為多樣性個體,x為需要重新初始化個體.

3.5 算法步驟

本文提出的算法具體步驟如下:

步驟1初始化種群數量為N,外部檔案最大存儲量為N/2,設置最大評價次數Evaluation,偵查蜂的最大淘汰次數為Limit,并對蜜源進行初始化.

步驟2按照式(3)對引領蜂位置進行更新,更新后如果支配原始蜜源則被保留,且ti ←0,否則ti ←ti+1,并將新產生的解與外部檔案中個體比較支配關系確定是否保留.

步驟3通過式(4)計算個體的適應度值和選擇概率,并通過輪盤賭方法選擇個體引導種群中個體進化,具體進化公式為式(5),并對其后代執行與引領蜂相同的保留策略.

步驟4判斷當達到個體ti >Limit 時,通過式(6)重新初始化產生一個新蜜源來替換舊蜜源位置.

步驟5在每次迭代完成后,對外部檔案進行維護,判斷是否達到最大的評價次數Evaluation.若達到則結束循環并輸出外部檔案中的個體作為最終結果,否則轉至步驟2.

4 實驗仿真與分析

為驗證本文算法的有效性, 與NSABC[17], S-MOABC/NS[15], MOABC[22]以及NSGAII算法[2]在10 個無約束多目標測試問題進行仿真.仿真采用Inter(R)Core(TM)i5-7500 CPU, 8G RAM 的PC 機, 實驗環境為MATLAB R2017a.

4.1 測試函數及性能指標

本文針對兩目標和三目標的優化問題進行測試,采用CEC09 測試集[25]中UF 系列測試函數,并將綜合性指標inverted generational distance(IGD)[26]作為性能評價指標,即

其中C為真實Pareto 前沿上解的個數,di為真實前沿PF 上第i個點到算法所求解集的最小歐氏距離.

IGD 指標通過計算真實Pareto 前沿與求得前沿之間的歐式距離,反映算法所求解集的分布性和收斂性.

4.2 仿真實驗結果與分析

為了測試本文RMOABC 算法的性能, 選取了四個對比算法在UF1～UF10 上進行仿真, 算法的參數如表1 所示, 其余在算法中涉及參數全部參考原文獻.表2 中統計了算法的IGD 最優值(best)、最差值(worse)、平均值(mean)和標準差(std),其中加粗項為同一測試函數中取得最優值.

表1 參數設置Table 1 The parameter settings

從表2 中可以看出,本文所提出的算法無論在UF 系列的雙目標還是三目標測試函數上,所提出的算法均可以獲得良好的效果,且具有較小的標準差,說明RMOABC 算法在保證分布性和收斂性的同時,還可以保證良好的穩定性.

表2 算法IGD 值指標仿真結果比較Table 2 Comparison of algorithms via IGD-metric

在雙目標測試問題上(UF1～UF7),對于凸優化測試函數(UF1～UF3),RMOABC 算法均獲得了較好的效果,說明RMOABC 算法在處理此類MOP 問題時相較于其他算更具有優勢; 對于非凸測試函數UF4 以及具有非連續Pareto 面函數UF5,UF6 測試問題,雖然本文算法在IGD 平均值上落后于MOABC,NSABC 經典算法, 但RMOABC 在結果上與以上兩種算法保持在同一數量級, 并且標準差優于以上兩種算法, 說明在處理此類問題時具有良好的穩定性; 對于UF7 測試問題,雖然NSGAII 算法在分布性上優于RMOABC算法, 但是在收斂性上劣于RMOABC 算法, 說明RMOABC 算法具有較好的收斂性; 在三目標測試問題(UF8～UF10),除了在UF10 上劣于MOABC,NSABC 算法外,在其他兩個測試問題無論是平均值還是標準差上,均取得了最好的結果,說明算法對比其余4種算法在處理三目標優化問題時具有良好的競爭力.

續表2Table 2 Continues

4.3 各策略IGD 值分析

為了驗證本文提出算法策略的有效性,本節設計3組對比實驗,RMOABC-I 為標準蜂群算法適應度計算公式的算法,RMOABC-II 為采用一般的外部檔案維護策略的算法,RMOABC-III 為采用標準人工蜂群算法搜索公式的算法.上述算法除部分策略不同,其余參數與4.1 節設置一致.

令R=其中n為測試函數的個數,ri表示算法在第i個測試函數上的排名.

表3 中給出四種算法的排名,其中R表示算法在10 個測試函數的平均排名,其值越小,表明算法表現的更優異.可以看出RMOABC 算法平均排名最小,表明基于3 種策略的RMOABC 算法性能更好.

由表2 和表3 可以看出本文提出的策略,無論是在收斂性和穩定性上都有較明顯的提升.

表3 不同策略算法IGD 比較Table 3 Comparison of algorithms based on different strategies via IGD-metric

續表3Table 3 Continues

4.4 算法收斂性分析

圖5 中給出了RMOABC 和其余4種算法的IGD 下降趨勢圖,所選擇的數據為UF 系列函數在30 次獨立實驗所獲得的IGD 平均值.為了能夠直觀的看出下降趨勢, 將IGD 對數作為縱坐標, 每評價105次記錄一次數據,圖中的虛線為5 種算法IGD 求和取平均值.對于雙目標測試問題(UF1～UF7),在非凸測試函數UF4 和非連續測試函數UF6 中,RMOABC 算法分別排在第四位和第二位,除此之外相較于其它4 種算法,RMOABC算法都具有較快的收斂速度,且都比較穩定;對于三目標測試問題(UF8～UF10),在UF10 函數收斂速度劣于S-MOABC 以及NSABC,但另外兩個測試函數上收斂速度和最終結果均優于其它4 種對比算法,說明RMOABC 算法在三目標問題上也能取得較好的結果.結合表2 和圖5 的實驗結果,RMOABC 算法在UF 測試問題相較于其他4種對比算法總體上具有顯著的收斂性和分布性上的優勢.

圖5 算法收斂性能Fig.5 The convergence performance of algorithms

續圖5Fig.5 Continues

5 結束語

為了達到加快算法收斂速度以及平衡全局搜索能力和局部開發能力的目的,本文提出了一種基于調節算子的多目標蜂群算法.首先,利用蜜源閾值生成的調節算子構成搜索公式,實現了對蜜源尋優方向的動態調節,根據蜜源自身情況精細控制,達到平衡全局搜索能力和局部開發能力的目的.其次算法在跟隨蜂階段計算概率時增加多樣性蜜源被選擇的概率,改善種群的分布性.最后算法采用新的外部檔案維護策略,避免了多樣性丟失的問題.通過RMOABC 算法與其它4 種代表性算法與10 個基準非約束多目標測試函數,在同一環境下進行仿真對比,結果表明本文的算法在分布性和收斂性方面有較好的提升.