李永鈺，馬 良，劉 勇

上海理工大學(xué) 管理學(xué)院，上海 200093

目前智能優(yōu)化算法發(fā)展迅速，出現(xiàn)了許多具有代表性的優(yōu)化算法。其中，受生物學(xué)原理的啟發(fā)提出的群體智能優(yōu)化算法是一類(lèi)較為常見(jiàn)的優(yōu)化算法，它們是從自然界群居生物的覓食、繁殖等行為或群體捕獵及生存策略中獲得靈感，設(shè)計(jì)模型對(duì)問(wèn)題進(jìn)行求解的優(yōu)化算法，例如蟻群優(yōu)化算法、粒子群優(yōu)化算法、鯨魚(yú)優(yōu)化算法和哈里斯鷹優(yōu)化算法等。自上述算法提出以來(lái)，眾多學(xué)者針對(duì)其不足提出改進(jìn)，并將其應(yīng)用于解決不同類(lèi)型的優(yōu)化問(wèn)題[1]。例如文獻(xiàn)[2]將粒子群優(yōu)化算法進(jìn)行改進(jìn)，并應(yīng)用于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域；文獻(xiàn)[3]利用改進(jìn)群智能優(yōu)化算法，進(jìn)行全局域中混沌局部的同步搜索，實(shí)現(xiàn)海上物流配送路徑優(yōu)化。

此外，還有受物理學(xué)原理的啟發(fā)提出的優(yōu)化算法。模擬退火算法就是一個(gè)經(jīng)典的基于物理學(xué)原理的優(yōu)化算法，其核心思想是模擬金屬熱浴之后的緩慢降溫（退火）達(dá)到能量最低態(tài)（即常溫固態(tài)）的過(guò)程，以隨機(jī)“跳阱”策略克服局部搜索法的缺陷，搜索優(yōu)化問(wèn)題的全局最優(yōu)解[4]；引力搜索算法是受到牛頓萬(wàn)有引力定律的啟發(fā)而提出的優(yōu)化算法，其讓種群粒子具有質(zhì)量，且質(zhì)量根據(jù)粒子的適應(yīng)度值進(jìn)行計(jì)算[5]；隨機(jī)分形搜索算法利用分形的擴(kuò)散特性進(jìn)行尋優(yōu)，算法的擴(kuò)散過(guò)程采用高斯隨機(jī)游走方式來(lái)開(kāi)發(fā)問(wèn)題的搜索空間，而更新過(guò)程則分別對(duì)個(gè)體的分量及個(gè)體本身采用相應(yīng)的更新策略來(lái)進(jìn)行更新，以此進(jìn)行全局搜索和局部搜索[6]。隨著求解的問(wèn)題逐漸呈現(xiàn)出大規(guī)模、高難度和不確定性等特點(diǎn)，近年來(lái)不斷有新型智能優(yōu)化算法提出，用于解決不同類(lèi)型的優(yōu)化問(wèn)題。

Lichtenberg 算法（Lichtenberg algorithm，LA）是由Pereira等人于2021年提出的一種新型智能優(yōu)化算法[7]，它是受閃電傳播這一物理現(xiàn)象啟發(fā)而產(chǎn)生的，算法以Lichtenberg 圖形（Lichtenberg figure，LF）來(lái)模擬閃電在空中生成的圖形。LF是分形圖的一種。與其他基于物理學(xué)原理的智能優(yōu)化算法相比，LA算法具有概念簡(jiǎn)單、容易實(shí)現(xiàn)等優(yōu)點(diǎn)。

目前，對(duì)LA算法的研究還處于起步階段。文獻(xiàn)[7]將LA算法應(yīng)用于對(duì)復(fù)合材料機(jī)械結(jié)構(gòu)的復(fù)雜逆損傷問(wèn)題進(jìn)行識(shí)別和評(píng)價(jià)，將其與遺傳算法和向日葵優(yōu)化算法進(jìn)行對(duì)比。實(shí)驗(yàn)證明，LA算法可以有效地識(shí)別損傷，而且即使在噪聲響應(yīng)低和損傷嚴(yán)重性大的特定情況下，它也能夠檢測(cè)到損傷。文獻(xiàn)[8]首次將LA 算法應(yīng)用于識(shí)別薄板類(lèi)結(jié)構(gòu)裂紋的問(wèn)題，用LA 算法生成表征裂紋的變量，若存在裂紋，則識(shí)別其擴(kuò)展方向和強(qiáng)度。實(shí)驗(yàn)結(jié)果表明LA算法在表征邊緣裂紋的擴(kuò)展方向和強(qiáng)度方面展現(xiàn)出了優(yōu)異的效果。文獻(xiàn)[9]使用LA 算法對(duì)假肢結(jié)構(gòu)模型參數(shù)進(jìn)行優(yōu)化，并與粒子群優(yōu)化算法進(jìn)行了對(duì)比，驗(yàn)證了LA算法的優(yōu)良性能。不僅如此，假肢結(jié)構(gòu)還可以根據(jù)用戶(hù)需求進(jìn)行制造和使用，并且可以利用LA算法分析各參數(shù)對(duì)假肢結(jié)構(gòu)體的影響，并制作出最適合使用者的假肢結(jié)構(gòu)。

上述研究成果表明了LA算法在求解工程應(yīng)用問(wèn)題上良好的效果。與此同時(shí)，LA算法和其他智能優(yōu)化算法一樣，也存在著過(guò)早收斂、易陷入局部最優(yōu)等問(wèn)題。針對(duì)上述問(wèn)題，本文提出融合分區(qū)導(dǎo)向搜索與自適應(yīng)擴(kuò)散更新的新型Lichtenberg算法（novel Lichtenberg algorithm，NLA），分別將螺旋系數(shù)和Levy因子融入對(duì)中心區(qū)域和邊緣區(qū)域粒子的更新中，增強(qiáng)算法的全局搜索能力；然后利用群體粒子的位置和適應(yīng)度值信息進(jìn)行自適應(yīng)擴(kuò)散更新，提高算法跳出局部最優(yōu)的能力。

1 Lichtenberg算法

LA算法是一種基于群體和軌跡的優(yōu)化算法。算法預(yù)先生成LF，算法的尋優(yōu)過(guò)程即為對(duì)LF 進(jìn)行放縮、旋轉(zhuǎn)、產(chǎn)生二次分形圖三種變換操作，從而實(shí)現(xiàn)對(duì)構(gòu)成LF的粒子位置進(jìn)行更新。上述變換操作完成后，隨機(jī)選取構(gòu)成LF 的部分粒子進(jìn)行適應(yīng)度值評(píng)估，僅保留適應(yīng)度值最優(yōu)的一個(gè)粒子，作為下一次迭代的初始點(diǎn)。當(dāng)算法達(dá)到預(yù)設(shè)最大迭代次數(shù)時(shí)，算法停止，輸出最優(yōu)解。LA算法包括初始化LF和基于LF的變換操作兩個(gè)階段。

1.1 初始化LF

Turner提出，LF可以通過(guò)許多粒子的隨機(jī)生長(zhǎng)過(guò)程模擬產(chǎn)生[10]。擴(kuò)散限制聚集（diffusion limited aggregation，DLA）模型是一種隨機(jī)的團(tuán)簇生長(zhǎng)模型，由Witten 和Sander模擬固體顆粒的團(tuán)簇生長(zhǎng)數(shù)值模型而提出，這種模型會(huì)導(dǎo)致復(fù)雜的混沌行為[11]。通?？梢杂梅中螏缀螆D形來(lái)刻畫(huà)，因此本文選取DLA模型構(gòu)造LF。

1.2 基于LF的變換操作

構(gòu)成分形圖的粒子的位置更新通過(guò)作用在分形圖上的放縮、旋轉(zhuǎn)、產(chǎn)生二次分形圖的變換操作實(shí)現(xiàn)。

1.2.1 放縮

放縮操作即對(duì)初始化生成的分形圖的大小乘以一個(gè)0～1之間的隨機(jī)數(shù)，稱(chēng)為放縮系數(shù)。分形圖的原始大小即為待優(yōu)化問(wèn)題搜索空間的大小。在每次迭代時(shí)，分形圖都會(huì)以不同的大小繪制出來(lái)。這一操作縮短了每次迭代時(shí)各個(gè)點(diǎn)之間的距離，且僅改變分形圖的形狀大小，其余特征均不改變，提高了LA算法的搜索效率。

1.2.2 旋轉(zhuǎn)

旋轉(zhuǎn)操作即對(duì)分形圖進(jìn)行隨機(jī)旋轉(zhuǎn)。隨機(jī)給定一個(gè)旋轉(zhuǎn)角度，并根據(jù)笛卡爾坐標(biāo)旋轉(zhuǎn)方程對(duì)整個(gè)圖形進(jìn)行旋轉(zhuǎn)。這僅適用于對(duì)二維和三維分形圖進(jìn)行旋轉(zhuǎn)。

笛卡爾二維坐標(biāo)旋轉(zhuǎn)方程如式（1），α表示旋轉(zhuǎn)角度。

其中，x、y分別表示構(gòu)成分形圖的一個(gè)粒子在平面直角坐標(biāo)系的橫坐標(biāo)和縱坐標(biāo)值，x′、y′分別是粒子經(jīng)旋轉(zhuǎn)操作后的橫、縱坐標(biāo)值。

笛卡爾三維坐標(biāo)旋轉(zhuǎn)方程如式（2），γ、β、α分別是作用在x、y、z軸上的旋轉(zhuǎn)角度。

其中，x、y、z分別表示構(gòu)成分形圖的一個(gè)粒子在空間直角坐標(biāo)系的橫坐標(biāo)值、縱坐標(biāo)值和豎坐標(biāo)值，x′、y′、z′分別是粒子經(jīng)旋轉(zhuǎn)操作后的橫、縱、豎坐標(biāo)值。

由于旋轉(zhuǎn)角度的隨機(jī)性，使得粒子在每次迭代時(shí)的位置都是不同的，增加了分形圖粒子位置的多樣性，避免了簡(jiǎn)單的重復(fù)操作，有利于算法跳出局部最優(yōu)。

1.2.3 生成二次分形圖

生成二次分形圖這一變換操作利用局部搜索改進(jìn)系數(shù)（ref）來(lái)實(shí)現(xiàn)，ref是介于0～1之間的隨機(jī)數(shù)。該操作會(huì)在原分形圖的基礎(chǔ)上產(chǎn)生一個(gè)新的分形圖，即為二次分形圖，其大小通常是原圖的0～100%。新生成的二次分形圖與原圖有相同的初始迭代點(diǎn)、放縮系數(shù)和旋轉(zhuǎn)角度。如果改進(jìn)系數(shù)為0，算法在本次迭代過(guò)程中將一直在同一個(gè)分形圖上進(jìn)行尋優(yōu)，不會(huì)產(chǎn)生二次分形圖，經(jīng)改進(jìn)系數(shù)作用后產(chǎn)生的二次圖將會(huì)大大提高算法的局部搜索能力。圖1 為初始化形成的LF 經(jīng)過(guò)放縮、旋轉(zhuǎn)和產(chǎn)生二次分形圖操作后的LF，藍(lán)色部分的圖形為初始化的LF，紅色部分為二次分形圖。

圖1 進(jìn)行放縮、旋轉(zhuǎn)和產(chǎn)生二次分形圖后的LFFig.1 LF after retracting，rotating and generating quadratic fractals

2 融合分區(qū)導(dǎo)向搜索與自適應(yīng)擴(kuò)散的新型Lichtenberg算法

2.1 分區(qū)導(dǎo)向搜索

基本LA 算法中個(gè)體的位置會(huì)受到當(dāng)前位置、目標(biāo)位置和群體其他個(gè)體位置的共同影響，這表示構(gòu)成分形圖的所有個(gè)體都影響每個(gè)個(gè)體的下一個(gè)位置。因此LA算法的全局搜索能力相對(duì)有所不足，也就是說(shuō)LA算法易出現(xiàn)在局部最優(yōu)值附近停滯的情況。而算法前期需要大范圍的全局搜索來(lái)找到所有可能的解。分形圖作為混沌形態(tài)具有以下特征：遠(yuǎn)離中心吸引子的一切運(yùn)動(dòng)都趨向于中心，屬于“穩(wěn)定”的方向；一切到達(dá)中心吸引子內(nèi)的運(yùn)動(dòng)都互相排斥，對(duì)應(yīng)于“不穩(wěn)定”方向，因此算法的迭代尋優(yōu)過(guò)程就是粒子不斷趨向中心吸引子的過(guò)程?？紤]到粒子所處區(qū)域的不同表現(xiàn)出的差異性，對(duì)搜索空間的尋優(yōu)過(guò)程也應(yīng)當(dāng)劃分成不同區(qū)域各自進(jìn)行更新。文獻(xiàn)[12]將群體劃分為兩部分，分別采取worker phase和breeder phase兩種更新規(guī)則進(jìn)行更新。雖然該更新策略具有較強(qiáng)的開(kāi)發(fā)能力，但是它存在“過(guò)度開(kāi)發(fā)”問(wèn)題，會(huì)極易導(dǎo)致粒子陷入局部最優(yōu)。在此基礎(chǔ)上，設(shè)計(jì)分區(qū)導(dǎo)向搜索策略。根據(jù)個(gè)體的適應(yīng)度值將整個(gè)搜索空間劃分為兩個(gè)區(qū)域來(lái)指導(dǎo)個(gè)體尋優(yōu)，群體中適應(yīng)度值排名前20%的個(gè)體離中心吸引子更近，構(gòu)成中心區(qū)域；剩下80%的個(gè)體離中心吸引子較遠(yuǎn)，構(gòu)成邊緣區(qū)域。由于中心區(qū)域和邊緣區(qū)域在搜索空間處于不同的區(qū)域，需要分別設(shè)計(jì)針對(duì)性的更新方法。結(jié)合螺旋系數(shù)的周期趨向性和Levy 變異的隨機(jī)性，實(shí)現(xiàn)中心區(qū)域的個(gè)體向最優(yōu)位置靠攏，同時(shí)邊緣區(qū)域的個(gè)體由子空間到整體解空間進(jìn)行全局搜索。

2.1.1 中心螺旋搜索

由于中心區(qū)域的粒子適應(yīng)度值較優(yōu)，離全局最優(yōu)的位置較近，說(shuō)明它們正沿著正確的搜索方向搜索。為了使它們更快地趨向到全局最優(yōu)位置，要求這些粒子能夠在搜索空間內(nèi)進(jìn)行充分的探索，擴(kuò)大搜索范圍。因此，在更新過(guò)程中以全局最優(yōu)粒子和中心區(qū)域的最優(yōu)粒子為導(dǎo)向，將鯨魚(yú)優(yōu)化算法的螺旋搜索系數(shù)ebmcos(2πm)進(jìn)行改進(jìn)，步長(zhǎng)因子b由固定值改為隨迭代次數(shù)改變的動(dòng)態(tài)步長(zhǎng)因子，賦予其動(dòng)態(tài)趨向性，可以動(dòng)態(tài)改變個(gè)體的位置更新步長(zhǎng)，使得中心區(qū)域的粒子在迭代前期可以大范圍地探索最優(yōu)位置，更新范圍也隨著迭代次數(shù)的增加而隨之減小，迭代后期可以圍繞目標(biāo)位置進(jìn)行周期性精細(xì)搜索。步長(zhǎng)因子b定義如下：

加入了動(dòng)態(tài)步長(zhǎng)因子b的螺旋搜索系數(shù)可以加快粒子趨向中心吸引子這一過(guò)程，從而提升算法尋優(yōu)精度，加快收斂速度。對(duì)中心區(qū)域粒子更新的數(shù)學(xué)表達(dá)式如式（3）所示：

其中，gbest是全局最優(yōu)粒子，為中心區(qū)域中適應(yīng)度值最優(yōu)的粒子，ebmcos(2πm)為螺旋搜索系數(shù)。圖2是模擬粒子進(jìn)行周期性螺旋搜索的軌跡圖，通過(guò)圖2可以直觀地看出當(dāng)前粒子以步長(zhǎng)x=ebmcos(2πm)向全局最優(yōu)粒子螺旋式靠近。其中，t為當(dāng)前迭代次數(shù)，n_iter為最大迭代次數(shù)。

圖2 螺旋搜索軌跡圖Fig.2 Spiral search trajectory graph

2.1.2 邊緣擾動(dòng)搜索

邊緣粒子由于適應(yīng)度值較差，遠(yuǎn)離中心吸引子，這些粒子的搜索方向和步長(zhǎng)均需要重新調(diào)整，它們需要探索更廣闊的區(qū)域，才能向全局最優(yōu)靠近。受文獻(xiàn)[13]提出的對(duì)布谷鳥(niǎo)算法的最優(yōu)鳥(niǎo)窩位置進(jìn)行分階段動(dòng)態(tài)擾動(dòng)的啟發(fā)，提出一種改進(jìn)的邊緣擾動(dòng)搜索策略，通過(guò)引入Levy 飛行機(jī)制，利用Levy 飛行方向和步長(zhǎng)的不確定性對(duì)粒子位置增加擾動(dòng)，提高群體的多樣性?；镜腖evy飛行機(jī)制在尋優(yōu)過(guò)程中雖然加強(qiáng)了算法的全局搜索能力，但是還會(huì)存在陷入局部最優(yōu)的問(wèn)題。針對(duì)上述問(wèn)題，引入sign函數(shù)，利用sign函數(shù)的分段特征，強(qiáng)化當(dāng)前粒子的隨機(jī)學(xué)習(xí)過(guò)程。sign函數(shù)表達(dá)式如下：

Levy分布的數(shù)學(xué)表達(dá)式如下：

其中，u、v均為0 到1 之間服從均勻分布的隨機(jī)數(shù)，ω=1.5。

邊緣擾動(dòng)策略的公式如下：

其中，Xrand_1(t)是從邊緣粒子中隨機(jī)選擇的，βmin=0.2,θ是（0，2]服從均勻分布的隨機(jī)數(shù)。當(dāng)sign函數(shù)取值為1時(shí)，個(gè)體由子空間到整體解空間進(jìn)行Levy全局搜索，大范圍搜尋最優(yōu)位置；當(dāng)sign 函數(shù)取值為0 時(shí)，個(gè)體保持當(dāng)前位置不變；當(dāng)sign函數(shù)取值為-1 時(shí)，產(chǎn)生邊緣擾動(dòng)搜索反向解，通過(guò)動(dòng)態(tài)地調(diào)整搜索方向，可以避免算法陷入局部最優(yōu)、搜索停滯的情況，幫助算法脫離局部極值。sign 函數(shù)的三種取值會(huì)使個(gè)體有三種不同的搜索方向進(jìn)行選擇，有效避免了迭代后期種群多樣性下降，算法易早熟收斂的問(wèn)題。在二維搜索空間中，假設(shè)群體規(guī)模為50，搜索空間為[-100，100]，繪制了不同迭代時(shí)刻的個(gè)體分布圖，如圖3所示。

圖3 不同迭代時(shí)刻的個(gè)體分布圖Fig.3 Individual distribution map at different iterations

迭代初期粒子分布在[-100，50]區(qū)間，隨著迭代次數(shù)增加，粒子逐漸向全局最優(yōu)附近靠攏，主要分布在[-0.1，0.1]區(qū)間。由圖3可以看出，迭代初期群體多樣性較高，個(gè)體分布在搜索空間的廣闊區(qū)域內(nèi)，可以大范圍地搜尋最優(yōu)解，確定后期搜索的大方向；隨著迭代次數(shù)的增加，個(gè)體不斷向全局最優(yōu)靠攏，種群多樣性也隨之降低。進(jìn)一步證明將螺旋搜索系數(shù)和Levy變異相結(jié)合可以加強(qiáng)算法的全局搜索能力，上述兩種更新策略相結(jié)合是切實(shí)可行的。

2.2 自適應(yīng)擴(kuò)散

在LA 算法原有的更新操作中，構(gòu)成分形圖的各粒子之間沒(méi)有信息交互，單純依靠對(duì)分形圖進(jìn)行放縮、旋轉(zhuǎn)等操作實(shí)現(xiàn)粒子的位置更新，因此算法尋優(yōu)能力較弱。適應(yīng)度值是反映個(gè)體與全局最優(yōu)之間關(guān)系的重要參數(shù)，適應(yīng)度值較優(yōu)的粒子所攜帶的位置信息更有利于算法進(jìn)行尋優(yōu)，因此如果能在個(gè)體更新時(shí)充分利用群體粒子的適應(yīng)度值，可以有效提高算法跳出局部最優(yōu)的能力[14]。但需要注意的是，如果構(gòu)成分形圖的粒子集中于某一方向進(jìn)行搜索，很可能陷入局部最優(yōu)，為了避免這種情況的發(fā)生，需要確定一個(gè)合適的選擇概率，既要保證大部分粒子向全局最優(yōu)方向進(jìn)行搜索，也要保證小部分粒子的獨(dú)立搜索能力。文獻(xiàn)[15]提出的具備觀測(cè)觸發(fā)機(jī)制的透鏡成像學(xué)習(xí)，嵌入一種基于迭代次數(shù)和最優(yōu)適應(yīng)度值的觀測(cè)算子，來(lái)觀測(cè)算法是否陷入局部最優(yōu)。

本文在此基礎(chǔ)上，提出了自適應(yīng)擴(kuò)散對(duì)算法進(jìn)行改進(jìn)，引入累積概率隨機(jī)選擇群體粒子與當(dāng)前粒子進(jìn)行交互，累積概率作為調(diào)節(jié)參數(shù)，使得個(gè)體根據(jù)種群所處的實(shí)際環(huán)境以及自身的適應(yīng)度值動(dòng)態(tài)調(diào)節(jié)，避免算法后期易陷入局部最優(yōu)的問(wèn)題。自適應(yīng)擴(kuò)散策略如式（10）所示：

其中，r是服從[0，1]均勻分布的隨機(jī)數(shù)，X(k,j)是按累積概率從群體中隨機(jī)選擇的一個(gè)粒子在其維度j上的值，隨機(jī)粒子k的具體選擇方法見(jiàn)式（12），fitnessk是粒子k的適應(yīng)度值。通過(guò)對(duì)隨機(jī)粒子k與當(dāng)前粒子的適應(yīng)度值進(jìn)行比較，選擇更優(yōu)的個(gè)體作為導(dǎo)向進(jìn)行擴(kuò)散更新。

其中，rand_num是[0，1]服從均勻分布的隨機(jī)數(shù)，Ci是累積概率。每次更新時(shí)，先計(jì)算群體每個(gè)粒子的累積概率Ci，然后生成rand_num，并判斷rand_num落在哪一個(gè)累積概率區(qū)間，則該粒子就被選中為X(k,j)。Ci的數(shù)學(xué)表達(dá)式如式（13）所示：

通過(guò)概率選擇的隨機(jī)性，當(dāng)前個(gè)體與其他個(gè)體間的信息交流更加豐富，個(gè)體在探索階段會(huì)根據(jù)收集到的信息自適應(yīng)調(diào)節(jié)自己的搜索方向，避免隨機(jī)選擇粒子所造成的盲目跟隨，使得粒子能有效跳出當(dāng)前區(qū)域。

3 融合分區(qū)導(dǎo)向搜索與自適應(yīng)擴(kuò)散的新型Lichtenberg算法流程

NLA 算法采用分區(qū)導(dǎo)向搜索和自適應(yīng)擴(kuò)散對(duì)算法進(jìn)行改進(jìn)，下面給出NLA算法的實(shí)現(xiàn)步驟和偽代碼，并對(duì)NLA算法進(jìn)行時(shí)間復(fù)雜度分析。

3.1 NLA算法的主要步驟

NLA算法的主要計(jì)算步驟如下：

步驟1初始化NLA算法參數(shù)，隨機(jī)生成初始解，計(jì)算適應(yīng)度值并擇優(yōu)保存作為生成LF的初始點(diǎn)。

步驟2生成LF（本文只在步驟2生成一次分形圖，后續(xù)迭代均在此分形圖基礎(chǔ)上進(jìn)行），并對(duì)其進(jìn)行放縮、旋轉(zhuǎn)、產(chǎn)生二次分形圖的變換操作。

步驟3分別從原LF 和生成的二次LF 中隨機(jī)選擇相同數(shù)量的粒子，其個(gè)數(shù)為群體規(guī)模的1/2。

步驟4將步驟3 選擇出的粒子按照適應(yīng)度值劃分為兩組，進(jìn)行分區(qū)導(dǎo)向搜索。

步驟5計(jì)算更新后的適應(yīng)度值，并按照式（7）進(jìn)行自適應(yīng)擴(kuò)散更新。

步驟6計(jì)算每個(gè)粒子更新后的位置和適應(yīng)度值，將適應(yīng)度值最優(yōu)的粒子保存，作為下一次迭代的初始點(diǎn)。

步驟7重復(fù)步驟2～步驟6的更新迭代過(guò)程，達(dá)到預(yù)設(shè)最大迭代次數(shù)時(shí)，終止NLA算法并輸出最優(yōu)解。

3.2 NLA算法偽代碼

3.3 NLA算法時(shí)間復(fù)雜度分析

LA 算法的時(shí)間復(fù)雜度如下：假設(shè)群體規(guī)模為N，搜索空間維度為D，則LA初始化分形圖的時(shí)間復(fù)雜度為O(N×D)，對(duì)分形圖進(jìn)行放縮、旋轉(zhuǎn)、產(chǎn)生二次分形圖的變換操作的時(shí)間復(fù)雜度為O(N)，計(jì)算個(gè)體適應(yīng)度值的時(shí)間復(fù)雜度為O(N×D)，LA 總的時(shí)間復(fù)雜度為O(N×D)。

同理，進(jìn)行中心螺旋搜索的時(shí)間復(fù)雜度為O(N×D)，進(jìn)行邊緣擾動(dòng)搜索的時(shí)間復(fù)雜度為O(N×D)，采取自適應(yīng)擴(kuò)散更新策略的時(shí)間復(fù)雜度為O(N×D)，因此NLA 算法總的時(shí)間復(fù)雜度為O(N×D)。因?yàn)镹LA 算法和LA 算法的時(shí)間復(fù)雜度處于同一水平，所以上述改進(jìn)策略并未對(duì)基本LA算法產(chǎn)生負(fù)面影響。

4 仿真實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)與測(cè)試函數(shù)

為了驗(yàn)證本文所提NLA 算法的有效性，采用CEC2021測(cè)試函數(shù)和20個(gè)不同特點(diǎn)的高維測(cè)試函數(shù)進(jìn)行數(shù)值實(shí)驗(yàn)。仿真實(shí)驗(yàn)基于Intel?CoreTMi7-8565U CPU@1.80 GHz 2.00 GHz，16.0 GB內(nèi)存，以及Win10操作系統(tǒng)，仿真軟件為MATLAB R2020b。

將NLA 算法與基本LA 算法[7]、粒子群優(yōu)化算法（particle swarm optimization，PSO）[16]、差分進(jìn)化算法（differential evolution，DE）[17]、鯨魚(yú)優(yōu)化算法（whale optimizaiton algorithm，WOA）[18]、金鷹優(yōu)化算法（golden eagle optimization，GEO）[19]、食肉植物算法（carnivorous plant algorithm，CPA）[20]進(jìn)行比較，算法參數(shù)設(shè)置見(jiàn)表1。其中NLA 算法各參數(shù)的含義如下：Np為生成LF 的預(yù)設(shè)粒子數(shù)，Rc為生成LF 的預(yù)設(shè)半徑，refinement(ref)為生成二次分形圖的比例系數(shù)。

表1 各算法參數(shù)設(shè)置Table 1 Experimental parameter settings of each algorithm

4.2 CEC2021測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果分析

本文對(duì)CEC2021 函數(shù)的尋優(yōu)實(shí)驗(yàn)參考文獻(xiàn)[21]進(jìn)行。CEC2021 測(cè)試函數(shù)是對(duì)表2 中10 個(gè)基本函數(shù)施加3種不同的變換操作而產(chǎn)生，3種變換操作包含Bias（偏差）、Shift（移位）和Rotation（旋轉(zhuǎn)），對(duì)每種操作都有添加和不添加2種選擇，共8種不同的組合方式，如表3（0代表不添加此變換，1代表添加此變換），總計(jì)10×8=80個(gè)不同的函數(shù)，進(jìn)行變換操作后的函數(shù)最優(yōu)值不變。本文選取表3 中勾選的4 種組合方式進(jìn)行20 維函數(shù)的測(cè)試實(shí)驗(yàn)。迭代次數(shù)為200 次，種群規(guī)模為50，每個(gè)算法獨(dú)立運(yùn)行30 次，實(shí)驗(yàn)結(jié)果如表4 所示。由表4 可知，對(duì)于大部分函數(shù)來(lái)說(shuō)，DE 和GEO 求得結(jié)果的平均值較大，說(shuō)明DE 和GEO 尋優(yōu)能力的不足，而且跳出局部最優(yōu)的能力較弱。NLA算法在最優(yōu)值、平均值、標(biāo)準(zhǔn)差這3 個(gè)指標(biāo)上不僅是上述7 種算法中最好的，而且它取得了全部函數(shù)的理論最優(yōu)值，收斂精度更高，尋優(yōu)穩(wěn)定性也更強(qiáng)。對(duì)單峰函數(shù)F1尋優(yōu)時(shí)，PSO的最優(yōu)值8.32E-05，WOA的最優(yōu)值5.21E-33，而NLA算法的最優(yōu)值是0；對(duì)添加Bias和Rotation操作的尋優(yōu)難度大的函數(shù)，NLA算法相較于其他6種智能優(yōu)化算法，在求解精度上具有明顯的優(yōu)勢(shì)，對(duì)于函數(shù)F2～F4，NLA 算法和WOA 均找到了最優(yōu)值，但NLA 算法較于WOA，在平均值和標(biāo)準(zhǔn)差上均有數(shù)百個(gè)量級(jí)的優(yōu)勢(shì)；另外，無(wú)論是對(duì)于單峰函數(shù)、基礎(chǔ)函數(shù)、混合函數(shù)還是組合函數(shù)，NLA算法在測(cè)試函數(shù)上的尋優(yōu)結(jié)果均優(yōu)于LA算法，而且NLA算法的標(biāo)準(zhǔn)差均為0，說(shuō)明NLA算法相較于基本LA算法，具有更穩(wěn)定的尋優(yōu)能力。根據(jù)上述實(shí)驗(yàn)結(jié)果分析，本文提出的改進(jìn)算法具有更高的求解精度和更穩(wěn)定的尋優(yōu)能力。

表2 CEC2021測(cè)試函數(shù)Table 2 CEC2021 test functions

表3 作用于基礎(chǔ)函數(shù)上的8種組合變換Table 3 Eight combined transformations acted on basic functions

本文選取了部分函數(shù)的迭代尋優(yōu)結(jié)果繪制了收斂曲線(xiàn)，由于大部分函數(shù)的收斂曲線(xiàn)較為相似，只挑選兩種具有代表性的呈現(xiàn)，其中縱坐標(biāo)取以10為底的對(duì)數(shù)，如圖4所示。由收斂曲線(xiàn)可知，NLA算法無(wú)論是在求解精度還是收斂速度上，都明顯優(yōu)于其他算法。針對(duì)F3，雖然WOA算法也收斂到了最優(yōu)值，但NLA算法的收斂速度明顯更快；針對(duì)F1 這個(gè)尋優(yōu)難度大的函數(shù)，NLA算法也表現(xiàn)出了優(yōu)越的性能，可以快速地收斂到最優(yōu)值，而且NLA算法在迭代初期就達(dá)到了WOA算法的求解精度，這說(shuō)明分區(qū)導(dǎo)向搜索加強(qiáng)了算法的全局搜索能力，此后基于自適應(yīng)擴(kuò)散的作用，使得算法跳出局部最優(yōu)繼續(xù)進(jìn)行搜索，最終收斂到最優(yōu)值。NLA 算法在初始階段的適應(yīng)度值就優(yōu)于其他對(duì)比算法，說(shuō)明分區(qū)導(dǎo)向搜索一定程度上提高了算法的全局搜索性能。綜合對(duì)表4和圖4的分析，NLA算法針對(duì)復(fù)雜的函數(shù)優(yōu)化問(wèn)題具有較好的求解精度和收斂速度，性能提升較大，是一種高效的算法。

表4 20維測(cè)試函數(shù)結(jié)果Table 4 Results for 20 dimensional functions

表4 （續(xù)）

圖4 CEC函數(shù)收斂曲線(xiàn)對(duì)比Fig.4 Comparison of CEC functions convergence curves

4.3 其他類(lèi)型測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果分析

本文將上述7 種算法進(jìn)行1 000 維函數(shù)的對(duì)比實(shí)驗(yàn)，分別在20個(gè)高維測(cè)試函數(shù)上獨(dú)立運(yùn)行30次，具體函數(shù)信息見(jiàn)表5。所有算法的群體規(guī)模設(shè)為50，迭代次數(shù)設(shè)為200，實(shí)驗(yàn)結(jié)果如表6所示。從表6可以看出，NLA算法是7 種算法中尋優(yōu)結(jié)果最優(yōu)的。對(duì)于這20 個(gè)測(cè)試函數(shù)，NLA算法能夠找到除函數(shù)f5 和f7 外其他所有函數(shù)的理論最優(yōu)值，并且得到的最優(yōu)值、標(biāo)準(zhǔn)差都為理論最優(yōu)值。對(duì)于尋優(yōu)難度較大的f5，NLA 算法雖未取得其理論最優(yōu)值，但尋優(yōu)精度比LA 算法提高了十幾個(gè)量級(jí)；對(duì)于f7，雖然上述算法都無(wú)法找到其理論最優(yōu)值，但NLA算法的最優(yōu)值更接近理論最優(yōu)值，與LA算法相比，NLA算法找到的最優(yōu)值提高了11個(gè)數(shù)量級(jí)的精度，且比其他對(duì)比算法有數(shù)個(gè)量級(jí)的提升；對(duì)于尋優(yōu)難度較大的函數(shù)f19，大多數(shù)算法的尋優(yōu)精度都很低，而NLA算法收斂到理論最優(yōu)解，說(shuō)明本文所提改進(jìn)策略能夠提高算法跳出局部最優(yōu)的能力。同時(shí)從表5 的標(biāo)準(zhǔn)差可知，NLA 算法在17 個(gè)測(cè)試函數(shù)上得到的標(biāo)準(zhǔn)差都為0，說(shuō)明NLA算法具有較強(qiáng)的穩(wěn)定性。

表5 基礎(chǔ)函數(shù)Table 5 Basic functions

表6 高維測(cè)試函數(shù)結(jié)果Table 6 Results for high-dimensional test functions

表6 （續(xù)）

為了更加直觀地對(duì)比各算法的收斂精度和收斂速度，本文根據(jù)迭代次數(shù)和適應(yīng)度值繪制了測(cè)試函數(shù)的收斂曲線(xiàn)圖像，其中縱坐標(biāo)取以10 為底的對(duì)數(shù)，如圖5 所示。由收斂曲線(xiàn)可知，基本LA 算法在迭代前期的尋優(yōu)性能較差，而在后期也陷入了局部最優(yōu)，而NLA算法在整個(gè)迭代過(guò)程中，尋優(yōu)性能良好，不斷向最優(yōu)解收斂。具體來(lái)說(shuō)，對(duì)于f1，NLA算法的最優(yōu)值在迭代過(guò)程中呈現(xiàn)指數(shù)級(jí)的下降速度，其收斂速度要遠(yuǎn)優(yōu)于其他算法，其后期也表現(xiàn)出了較強(qiáng)的局部搜索能力；對(duì)于f5，NLA算法在前期更側(cè)重于對(duì)搜索空間進(jìn)行開(kāi)發(fā)，因此放慢了收斂速度，但是在算法后期粒子找到最優(yōu)區(qū)域以后，算法較強(qiáng)的尋優(yōu)能力使得算法快速收斂；對(duì)于f7，算法在迭代前期對(duì)搜索空間進(jìn)行充分的探索，但在搜索后期，收斂速度減慢，但最終的收斂精度仍高于其他對(duì)比算法；對(duì)于f17，NLA算法的表現(xiàn)相當(dāng)優(yōu)異，僅用了幾次迭代就收斂到最優(yōu)值，雖然WOA算法也找到理論最優(yōu)值，但NLA算法的分區(qū)導(dǎo)向搜索和自適應(yīng)擴(kuò)散使得算法在迭代初期大范圍地搜索，確定潛在最優(yōu)解所在位置，迭代后期收斂速度加快，算法快速趨向于優(yōu)秀粒子，逐漸收斂到最優(yōu)值。針對(duì)大部分函數(shù)，NLA 算法的收斂精度要明顯優(yōu)于其他算法。綜上，NLA 算法優(yōu)化高維函數(shù)的可行性和有效性得以證明。

圖5 高維函數(shù)收斂曲線(xiàn)對(duì)比Fig.5 Comparison of high-dimensional functions convergence curves

4.4 Wilcoxon秩和檢驗(yàn)

Wilcoxon 秩和檢驗(yàn)是一種非參數(shù)統(tǒng)計(jì)檢驗(yàn)方法，可以針對(duì)復(fù)雜的數(shù)據(jù)分布進(jìn)行檢驗(yàn)，因此本文選取Wilcoxon 秩和檢驗(yàn)方法進(jìn)一步驗(yàn)證各算法之間差異性是否顯著。選取NLA 算法在CEC2021 測(cè)試函數(shù)集上的運(yùn)行結(jié)果與LA、PSO、DE、WOA、GEO、CPA的運(yùn)行結(jié)果進(jìn)行Wilcoxon 秩和檢驗(yàn)并計(jì)算p-value，由于篇幅限制，僅列出部分10 維函數(shù)的實(shí)驗(yàn)結(jié)果，如表7 所示。當(dāng)p-value 值小于5%時(shí)，說(shuō)明兩種算法的差異性顯著，反之，則沒(méi)有。由實(shí)驗(yàn)結(jié)果可知，大部分的p-value值都是小于5%的，因此可以認(rèn)為NLA算法對(duì)CEC2021函數(shù)上的尋優(yōu)性能優(yōu)勢(shì)是明顯的，進(jìn)一步證明了本文所提NLA算法的有效性。

表7 Wilcoxon秩和檢驗(yàn)結(jié)果Table 7 Wilcoxon rank sum test result

4.5 改進(jìn)策略的有效性分析

為了驗(yàn)證NLA 算法的有效性，將NLA 算法與其自身的兩個(gè)變體進(jìn)行測(cè)試，兩個(gè)變體為僅加入分區(qū)導(dǎo)向搜索策略的LA 算法（LA1）和僅加入自適應(yīng)擴(kuò)散更新的LA算法（LA2）。本文選取f5、f7 這兩個(gè)尋優(yōu)難度較大的高維函數(shù)和CEC2021 的兩個(gè)函數(shù)進(jìn)行尋優(yōu)對(duì)比，分別為不添加任何變換操作[000]的F5 和僅添加旋轉(zhuǎn)操作[001]的F9，其參數(shù)設(shè)置與上述實(shí)驗(yàn)完全相同。三種算法的對(duì)比結(jié)果如表8所示。

表8 不同改進(jìn)策略對(duì)比結(jié)果Table 8 Comparison of different improvement strategies

由表8所示結(jié)果可以看出，針對(duì)函數(shù)F5，僅使用分區(qū)導(dǎo)向搜索的LA1和僅使用自適應(yīng)擴(kuò)散的LA2都找到了最優(yōu)值，但其平均值和標(biāo)準(zhǔn)差較差，而NLA算法結(jié)合了兩種策略的優(yōu)勢(shì)，既能找到最優(yōu)值，且均值和方差均達(dá)到最優(yōu)效果；而對(duì)函數(shù)F9，融入分區(qū)導(dǎo)向搜索的LA1算法的尋優(yōu)結(jié)果與最優(yōu)值很接近，穩(wěn)定性也較好，融入自適應(yīng)擴(kuò)散的LA2算法找到了最優(yōu)值，但尋優(yōu)效果不穩(wěn)定，NLA 算法展現(xiàn)了良好的尋優(yōu)效果。針對(duì)f5、f7 這兩個(gè)尋優(yōu)難度大的函數(shù)，采用兩種改進(jìn)策略結(jié)合的NLA算法的尋優(yōu)精度和穩(wěn)定性要優(yōu)于采用單一改進(jìn)策略的LA算法。通過(guò)對(duì)比LA、LA1、LA2的尋優(yōu)效果，兩種改進(jìn)策略對(duì)算法的性能均有一定程度的提升，其中融入分區(qū)導(dǎo)向搜索的LA 算法（LA1）的尋優(yōu)穩(wěn)定性更好，融入自適應(yīng)擴(kuò)散的LA 算法（LA2）的尋優(yōu)精度更好，找到的最優(yōu)值也與NLA算法更為接近。而結(jié)合兩種改進(jìn)策略的NLA算法對(duì)基本LA算法性能提升更大。

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

本文針對(duì)LA 算法在求解復(fù)雜函數(shù)優(yōu)化問(wèn)題時(shí)，尋優(yōu)精度低、收斂速度慢、易陷入局部最優(yōu)等問(wèn)題，從混沌與分形的角度出發(fā)，結(jié)合復(fù)雜系統(tǒng)的內(nèi)在特征，提出融合分區(qū)導(dǎo)向搜索與自適應(yīng)擴(kuò)散更新的新型Lichtenberg算法（NLA）。首先，將構(gòu)成分形圖的粒子根據(jù)適應(yīng)度值進(jìn)行分區(qū)，靠近吸引子的那部分中心粒子采用螺旋搜索，遠(yuǎn)離吸引子的那部分邊緣粒子采用擾動(dòng)搜索，加強(qiáng)算法的全局搜索能力。然后，結(jié)合復(fù)雜系統(tǒng)各部分之間的交互依存特征，充分利用各粒子的位置和適應(yīng)度值信息，進(jìn)行自適應(yīng)擴(kuò)散更新，避免算法陷入局部最優(yōu)。為驗(yàn)證NLA 算法的性能，選取了CEC2021 測(cè)試函數(shù)以及20個(gè)不同特點(diǎn)的高維函數(shù)進(jìn)行數(shù)值實(shí)驗(yàn)。結(jié)果證明，與LA、PSO、DE、WOA、GEO、CPA 相比，本文提出的NLA算法在優(yōu)化復(fù)雜函數(shù)和高維函數(shù)時(shí)尋優(yōu)精度高，穩(wěn)定性更強(qiáng)，顯示了良好的效果。將NLA 算法應(yīng)用于智慧醫(yī)療系統(tǒng)資源調(diào)度是進(jìn)一步的工作。