張夢(mèng)溪,馬 良,劉 勇
上海理工大學(xué) 管理學(xué)院,上海 200093
近年來,優(yōu)化求解問題越來越復(fù)雜,計(jì)算規(guī)模日益增大,同時(shí)許多問題還具有非線性、多極值等特點(diǎn)。牛頓法、梯度下降法等傳統(tǒng)優(yōu)化算法存在依賴梯度信息和求解速度慢等缺陷,已無法滿足求解需求。而元啟發(fā)式算法具有更好的求解能力,其結(jié)構(gòu)簡(jiǎn)單、靈活性高和求解效率高,因此成為了求解復(fù)雜優(yōu)化問題的有力工具。
元啟發(fā)式算法根據(jù)其實(shí)現(xiàn)機(jī)理的不同,大致可以分為三類:基于遺傳進(jìn)化的算法、基于生物種群的算法和基于特定物理機(jī)制實(shí)現(xiàn)的算法[1]?;谶z傳進(jìn)化的算法有遺傳算法(genetic algorithms,GA)[2];基于生物種群的算法通過模擬自然界中動(dòng)植物的行為實(shí)現(xiàn)尋優(yōu),例如鯨魚優(yōu)化算法(whale optimization algorithm,WOA)[3]、麻雀搜索算法(sparrow search algorithm,SSA)[4]等;基于物理學(xué)原理所提出的算法有根據(jù)萬有引力定律提出的引力搜索算法(gravitational search algorithm,GSA)[5]、基于多元宇宙理論的多元宇宙優(yōu)化算法(multi-verse optimizer,MVO)[6]等?;谔囟ㄎ锢頇C(jī)制的算法從物理現(xiàn)象出發(fā),有物理學(xué)原理做基礎(chǔ),具備良好的搜索效果。
平衡優(yōu)化器算法(equilibrium optimizer,EO)是Faramarzi等人在2019年基于物理原理提出的一種新型啟發(fā)式算法[7]。該算法將搜索種群以不同濃度的粒子表示,粒子的濃度代表優(yōu)化問題的解。同時(shí),算法提出了平衡池候選解的概念,每次尋優(yōu)根據(jù)平衡池候選解的濃度更新粒子,最終達(dá)到濃度平衡的狀態(tài),即尋得最優(yōu)解。EO算法具有算法參數(shù)少,易于理解和實(shí)現(xiàn)的特點(diǎn)。算法提出至今,已被應(yīng)用到了電網(wǎng)設(shè)計(jì)[8]和路徑規(guī)劃[9]等諸多領(lǐng)域,是解決復(fù)雜問題的新工具。但是,EO算法在平衡池階段,候選解完全根據(jù)適應(yīng)度值大小進(jìn)行選取,使得平衡池候選解存在一定的相似性,導(dǎo)致種群多樣性降低,易陷入局部最優(yōu);同時(shí),算法平衡全局搜索和局部開發(fā)能力的參數(shù)為固定值,可能出現(xiàn)尋優(yōu)不穩(wěn)定的現(xiàn)象;此外,粒子位置更新僅依靠濃度更新公式,使得算法局部搜索能力較強(qiáng)但全局搜索能力較弱,影響算法收斂速度和尋優(yōu)精度。針對(duì)這些問題,國(guó)內(nèi)外諸多學(xué)者相繼對(duì)其進(jìn)行了改進(jìn)。Fan等人利用反向?qū)W習(xí)機(jī)制和新的濃度更新公式,提升了算法的求解精度[10]。劉成漢等人在禁忌搜索策略中引入振蕩算子,使算法跳出局部最優(yōu)[11]。Gupta等人利用高斯變異和新的種群劃分和重構(gòu)機(jī)制改進(jìn)了EO算法[12]。Too等人利用一般學(xué)習(xí)的思想改進(jìn)了平衡池階段的缺陷[13]。Wunnava等人利用拉普拉斯分布的隨機(jī)游動(dòng)改進(jìn)了候選解的質(zhì)量,然后通過反向?qū)W習(xí)加速得到最優(yōu)解[14]。Shankar等人利用對(duì)立學(xué)習(xí)的更新機(jī)制生成新的解空間[15]。Abdel-Basset等人提出了基于線性化簡(jiǎn)分集技術(shù)的新的學(xué)習(xí)機(jī)制,同時(shí)利用局部極小消去法增加了個(gè)體的多樣性,優(yōu)化了算法的性能[16]。Ahmed等人利用了自動(dòng)學(xué)習(xí)機(jī)來尋找適合算法模型的參數(shù)值[17]。李守玉等人首先采用正弦池策略動(dòng)態(tài)平衡算法的探索和開發(fā)能力,然后引入自適應(yīng)優(yōu)先引力策略動(dòng)態(tài)平衡算法的收斂速度和方向[18]。
雖然以上學(xué)者的研究對(duì)EO算法的尋優(yōu)能力有所提升,但在收斂速度、尋優(yōu)精度、平衡局部搜索和全局開發(fā)能力等方面的優(yōu)化潛力仍可以進(jìn)一步挖掘。針對(duì)EO算法的不足,本文提出一種融合濃度平衡和菲克定律的新平衡優(yōu)化器算法(NEO),引入了三種新穎有效的改進(jìn)策略:首先,在平衡池階段引入濃度平衡機(jī)制,將不同濃度的粒子劃分為三個(gè)種群,不同濃度的粒子之間相互影響,提升種群間的信息交流能力,增強(qiáng)搜索種群的多樣性;然后,引入自適應(yīng)調(diào)整的冪函數(shù)自適應(yīng)因子和指數(shù)自適應(yīng)因子,使算法根據(jù)迭代次數(shù)動(dòng)態(tài)調(diào)整參數(shù),平衡局部搜索和全局開發(fā)能力;最后,從菲克定律得到啟發(fā),在粒子位置更新處引入擾動(dòng)機(jī)制,改善濃度更新公式,加快收斂速度的同時(shí)提升算法尋優(yōu)精度。本文通過求解24個(gè)基準(zhǔn)測(cè)試函數(shù),并將NEO算法與其他智能優(yōu)化算法進(jìn)行仿真實(shí)驗(yàn)對(duì)比來驗(yàn)證算法改進(jìn)策略的有效性,實(shí)驗(yàn)結(jié)果表明NEO算法具有良好的優(yōu)化性能。
平衡優(yōu)化器算法首先在搜索空間中隨機(jī)初始化種群。種群初始化的公式如下所示:
其中,Ci,k表示第k個(gè)粒子所在的位置,rk表示[0,1]間的隨機(jī)向量,ub和lb表示解空間中的上界和下界,k的范圍為[1,N],N表示種群的數(shù)量。
在粒子初始化之后,粒子不斷搜索迭代,并計(jì)算適應(yīng)度值。該算法選取當(dāng)前解中適應(yīng)度值排名前四的粒子,作為候選解,并計(jì)算這四個(gè)粒子的平均值,進(jìn)而構(gòu)建平衡池。平衡池提高了粒子全局搜索和全局的能力,其表示如下:
其中,Cpool表示平衡池;Ceq1、Ceq2、Ceq3、Ceq4表示根據(jù)適應(yīng)度值在當(dāng)前迭代找到的最優(yōu)粒子位置;Cave表示平衡了以上四個(gè)解的粒子位置。
在粒子搜索迭代的過程中,平衡池中的每個(gè)候選解都以相同的概率被隨機(jī)選擇以更新濃度,此過程可以表示為:
為平衡算法的全局探索和局部開發(fā)的能力,算法采用指數(shù)項(xiàng)F進(jìn)行調(diào)整,其計(jì)算公式如下:
其中,a1和a2分別表示全局搜索和局部開發(fā)的權(quán)重系數(shù),其值越大,對(duì)應(yīng)的能力越強(qiáng),通常,a1和a2分別取2和1;Iter表示當(dāng)前的迭代次數(shù);Maxiter表示算法最大迭代次數(shù);λ表示[0,1]間的隨機(jī)數(shù)。
為進(jìn)一步增強(qiáng)算法的局部開發(fā)能力,利用生成速率G來改進(jìn)算法開發(fā)階段,其數(shù)學(xué)表達(dá)式如下:
其中,GP為生成概率,用來平衡算法全局搜索和局部開發(fā)能力,當(dāng)取值為0.5時(shí),算法的探索和開發(fā)能力達(dá)到平衡;GCP為生成速率G的控制參數(shù),由GP所決定;r1、r2和λ表示[0,1]間的隨機(jī)數(shù)。
平衡優(yōu)化器算法的標(biāo)準(zhǔn)濃度更新公式如下:
其中,V表示單位體積,通常為1。
相比其他元啟發(fā)式算法,EO算法具有以下特征:EO算法的核心原理和內(nèi)部結(jié)構(gòu)比較簡(jiǎn)單,其全局搜索能力和局部開發(fā)能力主要由指數(shù)項(xiàng)F和生成速率G進(jìn)行控制,位置更新通過濃度更新公式來完成,這使其具有很好的靈活性和適應(yīng)性;此外,EO算法具有特殊的平衡池階段,算法根據(jù)個(gè)體適應(yīng)度的大小進(jìn)行排序選取候選解,同時(shí)生成平均值共同構(gòu)成平衡池,其目的在于提高算法的探索和開發(fā)能力。
但是,平衡池只依賴適應(yīng)度值的大小選取個(gè)體會(huì)使候選解趨于相似,多樣性降低,容易陷入局部最優(yōu),影響算法精度;指數(shù)項(xiàng)F中的參數(shù)a1和a2調(diào)節(jié)探索和開發(fā)能力,但參數(shù)a1和a2為常數(shù),這使得算法不能根據(jù)迭代自適應(yīng)調(diào)整探索和開發(fā)能力,導(dǎo)致算法迭代過程中出現(xiàn)尋優(yōu)不穩(wěn)定現(xiàn)象,甚至?xí)绊懰惴▽?yōu)精度;EO算法中個(gè)體位置更新主要通過濃度更新公式,個(gè)體更新位置受到當(dāng)前位置、平衡池候選解個(gè)體位置的影響,表明其局部開發(fā)能力較強(qiáng)但全局搜索能力相對(duì)來說有所不足,極易出現(xiàn)在局部最優(yōu)值附近停滯的情況。針對(duì)以上問題,本文從三方面進(jìn)行了改進(jìn)。
EO算法基于適應(yīng)度值的大小,采用順序選擇法從總體中選出候選解,然后再對(duì)選擇出來的候選解進(jìn)行各種策略的搜索操作。因此,算法的尋優(yōu)效果很大程度上取決于候選解的選擇。而僅考慮適應(yīng)度值選取候選解,所選擇的個(gè)體很大概率落在相似區(qū)域,導(dǎo)致種群多樣性降低,過早向局部收斂。
大量事實(shí)表明,一切物質(zhì)分子都在無時(shí)無刻地做無規(guī)則運(yùn)動(dòng),即布朗運(yùn)動(dòng)。分子通過布朗運(yùn)動(dòng)會(huì)從高濃度區(qū)域(或高化勢(shì))向低濃度區(qū)域(或低化勢(shì))進(jìn)行轉(zhuǎn)移,直到均勻分布,這一分子熱運(yùn)動(dòng)現(xiàn)象被稱為擴(kuò)散現(xiàn)象[19]。由于容器中粒子濃度平衡過程中,不同區(qū)域不同濃度的粒子之間會(huì)相互影響,本文受分子擴(kuò)散現(xiàn)象的啟發(fā),提出濃度平衡機(jī)制。首先,根據(jù)粒子位置適應(yīng)度值的大小,由大到小,將粒子劃分為3個(gè)種群:低濃度區(qū)域、中濃度區(qū)域和高濃度區(qū)域。然后,不同濃度區(qū)域之間的粒子相互影響擴(kuò)散:低濃度區(qū)域受中高濃度區(qū)域的影響;中濃度區(qū)域粒子受高濃度區(qū)域和低濃度區(qū)域影響;高濃度區(qū)域的粒子則同時(shí)向中低濃度區(qū)域擴(kuò)散。因此,為增強(qiáng)不同粒子位置之間的信息交流,在此提出不同濃度區(qū)域粒子濃度平衡機(jī)制。
2.1.1 低濃度區(qū)域粒子位置更新
根據(jù)反向?qū)W習(xí)的思想,為更好地體現(xiàn)低濃度區(qū)域粒子受高濃度區(qū)域粒子和中濃度區(qū)域粒子的影響,加強(qiáng)粒子間的信息交流,采用如下公式:
2.1.2 中等濃度區(qū)域粒子位置更新
為增強(qiáng)中等濃度的區(qū)域與其他區(qū)域之間的信息交流,實(shí)現(xiàn)對(duì)其他粒子附近解空間信息的挖掘,加強(qiáng)算法的局部尋優(yōu)能力,在迭代過程中,中等濃度區(qū)域的粒子以一定的概率向周邊擴(kuò)散。此過程用如下公式表示:
其中,Cjworst、Cjmid和Cjbest分別表示當(dāng)前迭代中,濃度最低、濃度中等和濃度最高粒子的位置;d3和d4分別表示[0,1]間的隨機(jī)變量。
2.1.3 高等濃度區(qū)域粒子位置更新
由于高濃度區(qū)域的粒子代表著粒子在當(dāng)前適應(yīng)度值最小,因此,此區(qū)域的粒子更接近于全局最優(yōu)解,此時(shí)維持高濃度區(qū)域的粒子位置不變。此過程用如下公式表示:
其中,Cjbest表示當(dāng)前迭代中濃度最高粒子的位置。
在經(jīng)過多次實(shí)驗(yàn)測(cè)試后發(fā)現(xiàn),EO算法在迭代次數(shù)為1 000次時(shí)算法收斂效果較好。因此為驗(yàn)證濃度平衡機(jī)制對(duì)種群多樣性的影響,本文選取表1中部分測(cè)試函數(shù),在維度為2,種群數(shù)量為30,最大迭代次數(shù)為1 000時(shí),分別選取迭代次數(shù)為100次和900次時(shí)查看算法種群的分布情況。將加入濃度平衡機(jī)制的改進(jìn)算法與EO算法進(jìn)行對(duì)比,繪制個(gè)體位置圖,如圖1所示??梢园l(fā)現(xiàn),在迭代次數(shù)為100次時(shí),改進(jìn)算法的種群多樣性明顯得到提升,種群分布較分散,EO算法的種群雖看起來在最優(yōu)值附近,但由于縱坐標(biāo)數(shù)量級(jí)較小,尋優(yōu)精度距離理論最優(yōu)值仍有較大差距,仍需要進(jìn)一步尋優(yōu)探索;在迭代次數(shù)為900次時(shí),測(cè)試函數(shù)F3的縱坐標(biāo)數(shù)量級(jí)與迭代100次時(shí)相差209,EO算法的搜索精度相比迭代次數(shù)100次時(shí)有所提升,但仍與理論最優(yōu)值偏差較大,而此時(shí)改進(jìn)算法收斂到了理論最優(yōu)值附近。說明加入的濃度平衡機(jī)制改善了個(gè)體間信息交流缺乏的情況,中低濃度區(qū)域粒子每次迭代都會(huì)與最優(yōu)個(gè)體進(jìn)行信息交流,充分利用當(dāng)前最優(yōu)解信息,同時(shí)在一定程度上擴(kuò)大了搜索空間,提高了種群多樣性。
圖1 個(gè)體多樣性對(duì)比圖Fig.1 Comparison chart of diversity
表1 測(cè)試函數(shù)Table 1 Test function
在EO算法中,參數(shù)a1和a2用來調(diào)整全局搜索和局部開發(fā),參數(shù)a1負(fù)責(zé)調(diào)整算法全局搜索能力,其值越大,全局探索能力越強(qiáng),參數(shù)a2負(fù)責(zé)調(diào)整算法局部開發(fā)能力,其值越大,局部開發(fā)能力越強(qiáng)。但在EO算法中參數(shù)a1和a2為固定常數(shù),這樣可能導(dǎo)致算法不能根據(jù)迭代次數(shù)自適應(yīng)分配探索與開發(fā)能力,可能會(huì)出現(xiàn)尋優(yōu)不穩(wěn)定現(xiàn)象,影響算法的尋優(yōu)精度。因此,本文引入兩種可調(diào)節(jié)的自適應(yīng)因子改善算法,將算法迭代次數(shù)與參數(shù)相結(jié)合。利用指數(shù)自適應(yīng)因子動(dòng)態(tài)調(diào)整參數(shù)a1,利用冪函數(shù)自適應(yīng)因子動(dòng)態(tài)調(diào)整參數(shù)a2,使得算法根據(jù)迭代過程動(dòng)態(tài)平衡探索和開發(fā)能力,提高算法穩(wěn)定性和尋優(yōu)精度。參數(shù)a1和a2的公式定義如下:
經(jīng)過多次實(shí)驗(yàn)驗(yàn)證,λ取值為2.5時(shí)算法效果最好。如圖2所示,在算法迭代初期,參數(shù)a1接近2.5,參數(shù)a2接近于0,此時(shí)算法傾向于全局搜索;隨著迭代次數(shù)的增加,粒子濃度差減少,接近平衡,粒子轉(zhuǎn)向局部的平衡,算法更專注于局部搜索。
圖2 a1和a2參數(shù)變化曲線Fig.2 Parameter changes of a1 and a2
1855年德國(guó)人阿道夫·菲克(Adolf Fick)提出描述分子擴(kuò)散規(guī)律的基本定律:在單位時(shí)間內(nèi)通過垂直于擴(kuò)散方向的單位截面積的擴(kuò)散物質(zhì)流量(稱為擴(kuò)散通量diffusion flux)與該截面處的濃度梯度(concentration gradient)成正比,也就是說,濃度梯度越大,擴(kuò)散通量越大,這就是菲克定律[20]。其指出了在分子濃度差較大時(shí),單位時(shí)間內(nèi)的擴(kuò)散通量越大,隨著時(shí)間推移,容器內(nèi)的濃度差逐漸減小,擴(kuò)散通量變小。這說明在濃度平衡初期,容器中濃度差較高,高濃度區(qū)域粒子可以向全局?jǐn)U散,隨著濃度差逐漸減小,容器中濃度接近平衡,此時(shí)更專注于局部的濃度擴(kuò)散。也就是說,迭代初期應(yīng)加強(qiáng)算法全局搜索能力,全局搜索范圍和強(qiáng)度更大時(shí),尋優(yōu)效果更好,隨著迭代次數(shù)的增加,逐漸轉(zhuǎn)向局部搜索,從更多的候選解中尋得最優(yōu)解,提高解的精度。
在標(biāo)準(zhǔn)的EO算法中,算法在進(jìn)行濃度更新后,計(jì)算當(dāng)前解的適應(yīng)度值,然后更新粒子位置,隨后進(jìn)入后續(xù)的循環(huán),即所有候選解的位置都受當(dāng)前位置的影響,這表明EO算法雖然有很強(qiáng)的局部開發(fā)能力,但是其全局搜索能力相對(duì)來說有所不足,隨著迭代次數(shù)的增加,算法逐步趨于局部最優(yōu),而不是全局最優(yōu)。而文獻(xiàn)[21]中面對(duì)相似的問題采用擾動(dòng)因子增強(qiáng)了算法尋優(yōu)精度和收斂速度。因此,本文從菲克定律和文獻(xiàn)[21]得到啟發(fā),在算法位置更新策略中引入擾動(dòng)機(jī)制,利用擾動(dòng)因子η根據(jù)算法迭代次數(shù)來動(dòng)態(tài)改變粒子位置。算法在前期進(jìn)行較大范圍的全局搜索,隨著算法迭代次數(shù)的增加,在算法后期,小范圍的更新加強(qiáng)了算法的局部開發(fā)能力,提升解的精度,加快收斂速度。其公式定義如下:
其中,ξ為擾動(dòng)系數(shù),多次實(shí)驗(yàn)表明,其值為30時(shí)算法效果最好。加入了擾動(dòng)因子的濃度更新公式如下所示:
本文提出的NEO算法具體步驟描述如下:
步驟1設(shè)置算法相關(guān)的參數(shù),并初始化粒子種群位置。
步驟2進(jìn)入主循環(huán),計(jì)算個(gè)體適應(yīng)度值并排序,選出平衡池候選解。
步驟3利用濃度平衡機(jī)制公式(12)~(14)更新平衡池候選解。
步驟4利用公式(15)、(16)分別計(jì)算動(dòng)態(tài)參數(shù)a1和a2。
步驟5利用改進(jìn)后的濃度更新公式(18)更新粒子位置。
步驟6判斷是否滿足停止條件,若滿足則結(jié)束,否則返回步驟2。
步驟7輸出最優(yōu)解,結(jié)束程序。
假設(shè)種群規(guī)模為N,空間維度為D,最大迭代次數(shù)為T。EO算法的時(shí)間復(fù)雜度主要由種群初始化、迭代尋優(yōu)和濃度更新三部分組成。其中,種群初始化的時(shí)間復(fù)雜度為O(ND),迭代尋優(yōu)的時(shí)間復(fù)雜度為O(ND),濃度更新的時(shí)間復(fù)雜度為O(N)。因此,根據(jù)時(shí)間復(fù)雜度分析,EO算法總的時(shí)間復(fù)雜度為:
NEO算法的改進(jìn)主要由濃度平衡機(jī)制、動(dòng)態(tài)參數(shù)和擾動(dòng)機(jī)制組成。初始化階段,NEO算法與EO算法的時(shí)間復(fù)雜度相同,為O(ND);迭代尋優(yōu)階段,設(shè)濃度平衡機(jī)制花費(fèi)的時(shí)間為t1,計(jì)算動(dòng)態(tài)參數(shù)a1和a2的時(shí)間為t2,因此迭代尋優(yōu)的時(shí)間復(fù)雜度為O(ND)+t1+t2;濃度更新階段,設(shè)計(jì)算擾動(dòng)因子的時(shí)間為t3,故濃度更新的時(shí)間復(fù)雜度為t3×O(N)。因此,NEO算法最終的時(shí)間復(fù)雜度為:
綜上所述,NEO算法與EO算法的時(shí)間復(fù)雜度一致,屬于多項(xiàng)式時(shí)間算法,說明NEO算法并未犧牲空間來提升算法性能。
為了驗(yàn)證本文所提出的三種改進(jìn)策略的有效性,本文選取了國(guó)際上通用的24個(gè)基準(zhǔn)測(cè)試函數(shù)進(jìn)行仿真實(shí)驗(yàn)[22-23],包括高維單峰和高維多峰不同類型的測(cè)試函數(shù)。單峰測(cè)試函數(shù)是算法尋優(yōu)精度和收斂速度的度量,而多峰測(cè)試函數(shù)則可以體現(xiàn)算法的全局搜索能力和避免陷入局部最優(yōu)的能力。這些函數(shù)的函數(shù)名及表達(dá)式、最優(yōu)值見表1。
將NEO算法與遺傳算法(GA)[2]、粒子群算法(particle swarm optimization,PSO)[24]、鯨魚優(yōu)化算法(WOA)[3]、食肉植物算法(carnivorous plant algorithm,CPA)[25]、蜉蝣算法(mayfly algorithm,MA)[26]、平衡優(yōu)化器算法(EO)[1]以及一種改進(jìn)的平衡優(yōu)化器算法(MDSGEO)[18]進(jìn)行對(duì)比,同時(shí),設(shè)置種群大小為30,迭代次數(shù)為50,維度為1 000,保證各個(gè)法的最大適應(yīng)度評(píng)價(jià)次數(shù)相同。為使數(shù)據(jù)真實(shí)可信,仿真實(shí)驗(yàn)使用各個(gè)算法在所有測(cè)試函數(shù)上各獨(dú)立運(yùn)行20次,并記錄平均值和標(biāo)準(zhǔn)差兩個(gè)性能評(píng)價(jià)指標(biāo)。
本文實(shí)驗(yàn)采用處理器為Intel?Core?i5-8250U CPU,8 GB運(yùn)行內(nèi)存,Windows 10操作系統(tǒng),64位,仿真軟件為Matlab 2017b。
算法參數(shù)設(shè)置如下:GA算法的交叉率為0.1,變異率為0.9;PSO算法的慣性權(quán)重為1,慣性權(quán)重阻尼比為0.99,個(gè)人學(xué)習(xí)系數(shù)為1.5,全局學(xué)習(xí)系數(shù)為2.0;GWO算法參數(shù)a從2遞減到0;WOA算法參數(shù)a從2遞減到0,參數(shù)b為1;CPA算法吸引率為0.8,成長(zhǎng)率為2,生成率為1.8;MA算法父代和子代數(shù)量均為20,突變率為0.01;EO算法的a1為2,a2為1,GP為0.5;MDSGEO算法的a1為2,a2為1,GP為0.5。
為了驗(yàn)證改進(jìn)算法的有效性和可行性,本文利用平均值和標(biāo)準(zhǔn)差兩個(gè)性能指標(biāo)評(píng)估實(shí)驗(yàn)仿真結(jié)果。實(shí)驗(yàn)結(jié)果數(shù)據(jù)見表2,最優(yōu)結(jié)果已加粗表示。
表2 1 000維函數(shù)測(cè)試數(shù)據(jù)Table 2 Test data of 1 000 dimensional function
由表2可知,NEO算法和MDSGEO算法的尋優(yōu)結(jié)果優(yōu)于其他對(duì)比算法,而本文所提出的NEO算法則尋優(yōu)效果更好。
在高維測(cè)試函數(shù)上,無論是高維單峰測(cè)試函數(shù)還是高維多峰測(cè)試函數(shù),NEO算法均具有明顯的競(jìng)爭(zhēng)優(yōu)勢(shì),除函數(shù)F14和F20以外,NEO算法在兩個(gè)性能評(píng)價(jià)指標(biāo)上均取得了最好的結(jié)果0。值得注意的是,對(duì)于高維測(cè)試函數(shù)F14,雖然NEO算法的標(biāo)準(zhǔn)差稍差于CPA算法但是NEO算法的平均值明顯優(yōu)于CPA及其他對(duì)比算法,說明了NEO算法的尋優(yōu)精度更優(yōu)。而對(duì)于高維測(cè)試函數(shù)F20,顯然WOA算法的性能最好,但相較于除WOA算法以外的其他對(duì)比算法,NEO算法的搜索效果仍較為良好。綜合來看,本文提出的NEO算法具有更好的尋優(yōu)精度。
為更加清晰直觀地對(duì)比算法的尋優(yōu)精度和收斂速度,本文選取了4個(gè)測(cè)試函數(shù)繪制包含算法迭代次數(shù)和適應(yīng)度值的測(cè)試函數(shù)收斂曲線,如圖3所示。
從圖3的測(cè)試函數(shù)收斂曲線來看,NEO算法和MDSGEO算法均比其他對(duì)比算法具有更好的收斂速度和尋優(yōu)精度,但是NEO算法尋優(yōu)精度更好,收斂速度更快。NEO算法相較其他對(duì)比算法更具優(yōu)勢(shì),其收斂曲線均在其他算法收斂曲線左下方,在同等迭代次數(shù)下,NEO算法的收斂精度優(yōu)于其他算法,同時(shí)在同等收斂精度的情況下,NEO算法的迭代次數(shù)少于其他算法。
圖3 部分函數(shù)收斂曲線Fig.3 Convergence curve of partial function
其中,從測(cè)試函數(shù)F18的收斂曲線來看,NEO算法的優(yōu)勢(shì)明顯,WOA等算法在經(jīng)過一定次數(shù)的迭代之后,則陷入局部最優(yōu),無法尋得更優(yōu)解,而NEO算法則能避開此問題,說明濃度平衡機(jī)制更新了平衡池候選解,不同區(qū)域粒子進(jìn)行學(xué)習(xí)交流,增加了種群多樣性,避免個(gè)體趨同和陷入局部最優(yōu)。對(duì)于測(cè)試函數(shù)F14,NEO算法和MDSGEO算法在同等尋優(yōu)精度的情況下,NEO算法的收斂速度遠(yuǎn)快于MDSGEO算法,說明NEO算法加入的基于菲克定律的擾動(dòng)機(jī)制加快了算法收斂速度。從F14和F9可以看出,NEO算法的收斂曲線更加平滑,表明加入的自適應(yīng)參數(shù)根據(jù)算法迭代次數(shù)動(dòng)態(tài)調(diào)整,動(dòng)態(tài)平衡了算法探索和開發(fā)能力,尋優(yōu)更穩(wěn)定。而測(cè)試函數(shù)F2,NEO算法的尋優(yōu)精度和收斂速度都遠(yuǎn)遠(yuǎn)優(yōu)于MDSGEO等對(duì)比算法,同時(shí)NEO算法收斂曲線的斜率逐漸變大,說明在濃度更新公式中引入的擾動(dòng)機(jī)制在前期進(jìn)行大范圍的搜索,專注于全局搜索,在后期加快了收斂,專注于局部搜索,提高了收斂速度和尋優(yōu)精度。
以上兩組實(shí)驗(yàn)對(duì)比驗(yàn)證了本文提出的三種改進(jìn)策略都是有效的。可以看出,無論是高維單峰還是多峰測(cè)試函數(shù),NEO算法均有更好的尋優(yōu)能力和更快的收斂速度。
為更好地研究NEO算法的優(yōu)化性能,將本文提出的NEO算法與融合隨機(jī)反向?qū)W習(xí)的黏菌與算術(shù)混合優(yōu)化算法HSMAAOA[27]、模糊SCA-AOA算法[28]以及改進(jìn)Henry氣體溶解度優(yōu)化算法HHOHGSO[29]進(jìn)行對(duì)比,選取部分測(cè)試函數(shù),參數(shù)設(shè)置與3.1節(jié)保持一致,比較各個(gè)算法的尋優(yōu)精度和收斂速度。實(shí)驗(yàn)結(jié)果如表3所示,最優(yōu)結(jié)果已加粗表示。
表3 與其他改進(jìn)算法的對(duì)比結(jié)果Table 3 Comparison results with other improved algorithms
由表3可知,除測(cè)試函數(shù)F14和F20以外,NEO算法的平均值和標(biāo)準(zhǔn)差均為0。對(duì)于測(cè)試函數(shù)F14,雖然NEO算法的標(biāo)準(zhǔn)差稍差,但其具有更好的平均值。說明了NEO算法具有出色的尋優(yōu)精度。實(shí)驗(yàn)結(jié)果表明,相比其他最新改進(jìn)算法,NEO算法對(duì)某些測(cè)試函數(shù)的求解具有一定的競(jìng)爭(zhēng)力,綜合來看,NEO算法具有不錯(cuò)的優(yōu)化性能。
從圖4的部分函數(shù)收斂曲線來看,除F20以外,NEO算法的收斂速度明顯高于SCA-AOA、HSMAAOA和HHOHGSO。對(duì)于測(cè)試函數(shù)F4和F14,NEO算法在前期收斂速度較慢,后期收斂速度較快,說明加入自適應(yīng)調(diào)整參數(shù)的NEO算法根據(jù)迭代自動(dòng)調(diào)整參數(shù),前期專注于全局搜索,后期轉(zhuǎn)向局部開發(fā)。對(duì)于測(cè)試函數(shù)F18,NEO算法的收斂速度明顯優(yōu)于對(duì)比算法,說明引入的菲克定律擾動(dòng)因子加快了收斂,同時(shí)取得了良好的尋優(yōu)精度。函數(shù)F18同時(shí)說明了HSMAAOA等對(duì)比算法經(jīng)過一定的迭代次數(shù)后會(huì)陷入局部最優(yōu),而濃度平衡機(jī)制增強(qiáng)了種群間的信息交流,避免了粒子向局部最優(yōu)收斂,從而更好尋優(yōu)。函數(shù)F14則說明在尋優(yōu)精度一致時(shí),NEO算法則具有更快的收斂速度。綜上所述,NEO算法在大部分測(cè)試函數(shù)上具有不錯(cuò)的表現(xiàn),算法具有良好的優(yōu)化性能。
圖4 部分函數(shù)收斂曲線Fig.4 Convergence curve of partial function
為了更加清楚地對(duì)比算法的收斂時(shí)間和效率,表4列出了EO、SCA-AOA、HSMAAOA、HHOHGSO和NEO在所有測(cè)試函數(shù)上的評(píng)價(jià)次數(shù)對(duì)比。設(shè)定所有函數(shù)的尋優(yōu)精度為10-10,參數(shù)設(shè)置與3.1節(jié)保持一致,比較各個(gè)算法在同等尋優(yōu)精度下的函數(shù)評(píng)價(jià)次數(shù),最優(yōu)結(jié)果已加粗表示,INF表示算法無法尋得指定的尋優(yōu)精度。從表4可以看出,對(duì)于絕大部分的測(cè)試函數(shù),NEO算法的函數(shù)評(píng)價(jià)次數(shù)明顯優(yōu)于其他算法。對(duì)于測(cè)試函數(shù)F1、F4、F5、F7,雖然NEO算法的函數(shù)評(píng)價(jià)次數(shù)不是最優(yōu),但是與其他算法最優(yōu)的函數(shù)評(píng)價(jià)次數(shù)數(shù)量級(jí)相差不大。值得注意的是,NEO算法的評(píng)價(jià)次數(shù)遠(yuǎn)大于EO算法,說明本文所提出的改進(jìn)策略是有效的。因此,本文提出的NEO算法是一種較好的優(yōu)化算法。
表4 函數(shù)評(píng)價(jià)次數(shù)對(duì)比Table 4 Comparison of function evaluation times
為避免算法的偶然性,進(jìn)一步評(píng)估NEO算法的性能,在此進(jìn)行顯著性分析,運(yùn)用Wilcoxon秩和檢驗(yàn)的P值對(duì)比不同算法的差異,以確認(rèn)不同算法是否在統(tǒng)計(jì)上存在顯著不同。本次實(shí)驗(yàn)選取表1的基準(zhǔn)測(cè)試函數(shù),將NEO算法與GA、WOA、CPA、MA、EO、MDSGEO進(jìn)行對(duì)比。參數(shù)設(shè)置與3.1節(jié)保持一致,計(jì)算每個(gè)算法的Wilcoxon秩和檢驗(yàn)的P值,當(dāng)P值小于5%時(shí),說明兩個(gè)算法的尋優(yōu)效果有差異性,反之則沒有。表5中的+、-和=分別表示NEO算法秩和統(tǒng)計(jì)結(jié)果優(yōu)于、差于和等于當(dāng)前對(duì)比算法,NaN表示在秩和檢驗(yàn)中沒有統(tǒng)計(jì)數(shù)據(jù)進(jìn)行對(duì)比,Wilcoxon秩和檢驗(yàn)結(jié)果見表5。
表5 Wilcoxon秩和檢驗(yàn)的P值Table 5 P-value of Wilcoxon rank sum test
結(jié)果表明,除了沒有數(shù)據(jù)對(duì)比的情況外,NEO算法相較于其他對(duì)比算法的P值基本上都小于5%,說明從統(tǒng)計(jì)學(xué)上來說,NEO算法相比于GA、WOA、CPA、MA、EO、MDSGEO算法具有更好的尋優(yōu)能力,體現(xiàn)了NEO算法的魯棒性。
綜上所述,本節(jié)通過實(shí)驗(yàn)仿真與分析,對(duì)比了NEO算法與經(jīng)典算法、其他改進(jìn)EO算法及其他最新改進(jìn)智能優(yōu)化算法,分析了算法的尋優(yōu)效果、收斂曲線、運(yùn)算效率和Wilcoxon秩和檢驗(yàn),實(shí)驗(yàn)結(jié)果表明本文提出的NEO算法具有良好的尋優(yōu)精度和更快的收斂速度。之所以如此,得益于在NEO算法的平衡池階段,為避免只依靠適應(yīng)度值選取候選解產(chǎn)生的相似問題,加入了濃度平衡機(jī)制,在高、中、低三種濃度區(qū)域的個(gè)體都進(jìn)行不同程度的濃度融合,改變了粒子位置,增強(qiáng)了種群間的信息交流,同時(shí)豐富了種群多樣性;其次改進(jìn)了EO算法的重要參數(shù),指數(shù)自適應(yīng)因子a1和冪函數(shù)自適應(yīng)因子a2動(dòng)態(tài)平衡探索與開發(fā)能力,保證了探索與開發(fā)過程的穩(wěn)定性;最后在粒子位置更新處引入基于菲克定律的擾動(dòng)因子,擾動(dòng)因子的引入改善了濃度更新公式,加快收斂速度的同時(shí)提高了算法的尋優(yōu)精度??傊琋EO算法是性能不錯(cuò)的智能優(yōu)化算法。
本文為了解決平衡優(yōu)化器算法收斂速度慢、精度不夠、開發(fā)和搜索階段信息不平衡的問題,提出了融合濃度平衡和菲克定律的新平衡優(yōu)化器算法。算法首先引入濃度平衡機(jī)制,提高算法種群間的信息交流能力;同時(shí)改進(jìn)了算法參數(shù),采用動(dòng)態(tài)參數(shù)設(shè)計(jì)平衡全局搜索和局部開發(fā)能力;最后引入擾動(dòng)機(jī)制,擾動(dòng)更新粒子位置,提高算法的尋優(yōu)精度和收斂速度。通過24個(gè)基準(zhǔn)測(cè)試函數(shù)和Wilcoxon秩和統(tǒng)計(jì)檢測(cè)進(jìn)行實(shí)驗(yàn)仿真,結(jié)果表明,本文算法具有較好的收斂速度和尋優(yōu)精度,有效避免了早熟現(xiàn)象的發(fā)生。考慮將NEO算法應(yīng)用到應(yīng)急車輛路徑規(guī)劃問題中作為下一步的研究方向。