一種基于萊維飛行的新型改進平衡全局優(yōu)化算法

楊柳慶 楊婷婷 王鵬飛 張 勇

（1.南京航空航天大學(xué)無人機研究院，江蘇南京210016；2.南京航空航天大學(xué)中小型無人機先進技術(shù)工業(yè)和信息化部重點實驗室，江蘇南京210016；3.南京航空航天大學(xué)自動化學(xué)院，江蘇南京210016）

1 引 言

科學(xué)和工程應(yīng)用中的大部分優(yōu)化問題都非常復(fù)雜，具有挑戰(zhàn)性。傳統(tǒng)方法傾向于使用特定問題的信息指導(dǎo)產(chǎn)生解決方案，因此傳統(tǒng)方法是高度特色化的，普適性不強，傳統(tǒng)方法具有線性編程和凸優(yōu)化［1］的特點，同時有很多缺陷和不足，比如解決問題過程極其復(fù)雜、易陷入局部最優(yōu)解。傳統(tǒng)方法已經(jīng)很難解決當(dāng)前面臨的工程應(yīng)用問題，當(dāng)前的趨勢之一是使用元啟發(fā)式算法，該算法大多數(shù)源于各種自然現(xiàn)象，可分為基于自然進化（EA）的算法、基于物理學(xué)技術(shù)的算法和群智能算法（SI）三大類。其中，最受歡迎和最具代表性的算法是群智能算法中的粒子群優(yōu)化算法［2］（PSO）和蟻群優(yōu)化算法（ACO）［3］。除了這兩種算法，還有很多有效的元啟發(fā)式算法，這些算法的特點是計算簡單、不需要使用優(yōu)化問題的派生信息，而且能在不改變算法結(jié)構(gòu)的情況下解決多種類型的優(yōu)化問題。

平衡優(yōu)化算法（EO）［10］是Afshin Faramarzia 和Mohammad Heidarinejad 于2020年提出的一種基于物理學(xué)技術(shù)的算法，受動態(tài)資源和庫模型的啟發(fā)，該算法用于估計平衡狀態(tài)。算法基于控制體積的動態(tài)質(zhì)量平衡，其中質(zhì)量平衡方程根據(jù)各種資源庫模型來描述控制體積中非反應(yīng)性成分的濃度。萊維飛行策略有助于在探索和開發(fā)之間獲得更好的平衡，并且在很大程度上可以防止陷入局部最優(yōu)解。因此，本文提出一種基于萊維飛行的改進EO算法，稱為LEO，其目的在于對EO 進行優(yōu)化，提高EO 的收斂速度和最優(yōu)解的質(zhì)量。LEO 經(jīng)過23 種基準(zhǔn)函數(shù)模型進行了測試和仿真，并與其它5 種元啟發(fā)式算法進行比較，仿真結(jié)果表明LEO 可行且有效，在性能方面比EO 有較大提升。

本文詳細(xì)介紹了原始平衡優(yōu)化算法和萊維飛行的飛行軌跡，描述了LEO 的研究細(xì)節(jié)。建立了新型全局優(yōu)化算法LEO 的數(shù)學(xué)模型和算法流程，采用23 種基準(zhǔn)函數(shù)模型對LEO 算法進行實驗驗證，并對實驗結(jié)果進行論證、分析和總結(jié)。

2 平衡優(yōu)化算法和萊維飛行策略

2.1 平衡優(yōu)化算法

平衡優(yōu)化算法是一種新提出的元啟發(fā)式算法，其靈感來源于在控制體積上進行簡單混合的動態(tài)質(zhì)量平衡。在平衡優(yōu)化算法中，粒子類似于溶液，濃度類似于粒子優(yōu)化算法（PSO）中粒子的位置。使用質(zhì)量平衡方程來描述控制體積中非反應(yīng)性成分的濃度，該濃度取決于各種源匯機制。質(zhì)量平衡方程為控制體積過程中物體進入、離開和生成的質(zhì)量守恒提供了基本物理原理。質(zhì)量平衡的通用方程式由式（1）給出的一階常微分方程表示

式中:V——控制體積；C——控制體積濃度；Ceq——在控制體積內(nèi)沒有任何生成的平衡態(tài)濃度；G——質(zhì)量生成速率；——質(zhì)量變化速率；Q——流入和流出控制體積的體積流量。

其中，F(xiàn)可用于估算已知流失率對照體積的濃度，或者用于計算具有已知發(fā)生率和其它條件的簡單線性回歸的平均流失率。

平衡狀態(tài)是算法的收斂狀態(tài)，并且希望是所考慮問題的全局最優(yōu)解。在優(yōu)化過程的初始狀態(tài)，平衡濃度是未知狀態(tài)，平衡候選對象為粒子提供了搜索模式。根據(jù)在多種類型優(yōu)化問題下進行的不同實驗，將候選對象確定為優(yōu)化過程中的四個最佳粒子，四個粒子濃度的算數(shù)平均值組成平衡池。這四個候選對象，即四個濃度有助于提高EO 的探索能力，算術(shù)平均值有助于提高EO 的開發(fā)能力。平衡池的向量表示為

2.2 萊維飛行

萊維飛行是一種隨機游走類型，服從萊維分布的隨機搜索方法，是一種短距離的搜索和偶爾較長距離的行走相交叉的行走方式，這種行走方式可以使得萊維飛行具有較好的全局搜索能力。萊維飛行軌跡最初是由Lévy 提出的，后來Benoit Mandelbrot 對其進行了詳細(xì)描述。萊維飛行策略已經(jīng)被廣泛應(yīng)用于優(yōu)化問題和最優(yōu)搜索，具有廣闊的發(fā)展前景。

利維飛行是一種步長服從利維分布的隨機游走類型，其分布方程為

其中，λ=1 +β，利維飛行是隨機行走的一種特殊類型，其步長的概率分布服從重尾分布，將利維飛行步長s定義為

u和υ定義如下

其中，α0=0.01，β=3/2；u和υ從正態(tài)分布μ=中選擇。

3 基于萊維飛行的改進平衡優(yōu)化算法

平衡優(yōu)化算法（LEO）在解決單峰優(yōu)化問題時表現(xiàn)良好，但是在處理多峰優(yōu)化問題時，EO 獲得的解決方案并不理想?？梢园l(fā)現(xiàn)EO 具備較好的開發(fā)能力和收斂速度，但容易陷入局部最優(yōu)解，全局搜索能力不強，收斂性不高，因此，本文提出一種改進的平衡優(yōu)化算法（LEO）。萊維飛行可以使搜索代理的多樣性最大化，這樣既能保證算法的全局搜索能力，又能防止算法陷入局部最優(yōu)解，即萊維飛行軌跡有助于EO 在探索能力和開發(fā)能力之間取得更好的平衡。改進的平衡優(yōu)化算法使用萊維飛行軌跡來更新位置，表示如下

必須指出，sign（rand-1/2）只有3 個有效值分別為:1，0 和-1。Levy表示萊維飛行的隨機游走方程。

本文的改進策略，即在EO 中加入萊維飛行策略，有助于基本的EO 跳出局部最優(yōu)值，萊維飛行軌跡的步長通常是很小的，但有時會出現(xiàn)較大的步長，因此，從長遠(yuǎn)來看，加入萊維飛行策略可以確保粒子可以有效地在搜索空間里進行搜索，提高粒子的搜索能力。同時，這種方法可以增加EO 解決方案的多樣性，提高算法的全局搜索能力，對于單峰和多峰基準(zhǔn)函數(shù)來說，改進的EO 可以提供更有意義的結(jié)果。改進的EO（LEO）流程圖如圖1 所示，其在解決優(yōu)化問題中的性能將在第4 節(jié)中通過基準(zhǔn)函數(shù)和仿真實驗來進行驗證。

圖1 LEO 流程圖Fig.1 LEO flow chart

4 仿真實驗

為了更好地驗證LEO 的性能，第4 節(jié)內(nèi)容設(shè)計了無約束的優(yōu)化問題測試實驗，對LEO 進行全面地研究分析。實驗選取23 個基準(zhǔn)函數(shù)分別進行測試，并與其它幾種智能優(yōu)化算法的結(jié)果相比較。

高維基準(zhǔn)函數(shù)具體參見文獻［11］，包括高維單峰基準(zhǔn)函數(shù)（f1～f7）和高維多峰基準(zhǔn)函數(shù)（f8～f23），高維單峰基準(zhǔn)函數(shù)只有唯一的全局最優(yōu)解，可以有效測試算法的開發(fā)和收斂性，而高維多峰基準(zhǔn)函數(shù)則具有更多的局部最優(yōu)解，用于測試算法跳出局部最優(yōu)解的能力。因此，算法的探索能力和避免局部最小值的能力可以由多峰函數(shù)來測試，見表1 和表2。

表1 高維基準(zhǔn)函數(shù)Tab.1 High-dimension benchmark functions

表2 低維基準(zhǔn)函數(shù)Tab.2 Low-dimension benchmark functions

表1 中，由于函數(shù)f1～f7特性類似，因此表1 只顯示f1為例，f12和f13特性類似，表中只顯示f13。表2 中，由于函數(shù)f15～f17特性類似，因此表1 只顯示f15為例，同樣的，f21～f23特性類似，表中只顯示f23。

為了對LEO 的測試結(jié)果進行全面的分析，實驗選取其它4 種智能算法進行對比，算法的主要參數(shù)設(shè)置見表3。為了保證測試的有效性和準(zhǔn)確性，每種算法在單個基準(zhǔn)函數(shù)上分別獨立運行30 次，記錄運行結(jié)果的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差，所有的算法根據(jù)其標(biāo)準(zhǔn)差的大小進行排序，此種排序方式可以看出哪種算法的運行結(jié)果更加穩(wěn)定。

表3 比較算法參數(shù)設(shè)置Tab.3 Comparison algorithm parameter settings

表3 中，EO 算法中a1是表示控制搜索能力的常數(shù)，a2表示算法的搜索能力，GP表示生成概率。GWO 中，a表示收斂參數(shù)，t和T 分別表示當(dāng)前迭代次數(shù)和最大迭代次數(shù)。PSO 中，wmax和wmin分別表示最大和最小慣性權(quán)重，c1和c2分別表示認(rèn)知常數(shù)和社會屬性常數(shù)。

高、低維基準(zhǔn)函數(shù)的測試結(jié)果分析見表4 和表5，總結(jié)了5 種算法在高維基準(zhǔn)函數(shù)中獨立運行30次獲得的最優(yōu)、最差、均值和標(biāo)準(zhǔn)差的統(tǒng)計結(jié)果受版面限制，表4 中只展示f1～f3和f5～f12的結(jié)果（f3和f4結(jié)果基本相同），表5 中只展示f14～f22的結(jié)果。其中f1～f7為高維單峰函數(shù)，沒有局部最優(yōu)解，因此適用于測試算法的收斂速度。在表中可以看出，LEO 在單峰基準(zhǔn)函數(shù)中表現(xiàn)出極佳的性能，能比其它算法更有效地找到最優(yōu)解。LEO 在f1、f2、f6、f7中的表現(xiàn)優(yōu)異，其標(biāo)準(zhǔn)差也小于其它算法。在f5中，LEO 相比其它算法準(zhǔn)確地找到了最優(yōu)解，但標(biāo)準(zhǔn)差比GWO 大。可以看出GWO 在優(yōu)化f3和f4方面比LEO 具有更好的效果，LEO 的表現(xiàn)基本處于第3 的位置。

f8～f13為高維多峰基準(zhǔn)函數(shù)，具有多個局部最優(yōu)解，可用于檢測函數(shù)跳出局部最優(yōu)解的能力。從表5 中可以看出，在f9～f14中，LEO 表現(xiàn)出的性能都遠(yuǎn)高于其它4 種算法，不僅能比其它算法更有效地找到全局最優(yōu)解，而且標(biāo)準(zhǔn)差也小于其它算法?？傮w來看，不論單峰函數(shù)還是多峰函數(shù)，所有的統(tǒng)計結(jié)果都顯示LEO 的優(yōu)越性能。

表4 高維基準(zhǔn)函數(shù)測試結(jié)果Tab.4 High-dimension benchmark function test results

續(xù)表4

表5 低維基準(zhǔn)函數(shù)測試結(jié)果Tab.5 Low-dimension benchmark function test results

續(xù)表5

5 結(jié)束語

本文將萊維飛行（Lévy flight）和平衡優(yōu)化算法（EO）相結(jié)合提出一種新型的全局優(yōu)化算法（LEO），并給出了新型全局優(yōu)化算法的數(shù)學(xué)模型和算法流程。新算法保證了算法中全局搜索和局部開發(fā)之間平衡性，具有跳出局部最優(yōu)解的能力。將該算法應(yīng)用于基準(zhǔn)測試函數(shù)求解以測試算法性能，通過與主流智能算法對比，優(yōu)化結(jié)果表明新算法在解決優(yōu)化問題方面表現(xiàn)更為優(yōu)越，該算法后續(xù)將應(yīng)用于無人機航路規(guī)劃和任務(wù)分配等工程問題。