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

倪龍雨,符 強(qiáng),吳滄辰

(寧波大學(xué)科學(xué)技術(shù)學(xué)院,寧波 315300)

1 引言

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

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

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

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

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

(2)為了保持總?cè)丝诓蛔?本文將會(huì)對父代與子代進(jìn)行統(tǒng)一排序,僅選取排名靠前的個(gè)體作為下一代種群.

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

2.1 初始化

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

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

2.2 精英策略

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

2.3 遷徙算子

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

在標(biāo)準(zhǔn)MBO中遷徙算子子代生成的公式為取某一個(gè)體的維度直接進(jìn)行賦值,而本文改為對多個(gè)對象進(jìn)行權(quán)重分配,再賦值.

2.4 調(diào)整算子

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

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

在此條件下,若r>BAR,則該個(gè)體由式(5)進(jìn)行調(diào)整:

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

其中,Smax為君主蝶的最大步長,t為當(dāng)前迭代數(shù).

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

3.1 Logistic 混沌映射

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

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

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

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

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

圖1 μ 與zi的相關(guān)曲線圖

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

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

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

3.2 LCMMBO 算法

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

步驟1.在目標(biāo)空間隨機(jī)初始化50個(gè)個(gè)體,初始化設(shè)置t=1,MaxFEs=500,P=5/12,BAR=5/12,peri=1.2,N1,N2,Smax=1.計(jì)算種群中每個(gè)個(gè)體的適應(yīng)值.

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

4.1 Benchmark 測試函數(shù)

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

(1)Ackley 函數(shù)

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

(2)Dixon-Price 函數(shù)

(3)Griewank 函數(shù)

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

(4)Levy 函數(shù)

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

(5)Rastrigin 函數(shù)

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

(6)Rosenbrock 函數(shù)

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

(7)Rotated Hyper-Ellipsoid 函數(shù)

該函數(shù)為一個(gè)單峰的旋轉(zhuǎn)的橢球,再點(diǎn)(0,···,0)處取得全局最小值0.

(8)Salomo 函數(shù)

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

(9)Sphere 函數(shù)

該函數(shù)為經(jīng)典單峰測試函數(shù),在點(diǎn)(0,···,0)處取得全局最小值0.

(10)Wavy 函數(shù)

該函數(shù)是個(gè)經(jīng)典多峰函數(shù),在點(diǎn)(0,···,0)處取得最小值0.

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

4.2 模擬實(shí)驗(yàn)

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

對于10個(gè)Benchmark 基準(zhǔn)函數(shù),每個(gè)算法獨(dú)立進(jìn)行30 次實(shí)驗(yàn),并記錄其30 次實(shí)驗(yàn)中的最優(yōu)解,最劣解,平均解和標(biāo)準(zhǔn)差等測試結(jié)果.本文選擇的這些評價(jià)指標(biāo)能一定程度上的反應(yīng)新算法LCMMBO 在標(biāo)準(zhǔn)MBO 算法的魯棒性以及全局搜索能力上的優(yōu)化.

表1為3 種算法在10個(gè)優(yōu)化問題上獨(dú)立運(yùn)行30 次的具體實(shí)驗(yàn)結(jié)果.

表1 實(shí)驗(yàn)結(jié)果

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

4.3 實(shí)驗(yàn)結(jié)果分析

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

從圖2至圖11中可以看到LCMMBO 算法的收斂曲線具有明顯的下降趨勢,相比MBO、CABC 更接近目標(biāo)函數(shù)的理論最優(yōu)值,而從圖2、圖7、圖11中可以看出MBO和CABC的進(jìn)化曲線幾乎沒有下降的趨勢,從曲線的下降速度看,除了圖6、圖11以外,LCMMBO的下降速度也要優(yōu)于二者.這說明LCMMBO 由于具有更好的全局探索及局部搜索平衡能力,因此尋優(yōu)性能明顯優(yōu)于MBO和CABC;LCMMBO 比MBO和CABC 具有更快的全局收斂速度,表現(xiàn)出更好的收斂性;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 在處理高維問題時(shí)易陷入局部最優(yōu)的問題;CABC 雖然對陷入局部最優(yōu)問題做了一些處置,但效果顯然沒有LCMMBO明顯.另外,從圖3、圖6中可以看到CABC 在資源的利用率上不如LCMMBO,在陷入局部最優(yōu)時(shí)CABC需要更多的迭代實(shí)現(xiàn)跳出局部最優(yōu)的行為.

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

5 結(jié)語

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