楊柳慶 楊婷婷 王鵬飛 張 勇

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

1 引 言

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

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

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

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

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

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

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

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

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

2.2 萊維飛行

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

利維飛行是一種步長(zhǎng)服從利維分布的隨機(jī)游走類型，其分布方程為

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

u和υ定義如下

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

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

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

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

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

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

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

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

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

為了對(duì)LEO 的測(cè)試結(jié)果進(jìn)行全面的分析，實(shí)驗(yàn)選取其它4 種智能算法進(jìn)行對(duì)比，算法的主要參數(shù)設(shè)置見(jiàn)表3。為了保證測(cè)試的有效性和準(zhǔn)確性，每種算法在單個(gè)基準(zhǔn)函數(shù)上分別獨(dú)立運(yùn)行30 次，記錄運(yùn)行結(jié)果的最優(yōu)值、最差值、平均值和標(biāo)準(zhǔn)差，所有的算法根據(jù)其標(biāo)準(zhǔn)差的大小進(jìn)行排序，此種排序方式可以看出哪種算法的運(yù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ù)和社會(huì)屬性常數(shù)。

高、低維基準(zhǔn)函數(shù)的測(cè)試結(jié)果分析見(jiàn)表4 和表5，總結(jié)了5 種算法在高維基準(zhǔn)函數(shù)中獨(dú)立運(yùn)行30次獲得的最優(yōu)、最差、均值和標(biāo)準(zhǔn)差的統(tǒng)計(jì)結(jié)果受版面限制，表4 中只展示f1～f3和f5～f12的結(jié)果（f3和f4結(jié)果基本相同），表5 中只展示f14～f22的結(jié)果。其中f1～f7為高維單峰函數(shù)，沒(méi)有局部最優(yōu)解，因此適用于測(cè)試算法的收斂速度。在表中可以看出，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 大?？梢钥闯鯣WO 在優(yōu)化f3和f4方面比LEO 具有更好的效果，LEO 的表現(xiàn)基本處于第3 的位置。

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

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

續(xù)表4

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

續(xù)表5

5 結(jié)束語(yǔ)

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