具有Levy變異和精英自適應競爭機制的蟻獅優(yōu)化算法

景坤雷，趙小國,3，張新雨，劉丁

近幾十年來，越來越多的群體智能算法被提出，并以其操作簡單、不受求解對象約束等特點在工程領(lǐng)域得到廣泛應用。蟻獅優(yōu)化算法(ant lion optimizer，ALO)是澳大利亞學者Seyedali Mirjalili[1]通過研究蟻獅捕食螞蟻的仿生學機制，提出的一種智能優(yōu)化算法。ALO算法以其調(diào)節(jié)參數(shù)少、求解精度高的優(yōu)點，備受科研工作者的青睞，目前已被成功應用于天線布局優(yōu)化、分布式系統(tǒng)的選址和控制器增益值優(yōu)化等工程領(lǐng)域[2-4]。

文獻[5]為改善種群多樣性，通過對基本算法的精英化過程引入了權(quán)值操作，提出了MALO算法，但是隨著種群不斷向精英靠攏，多樣性仍會不可避免地降低，因而該方法沒有從根本上提高算法的全局搜索能力；文獻[6]為減小適應值較差個體對種群的誤導，提出一種具有混沌偵查機制的CIALO算法，提高了種群對求解域的映射能力，但并未改善算法的收斂速度。

針對以上不足，本文提出一種具有Levy變異和精英自適應競爭機制的蟻獅優(yōu)化算法(ALO with Levy variation and adaptive Elite competition, LEALO)。服從Levy分布的隨機數(shù)具有短距離游走結(jié)合偶爾長距離跳躍的特征，利用其對種群較差的個體進行變異，可以改善種群多樣性，實現(xiàn)對求解域的充分探索，從而提高算法的全局搜索能力；多個精英之間的自適應并行競爭，有助于種群更快地鎖定更優(yōu)的區(qū)域，保證算法收斂速度的同時避免了較大的計算量。本文選擇標準函數(shù)對LEALO算法進行測試，并與基本ALO算法[1]、MALO算法[5]和CIALO[6]算法進行比較，結(jié)果表明LEALO算法具有更高的尋優(yōu)精度和收斂速度。最后將其用于硅單晶熱場溫度模型的參數(shù)辨識中，仿真結(jié)果說明了該算法良好的優(yōu)化能力。

1 蟻獅優(yōu)化算法及其缺點

1.1 ALO算法原理

蟻獅是一種靠捕食螞蟻生存的蟻蛉科昆蟲，以其獨特的狩獵方式得名。蟻獅“狩獵”時先在沙地上挖出“陷阱”，然后躲入穴底等待“獵物”，一旦螞蟻進入“陷阱”，為防止其逃走蟻獅會立刻向外刨出沙土使其滑入穴底進而捕食。Mirjalili將二者間的仿生學機制公式化再現(xiàn)，提出了蟻獅優(yōu)化算法。該算法的主要步驟如下。

1.1.1 蟻獅修筑陷阱

根據(jù)適應值，通過輪盤賭操作從上一代的螞蟻種群中選擇個體。被選中的個體將和精英一起作為蟻獅修筑“陷阱”。

1.1.2 螞蟻隨機游走

按照式(1)產(chǎn)生隨機游走的螞蟻種群：

1.1.3 螞蟻進入陷阱

螞蟻爬入陷阱的過程，可以看作螞蟻圍繞修筑“陷阱”的蟻獅游走，即螞蟻游走的區(qū)域邊界受蟻獅位置的影響：

1.1.4 螞蟻滑落穴底

一旦螞蟻進入陷阱，為阻止其逃走，蟻獅會立即向穴外刨出沙土使其滑入穴底。該過程可以看作螞蟻繞蟻獅游走的半徑在不斷縮?。?/p>

1.1.5 蟻獅重筑陷阱

若游走的螞蟻種群中出現(xiàn)了適應值高于蟻獅的個體，則該個體為新的精英。即該個體將作為蟻獅在下一代修筑“陷阱”：

1.1.6 螞蟻種群精英化

繞精英游走的螞蟻種群，影響著繞輪盤賭選擇的個體游走的螞蟻種群。

1.2 ALO算法缺點

在ALO算法中，螞蟻種群繞精英蟻獅的隨機游走保證了尋優(yōu)過程的收斂性，輪盤賭操作在一定程度上有助于提高螞蟻種群的全局搜索能力。但是，算法仍存在以下問題：蟻獅的捕食半徑的隨著迭代次數(shù)的增加階段性收縮，會導致種群多樣性的逐漸降低，算法一旦陷入局部最優(yōu)就難以跳出；若當代精英和輪盤賭選擇的個體并不處于全局最優(yōu)區(qū)域時，整個種群在單個精英帶領(lǐng)下會降低算法的收斂速度。

2 改進算法(LEALO)

針對ALO算法存在的缺點，本文引入Levy變異和并行的自適應精英競爭機制。將服從Levy分布的隨機數(shù)用于種群較差個體的變異，可以有效改善種群的多樣性，提高算法的全局搜索能力；多個精英同時帶領(lǐng)種群探索加快了算法的收斂速度。另外，引入精英的個數(shù)隨迭代次數(shù)的增加而減少的自適應機制可以避免較大的計算量。

2.1 Levy變異機制

Levy游走一詞是由法國數(shù)學家保羅·列維提出的，而后有學者發(fā)現(xiàn)很多生物群體的活動方式均可以用Levy游走模式進行描述[7]。研究人員們通過對生物群體基于Levy游走模式的活動方式進行研究，形成了一種Levy飛行覓食假說，即Levy游走可以提高覓食效率，基于Levy游走的覓食方式自然適應性更強。Levy飛行表現(xiàn)為長期短距離游走和偶爾長距離跳躍的結(jié)合，這種長距離跳躍具有方向多變性的特點[8]。

利用Levy飛行特點形成Levy變異機制來提高種群的多樣性，保證了種群對附近區(qū)域詳細搜索的同時又具有一定的突變性。兩種方式交替從而實現(xiàn)對求解域的充分遍歷，有助于提高算法的全局搜索能力[9]。Levy飛行服從Levy分布，其概率密度函數(shù)如下：

根據(jù)式(8)～(10)計算得到Levy飛行軌跡，式(11)通過尺度因子和限幅操作將Levy飛行位置映射在求解域內(nèi)。取模擬出二維的Levy飛行軌跡如圖1所示，充分驗證了Levy飛行短距離結(jié)合偶爾長距離跳躍的特征，對求解域?qū)崿F(xiàn)了充分的探索。因此選擇適當數(shù)量的蟻獅種群進行Levy變異可以顯著改善整個種群的多樣性，從而提高算法的全局搜索能力。

圖1 設定搜索范圍內(nèi)的Levy飛行軌跡圖Fig. 1 Simulation tracks of Levy flights in the set region

2.2 精英自適應競爭機制

單個精英所擁有的極值信息極其有限，因此有必要建立精英庫存儲歷代較佳的個體(變異后適應值較佳的個體也會被存入精英庫)。對ALO算法引入精英競爭機制，在每一代的尋優(yōu)中，多個精英之間并行競爭，而不是通過輪盤賭的方式選擇。在多個精英的同時帶領(lǐng)下，種群能夠快速鎖定相對較優(yōu)解的所在區(qū)域，有助于加快算法收斂速度[14-15]。

為保證尋優(yōu)前期的收斂速度，應選取較多個精英參與競爭；而后期，應減少精英個數(shù)避免較大的計算量。因此并行競爭的精英個數(shù)應隨著迭代次數(shù)的增加而衰減。這種自適應選取方式在保證算法尋優(yōu)速度的同時避免了不必要的計算量。設置精英個數(shù)范圍為，則對于當代精英個數(shù)和迭代次數(shù)t，構(gòu)造如下關(guān)系式：

圖2 精英個數(shù)和迭代次數(shù)之間的函數(shù)曲線Fig. 2 Function curve between the number of elites and iterations

2.3 LEALO算法執(zhí)行偽代碼

Algorithm: LEALO algorithm

Initialize Antlions position

Building Elites library

Select a antlion from the Antlions;

Ants walk around iith elite using Eq.(1)

Normalize ants using Eq.(2);

Update ants using Eqs.(14)(4);

Elitism the ants using Eqs.(6);

Calculate the objective values of ants;

Update the Elites library using Eq.(15);

end for

end for

Make Levy-mutation using Eq.(8)(9)(10)(11)(12)

end while

3 測試對比分析與應用

3.1 仿真實驗

下面通過6個標準函數(shù)測試LEALO算法的尋優(yōu)精度和收斂速度，測試函數(shù)設置見表1。其中f1、f2為單峰函數(shù)，為多峰函數(shù)。

表1 標準測試函數(shù)Table 1 Standard test functions

仿真平臺，操作系統(tǒng)：win7旗艦版(64 b)；CPU：Intel(R)Core(TM)i5-4590；主頻：3.30 GHz；RAM：4.00 GB；編程工具：MATLAB2016b。選擇3種算法(ALO、MALO、CIALO)和LEALO算法進行對比，測試100次，分別統(tǒng)計歷代最優(yōu)解、平均解和尋優(yōu)成功率(當尋優(yōu)值達到設置精度時，視作尋優(yōu)成功)。因3種改進算法效果均優(yōu)于基本ALO算法(結(jié)果見圖3)，考慮到表格篇幅，只給出3種改進算法的測試結(jié)果，如表2所示。

圖3 對數(shù)坐標下3種算法的尋優(yōu)收斂曲線Fig. 3 Convergence curves of the three algorithms under logarithmic coordinates

表2 LEALO、CIALO、MALO 3種改進優(yōu)化算法的測試結(jié)果對比Table 2 Test results comparison of LEALO、CIALO and MALO

精度方面：對于函數(shù)f1，MALO算法高于CIALO 算法；對于函數(shù) f2、f3、f4、f5、f6，MALO 算法低于CIALO算法。尋優(yōu)成功率方面：對于函數(shù)f3、f5，CIALO算法高于MALO算法。整體而言，這兩種算法的尋優(yōu)精度和成功率均不高，而LEALO算法在尋優(yōu)精度和尋優(yōu)成功率上均遠優(yōu)于MALO算法和CIALO算法。

為了使尋優(yōu)精度和收斂速度對比更為直觀，分別取經(jīng)過100次測試的4種算法收斂曲線平均值，繪制在對數(shù)坐標系中，如圖3所示。對于函數(shù)f1、f3、f4、f6，LEALO算法的尋優(yōu)精度遠高于MALO和CIALO算法；對于函數(shù)f2、f5，LEALO算法尋優(yōu)精度略高于和MALO和CIALO算法，但是收斂速度明顯快于這兩種算法；對于函數(shù)f4、f5，MALO和CIALO算法均早早陷入局部最優(yōu)不再收斂，而LEALO算法能夠不斷跳出局部最優(yōu)對求解域進行充分探索，在得到更高精度解的同時保證了較快的收斂速度。綜合表2和圖3得出，LEALO算法有效克服了基本ALO算法及MALO和CIALO兩種改進算法易陷入局部最優(yōu)、收斂速度慢的缺點，對于高維度變量的多峰函數(shù)可以實現(xiàn)高精度快速尋優(yōu)。

3.2 硅單晶熱場溫度模型參數(shù)的辨識

硅單晶是一種重要的半導體材料，基于直拉法的單晶爐是制備硅單晶的關(guān)鍵設備[16]。為了得到高品質(zhì)硅單晶，通常通過調(diào)節(jié)加熱器功率來有效控制爐內(nèi)的熱場溫度，因此有必要建立精確的熱場溫度模型。本文針對拉晶過程中的引晶階段，采用式(16)作為該階段的熱場溫度模型，基于現(xiàn)場采集的大量數(shù)據(jù)，對模型參數(shù)進行離線辨識，進而得到熱場溫度模型。

上面已證實了LEALO算法對包含多維參數(shù)的多峰函數(shù)的尋優(yōu)能力，現(xiàn)將LEALO算法應用于熱場溫度模型的離線辨識[17]。設置種群個數(shù)為30，最大迭代次數(shù)1 000，辨識20次，所得參數(shù)如表3所示。模型離散化的采樣周期為0.1，真實數(shù)據(jù)采樣間隔。在加熱器功率作用下，辨識所得最佳參數(shù)模型輸出與硅單晶熱場溫度系統(tǒng)真實輸出對比如圖4所示。

圖4表明，離線辨識所得最佳參數(shù)模型的輸出較好地擬合了熱場溫度的真實數(shù)據(jù)，從而說明了LEALO算法具有較好的離線參數(shù)辨識能力。

表3 參數(shù)辨識結(jié)果Table 3 The parameters identification results

圖4 加熱功率作用下熱場真實溫度和模型輸出對比Fig. 4 The contrast between true thermal field temperature and the output of model

4 結(jié)束語

作為一種新的尋優(yōu)算法，蟻獅算法具有調(diào)節(jié)參數(shù)少、尋優(yōu)精度高的特點。本文針對其缺點提出一種具有Levy變異和精英自適應競爭機制的LEALO算法。選擇部分較差的個體進行Levy變異，保證了種群豐富度從而實現(xiàn)對求解區(qū)域進行充分探索，可以有效提高種群全局搜索能力；多個精英之間的并行競爭，削弱了單個精英對種群的誤導，加快了尋優(yōu)的收斂速度，精英競爭的自適應操作在保證尋優(yōu)效率的同時，避免了較大的計算量。并與基本ALO算法及改進的MALO和CIALO算法進行對比，測試結(jié)果表明本文所提出的LEALO算法具有更好的尋優(yōu)精度和收斂速度。最后將LEALO算法應用于硅單晶熱場溫度模型的參數(shù)辨識，仿真結(jié)果說明了該算法具有較好的優(yōu)化能力。

[1]MIRJALILI S. The ant lion optimizer[J]. Advances in engineering software, 2015, 83: 80–98.

[2]SAXENA P, KOTHARI A. Ant lion optimization algorithm to control side lobe level and null depths in linear antenna arrays[J]. AEU-International journal of electronics and communications, 2016, 70(9): 1339–1349.

[3]HADIDIAN-MOGHADDAM M J, ARABI-NOWDEH S,BIGDELI M, et al. A multi-objective optimal Sizing and sit-ing of distributed generation using ant lion optimization technique[J]. Ain shams engineering journal, 2017, doi:10.1016/j.asej.2017.03.001.

[4]RAJU M, SAIKIA L C, SINHA N. Automatic generation control of a multi-area system using ant lion optimizer algorithm based PID plus second order derivative controller[J]. International journal of electrical power and energy systems, 2016, 80: 52–63.

[5]RAJAN A, JEEVAN K, MALAKAR T. Weighted elitism based ant lion optimizer to solve optimum VAr planning problem[J]. Applied soft computing, 2017, 55: 352–370.

[6]趙世杰, 高雷阜, 于冬梅, 等. 帶混沌偵查機制的蟻獅優(yōu)化算法優(yōu)化SVM參數(shù)[J]. 計算機科學與探索, 2016, 10(5):722–731.ZHAO Shijie, GAO Leifu, YU Dongmei, et al. Ant lion optimizer with chaotic investigation mechanism for optimizing SVM parameters[J]. Journal of frontiers of computer science and technology, 2016, 10(5): 722–731.

[7]REYNOLDS A. Liberating Lévy walk research from the shackles of optimal foraging[J]. Physics of life reviews,2015, 14: 59–83.

[8]何莉, 王淼, 李博. 面向單目標優(yōu)化的集成粒子群算法[J].重慶郵電大學學報: 自然科學版, 2017, 29(4): 527–534.HE Li, WANG Miao, LI Bo. Ensemble particle swarm optimizer for single objective optimization[J]. Journal of Chongqing university of posts and telecommunications: natural science edition, 2017, 29(4): 527–534.

[9]REYNOLDS A M. Cooperative random Lévy flight searches and the flight patterns of honeybees[J]. Physics letters A, 2006, 354(5/6): 384–388.

[10]朱顥東, 孫振, 吳迪, 等. 基于改進蟻群算法的移動機器人路徑規(guī)劃[J]. 重慶郵電大學學報: 自然科學版, 2016,28(6): 849–855.ZHU Haodong, SUN Zhen, WU Di, et al. Path planning for mobile robot based on improved ant colony algorithm[J].Journal of Chongqing university of posts and telecommunications: natural science edition, 2016, 28(6): 849–855.

[11]LEE C Y, YAO Xin. Evolutionary programming using mutations based on the levy probability distribution[J].IEEE transactions on evolutionary computation, 2004,8(1): 1–13.

[12]MANTEGNA R N. Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes[J]. Physical review E, 1994, 49(5): 4677–4683.

[13]JENSI R, JIJI G W. An enhanced particle swarm optimization with levy flight for global optimization[J]. Applied soft computing, 2016, 43: 248–261.

[14]江建. 精英自適應混合遺傳算法及其實現(xiàn)[J]. 計算機工程與應用, 2009, 45(27): 34–35, 101.JIANG Jian. Elite adaptive hybrid genetic algorithm and its realization[J]. Computer engineering and applications,2009, 45(27): 34–35, 101.

[15]周新宇, 吳志健, 王暉, 等. 一種精英反向?qū)W習的粒子群優(yōu)化算法[J]. 電子學報, 2013, 41(8): 1647–1652.ZHOU Xinyu, WU Zhijian, WANG Hui, et al. Elite opposition-based particle swarm optimization[J]. Acta electronica sinica, 2013, 41(8): 1647–1652.

[16]劉丁. 直拉硅單晶生長過程建模與控制[M]. 北京: 科學出版社, 2015: 1–3, 46–57.LIU Ding. Modeling and controlling of crystal growth in the Czochralski process[M]. Beijing: Science Press, 2015:1–3, 46–57.

[17]劉勝, 宋佳, 李高云. PSO并行優(yōu)化LSSVR非線性黑箱模型辨識[J]. 智能系統(tǒng)學報, 2013, 5(1): 51–56.LIU Sheng, SONG Jia, LI Gaoyun. Modeling a complex nonlinear system with particle swarm optimization and parallel-optimized least squares support vector regression[J].CAAI transactions on intelligent systems, 2013, 5(1): 51–56.