基于Logistic混沌映射優(yōu)化的君主蝶優(yōu)化算法①

倪龍雨,符 強,吳滄辰

(寧波大學科學技術學院,寧波 315300)

1 引言

近些年來,元啟發(fā)式算法中最具代表性的范例之一:群智能(SI)算法,越來越受到廣泛的學者歡迎.其各個方向的研究成果已運用到計算機、圖畫、數學、決策控制等眾多領域中,例如:機場調度、風力發(fā)電優(yōu)化等.群智能的概念最早是在1993年由Bonabeau 等提出,其靈感主要來自于自然中的群體工作的集體或系統(tǒng).例如受螞蟻通過信息素記住曾經去過的地方的行為方式啟發(fā),Dorigo 等學者提出蟻群優(yōu)化(ACO)[1];受鳥群尋找食物的社會行為啟發(fā),Kennedy 等學者提出粒子群優(yōu)化(PSO)[2].之后,越來越多優(yōu)異的群智能算法被學者們提出,例如灰狼蝙蝠(BA)算法[3]、人工蜂群(ABC)算法[4]、螢火蟲(FA)算法[5]、蜻蜓(DA)算法[6],以及本文要講述的由Wang 等學者提出的君主蝶優(yōu)化(MBO)算法[7]等等.

君主蝶優(yōu)化算法(Monarch Butterfly Optimization,MBO)是由Wang 等學者經過模仿君主蝶在自然界中的遷移行為于2015年提出的一種元啟發(fā)式算法,該算法可用以處理函數、陳列組合等經典優(yōu)化問題,具有相較于其他算法可以在大多數基準測試函數上找到更優(yōu)值的能力.在君主蝶優(yōu)化算法中,所有個體都被理想化,并且只棲息在兩個地區(qū),這里稱為子群一(LandP1)和子群二(LandP2).君主蝶的位置以兩種方式進行更新,分別為遷移算子(子群一)與調整算子(子群二).當然也能同時實現兩種算子,這體現了其并行處理的功能,可以通過調節(jié)二者關系對算法的收斂性與多樣性進行平衡性調整.本文從MBO 尋優(yōu)過程出發(fā),注意到MBO 易陷入局部最優(yōu)的問題,本文使用Logistic 混沌映射[8]擾動當前種群中的最優(yōu)解以增強其跳出局部最優(yōu)的能力.還注意到遷移算子產生的子代受其父代影響過大[9],不利于其更為多樣化的全局搜索,本文優(yōu)化了遷移算子中子代傳遞的方式,使其受到影響源更多.本文提出的新算法,Logistic 混沌映射君主蝶優(yōu)化算法(Monarch Butterfly Optimization with Logistic Chaotic Map,LCMMBO).通過隨機抽取Benchmark 庫中的10個基準測試函數對其進行數值模擬實驗驗證,發(fā)現其相較于標準MBO 算法與CABC 算法[10]在處理高維的優(yōu)化問題時表現出良好的性能,不僅魯棒性優(yōu)異,而且跳出局部最優(yōu)的能力強.

2 君主蝶優(yōu)化算法

在MBO中,所有君主蝶的生成位置僅在兩個子群內,它們以兩種方式更新位置,分別是遷徙算子生成新的位置,可以通過遷徙率P對其進行調整;還有調整算子生成,同樣可以通過調整率BAR對其進行影響.二者可以并行執(zhí)行,以便更好地處理收斂性與多樣性之間的平衡關系.MBO 對君主蝶的遷徙行為的理想假設模型:

(1)種群中所有個體均來自LandP1 與LandP2.

(2)為了保持總人口不變,本文將會對父代與子代進行統(tǒng)一排序,僅選取排名靠前的個體作為下一代種群.

(3)不對適應值最優(yōu)的兩個個體做任何處理,自動移到下一代.

2.1 初始化

在搜索空間中隨機生成滿足種群數量的個體,依據目標函數計算每個個體的適應度,并據此進行從優(yōu)到劣的一次排序.

將種群分為兩個子群LandP1、LandP2,保證種群中的個體只會棲息在兩個子群中.子群一的個體數N1為種群的總個數N×遷徙率P(P=5/12)的整數部分,即N1=ceil(P×N),子群二的個體數N2為剩下的部分N–N1.

2.2 精英策略

對于每次迭代,選出種群中適應度最好的兩個個體,將他們替代掉下一次迭代過后的種群中的最差的兩個個體.

2.3 遷徙算子

對子群一中的君主蝶第i個體的所有維度,生成一個隨機數r=rand*peri與P比較,若r≤P則子代的第k維由式(1)生成:

在標準MBO中遷徙算子子代生成的公式為取某一個體的維度直接進行賦值,而本文改為對多個對象進行權重分配,再賦值.

2.4 調整算子

除了子群一中的遷徙算子對其進行位置更新,還有對子群二作用的調整算子.對子群二中的君主蝶第i個體的所有維度,生成一個隨機數r=rand與P比較,若r≤P,則子代的第k維由式(3)生成:

若r>p則子代的第k維由式(4)生成:

在此條件下,若r>BAR,則該個體由式(5)進行調整:

其中,BAR為調整率,算法中設置BAR=P,α為權重因子,dx為君主蝶i的步長.α和dx分別由式(6)和式(7)來計算:

其中,Smax為君主蝶的最大步長,t為當前迭代數.

3 Logistic 混沌映射君主蝶優(yōu)化算法

3.1 Logistic 混沌映射

一個系統(tǒng)如果在其進化的過程中對初始的狀態(tài)非常敏感,則這個系統(tǒng)就是混沌系統(tǒng),且這個過程具有確定性、類似隨機性、非周期性.混沌序列的生成方法主要采用以下幾類混沌映射[11]:Logistic 映射、Tent 映射、Henon 映射、Lorenz 映射、逐段線性混沌映射等.由于Logistic 映射從數學的形式上看是個相對簡單的映射方法,經驗實驗表明其混沌系統(tǒng)具有良好的安全性,所以經常被用作設計混沌流密碼系統(tǒng),本文即選用Logistic 對種群中的最優(yōu)個體進行混沌映射.

標準的MBO 在解決高維問題時易陷入局部最優(yōu),這里引入方差 σ2的定義對君主蝶的種群是否陷入局部最優(yōu)進行判斷:

其中,N為君主蝶中的種群個體總數,favg為種群整體適應度的平均值,ft為個體t的適應度.f用來限制 σ2的大小,其取值方式為:

若相鄰的兩次 σ2相差小于一個閾值(本文定為10?6),則表示算法在迭代過程中陷入了局部最優(yōu),此時進入Logistic 混沌映射階段對當前種群中適應度最優(yōu)的個體的位置進行擾動,由式(9)生成擾動個體:

其中,zi∈[0,1]是第i個混沌變量,zi(t)是zi經過t次迭代后產生的.圖1為當君主蝶中的個體xi一定時,對μ不同的取值,zi可 能得到的值.μ ∈[0,4],由圖1可以看出當3.57<μ≤4時,整個系統(tǒng)處于混沌狀態(tài),因此需要選取的μ應該越接近4 越好,但是考慮到對于進行混沌映射時不同的情況可能需要不同的μ值,為了盡可能地取到更多的μ,因此本文在每次進入混沌映射階段時取μ為一個[0,4]中均勻分布的隨機值.

圖1 μ 與zi的相關曲線圖

由于當zi∈[0,1]且zi?{0.25,0.50,0.75}時將產生混沌現象,所以0.25,0.50,0.75為zi定義域中的斷點,映射時應當不處理這些值.對于君主蝶群體中的個體xi∈[ai,bi]由 式(10)映射到zi∈[0,1]:

而zi由 式(11)映射回xi:

算法對適應度最優(yōu)的個體一次映射生成20個個體.

3.2 LCMMBO 算法

眾所周知,群智能算法需要平衡其收斂性與多樣性[12],本文通過改進的遷徙算子遺傳方程增加其全局搜索能力,通過混沌映射增加其局部搜索能力,進而帶動種群朝全局最優(yōu)的位置進化[13].LCMMBO 算法的流程如下:

步驟1.在目標空間隨機初始化50個個體,初始化設置t=1,MaxFEs=500,P=5/12,BAR=5/12,peri=1.2,N1,N2,Smax=1.計算種群中每個個體的適應值.

步驟2.把君主蝶種群根據遷徙率P分成兩個子群LandP1,LandP2,個體數分別為N1,N2.

步驟3.精英策略:取當前種群中最優(yōu)的兩個體放入臨時序列,并在本次迭代結束的時候替換掉種群中最差的兩個個體.

步驟4.將遷徙算子作用于LandP1.

步驟5.將遷徙算子作用于LandP2.

步驟6.合并兩個子群為一個種群,并根據公式(8)計算本次迭代中種群的方差 σ2,從t>2 時開始比較相鄰兩次的方差,如果小于1 0?6則表示陷入局部最優(yōu),進入步驟7,否則進入步驟8.

步驟7.取出當前種群中適應度最優(yōu)個體的位置,對其進行混沌映射,生成20個個體,計算它們的適應值.若最優(yōu)個體比種群中的最優(yōu)個體的適應值更好,那就把種群中的最優(yōu)個體替換,否則不變.

步驟8.判斷是否滿足迭代終止條件,若不滿足則t=t+1,進入步驟2.

4 仿真實驗

4.1 Benchmark 測試函數

本文將LCMMBO 算法與MBO 算法、CABC 算法進行優(yōu)化性能對比分析.隨機抽取10個常見的用來測試算法性能的基準函數用于測試以上算法的優(yōu)化性能,本文所有用于測試的基準函數的全局最小值均為0,且n=50.

(1)Ackley 函數

Ackley 函數的特點是外部區(qū)域幾乎平坦,中央有一個大孔,該函數容易使算法陷入許多局部最優(yōu).

(2)Dixon-Price 函數

(3)Griewank 函數

該函數具有許多分布規(guī)則的復雜的局部最小值在其中,在點(0,···,0)處取得全局最小值0.

(4)Levy 函數

該函數為多峰函數,在點(1,···,1)處取得全局最小值0.

(5)Rastrigin 函數

該函數是個典型的測試函數,是個高度多峰但位置卻均勻分布的函數,在點(0,···,0)取得全局最小值0.

(6)Rosenbrock 函數

該函數時單峰函數,全局最小值位于狹窄的拋物線型的山谷中,很難收斂到最小,在點(1,···,1)處取得全局最小值0.

(7)Rotated Hyper-Ellipsoid 函數

該函數為一個單峰的旋轉的橢球,再點(0,···,0)處取得全局最小值0.

(8)Salomo 函數

該函數為多峰函數,在(0,···,0)處取得全局最小值0.

(9)Sphere 函數

該函數為經典單峰測試函數,在點(0,···,0)處取得全局最小值0.

(10)Wavy 函數

該函數是個經典多峰函數,在點(0,···,0)處取得最小值0.

目前的群智能算法已經在低維的優(yōu)化問題上表現出良好的性能,但是對于高維問題一些算法的求解效果會出現明顯下滑[14].現實中的問題往往具有多個影響因素,也就意味著我們對高維優(yōu)化問題的求解方法不能忽視,這也是本文研究的目標之一.

4.2 模擬實驗

初始化參數設置:3 種算法的種群個體數都為50、最大迭代次數為50、每個個體維度50,其他參數與原文保持一致.

對于10個Benchmark 基準函數,每個算法獨立進行30 次實驗,并記錄其30 次實驗中的最優(yōu)解,最劣解,平均解和標準差等測試結果.本文選擇的這些評價指標能一定程度上的反應新算法LCMMBO 在標準MBO 算法的魯棒性以及全局搜索能力上的優(yōu)化.

表1為3 種算法在10個優(yōu)化問題上獨立運行30 次的具體實驗結果.

表1 實驗結果

為了更直觀的體現LCMMBO 算法相較于MBO、CABC的優(yōu)越性,本文將作LCMMBO、MBO、CABC 三種算法分別在10個基準函數上獨立運行30 次的迭代次數與平均適應值的曲線仿真圖2至圖11作為參考.

4.3 實驗結果分析

在表1中,從最優(yōu)值這個評價指標上看,LCMMBO算法除了在f3上得到了明顯優(yōu)于MBO、CABC 兩個算法的最優(yōu)值,在其余的基準函數上LCMMBO 算法并沒有表現出優(yōu)異的性能.從最差值、平均值與標準差上看,由于LCMMBO 算法跳出局部最優(yōu)的優(yōu)異,所以在這3個評價指標上可以清楚地看到新算法在魯棒性上的優(yōu)化.例如:最差在函數f1、f8上平均值相比MBO 算法優(yōu)化了大約10 倍;最好在f2、f4上平均值相比MBO 算法優(yōu)化了106倍.

從圖2至圖11中可以看到LCMMBO 算法的收斂曲線具有明顯的下降趨勢,相比MBO、CABC 更接近目標函數的理論最優(yōu)值,而從圖2、圖7、圖11中可以看出MBO和CABC的進化曲線幾乎沒有下降的趨勢,從曲線的下降速度看,除了圖6、圖11以外,LCMMBO的下降速度也要優(yōu)于二者.這說明LCMMBO 由于具有更好的全局探索及局部搜索平衡能力,因此尋優(yōu)性能明顯優(yōu)于MBO和CABC;LCMMBO 比MBO和CABC 具有更快的全局收斂速度,表現出更好的收斂性;LCMMBO 比MBO和CABC 具有更好的全局搜索能力.

圖2 f1收斂曲線對比圖

圖3 f2收斂曲線對比圖

圖4 f3收斂曲線對比圖

圖5 f4收斂曲線對比圖

圖6 f5收斂曲線對比圖

圖7 f6收斂曲線對比圖

圖8 f7收斂曲線對比圖

圖9 f8收斂曲線對比圖

圖10 f9收斂曲線對比圖

圖11 f10收斂曲線對比圖

圖2至圖11都非常清楚地顯示了MBO 在處理高維問題時易陷入局部最優(yōu)的問題;CABC 雖然對陷入局部最優(yōu)問題做了一些處置,但效果顯然沒有LCMMBO明顯.另外,從圖3、圖6中可以看到CABC 在資源的利用率上不如LCMMBO,在陷入局部最優(yōu)時CABC需要更多的迭代實現跳出局部最優(yōu)的行為.

綜上所述,新算法LCMMBO的穩(wěn)定性比MBO和CABC 更優(yōu);LCMMBO 相較于MBO和CABC 具有更好的收斂性;LCMMBO 相較于MBO和CABC 具有更強的局部搜索能力以及全局搜索能力;LCMMBO跳出局部最優(yōu)的能力比MBO和CABC 好.

5 結語

本文針對標準MBO 存在的遷徙算子影響源過少,以及處理高維度問題時容易陷入局部最優(yōu),全局搜索能力差,提出一種新的基于Logistic 混沌映射的MBO算法,并改進了其遷徙算子遺傳方程.通過對10個Benchmark 基準測試函數的模擬實驗,說明了新算法LCMMBO在解決高維函數優(yōu)化問題時相比較標準MBO,CABC算法具有更優(yōu)的魯棒性、更快的全局收斂速度、更強的局部搜索能力和全局搜索能力、更好的跳出局部最優(yōu)的能力;說明了本文提出的改進方案是有效且可實施的.在未來的研究中還應該注意一些可能進行優(yōu)化的地方,比如:參數對于群智能優(yōu)化算法的性能有很大的影響,最佳的參數設置應該經過理論分析或經驗實驗決定等.