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

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

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

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

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

1 蟻獅優化算法及其缺點

1.1 ALO算法原理

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

1.1.1 蟻獅修筑陷阱

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

1.1.2 螞蟻隨機游走

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

1.1.3 螞蟻進入陷阱

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

1.1.4 螞蟻滑落穴底

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

1.1.5 蟻獅重筑陷阱

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

1.1.6 螞蟻種群精英化

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

1.2 ALO算法缺點

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

2 改進算法(LEALO)

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

2.1 Levy變異機制

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

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

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

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

2.2 精英自適應競爭機制

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

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

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

2.3 LEALO算法執行偽代碼

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個標準函數測試LEALO算法的尋優精度和收斂速度，測試函數設置見表1。其中f1、f2為單峰函數，為多峰函數。

表1 標準測試函數Table 1 Standard test functions

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

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

表2 LEALO、CIALO、MALO 3種改進優化算法的測試結果對比Table 2 Test results comparison of LEALO、CIALO and MALO

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

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

3.2 硅單晶熱場溫度模型參數的辨識

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

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

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

表3 參數辨識結果Table 3 The parameters identification results

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

4 結束語

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

[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]趙世杰, 高雷阜, 于冬梅, 等. 帶混沌偵查機制的蟻獅優化算法優化SVM參數[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]何莉, 王淼, 李博. 面向單目標優化的集成粒子群算法[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]朱顥東, 孫振, 吳迪, 等. 基于改進蟻群算法的移動機器人路徑規劃[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]江建. 精英自適應混合遺傳算法及其實現[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]周新宇, 吳志健, 王暉, 等. 一種精英反向學習的粒子群優化算法[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并行優化LSSVR非線性黑箱模型辨識[J]. 智能系統學報, 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.