張九龍,王曉峰,蘆 磊,牛鵬飛
1.北方民族大學 計算機科學與工程學院,銀川750021
2.北方民族大學 圖像圖形智能處理國家民委重點實驗室,銀川750021
用于解決優化問題的方法叫作優化算法,它是基于某種思想或機制,通過一定的途徑或規則得到滿足問題要求的解的過程。傳統的優化算法如遺傳算法、蟻群算法、粒子群算法、模擬退火算法、禁忌搜索算法等,這類算法構造直觀,原理便于理解,通常被稱作智能優化算法(intelligent optimization algorithms,IOA)或現代啟發式算法(meta-heuristic algorithms,MA)。按照算法原理的不同,智能優化算法可以分為以下幾個大的類別:仿人智能類算法、進化類算法、群體智能類算法、仿植物生長類算法、仿自然類算法等。
仿人智能類算法是指一類包括模擬人腦思維、人體系統、組織、器官乃至細胞及人類社會競爭進化相關的算法,其中經典的算法有神經網絡算法、免疫算法、禁忌搜索算法、頭腦風暴算法、帝國主義競爭算法等。進化類算法是一類模仿自然界的生物在生殖繁育過程里,通過遺傳和變異及“優勝劣汰”自然選擇法則不斷進化的算法,在一些可行解組成的種群中,迭代進化尋求最優解。主要算法包括遺傳算法、差分進化算法、基因表達式編程算法等。群體智能類算法是從自然界群居生物的覓食、繁殖等行為或群體捕獵及生存策略中獲得靈感,設計模型對問題求解的優化算法,核心思想就是若干個簡單的個體構成一個群體,通過合作、競爭、交互與學習等機制實現高級和復雜的功能,在缺少局部信息和模型的情況下,仍能完成復雜問題的求解。其中代表性的算法有蟻群優化算法、粒子群優化算法、人工蜂群算法、布谷鳥搜索算法等。仿植物生長類算法指的是模擬花草樹木等植物在生長過程中表現出來的向光性、根的吸水性、種子繁殖、花朵授粉等特性而構造出的優化算法,主要算法有入侵雜草優化算法、森林優化算法、花朵授粉算法等。仿自然類優化算法是指模擬風雨云電等自然現象或物理、化學、數學定律等非線性科學的優化方法,其中較知名的算法有模擬退火算法、閃電搜索算法、引力搜索算法、熱傳遞搜索算法等。
隨著人工智能及工業技術的發展,對算法性能的要求越來越嚴格,然而一個算法在某些優化問題上表現出來的優異性能并不代表同樣適用于其他類型的優化問題,因此近年來不斷有新型智能優化算法提出,用于解決不同類型的優化問題。相較于傳統的智能優化算法,新型智能優化算法在收斂速度、求解時間、計算精度等不同方面各有側重,為解決優化問題提供了新的思路和方法。本文按照算法提出的時間選取了2015 年以來的若干新型智能優化算法,分別是2015 年提出的蝴蝶優化算法、飛蛾撲火優化算法,2016 年提出的正弦余弦優化算法,2017 年提出的蝗蟲優化算法,2019 年提出的哈里斯鷹優化算法和2020 年提出的麻雀搜索算法,本文詳細介紹了各算法的基本原理、算法流程和相關改進策略,并從求解的平均值、標準差、最優值、最差值、平均運行時間及收斂曲線6 個指標對算法性能對比分析,最后是對智能優化算法未來研究發展的展望。
Arora 等在2015 年提出一種新的元啟發式智能優化算法——蝴蝶優化算法(butterfly optimization algorithm,BOA),蝴蝶優化算法所涉及的主要公式如下:


蝴蝶優化算法的大致流程為:蝴蝶在迭代過程中產生一定的香味,依據香味濃度指導蝴蝶在搜索空間內移動,每次迭代生成一個隨機數與轉換概率進行比較來決定全局搜索或局部開發,循環迭代直至滿足終止條件算法結束。
蝴蝶優化算法原理簡單,便于理解,但和其他智能優化算法一樣,也存在容易陷入局部最優、收斂性差的問題。為此不斷有新的改進蝴蝶優化算法被提出來,選取了部分改進的相關文獻并從改進策略、優勢、局限和應用場景等方面歸納如表1 所示。
除表1 中列舉出的各種改進方法外,還有其他的一些改進和應用,如文獻[34]中,采用了可變感知模態參數策略,以提高蝴蝶優化算法的收斂速度。文獻[35]在BOA 中嵌入了學習自動機,利用學習自動機配置蝴蝶的行為,在全局搜索和局部開發之間建立適當的平衡。寧杰瓊等提出混合策略改進的蝴蝶優化算法,采用Circle 映射初始化蝴蝶個體的位置,通過動態切換概率控制正弦余弦算法與蝴蝶優化算法的轉換,將自適應余切權重系數引入位置更新中,并添加逐維辨析策略避免算法陷入局部最優。Rachapudi 等將蝴蝶優化算法用于染色圖像中細胞核的分割;李鵬等將改進蝴蝶優化算法和例子濾波的聯合算法用于鋰電池健康狀態預測。

表1 蝴蝶優化算法改進分析Table 1 Improvement analysis of BOA
飛蛾撲火算法(moth-flame optimization,MFO)是在2015 提出的一種群智能優化算法,該算法的靈感來源于自然界中飛蛾的橫向定位(transverse orientation)導航機制,以對數螺線形式更新位置的飛蛾撲火算法涉及到的主要公式有:

其中,M表示第只飛蛾;為螺旋形函數;F表示第個火焰;D表示第只飛蛾與第個火焰之間的距離;參數稱為極半徑,是定義對數螺旋形狀的常數;稱為收斂常數,是[-1,1]之間的隨機數,用于定義飛蛾下一個位置距離火焰的程度;為火焰數量;是火焰最大數量;為當前迭代次數;是最大迭代次數。
飛蛾撲火算法的大致流程為:初始化飛蛾種群,計算每只飛蛾的適應度值并選擇其中前個作為火焰。每次迭代均計算火焰和飛蛾的適應度值進行排序并更新角色。火焰數隨著迭代次數的增加而減少,一直迭代直到滿足終止條件算法結束。
飛蛾撲火算法的改進有很多,選取了部分改進的相關文獻并從改進策略、優勢、局限和應用場景等方面歸納如表2 所示。
除表2 中列舉出的各種改進方法外,還有其他的一些改進和應用,如王光等在算法中引入歷史最優火焰平均值的概念,改進飛蛾位置更新公式,使用隨機反向學習策略進行反向學習,引入折射原理對解進行折射操作。劉小龍在飛蛾撲火算法中引入縮放因子和視距因子的概念,在協同演化框架下,提出飛蛾直飛模型,使得算法解決大規模優化問題表現出較好的優越性和魯棒性。文獻[49]中定義了全局搜索和局部開發之間的混合階段,增加依賴適應度的權重因子來更新飛蛾的位置。文獻[50]將MFO 算法應用于混合無線寬帶接入網領域,提出一種新的基于自然啟發的多光纖網絡單元布局啟發式飛蛾撲火算法。文獻[51]中提出將飛蛾撲火算法和頻域法相結合,用于永磁同步電機控制器參數整定,提高了系統的快速跟蹤能力和抗干擾能力。

表2 飛蛾撲火算法改進分析Table 2 Improvement analysis of MFO
正弦余弦優化算法(sine cosine algorithm,SCA)是Mirjalili 教授2016 年提出的新型智能優化算法,正弦余弦優化算法所涉及的主要公式有:



正弦余弦優化算法的大致流程為:初始化種群,計算種群中個體的適應度值,更新參數、、、并根據式(7)不斷更新個體的位置,更新種群最優個體,持續迭代直至滿足終止條件算法停止。
很多學者對正弦余弦優化算法的改進不斷探索,選取了部分改進的相關文獻并從改進策略、優勢、局限和應用場景等方面歸納如表3 所示。

表3 正弦余弦優化算法改進分析Table 3 Improvement analysis of SCA
除表3 中列舉出的各種改進方法外,還有其他的一些改進和應用,如文獻[60]提出基于改進正弦余弦算法的極限學習機(modified sine cosine algorithmextreme learning machine,MSCA-ELM)并在腦部病理核磁共振圖像分類中得到了應用。于坤等將改進的正弦余弦算法與多種光譜線型擬合方法相結合,用于計算對應的光譜特征峰位置。文獻[62]將正弦余弦算法和遺傳算法混合用于數據挖掘中的特征選擇,取得了較好的效果。
蝗蟲優化算法(grasshopper optimization algorithm,GOA)是Saremi 等在2017 年提出的一種模仿自然界中蝗蟲遷徙及覓食的元啟發式智能優化算法。蝗蟲優化算法的主要公式如下:


蝗蟲優化算法的大致流程為:初始化種群位置及參數,通過式(9)及式(10)循環更新參數和蝗蟲位置并計算每個蝗蟲的適應度值,每次迭代保存種群中最好適應度值的個體,持續迭代并判斷迭代次數是否達到設定的最大值。若未達到最大迭代次數繼續迭代,否則退出循環并返回全局最優解。
蝗蟲優化算法與其他群智能優化算法一樣,存在一定缺陷。不斷有學者及研究人員對其進行改進,選取了若干改進的方法歸納如表4 所示。
除表4 中列舉出的各種改進方法外,還有其他的一些改進和應用,如王博等在此基礎上進一步提出混合多目標蝗蟲優化算法,利用Halton 序列進行種群初始化,由差分變異算子引導種群更新并加入自適應權重因子,提高了算法優化效率和解集質量。文獻[72]提出基于反向學習策略改進的蝗蟲優化算法,第一階段使用反向學習策略生成初始種群,第二階段使用反向學習作為附加階段在每次迭代中更新蝗蟲種群,通過基準函數及工程問題驗證了算法有較好的性能。Arora 等將混沌理論引入GOA 的優化過程中利用混沌映射在局部開發和全局搜索間做到有效平衡。文獻[74]將蝗蟲優化算法用于數據聚類。潘峰等使用蝗蟲算法進行尋優求解最佳閾值,并利用最佳閾值對圖像進行分割等。

表4 蝗蟲優化算法改進分析Table 4 Improvement analysis of GOA
哈里斯鷹優化算法(Harris hawks optimization,HHO)是Heidari 等在2019 年提出的一種新型群智能優化算法,哈里斯鷹優化算法主要包括探索階段和開發階段。
探索階段的主要公式為:

式中,為當前種群中隨機選擇的個體;為當前最優個體;X為種群個體的平均位置;、、、均為0 到1 之間的隨機數;和分別為種群的上下邊界;為種群數量。
探索階段到開發階段的轉換公式為:

式中,代表控制算法全局搜索和局部開發的逃逸能量因子;是-1 到1 的隨機數;為當前迭代次數;為最大迭代次數。
開發階段軟包圍公式有:

開發階段硬包圍公式為:

開發階段漸進軟包圍公式有:

其中,為Lévy 飛行函數,參數取值為1.5。
開發階段漸進硬包圍公式:

開發階段中Δ為最優個體和當前個體的差值,是0到1之間的隨機數,為逃跑過程中的跳躍距離,是問題的維度,是一個維的隨機向量。
哈里斯鷹優化算法的大致流程為:初始化種群,將適應度最優的個體設置為獵物,根據逃逸能量和生成的隨機數執行全局搜索或局部開發中對應的包圍策略。計算每個個體的適應度并與獵物適應度比較,若位置更新后的個體適應度值優于獵物,則以適應度值更優的個體位置作為新的獵物位置,不斷迭代直至滿足終止條件或達到最大迭代次數算法終止。
自HHO 算法面世后,關于該算法的各種改進相繼被提出來,選取了若干改進的方法歸納如表5所示。
除表5 中列舉出的各種改進方法外,還有其他的一些改進和應用,如文獻[83]中發現逃逸能量因子采用指數遞減策略能夠有更快的收斂速度和更高的求解精度。哈里斯鷹優化算法在圖像分割、神經網絡訓練等各領域也得到廣泛運用。

表5 哈里斯鷹優化算法改進分析Table 5 Improvement analysis of HHO
麻雀搜索算法(sparrow search algorithm,SSA)是由Xue 等于2020 年提出的群智能優化算法,SSA 算法涉及到的主要公式如式(25)~(27)所示:







麻雀搜索算法的基本流程:初始化麻雀種群,計算個體的適應度值并排序,找到最佳和最差適應度的個體,依次更新發現者、加入者、警戒者位置,不斷迭代更新,直至滿足算法終止條件算法終止。
有關麻雀搜索算法的相關改進也有很多,選取了若干改進的方法歸納如表6 所示。

表6 麻雀搜索算法改進分析Table 6 Improvement analysis of SSA
除表6 中列舉出的各種改進方法外,麻雀搜索算法還有其他的一些改進和應用,如史春天等歸納的麻雀搜索算法在應用于圖像分割時各種有效的改進策略。
為對比分析6 種智能優化算法的優缺點,本文從若干優化文獻[95-97]中選取3 種類型共21 個基準測試函數進行仿真實驗用于評價算法的性能。其中~為高維單峰測試函數,~為高維多峰測試函數,~為低維度多峰函數測試函數。單峰測試函數可以評估算法的開發能力及開發精度,多峰測試函數可以評估算法跳出局部最優解的能力。各測試函數的詳細信息見表7~表9。

表7 單峰測試函數Table 7 Single peak test function

表8 多峰測試函數Table 8 Multimodal peak test function

表9 固定維度測試函數Table 9 Fixed dimension test function
為減少統計誤差并產生有說服力的結果,每個算法進行30 次獨立實驗。實驗環境為:操作系統Windows 10,處理器為IntelXeonGold 6154 CPU@3.00 GHz,內存為32 GB,集成開發環境為Matlab_R2017b。種群設置為50,最大迭代次數1 000次,算法所設置的其他初始參數如表10 所示。

表10 算法控制參數的初始值Table 10 Initial value of control parameters
針對21 個基準測試函數,通過算法找到解的平均值、最優值、最差值、標準差、平均運行時間和收斂曲線等六方面評價算法的性能。平均值用于衡量算法的優化精度,最優值和最差值反映解的質量,標準差反映算法的穩定性和魯棒性,平均運行時間反映算法執行的時間代價,收斂曲線反映算法的收斂情況,綜合比較平均值和標準差得到算法的排名,計算算法在21 個測試函數排名的平均值作為Mean rank 值。
統計6 個智能優化算法在21 個基準測試函數上的求解結果得到表11,表中參數mean 表示求解平均值,std 表示標準差,best 代表最優值,worst 代表最差值。分析表11 可知,對于本文選擇的21 個測試函數,總體上看,HHO 和SSA 尋優能力明顯強于其他算法,且HHO 相較于SSA 效果更好,BOA 和SCA 尋優效果處于中等水平,GOA 和MFO 的求解效果較差。在高維單峰函數~上,HHO 和SSA 表現出優秀的求解精度,所求得解的平均值與全局最優值十分接近,30 次實驗中的標準差小,效果最好。BOA 效果較好,平均值和標準差也在可接受的范圍內,SCA 和GOA效果一般,MFO 所求得解的平均值與真實的全局最優解有較大差距,多次實驗得到的最優值也遠不及其他算法,效果最差。在高維多峰函數~上,HHO 和SSA 在函數和中找到了全局最優值,BOA在函數中找到了全局最優值,整體上看,HHO和SSA 效果最好,BOA 效果次之,SCA 和GOA 效果一般,MFO 效果最差,測試結果與高維單峰函數測試的結果基本一致。需要注意的是MFO 在和中,所求得解的平均值與真實的全局最優解有極大差距。在低維多峰函數~上,測試結果與單峰和多峰函數上的結果出現差異,SSA 在5 個函數上取得較好效果,MFO 在2 個函數上取得較好的效果,MFO 和SSA 效果較好,GOA 和HHO 效果次之,BOA和SCA 效果較差。

表11 測試函數優化結果Table 11 Test function optimization results

表11 (續)
為驗證6 個算法的穩定性與收斂性,列出了各算法在部分單峰測試函數和多峰測試函數上的收斂性對比圖,如圖1 所示。MFO、SCA 和GOA 算法在處理單峰測試函數和多峰測試函數時均存在早熟收斂現象。哈里斯鷹算法和麻雀搜索算法在少數測試函數中也存在早熟收斂,但求解的精度優于其他算法。哈里斯鷹算法在求解單峰測試函數、、和時,迭代至750 次左右收斂,此時的求解精度遠好于其他算法。蝴蝶搜索算法在多峰測試函數、、時性能表現較好,隨迭代次數的增加求解的精度不斷提升。哈里斯鷹算法和麻雀搜索算法在求解多峰函數和時,迭代到300 次左右找到了全局最優解,在其他多峰函數上的求解精度也高于其他算法,說明這兩個算法能在全局搜索和局部開發間維持較好的平衡。
根據圖1 縱向分析,在相同的迭代次數下,哈里斯鷹算法和麻雀搜索算法可以取得較高求解精度;根據圖1 橫向分析,各算法達到相同求解精度時哈里斯鷹算法和麻雀搜索算法只需要較少的迭代次數便能實現。在BOA 算法中蝴蝶有兩種搜索方式,全局搜索時向著香味濃度最高的蝴蝶飛行,局部開發時在種群中隨機選擇一只蝴蝶向其移動。通過分析圖1 可以發現,蝴蝶優化算法在處理測試函數時,收斂精度不高,整個群體雖然向著解中心聚集,但多次迭代浪費在隨機找蝴蝶移動上,種群多樣性一旦降低,沒有相應策略幫助跳出局部最優解,即使增加最大迭代次數,效果提升也不大。結合表11 可以看出,BOA 在求解函數時表現出極大的誤差,不是算法求解效果都差,而是在實驗中某次產生的巨大誤差拉大了多次實驗求解的平均值,說明BOA 算法存在一定的不穩定性。MFO 算法中以對數螺線的更新機制更新飛蛾的位置信息,與蝴蝶優化算法相比,蝴蝶算法的位置更新目標在最優蝴蝶和隨機蝴蝶中選擇,而飛蛾的位置更新則是以火焰為基準,隨迭代次數的增加,飛蛾與火焰間的距離變短,飛蛾飛行的振幅越來越小,逐漸由全局搜索轉向局部開發,同時火焰數量的減少也帶來種群多樣性降低,在求解多峰函數時多次較早陷入局部最優。再結合表11 不難看出,MFO 在函數、、求解中出現了巨大誤差,穩定性比BOA 更差。正弦余弦優化算法基于正弦和余弦數學模型在求解過程中使得種群向外或向最優解的方向波動,算法原理簡單,所需初始參數少,利用多個隨機變量和控制參數來計算當前解所在的位置,全局搜索能力強但搜索精度不夠,隨迭代次數的增加控制參數逐漸減小,使得正弦余弦算法函數振動幅度變小,全局搜索能力減弱,局部開發能力增強,同時帶來種群多樣性降低的問題,種群個體聚集在搜索空間的一個或幾個位置,結合在、、、函數上的收斂曲線,進一步證實算法容易出現早熟收斂現象。蝗蟲優化算法中參數的作用是平衡算法全局搜索和局部開發的過程,自適應減小蝗蟲間的排斥力,用以提升種群密度。在蝗蟲位置更新過程中,位置差的蝗蟲出現適應度值一直波動的情況,適應度值下降緩慢,且適應度值差的蝗蟲也參與蝗蟲位置的更新,對位置較好的蝗蟲產生了干擾,降低了算法的收斂速度。如在、、、、函數上的收斂曲線出現陷入局部最優的現象。哈里斯鷹優化算法中有4 個位置更新策略,可以根據獵物的行為做出必要的調整,通過一個能量逃逸因子和一個隨機數來決定使用哪個包圍策略,有更強的普適性。在所選取的21 個基準測試函數中,除去、、、、外均有優秀的求解效果,在處理高維單峰測試函數~時,迭代750 次左右完全收斂,在高維多峰測試函數上也比其他算法收斂得更快,求解精度更高。麻雀搜索算法通過將種群個體分為發現者、追隨者和警戒者3 個角色,各角色有不同的功能,在測試函數上表現出很強的尋優能力,在某些測試函數如、、、上效果比HHO 算法更優秀。但麻雀算法收斂于最優解的方式是部分發現者直接跳躍至當前最優解附近,收斂速度快的同時使得種群多樣性迅速減少,因此麻雀搜索算法仍存在容易陷入局部最優的問題。HHO 算法個體位置更新公式(15)和SSA 算法個體位置更新公式(25)中都存在向原點靠近的行為,這一行為使得兩個算法在算法執行到算法后期時,整個種群大致分為兩個群體,一部分聚集在原點附近,另一部分聚集在當前最優解附近。麻雀搜索算法位置更新策略相較于哈里斯鷹算法更為單一,當全局最優解在原點附近時可以取得較好的求解效果,而哈里斯鷹算法中的4 種包圍策略對于全局最優解不在原點附近的優化問題也能進行不錯的求解,因此HHO 對于問題的普適性優于SSA 算法。

圖1 各算法在測試函數上收斂曲線對比Fig.1 Comparison of convergence curves of each algorithm on test functions
統計各算法在測試函數上的運行時間得到表12。通過表12 可以看出,6 個算法平均執行時間最短的是正弦余弦優化算法,執行時間最長的是蝗蟲優化算法。正弦余弦優化算法中,使用一個線性遞減的控制參數改變函數的振幅幫助尋優,相較于其他算法沒有單獨設置跳出局部最優的步驟,很大程度上降低了算法的時間復雜度。而蝗蟲優化算法中,每只蝗蟲個體位置信息的更新都需要除它本身之外其余所有蝗蟲的位置信息,與其他算法相比個體更新位置的成本更大,時間復雜度更高,因此耗費的時間也更多。

表12 各算法的執行時間Table 12 Execution time of each algorithm s
結合6 個算法在21 個測試函數上的表現,從求解平均值、標準差、最優值、最差值、收斂曲線和運行時間等各個方面定性分析算法的尋優能力,可以發現在6 個算法中,蝴蝶優化算法在解決具有多個局部最優解的問題上表現出較好的精度,在尋優能力和求解時間上明顯優于一些經典的智能算法,原理簡單,易于實現,沒有明顯的短板。飛蛾撲火算法在求解高維測試函數時容易出現較大誤差,但求解低維多峰問題時求解效果較好,時間成本不高,適合應用于工程實踐中的參數優化。正弦余弦優化算法求解時所消耗的實踐成本明顯低于其他算法,適合應用于對精度要求不高,但對時間要求嚴苛的場景中。蝗蟲優化算法存在時間成本高,求解精度不佳等問題,但若將其改進為分布式計算方式,可大幅度降低求解的時間成本。哈里斯鷹優化算法在運行時間和求解精度上優于其他5 個算法,跳出局部最優的能力強,在應對復雜問題時有更高的包容性,但其算法構成復雜,對于具體實際問題進行算法實現時具有一定難度。麻雀搜索算法在提升求解精度的同時運行時間并未大幅度增加,應對全局最優解靠近原點附近的優化問題時能表現出優秀的性能。需要注意的是本文得出的結論只是基于實驗所得的數值結果,各算法的具體求解性能還要依據實際問題進行分析。
智能優化算法的尋優過程總體可以分為兩部分,全局搜索和局部開發。這兩部分相互促進又相互矛盾,全局搜索用于快速定位最優解的范圍,而局部開發用于鎖定最優解存在的區域并進一步尋找最優解,只有兩部分達到一個良好的平衡狀態才能有較好的求解效果。當算法偏重全局搜索時,算法執行慢,效率低,很難找到一個滿意的解,尤其是問題規模達到一定程度,這種缺陷顯得更為突出;而算法側重于局部開發時,會降低種群多樣性,使算法容易陷入局部最優。對智能優化算法的改進多數也是從這兩個角度入手,具體算法的改進要依據實際問題具體分析。設計出收斂速度快,求解精度高,跳出局部最優能力強,且普適性、魯棒性和穩定性優秀的智能優化算法是學者們不斷追尋的目標。
本文挑選了2015 年以來提出的六種新型智能優化算法,詳細闡述了每種智能優化算法的基本原理和算法流程,梳理了相關的改進方法和應用場景,并通過基準測試函數從求解平均值、標準差、最優值、最差值、收斂曲線和運行時間六方面分析了算法的尋優能力,對比發現近兩年提出的哈里斯鷹算法和麻雀搜索算法在求解精度、收斂速度、執行時間等方面有較好的效果。目前智能優化算法處于快速發展的時期,針對不同領域不同類型的問題不斷有新的智能優化算法被提出來,這些智能優化算法的涌現為解決優化問題提供了新的思路和靈感。未來的智能優化算法在實際應用和工程領域將會有更廣闊的應用前景。