方波觸發(fā)勘探與開發(fā)的粒子群優(yōu)化算法

鄧志誠 孫輝, 趙嘉, 王暉 , 呂莉 , 謝海華

為解決傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜優(yōu)化問題,研究者們受啟發(fā)于生物和自然物理現(xiàn)象,提出了粒子群優(yōu)化算法、差分進化算法、人工蜂群算法、和聲搜索算法和進化策略等優(yōu)化技術(shù)以解決各領(lǐng)域的優(yōu)化任務(wù).

粒子群優(yōu)化算法(Particle swarm optimization,PSO)是由Kennedy等[1]在1995 年提出的群智能優(yōu)化算法.該算法具備計算快速和易實現(xiàn)等優(yōu)點,作為群體智能算法的一個重要分支,得到了眾多學(xué)者廣泛深入的研究.且已應(yīng)用于預(yù)測[2]、工程設(shè)計[3]、特征選擇[4]和經(jīng)濟[5]等眾多領(lǐng)域.

粒子群優(yōu)化算法是源于對鳥群捕食行為的模仿研究,人們從鳥群捕食過程當(dāng)中得到啟示,并將其用于解決優(yōu)化問題.該算法通過群體中粒子間合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索.根據(jù)算法的特性,全局最優(yōu)粒子將信息傳遞給其他粒子是單向的信息流動,可使粒子快速的收斂于最優(yōu)解.但當(dāng)全局最優(yōu)粒子處于局部最優(yōu)位置時,易導(dǎo)致所有粒子收斂到局部最優(yōu).此外,粒子在進化過程中,從全局勘探轉(zhuǎn)為局部開發(fā)階段后,若粒子處于局部最優(yōu)位置,將難以獲得逃離局部最優(yōu)位置的步長.針對上述問題,提出方波觸發(fā)勘探與開發(fā)的粒子群優(yōu)化算法(Particle swarm optimization with square wave triggered exploration and exploitation,SWTPSO),在提高全局最優(yōu)質(zhì)量的同時,進一步增強粒子逃離局部最優(yōu)的能力.

SWTPSO 中提出方波觸發(fā)機制.首先,將標(biāo)準(zhǔn)PSO 的更新公式進行改進,去除速度項和加速因子的影響,使新改進的公式局部搜索能力增強,并存儲當(dāng)前粒子的位置,作為下次使用標(biāo)準(zhǔn)PSO 公式更新種群時粒子的新步長.然后,根據(jù)種群設(shè)定的總迭代次數(shù),將種群進化的過程劃分為多個方波周期.最后,按照種群當(dāng)前運行的迭代次數(shù)屬于方波周期內(nèi)的 “高”或 “低”值,分別執(zhí)行標(biāo)準(zhǔn)PSO 公式和新改進公式更新種群,使粒子的搜索狀態(tài)隨方波周期性變化.將SWTPSO與多種其他優(yōu)化算法進行比較,其在數(shù)值優(yōu)化問題上展現(xiàn)較好的優(yōu)化性能.

本文結(jié)構(gòu)如下: 第1 節(jié)介紹標(biāo)準(zhǔn)粒子群算法原理及相關(guān)研究;第2 節(jié)闡述方波觸發(fā)機制;第3 節(jié)對本文提出的策略進行理論分析和實驗驗證;第4節(jié)將SWTPSO與新改進的PSO 和其他智能算法進行仿真實驗,并分析算法的優(yōu)化性能;第5 節(jié)為總結(jié)與展望.

1 粒子群算法及其簡要綜述

1.1 粒子群算法基本原理

設(shè)粒子數(shù)為N的種群,在維度為D的空間中搜索,粒子在解空間所處的位置可表示為xi=(xi1,xi2,···,xiD),i=1,2,···,N代表第i個粒子的位置,而每個xi都可由目標(biāo)函數(shù)求得函數(shù)值f(xi)·vi=(vi1,vi2,···,viD),i=1,2,···,N代表第i個粒子的速度,表示在每一次迭代中粒子移動的步長,pbesti=(pbesti1,pbesti2,···,pbestiD),i=1,2,···,N代表第i個粒子所經(jīng)歷的歷史最優(yōu)位置,gbest=(gbest1,gbest2,···,gbestD)代表整個種群的歷史最優(yōu)位置.速度和位置可按照以下公式更新:

式中,慣性權(quán)重w控制粒子速度v使粒子的局部和全局搜索能力相平衡,當(dāng)w較大時粒子的全局搜索能力較強,反之粒子的局部搜索能力較強.式(1)中c1和c2為學(xué)習(xí)因子(也叫加速因子),可使粒子具有自主學(xué)習(xí)和向其他優(yōu)秀粒子學(xué)習(xí)的能力,使其以較快速度向最優(yōu)解靠近.r1和r2為(0,1)內(nèi)的隨機數(shù),為粒子i在第t次迭代時歷史最優(yōu)位置的第j維,為第t次迭代時整個種群歷史最優(yōu)位置的第j維.

1.2 粒子群算法簡要綜述

粒子群優(yōu)化算法具有高效和實現(xiàn)簡單等特點,已成功應(yīng)用于許多現(xiàn)實優(yōu)化任務(wù)[6?7],但存在多樣性差、易早熟收斂等問題制約了粒子群優(yōu)化算法的發(fā)展,為克服上述問題,眾多學(xué)者做了大量研究,所做工作包含以下4 類:

1)參數(shù)選擇

慣性權(quán)重和學(xué)習(xí)因子等參數(shù),對算法的優(yōu)化性能有重要影響.文獻(xiàn)[8]首次引入時變慣性權(quán)重,改善粒子的收斂速度.文獻(xiàn)[9]根據(jù)種群的信息調(diào)整慣性權(quán)重.文獻(xiàn)[10]引入貝葉斯技術(shù)調(diào)整慣性權(quán)重.文獻(xiàn)[11]提出時變的加速因子策略.文獻(xiàn)[12]引入正余弦函數(shù)控制加速因子的變化.文獻(xiàn)[13]將慣性權(quán)重和加速因子作為三個維度信息處理.文獻(xiàn)[14]提出一種反饋系統(tǒng),該系統(tǒng)可使參數(shù)適應(yīng)粒子所處的特定環(huán)境,并使用懲罰函數(shù)來處理約束.

2)粒子更新方程

為增強粒子逃離局部最優(yōu)能力,探索更多新區(qū)域,文獻(xiàn)[15]使用高斯分布更新粒子位置.文獻(xiàn)[16]引入反向?qū)W習(xí)生成粒子的反向解參與種群進化.文獻(xiàn)[17]結(jié)合隨機學(xué)習(xí)和列維飛行策略,在標(biāo)準(zhǔn)速度更新公式中增加向隨機粒子學(xué)習(xí)項.文獻(xiàn)[18]在速度更新公式中增加子社會學(xué)習(xí)項,使粒子向鄰域最優(yōu)粒子學(xué)習(xí).文獻(xiàn)[19]中,為消除對gbest的過度依賴,將其他粒子的維度信息作為新的信息源,并提出了3 個更新粒子的公式.

3)拓?fù)浣Y(jié)構(gòu)

種群的拓?fù)浣Y(jié)構(gòu)與種群的多樣性有關(guān),吸引了眾多學(xué)者關(guān)注.文獻(xiàn)[20]分析了不同類型的靜態(tài)鄰域結(jié)構(gòu)及其對PSO 性能的影響,并認(rèn)為星型、環(huán)型和馮諾依曼拓?fù)浣Y(jié)構(gòu)的適應(yīng)性最好.文獻(xiàn)[21]使用整個鄰域的信息引導(dǎo)粒子搜索最優(yōu)解.文獻(xiàn)[22]提出自適應(yīng)時變拓?fù)溥B接模型,根據(jù)種群搜索性能改變粒子的拓?fù)溥B接,平衡算法的勘探與開發(fā)搜索.文獻(xiàn)[23]采用環(huán)形拓?fù)浣Y(jié)構(gòu)增強種群的多樣性和開發(fā)能力.文獻(xiàn)[24]在迭代過程中保留局部最優(yōu)解,并根據(jù)位置對維度進行排序,生成局部最優(yōu)拓?fù)?

4)算法混合

各優(yōu)化技術(shù)在處理不同優(yōu)化問題時展現(xiàn)不同的優(yōu)勢.文獻(xiàn)[25]通過差分算法和混沌映射控制算法運行期間的參數(shù).文獻(xiàn)[26]將遺傳算法的變異和交叉操作引入粒子群算法中.文獻(xiàn)[27]將螢火蟲算法的局部搜索能力與粒子群的全局搜索能力結(jié)合.文獻(xiàn)[28]將多種經(jīng)典的改進粒子群算法優(yōu)勢集合,通過學(xué)習(xí)上一代粒子經(jīng)驗,采用自適應(yīng)方法為粒子分配最佳策略.文獻(xiàn)[29]將標(biāo)準(zhǔn)PSO 和社交學(xué)習(xí)粒子群優(yōu)化相結(jié)合,以提高算法的探索和開發(fā)能力,并在30、50 和100 維上驗證了算法的性能.

綜上研究可知,通過在種群進化過程中調(diào)節(jié)參數(shù),動態(tài)調(diào)節(jié)勘探與開發(fā);通過改變粒子的更新方程,進一步改變粒子的運動方式或運動軌跡;通過改變粒子的拓?fù)浣Y(jié)構(gòu),根據(jù)粒子間不同的信息分享機制調(diào)節(jié)勘探與開發(fā);通過將其他智能算法的策略引入粒子群算法中,調(diào)節(jié)勘探與開發(fā).

上述算法的種群在進化的全過程,始終保持初始設(shè)置的進化方式不變,或只對進化方式進行簡單單一調(diào)整.例如,在進行參數(shù)選擇的改進中,其使用的慣性權(quán)重線性變化策略,可等價為以整個進化過程為一個周期,通過慣性權(quán)重的變化,調(diào)節(jié)勘探與開發(fā).因周期設(shè)置不合理,容易出現(xiàn)因勘探持續(xù)時間過長而耗費評估資源,或因陷入局部最優(yōu)后難以再次進行全局勘探等問題.同理,在粒子更新方程、拓?fù)浣Y(jié)構(gòu)和算法混合等改進中,都未考慮多階段調(diào)整種群的進化方式,進而調(diào)節(jié)勘探與開發(fā)等問題.

針對上述問題,本文提出方波觸發(fā)勘探與開發(fā)的粒子群優(yōu)化算法,其將種群進化過程劃分為多個方波周期,周期性地增強種群勘探與開發(fā)能力,可避免因過度勘探造成評估資源浪費,又同時增強粒子逃離局部最優(yōu)的能力,進一步提升算法的收斂速度和精度.

2 方波觸發(fā)勘探與開發(fā)的粒子群優(yōu)化算法

2.1 方波觸發(fā)機制

方波(Square wave,SW)是一種非正弦曲線波形,通常在邏輯電路和信號處理時出現(xiàn).理想方波只有 “高”和 “低”兩個值.“高”值在一個波形周期內(nèi)占有的時間比值稱為占空比,占空比為50%的矩形波稱為方波.若使用1 和0 分別表示方波振幅的高和低值,則方波的前半個周期內(nèi)振幅為1,后半個周期振幅為0.方波表達(dá)式見下:

式中,t為種群當(dāng)前迭代次數(shù),T為方波函數(shù)的周期,n為整個迭代過程可劃定的周期個數(shù),n=1,2,···,Max_iteration/T,Max_iteration為最大迭代次數(shù).

標(biāo)準(zhǔn)粒子群算法在優(yōu)化過程中,整個粒子群體根據(jù)全體粒子和自身的搜索經(jīng)驗向著最優(yōu)解的方向“飛行”,在較大動量項系數(shù)(加速因子等)的作用下,粒子可能錯過最優(yōu)解,使算法收斂到局部最優(yōu).

為消除動量項的影響,在新速度更新式(4)中,原等式(1)右邊的速度項替換成粒子的當(dāng)前位置,加速因子設(shè)置為1,r4和r5為(0,1)間的隨機數(shù).聯(lián)合式(4)～ (5)可知,其可使粒子獲得比前半周期更小的步長,粒子直接向個體最優(yōu)(pbest)和全局最優(yōu)(gbest)學(xué)習(xí),探測兩者外圍解空間區(qū)域,相對增強種群局部搜索能力.

在標(biāo)準(zhǔn)粒子群算法進化過程中,搜索狀態(tài)由全局勘探轉(zhuǎn)為局部開發(fā)后,若種群陷入局部最優(yōu),則粒子多樣性喪失較快,難以逃離局部最優(yōu).此外,種群執(zhí)行局部開發(fā)搜索后,難以再次開啟全局勘探搜索.

針對上述問題,SWTPSO 利用方波的周期特性,在種群的進化過程中,使粒子周期性增強全局勘探與局部開發(fā)搜索.具體實現(xiàn)過程如下:

由式(6)可知,在前半個方波周期內(nèi),使用標(biāo)準(zhǔn)PSO 公式增強全局勘探能力,提高尋得最優(yōu)解的概率;在后半個方波周期內(nèi),使用去除動量項的改進公式更新種群,增強其局部搜索能力,對所探得區(qū)域進行精細(xì)搜索.在整個方波周期內(nèi),種群在前半周期相對于后半周期,增強全局勘探能力,后半周期相對前半周期增強局部開發(fā)能力.當(dāng)種群粒子執(zhí)行完后半個周期的局部搜索后,在下個周期將自動獲得與粒子當(dāng)前位置有關(guān)的新速度,使粒子獲得的運動步長多變,種群多樣性增強.

2.2 算法實現(xiàn)步驟

本文采用方波觸發(fā)機制,可有效平衡算法全局勘探與局部開發(fā)的能力,算法實現(xiàn)步驟如下:

算法1.SWTPSO 程序

3 算法策略分析

本節(jié)主要對算法采用的策略進行理論分析或?qū)嶒烌炞C,通過實驗測定方波觸發(fā)機制中的最佳方波周期T,并驗證方波觸發(fā)機制可有效提高種群多樣性.

方波觸發(fā)機制從整個種群搜索狀態(tài)入手,在式(1)中去除速度項,使算法擁有更強的局部搜索能力,而保留速度項的標(biāo)準(zhǔn)PSO 更新公式,則可探索更多新搜索空間[8].方波觸發(fā)機制將種群進化的全過程劃分為若干個方波周期,在一個周期內(nèi)的前半個周期采用式(1)～ (2)更新種群,進行大范圍的全局搜索,在后半個周期內(nèi)采用式(4)～ (5)更新種群,進行小范圍的局部搜索,以此平衡算法的勘探與開發(fā)能力.因此,為提高算法的優(yōu)化性能,劃分合適的方波周期是本文的關(guān)鍵.

3.1 方波周期分析

為便于實驗分析設(shè)定最佳方波周期T,改為求f=1/T=n/Max_iteration的值,n為周期的個數(shù),Max_iteration為最大迭代次數(shù).在算法運行時,周期T為初始化設(shè)定的常數(shù),當(dāng)最大迭代次數(shù)Max_iteration變化,則只有周期執(zhí)行的個數(shù)n變化.本文通過取不同的f值,測試算法在優(yōu)化不同函數(shù)時展現(xiàn)的綜合性能,選取最佳方波周期T.因此,本文設(shè)定的最佳方波周期T只與算法的優(yōu)化性能有關(guān),與本節(jié)設(shè)定的最大迭代次數(shù)無關(guān).

實驗選取多模函數(shù)Penalized 2、Levy 作為測試函數(shù),粒子數(shù)N為10,維度D為30,最大迭代次數(shù)為20000,各函數(shù)運行30 次,當(dāng)所得全局最優(yōu)適應(yīng)值達(dá)到 10?18,則認(rèn)為算法求得函數(shù)最優(yōu)解,記錄下所需迭代次數(shù).當(dāng)算法達(dá)到終止條件,全局最優(yōu)適應(yīng)值未滿足10?18,則判定此次運行搜索失敗,用“×” 標(biāo)示,且不計入平均值的計算.f分為0.01～0.002共9 個值,實驗結(jié)果見表1～ 2.

表1 Penalized 2 函數(shù)上使用不同的f 值尋找全局最優(yōu)值的迭代次數(shù)Table 1 Numbers of iterations for finding the global optimum using different values of f on the Penalized 2 function

在Penalized 2 函數(shù)上,當(dāng)f為0.01 時,算法有28 次求得最優(yōu)解,其平均迭代次數(shù)為4798.當(dāng)f為0.009、0.008、0.007、0.006、0.005、0.004 時,算法在30 次都求得最優(yōu)解.其中,當(dāng)f為0.009 時,平均迭代次數(shù) 為5148;當(dāng)f為0.008 時,平均迭代次數(shù)為6028;當(dāng)f為0.007 時,平均迭代次數(shù)為5277;當(dāng)0.006 時,平均迭代次數(shù)為5021;當(dāng)f為0.005 時,平均迭代次數(shù)為4488;當(dāng)f為0.004 時,平均迭代次數(shù)為4510.當(dāng)f為0.003 時,算法有29 次求得最優(yōu)解,平均迭代次數(shù)4907.當(dāng)f為0.002 時,算法有25 次求得最優(yōu)解,平均迭代次數(shù)為3219.

在Levy 函數(shù)上,當(dāng)f為0.01 時,算法有22 次求得最優(yōu)解,平均迭代次數(shù)5887.當(dāng)f為0.009、0.008、0.007 和0.005 時,算法在29 次都求得最優(yōu)解,其中0.009 時平均迭代次數(shù)為5954;0.008 時平均迭代次數(shù)為5259;0.007 時平均迭代次數(shù)為4923;0.005 時平均迭代次數(shù)為4321.當(dāng)f為0.006 時,算法有27 次求得最優(yōu)解,平均迭代次數(shù)4027.當(dāng)f為0.004 時,算法有30 次求得最優(yōu)解,平均迭代次數(shù)4494.當(dāng)f為0.003 時,算法有28 次求得最優(yōu)解,平均迭代次數(shù)4252.當(dāng)f為0.002 時,算法有27 次求得最優(yōu)解,平均迭代次數(shù)5146.

為更直觀反映f值對算法優(yōu)化性能的影響,以不同f值為橫坐標(biāo),算法在運行30 次中未尋得最優(yōu)解的次數(shù)為縱坐標(biāo),繪制折線圖1.在Penalized 2函數(shù)上,f為0.004、0.005、0.006、0.007、0.008、0.009 時,算法都能求得最優(yōu)解.在Levy 函數(shù)上,f為0.004 時,算法能求得最優(yōu)解.

圖1 不同f 值的失敗次數(shù)Fig.1 Number of failures for different f

綜合分析實驗結(jié)果可知,不同的周期T對算法優(yōu)化性能有重要影響,當(dāng)T設(shè)置過大,種群長時間使用標(biāo)準(zhǔn)PSO 更新公式搜索解空間,其具有的較大動量項系數(shù)將使種群錯過最優(yōu)解,且周期過大將占用大量的迭代次數(shù),使執(zhí)行的周期次數(shù)變少,種群粒子自動獲得較大步長的次數(shù)減少,削弱了種群逃離局部最優(yōu)的能力;當(dāng)T設(shè)置過小,種群粒子或未探得最優(yōu)解所在區(qū)域,就進行局部搜索,使種群在局部最優(yōu)區(qū)域耗費評估次數(shù).

對于f的取值,通過增加兩組不同類型(單模、多模、旋轉(zhuǎn)、偏移、組合等)測試函數(shù)進行實驗,驗證了f的最佳取值范圍為[0.004,0.009].當(dāng)f=0.004 時,所得秩均值最小,算法擁有更好優(yōu)化性能.

3.2 粒子步長和種群多樣性分析

分析標(biāo)準(zhǔn)PSO 算法中粒子的運動方式,將式(1)～ (2)經(jīng)整理變化,可得:

粒子的實際運動步長為:

本文提出的方波觸發(fā)機制,在一個方波周期內(nèi)的前半個方波周期采用式(1)～ (2)更新種群,搜索到一定區(qū)域后,使用式(4)～ (5)在后半個方波周期對該區(qū)域進行精細(xì)搜索.再到執(zhí)行下一個方波周期時,式(6)中所得粒子的速度V,將自動替換成為式(1)等號右邊第1項V,此時再次使用式(1)～(2)更新,粒子的實際運動步長為:

為驗證標(biāo)準(zhǔn)PSO 公式下 (steppso),相比方波觸發(fā)機制下 (stepsw) 的優(yōu)勢,使用Rastrigin 函數(shù),測試粒子在進化過程中步長的變化.實驗中,種群個數(shù)為N=10,維度D=10,迭代次數(shù)為500 次.隨機選取種群中一個粒子,記錄粒子10 個維度中步長的變化情況.實驗結(jié)果見圖2.

第1～ 250 迭代次數(shù)為前半個周期,第251～500 迭代次數(shù)為后半個周期.由圖2 中可以看出,在粒子的10 個維度中,stepsw步長的變化次數(shù)在進化全過程多于steppso,驗證在stepsw策略下,通過提供多變的步長,可達(dá)到按周期觸發(fā)勘探與開發(fā)的目的.

圖2 粒子在10 維中的步長變化Fig.2 Step size changes of 10 dimensions of particles

為驗證引入方波觸發(fā)機制可有效提高種群多樣性,使用多樣性度量式(10)[30],對比標(biāo)準(zhǔn)PSO 和加入方波觸發(fā)機制的PSO,其種群進化過程中多樣性的變化.

式中,N表示種群的個數(shù),2·a為搜索空間的范圍,D表示維度,xˉ 表示種群的中心位置.方波觸發(fā)機制記為SW,選取Rastrigin 旋轉(zhuǎn)偏移函數(shù)和Shifted 旋轉(zhuǎn)偏移函數(shù)進行測試,粒子數(shù)N為10,維度D為30,評估次數(shù)為10000 次,所得兩者多樣性實驗結(jié)果見圖3.引入方波觸發(fā)機制的PSO (PSO +SW)比標(biāo)準(zhǔn)PSO,在種群進化的全過程中能保持更高的多樣性,種群勘探與開發(fā)能力可保持更好平衡.同時對標(biāo)準(zhǔn)PSO 和PSO+SW 進行收斂性分析,見圖4.實驗結(jié)果表明,PSO+SW 比標(biāo)準(zhǔn)PSO可收斂到更高精度解.

圖3 PSO 和PSO+SW 的種群多樣性變化Fig.3 The population’s diversity of PSO and PSO+SW

圖4 PSO 和PSO+SW 的收斂性Fig.4 The convergence performance of PSO and PSO+SW

4 仿真實驗

本節(jié)結(jié)構(gòu)如下: 第4.1 節(jié)設(shè)置SWTPSO 涉及的參數(shù),給出測試函數(shù)的基本信息;第4.2 節(jié)選取新近改進的PSO與SWTPSO 在維度為30、50、100的條件下比較;第4.3 節(jié)對算法收斂性能進行分析.第4.4 節(jié)將SWTPSO與新改進的蜂群和差分算法在26 個函數(shù)上進行50 維比較,再與改進和聲搜索算法、粒子群算法、人工蜂群算法、差分算法進行100 維比較,最后在CEC2015 測試集上進一步驗證SWTPSO 的優(yōu)化性能.

4.1 測試函數(shù)和參數(shù)設(shè)置

引入26 個基準(zhǔn)函數(shù)進行仿真實驗,表3 給出了26 個測試函數(shù)的基本信息.SWTPSO 的參數(shù)設(shè)置如下: 種群規(guī)模N設(shè)置為10,c1和c2設(shè)置為2.0,慣性權(quán)重w=0.55×exp(?0.5×iterNum/Max?iterNum),用Max_iterNum表示最大迭代次數(shù),iterNum表示當(dāng)前迭代次數(shù),方波觸發(fā)機制中,f值設(shè)為0.004.

表3 26 個基準(zhǔn)測試函數(shù)Table 3 Information of 26 benchmark functions

表3 26 個基準(zhǔn)測試函數(shù) (續(xù)表)Table 3 Information of 26 benchmark functions (continued table)

表3 26 個基準(zhǔn)測試函數(shù) (續(xù)表)Table 3 Information of 26 benchmark functions (continued table)

4.2 仿真實驗及結(jié)果分析

將SWTPSO與7 種PSO 改進算法在維度D=30、50、100 的條件下對比,7 種PSO 改進算法分別為Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients (HPSO-TVAC)[11]、Comprehensive learning particle swarm optimizer for global optimization of multi-modal functions (CLPSO)[31]、A novel particle swarm optimization algorithm with levy flight (LFPSO)[32]、Dynamic multi-swarm particle swarm optimizer (DMS-PSO)[33]、An enhanced particle swarm optimization with levy flight for global optimization (PSOLF)[34]、A particle swarm optimization algorithm with random learning mechanism and levy flight for optimization of atomic clusters (RPSOLF)[17]、A hybrid particle swarm optimizer with sine cosine acceleration coefficients (H-PSO-SCAC)[12].各算法的參數(shù)都按照原文獻(xiàn)設(shè)置,當(dāng)D=30 時,評估次數(shù)設(shè)為20 萬次;D=50 時,評估次數(shù)設(shè)為25 萬次;D=100 時,評估次數(shù)設(shè)為50 萬次.所有算法獨立運行50 次,最終結(jié)果取50 次的平均值,具體實驗數(shù)據(jù)見表4～6.表中,MBF 表示平均最優(yōu)適應(yīng)值,SD 表示標(biāo)準(zhǔn)差,粗體表示最好值.

由表4～6 可以看出,在相同評估次數(shù)下,SWTPSO在D=30,50,100 維時,所測函數(shù)f1、f2、f6、f8、f12、f13、f14全部求得最優(yōu)解,所測函數(shù)f9、f10同樣求得比其他算法更高質(zhì)量的解,測試f3、f4、f5函數(shù)所得最優(yōu)解相比其他算法優(yōu)勢明顯.CLPSO在測試函數(shù)f5時優(yōu)勢明顯,其余函數(shù)在30 維時能取得較好質(zhì)量的解,但在50、100 維時算法性能有待加強.CLPSO 主要借助不同的個體最優(yōu)(pbest)優(yōu)勢信息產(chǎn)生最優(yōu)解,但因其在搜索過程中種群常易更新停滯,早熟收斂仍是CLPSO 需解決的問題.HPSO-TVAC 和DMS-PSO 在測試函數(shù)f9、f10時優(yōu)勢明顯,測試其余函數(shù)時,上述算法在低維時能求得較好質(zhì)量的解,在高維搜索時算法易陷入局部最優(yōu).LFPSO、RPSOLF 都采用列維飛行策略,使種群增加了隨機步長,其中LFPSO 使種群粒子繞著最優(yōu)解做列維飛行,在算法后期種群易更新停滯,故LFPSO 在低維時,測試單模和多模函數(shù)時,搜索到最優(yōu)解的質(zhì)量較高,但在高維仍易陷入局部最優(yōu).LFPSO 和RPSOLF 則另增加了隨機選擇策略,在一定概率范圍內(nèi)使用列維飛行策略,在測試函數(shù)f1、f2、f6、f8、f12、f13、f14求得了函數(shù)最優(yōu)解,但在高維條件下測試f9、f10時算法仍陷入局部最優(yōu).H-PSOSCAC 采用sin、cos 函數(shù)控制加速因子的變化,并在使用反向?qū)W習(xí)初始化種群后,采用改進的速度更新公式,其在優(yōu)化函數(shù)f4時,能夠取得較高質(zhì)量的解,在函數(shù)f1、f2、f6、f8、f12、f13、f14同樣能求得函數(shù)最優(yōu)解,但在測試函數(shù)f9和f10時,算法仍陷入局部最優(yōu).

表4 30 維實驗結(jié)果對比Table 4 Comparison of 30-dimensional test results

為進一步綜合評價SWTPSO 的性能,引入Friedman 檢驗分析所得測試數(shù)據(jù),秩均值作為Fri-edman 檢驗的評價參數(shù),該值越小,表明算法的性能更優(yōu).表7 給出各算法數(shù)據(jù)的Friedman 檢驗結(jié)果,其中SWTPSO 在維度D=30,50,100 維時,所得秩均值最小,故該算法性能更優(yōu).H-PSO-SCAC在不同維度下的優(yōu)化性能較為穩(wěn)定,RPSOLF、PSOLF、LFPSO 在30 和50 維時優(yōu)化性能較強,在100 維時優(yōu)化性能減弱,CLPSO 和DMS-PSO的優(yōu)化性能隨維度的增加逐漸減弱,HPSO-TVAC在30 維的優(yōu)化性能弱于50 和100 維.

表5 50 維實驗結(jié)果對比Table 5 Comparison of 50-dimensional test results

表6 100 維實驗結(jié)果對比Table 6 Comparison of 100-dimensional test results

表6 100 維實驗結(jié)果對比 (續(xù)表)Table 6 Comparison of 100-dimensional test results (continued table)

表7 各PSO 算法的Friedman 檢驗結(jié)果Table 7 Friedman test results of each POS algorithm

4.3 收斂性分析

圖5 在維度為30,評估次數(shù)20 萬次的條件下,對SWTPSO與CLPSO、HPSO-TVAC、DMSPSO、LFPSO、PSOLF、RPSOLF 和H-PSOSCAC,在函數(shù)f1～f14優(yōu)化過程中的收斂性能進行分析,圖5 中Fitness 表示算法所得適應(yīng)值.在單模函數(shù)Sphere、Schwefel2.22上,所有算法在Sphere函數(shù)上都能夠求得較高精度的解,但SWTPSO 求得最優(yōu)解所用評估次數(shù)更少,收斂速度最快.在Schwefel2.2 上,DMS-PSO未能求得最優(yōu)解,其余算法能求得較高精度的解,但消耗的評估次數(shù)比SWTPSO 多.

圖5 14 個函數(shù)進化曲線圖Fig.5 Evolution curves of 14 functions

在單模函數(shù)Rosebrock、Quartic 上,H-PSOSCAC 的優(yōu)化性能突出,能求得比其他算法更高精度的解.SWTPSO 相比其他算法,收斂到較有優(yōu)勢的解且收斂速度較快.

在多模函數(shù)Schwefel2.26 上,CLPSO 的優(yōu)化性能相比其他算法優(yōu)勢明顯,所求解的精度最高,收斂速度最快.SWTPSO 對此函數(shù)的優(yōu)化能力相比其他函數(shù)較有優(yōu)勢.

在多模函數(shù)Rastrigin、Ackley、Griewank 上,SWTPSO、PSOLF、RPSOLF 和H-PSO-SCAC 都能求得最優(yōu)解,SWTPSO 相比其他算法在收斂速度上,有較大優(yōu)勢.其余算法收斂速度慢,且收斂精度低.

在多模函數(shù)Penalized 1、Penalized 2 上,HPSO-SCAC 和PSOLF 收斂精度較低,其他算法能夠收斂到較高精度的解,SWTPSO 的收斂速度更快、精度更高.

在旋轉(zhuǎn)函數(shù)Rotated Schwefel2.26 上,PSOLF的收斂精度最高,SWTPSO 相比其他算法收斂速度和精度有較大優(yōu)勢.

在旋轉(zhuǎn)函數(shù)Rotated Rastrigin、Rotated Ackley、Rotated Griewank 上,SWTPSO、PSOLF、RPSOLF 和H-PSO-SCAC 都能求得最優(yōu)解,SWTPSO在收斂速度上優(yōu)勢明顯,其余算法未能求得最優(yōu)解.

4.4 與相關(guān)新算法比較

4.4.1 在50 維的常規(guī)基準(zhǔn)函數(shù)上的實驗結(jié)果

為進一步體現(xiàn)SWTPSO 的性能,將其與改進人工蜂群算法Bare bones artificial bee colony algorithm with parameter adaptation and fitnessbased neighborhood (BABC)[35]、Accelerating artificial bee colony algorithm with adaptive local search (AABCLS)[36]、Artificial bee colony algorithm with variable search strategy for continuous optimization (ABCVSS)[37]、Modified Gbestguided artificial bee colony algorithm with new probability model (MPGABC)[38]改進差分算法Differential evolution with composite trial vector generation strategies and control parameters (Co-DE)[39]、Adaptive differential evolution with optional external archive (JADE)[40]、Self-adaptive differential evolution algorithm using population size reduction and three strategies (jDEscop)[41]、Differential evolution algorithm with strategy adaptation for global numerical optimization (Sa-DE)[42],以及高效的進化策略Completely derandomized self-adaptation in evolution strategies(CMAES)[43]比較.實驗選取第4.1 節(jié)的26 個基準(zhǔn)函數(shù),設(shè)置維度D=50,評估次數(shù)為25 萬次,各函數(shù)參數(shù)設(shè)置參照原文獻(xiàn),所得實驗結(jié)果見表8,表8中MPGABC 的數(shù)據(jù)來源文獻(xiàn)[38],其余各算法的數(shù)據(jù)參照文獻(xiàn)[30].由表8 數(shù)據(jù)可知,在測試的22個函數(shù)中,SWTPSO在f1～f7、f11～f13、f18、f20共12 個函數(shù)上尋得最優(yōu)解,且穩(wěn)定性強,相比其他8 種相關(guān)新算法,優(yōu)勢突出.在f9和f15函數(shù)上,SWTPSO 所得最優(yōu)解,算法的穩(wěn)定性都優(yōu)于其他算法.在剩余的函數(shù)上,SWTPSO 總體優(yōu)勢明顯.將8 種新相關(guān)算法與SWTPSO 進行Friedman 檢驗,所得結(jié)果見表9.表9 中SWTPSO 所得秩均值最小,表明其更具優(yōu)勢.

4.4.2 在100 維的常規(guī)基準(zhǔn)函數(shù)上的實驗結(jié)果

將改進的和聲搜索算法Global dynamic harmony search algorithm (GDHS)[44]、An improved global-best harmony search algorithm (IGHS)[45]、差分算法Opposition-based differential evolution(ODE)[46]、人工蜂群算法Gbest-guided artificial bee colony algorithm for numerical function opti- mization (GABC)[47]、粒子群Improved global-bestguided particle swarm optimization with learning operation for global optimization problems (IGPSO)[48]和本文算法比較,維度為100,評估次數(shù)為50 萬次,各算法獨立運行50 次,算法所測函數(shù)參考文獻(xiàn)[48]的表2～ 3,數(shù)據(jù)來源參考文獻(xiàn)[48]中表9～10.實驗所得結(jié)果見表10,本文算法在f1～f4、f6、f9、f11、f14～f15共9 個函數(shù)中求得最優(yōu)解,在f5、f7、f8、f10、f12～f13共6 個函數(shù)中求得最優(yōu)解優(yōu)勢明顯,將6 種算法與SWTPSO 進行Friedman 檢驗,所得結(jié)果見表11,表11 中SWTPSO 所得秩均值最小,表明其更具優(yōu)勢.

表2 Levy 函數(shù)上使用不同的f 值尋找全局最優(yōu)值的迭代次數(shù)Table 2 Numbers of iterations for finding the global optimum using different values of f on the Levy function

表2 Levy 函數(shù)上使用不同的f 值尋找全局最優(yōu)值的迭代次數(shù) (續(xù)表)Table 2 Numbers of iterations for finding the global optimum using different values of f on the Levy function (continued table)

表9 8 種新相關(guān)算法和SWTPSO 的Friedman 測試結(jié)果Table 9 Friedman test results of 8 new correlation algorithms and SWTPSO

表10 6 種算法在15 個函數(shù)上的比較結(jié)果Table 10 Results of the fifteen functions for six algorithms

表10 6 種算法在15 個函數(shù)上的比較結(jié)果 (續(xù)表)Table 10 Results of the fifteen functions for six algorithms (continued table)

表11 6 種算法的Friedman 檢驗結(jié)果Table 11 Friedman test results of 6 algorithms

4.4.3 在30 維的CEC2015 測試集上的實驗結(jié)果

群智能算法經(jīng)過近幾年的大量研究,絕大多數(shù)改進算法對較早版本的標(biāo)準(zhǔn)測試函數(shù)有較好優(yōu)化效果.因此,本文采用新近提出的測試函數(shù)CEC2015[49]進一步驗證算法的優(yōu)化性能,表12 為CEC2015函數(shù)集.

表12 CEC2015 函數(shù)集Table 12 CEC2015 test suite

表12 CEC2015 函數(shù)集 (續(xù)表)Table 12 CEC2015 test suite (continued table)

SWTPSO 分別與新近提出的螢火蟲與粒子群混合優(yōu)化算法(Fire fly particle swarm optimization,FFPSO)[50],Hybrid particle swarm opti-mization and fire fly (HPSOFF)[51]、A hybrid algorithm combining firefly and particle swarm optimization (HFPSO)[27]比較,維度D=30,評估次數(shù)為1500,實驗數(shù)據(jù)和其他參數(shù)設(shè)置參見文獻(xiàn)[27].

表13 為各算法測函數(shù)CEC 2015 的實驗結(jié)果,SWTPSO 在所測15 個函數(shù)中,有14 個函數(shù)占較大優(yōu)勢.表14 對各算法進行Friedman 檢驗,SWTPSO 所得秩均值最小,再次驗證了本文算法更具優(yōu)勢.

表13 CEC2015 實驗結(jié)果對比Table 13 Test results comparison of CEC2015 test suite

表14 Friedman 檢驗結(jié)果Table 14 Results of Friedman test

5 結(jié)束語

為提高粒子群算法全局最優(yōu)的質(zhì)量,增強粒子逃離局部最優(yōu)的能力,本文提出方波觸發(fā)機制,在種群初始化后,在前半個方波周期內(nèi)進行全局勘探,探索更多新解空間區(qū)域,在后半個方波周期內(nèi)轉(zhuǎn)換為局部開發(fā),對該區(qū)域進行精細(xì)搜索.在下個周期將自動獲得與粒子當(dāng)前位置有關(guān)的新速度,使粒子獲得的運動步長多變,種群多樣性增強.在第3.1 節(jié)中通過實驗測定出方波觸發(fā)機制的最佳周期,并在第3.2 節(jié)中證明,方波觸發(fā)機制通過為粒子提供多變步長,提升種群的多樣性.在多類型測試函數(shù)上與新改進粒子群算法進行30、50、100 維的測試,且與其他新種類智能算法比較,結(jié)果都表明SWTPSO優(yōu)化性能更具優(yōu)勢.

但是,SWTPSO 在高維情況下測試復(fù)雜函數(shù)時,仍易陷入局部最優(yōu).下一步的研究工作可從以下方面展開: 在方波觸發(fā)機制中,使用標(biāo)準(zhǔn)PSO 公式進行全局勘探,未考慮進化后期標(biāo)準(zhǔn)PSO 中粒子的速度將變小,全局勘探能力減弱的問題,下一步的研究中,可提出改進的更新公式,承擔(dān)全局勘探任務(wù).