趨優(yōu)算子和Levy Flight混合的粒子群優(yōu)化算法

張新明，王 霞，涂 強(qiáng)，康 強(qiáng)

(1. 河南師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453007；2. 河南省高校計(jì)算智能與數(shù)據(jù)挖掘工程技術(shù)研究中心 河南 新鄉(xiāng) 453007)

使用傳統(tǒng)的優(yōu)化方法已經(jīng)無(wú)法有效地解決現(xiàn)實(shí)中的許多優(yōu)化問(wèn)題，因此，近年來(lái)引進(jìn)了大量的自然啟發(fā)式算法。自然啟發(fā)式算法又稱為智能優(yōu)化算法，受啟發(fā)于自然界生物的社會(huì)行為等。粒子群優(yōu)化(particle swarm optimization, PSO)算法[1]作為較早的自然啟發(fā)式算法，它模擬了鳥(niǎo)群或魚(yú)群捕食時(shí)的社會(huì)行為。該算法因需調(diào)整的參數(shù)較少和易于實(shí)施的優(yōu)勢(shì)在許多優(yōu)化問(wèn)題上被廣泛使用，但仍然存在早熟收斂、極易陷入局部最優(yōu)等問(wèn)題。針對(duì)PSO存在的問(wèn)題，研究人員已經(jīng)提出了許多基于PSO的改進(jìn)算法[2-10]，目的在于提高PSO的優(yōu)化性能。文獻(xiàn)[2]通過(guò)反向?qū)W習(xí)與局部學(xué)習(xí)的協(xié)同行為，提出了具有反向?qū)W習(xí)和局部學(xué)習(xí)能力的PSO算法(reverselearning and local-learning PSO, RLPSO)。文獻(xiàn)[3]結(jié)合自適應(yīng)勞動(dòng)分工模塊，采用凸算子和反射算子，提出了自適應(yīng)勞動(dòng)分工的PSO算法。文獻(xiàn)[4]將PSO與兩種人類(lèi)最好的學(xué)習(xí)策略(包括自我調(diào)節(jié)慣性權(quán)重、在全局搜索方向進(jìn)行自我認(rèn)知)進(jìn)行結(jié)合實(shí)現(xiàn)算法的快速收斂，提出了一種自我調(diào)節(jié)PSO算法(self regulating PSO, SRPSO)。文獻(xiàn)[5]針對(duì)PSO的早熟收斂問(wèn)題，引進(jìn)5次連續(xù)變異策略，提出了一種增強(qiáng)領(lǐng)導(dǎo)者的PSO算法(enhanced leader PSO, ELPSO)。文獻(xiàn)[6]結(jié)合PSO和Levy Flight算子，提出了嵌入Levy Flight的PSO算法(PSO with Levy Flight, LFPSO)。文獻(xiàn)[7]結(jié)合動(dòng)態(tài)概率PSO算法的特點(diǎn)，提出了一種基于異構(gòu)多種群策略的DPPSO算法。文獻(xiàn)[10]提出了一種自適應(yīng)慣性權(quán)重策略，每一個(gè)粒子在不同維都有它自己的慣性權(quán)重，是一種新的基于自適應(yīng)慣性權(quán)重的PSO算法。但以上算法或多或少存在如下問(wèn)題：優(yōu)化效率不高，普適性不強(qiáng)等。另外，在現(xiàn)有的改進(jìn)算法中，許多是對(duì)PSO的基本參數(shù)進(jìn)行研究和改進(jìn)，以便提高算法的性能。在PSO參數(shù)研究文獻(xiàn)中，對(duì)慣性權(quán)重ω、學(xué)習(xí)因子1c和2c參數(shù)研究較多，但對(duì)速度邊界參數(shù)Vmax和Vmin研究甚少。

本文針對(duì)LFPSO存在的問(wèn)題，首先改進(jìn)Levy Flight，然后引進(jìn)趨優(yōu)算子，并使趨優(yōu)算子與改進(jìn)的Levy Flight算子交替執(zhí)行；最后對(duì)固定速度邊界采用動(dòng)態(tài)調(diào)整策略，構(gòu)成改進(jìn)的LFPSO(improved LFPSO,ILFPSO)算法。

1 LFPSO算法

圖1 LFPSO算法流程圖

LFPSO算法[6]將Levy Flight嵌入到PSO算法中，用于解決PSO的早熟收斂和全局搜索能力不足的問(wèn)題。Levy Flight是一種非高斯隨機(jī)過(guò)程，是從Levy穩(wěn)定分布中提取的隨機(jī)游走方式，確保了PSO可以更有效地進(jìn)行全局搜索而不會(huì)陷入局部停滯。LFPSO算法為每個(gè)粒子的試驗(yàn)次數(shù)設(shè)置一個(gè)閾值，在閾值以內(nèi)的粒子速度與其位置更新如下：

而超出閾值時(shí)，粒子則執(zhí)行Levy Flight操作，對(duì)粒子的位置進(jìn)行重新分配：

式中，符號(hào)⊕表示數(shù)組中每個(gè)對(duì)應(yīng)元素的乘法運(yùn)算。LFPSO算法的基本流程圖如圖1所示。其中，trial(i)表示第i個(gè)粒子當(dāng)前的試驗(yàn)次數(shù)，limit表示為每個(gè)粒子設(shè)置的閾值。值得注意的是：若更新后的粒子較優(yōu)，trial(i)重置為0，否則trial(i)就加1。

2 趨優(yōu)算子與Levy Flight混合的粒子群優(yōu)化算法(ILFPSO)

2.1 LFPSO存在的問(wèn)題

LFPSO存在的兩大問(wèn)題：1) 由于Levy步長(zhǎng)的計(jì)算公式中參數(shù)β的取值范圍為(0,2)，不合適，有可能產(chǎn)生無(wú)效解。2) 由于LFPSO是針對(duì)原始的PSO全局搜索能力差的問(wèn)題引進(jìn)Levy Flight，用于提高全局搜索能力；雖然全局能力有所提升，但仍然存在收斂速度慢，優(yōu)化效率低和普適性不強(qiáng)的問(wèn)題，其主要原因是探索與開(kāi)采沒(méi)有達(dá)到平衡?，F(xiàn)代智能優(yōu)化算法不是僅追求全局搜索能力或者局部搜索能力單方面的提升，而是考慮二者的平衡，這樣才能提高算法的整體優(yōu)化性能。針對(duì)以上問(wèn)題，ILFPSO有3點(diǎn)創(chuàng)新：

1) 改進(jìn)Levy Flight以減少無(wú)效解；

2) 將既有一定的全局搜索能力又有較強(qiáng)的局部搜索能力的趨優(yōu)算子與改進(jìn)的Levy Flight融合，使其全局搜索能力和局部搜索能力同時(shí)提高，二者達(dá)到平衡；

3) 將LFPSO中固定的速度邊界改為動(dòng)態(tài)調(diào)整，以便搜索前期易于找到全局最優(yōu)點(diǎn)，后期容易獲得局部最優(yōu)解，也用于平衡探索與開(kāi)采能力。

2.2 改進(jìn)的Levy Flight算子

Levy Flight作為一種隨機(jī)游走方式，其長(zhǎng)跳躍的搜索方式與偶爾短跳躍的搜索方式交叉執(zhí)行，保證了算法能夠及時(shí)跳出局部最優(yōu)點(diǎn)，擴(kuò)大了粒子的搜索范圍。Levy分布中，參數(shù)β影響較大，其小值執(zhí)行長(zhǎng)距離跳躍，防止陷入局部最小值。由于Levy步長(zhǎng)中β的取值范圍是(0,2]，不夠合適，在低值區(qū)域易產(chǎn)生無(wú)效的σ，最終產(chǎn)生無(wú)效的粒子。本文將Levy分布中參數(shù)β的取值范圍更精確選擇為[0.1,2]，防止產(chǎn)生無(wú)效解。參數(shù)β取值的程序偽代碼見(jiàn)算法1。

算法1：β取值限定

求解Levy分布中的β值：β=2?rnd；

根據(jù)式(4)求解步長(zhǎng)s

其中，rand表示在區(qū)間[0,1]中均勻分布的隨機(jī)數(shù)。Levy分布中的步長(zhǎng)s為：

式中，u和v分別服從正態(tài)分布[6]：

式中，

式中，Γ是標(biāo)準(zhǔn)的伽馬函數(shù)。從式(4)中獲得步長(zhǎng)s值來(lái)更新第i個(gè)粒子iX的位置。

圖2 參數(shù)β與σ值的關(guān)系曲線

通過(guò)分析可知，參數(shù)β影響著σ的取值。通過(guò)大量的實(shí)驗(yàn)發(fā)現(xiàn)：

1)β取值為區(qū)間[0,0.000 3]之間的隨機(jī)數(shù)時(shí)，σ為無(wú)窮值(即無(wú)效)，導(dǎo)致s為無(wú)效值。

2)β取值為區(qū)間[0.000 3,0.1]之間的隨機(jī)數(shù)時(shí)，σ過(guò)大，它又導(dǎo)致兩種結(jié)果：①s過(guò)大，隨機(jī)步長(zhǎng)過(guò)大，此跳躍無(wú)意義；②s趨于0，使此跳躍在實(shí)質(zhì)上未發(fā)生。為了能更清晰地看出參數(shù)β對(duì)σ值的影響，參數(shù)β取[0.05,0.1]之間的數(shù)，β對(duì)σ值的影響曲線如圖2所示。從圖2可知，隨著參數(shù)β減少，σ值呈指數(shù)級(jí)增加，進(jìn)而無(wú)效。

2.3 趨優(yōu)算子

文獻(xiàn)[11]提出了一種全局最優(yōu)和聲搜索算法，該算法首次使用了趨優(yōu)算子，見(jiàn)算法2，通過(guò)將最優(yōu)和聲的信息賦給當(dāng)前和聲，提高了搜索能力。從算法2可知，趨優(yōu)算子充分地利用了群體歷史最優(yōu)解的位置信息，從解的角度向群體中當(dāng)前最優(yōu)解趨近，故稱趨優(yōu)算子[11-12]；從維的角度發(fā)生突變，通過(guò)隨機(jī)選取最優(yōu)解中某一維度的值直接替換當(dāng)前維度的值，提高全局搜索能力。此算子主要體現(xiàn)在局部搜索能力上，全局搜索能力有限，所以從總體上講，更側(cè)重于提高算法優(yōu)化精度和收斂速度。

2.4 Levy Flight算子與趨優(yōu)算子有機(jī)融合

使用趨優(yōu)概率pa將Levy算子與趨優(yōu)算子交替運(yùn)行。當(dāng)均勻分布在[0,1]中的隨機(jī)數(shù)小于0.5時(shí)，趨優(yōu)概率pa取值為0.5，否則取值為0.99。采取這樣的隨機(jī)選取方式，減少了人工選取pa參數(shù)的過(guò)程。下面分別對(duì)兩種趨優(yōu)概率的情況進(jìn)行分析：

1) 當(dāng)pa=0.5時(shí)，趨優(yōu)算子與Levy算子交替運(yùn)行的概率均等。若隨機(jī)數(shù)大于pa值，執(zhí)行趨優(yōu)算子，獲取一個(gè)隨機(jī)維，將全局最優(yōu)解隨機(jī)維的值賦給當(dāng)前維。此時(shí)，當(dāng)前粒子向當(dāng)前最優(yōu)位置趨近，加快了收斂速度。若小于pa值，執(zhí)行Levy算子，提高全局搜索能力。兩種算子的交叉執(zhí)行，提高了算法的整體搜索能力。

2) 當(dāng)pa=0.99時(shí)，趨優(yōu)算子運(yùn)行的概率極小，多數(shù)情況下僅執(zhí)行改進(jìn)的Levy Flight操作，更強(qiáng)化全局搜索，且改進(jìn)的Levy Flight算子防止產(chǎn)生無(wú)效解。

2.5 速度邊界的動(dòng)態(tài)更新

本文將LFPSO算法中的恒定速度邊界值改為對(duì)速度的邊界動(dòng)態(tài)更新。首先設(shè)置動(dòng)態(tài)邊界的極值(最大值0v和最小值1v)，然后動(dòng)態(tài)調(diào)整，隨著迭代次數(shù)的增加，速度的上邊界maxV由大變小。在每次迭代中，對(duì)粒子的速度邊界更新公式為：

式中，minV為速度的下邊界；t為當(dāng)前迭代次數(shù)；MaxDT為最大迭代次數(shù)。原算法中，固定的速度邊界值不利于探索與開(kāi)采的平衡。而在ILFPSO中，由于引進(jìn)了動(dòng)態(tài)更新機(jī)制，前期階段，算法中的粒子分布范圍較為廣泛，根據(jù)式(2)，若粒子速度大，其位置變化范圍大，即擴(kuò)大了粒子的搜索空間，增加了找到全局最優(yōu)值的概率；而在后期階段，粒子分布相較于前期較為集中，粒子速度小，其位置變化范圍小，即縮減了搜索空間的范圍，增加了粒子尋找局部最優(yōu)值的概率，提高了搜索精度，從而提高了局部搜索能力。因此，動(dòng)態(tài)的速度邊界調(diào)整機(jī)制有利于尋找全局和局部最優(yōu)解，即前期有利于搜索全局最優(yōu)解，后期能加快算法的收斂速度。

2.6 ILFPSO算法流程

基于以上3點(diǎn)創(chuàng)新，ILFPSO的算法流程如下：

1) 初始化參數(shù)。參數(shù)包括學(xué)習(xí)因子1c和2c、試驗(yàn)次數(shù)trail、閾值limit等。2) 隨機(jī)初始化種群的位置和速度，計(jì)算適應(yīng)度值，選擇個(gè)體歷史最優(yōu)值pbest和全局最優(yōu)值gbest。3) 用式(7)和式(8)動(dòng)態(tài)更新速度邊界，隨機(jī)選取趨優(yōu)概率pa的值。4) 若trail(i)未超過(guò)limit，則對(duì)粒子的速度和位置按式(2)更新，并進(jìn)行邊界檢查。否則執(zhí)行流程5)，并將trail(i)重置為0。5) 當(dāng)隨機(jī)數(shù)大于pa，則執(zhí)行趨優(yōu)算子，否則執(zhí)行改進(jìn)的Levy Flight算子。6) 計(jì)算粒子的適應(yīng)度值，更新trail(i)，并更新個(gè)體歷史最優(yōu)解pbest和全局最優(yōu)解gbest。7) 判斷是否滿足終止準(zhǔn)則，若滿足則算法終止，否則返回流程3)。

ILFPSO融入了3點(diǎn)創(chuàng)新，提升了優(yōu)化效率，較好地平衡了探索與開(kāi)采能力，提高了算法整體性能。

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

3.1 測(cè)試函數(shù)與實(shí)驗(yàn)環(huán)境

為測(cè)試本文提出的ILFPSO算法的尋優(yōu)能力，選用4類(lèi)benchmark函數(shù)進(jìn)行仿真實(shí)驗(yàn)，分別為：?jiǎn)畏搴瘮?shù)、多峰函數(shù)、平移函數(shù)和旋轉(zhuǎn)函數(shù)[13]。表1和表2給出了這4類(lèi)28個(gè)benchmark函數(shù)的名稱、搜索范圍和理論最優(yōu)值(Fmin)情況，函數(shù)的相關(guān)表達(dá)式見(jiàn)文獻(xiàn)[3-6,13]。單峰函數(shù)只有一個(gè)全局最優(yōu)點(diǎn)，適合用于評(píng)估算法的開(kāi)采能力；多峰函數(shù)有多個(gè)局部最優(yōu)點(diǎn)，適合用于評(píng)估算法的探索能力；平移函數(shù)和旋轉(zhuǎn)函數(shù)用于評(píng)估優(yōu)化算法解決復(fù)雜優(yōu)化問(wèn)題的能力。

選取這28個(gè)benchmark函數(shù)，目的在于檢測(cè)ILFPSO算法的優(yōu)化性能，通過(guò)與國(guó)外學(xué)者提出的LFPSO算法、增強(qiáng)領(lǐng)導(dǎo)者粒子群算法(ELPSO)、自我調(diào)節(jié)粒子群優(yōu)化算法(SRPSO)進(jìn)行優(yōu)化性能、收斂性、運(yùn)行時(shí)間的對(duì)比，驗(yàn)證ILFPSO的優(yōu)越性。所有的仿真實(shí)驗(yàn)均在操作系統(tǒng)為Windows 7、CPU為主頻為3.10 GHz和內(nèi)存為4 GB的PC上進(jìn)行，編程語(yǔ)言采用MATLAB R2014a。

表1 單峰和多峰benchmark函數(shù)信息表

表2 平移和旋轉(zhuǎn)benchmark函數(shù)信息表

3.2 優(yōu)化性能對(duì)比

為了控制參數(shù)對(duì)各個(gè)算法性能的影響，也為了公平起見(jiàn)，所有算法的最大迭代次數(shù)都設(shè)為2 500，種群數(shù)量都設(shè)為20，函數(shù)的維數(shù)n設(shè)為30。ILFPSO最大速度初值0v和終值1v分別設(shè)置為位置邊界最大長(zhǎng)度的20%和0.1%，學(xué)習(xí)因子1c、2c和慣性權(quán)重因子w同LFPSO參數(shù)設(shè)置。LFPSO、ELPSO和SRPSO參數(shù)設(shè)置見(jiàn)相應(yīng)的參考文獻(xiàn)。表3和表4分別給出了4種算法在28個(gè)benchmark函數(shù)上30次獨(dú)立運(yùn)行的尋優(yōu)結(jié)果減去理想最優(yōu)值(Fmin)后(除f15以外)的最大值(Max)、最小值(Min)、均值(Mean)和方差(Std)，其中黑體代表算法中的最優(yōu)者。

表3 4種函數(shù)對(duì)單峰和多峰函數(shù)的性能測(cè)試結(jié)果

續(xù)表

表4 4種算法對(duì)平移和旋轉(zhuǎn)函數(shù)的性能測(cè)試結(jié)果

采用單峰函數(shù)進(jìn)行算法的性能測(cè)試，主要是檢測(cè)算法的局部搜索能力和收斂精度。4種算法在7個(gè)單峰函數(shù)f1～f6和f19上的性能測(cè)試數(shù)據(jù)看出，在Max、Min、Mean和Std上，與LFPSO、ELPSO、SRPSO相比，ILFPSO均表現(xiàn)了優(yōu)異的開(kāi)采能力。這說(shuō)明具有較強(qiáng)局部搜索能力的趨優(yōu)算子融合到Levy Flight中和動(dòng)態(tài)調(diào)整速度邊界這兩項(xiàng)改進(jìn)是有效的，提高了算法的局部搜索能力和收斂精度，尤其在f3、f4和f19上大幅度領(lǐng)先于LFPSO。

通過(guò)使用15個(gè)多峰函數(shù)f7～f18，f20～f22對(duì)4種算法進(jìn)行性能測(cè)試，以檢驗(yàn)算法的全局搜索能力。對(duì)于多峰函數(shù)f7～f15、f17、f18、f20、f22，ILFPSO明顯優(yōu)于其他3種對(duì)比算法，效果最好。在Max、Min和Mean上，ILFPSO均獲得了最小值，說(shuō)明該算法在求解多峰函數(shù)時(shí)全局搜索能力較強(qiáng)。在Std上，ILFPSO也都獲得了最小的值，這說(shuō)明其穩(wěn)定性最強(qiáng)。當(dāng)求解函數(shù)f16、f21時(shí)，ILFPSO的性能測(cè)試結(jié)果相對(duì)來(lái)說(shuō)稍差，但對(duì)于求解函數(shù)f16時(shí)，在Mean上，ILFPSO獲得了最好的結(jié)果；在Std上，則是SRPSO表現(xiàn)了最優(yōu)的性能，ILFPSO次之；在Max上，SRPSO獲得了最好的值，ILFPSO次之；在Min上，ELPSO獲得了最小的值，ILFPSO次之。而對(duì)于函數(shù)f21，ELPSO表現(xiàn)的尋優(yōu)能力最優(yōu)，ILFPSO次之。但是相對(duì)于LFPSO，ILFPSO具有更強(qiáng)的搜索能力，這說(shuō)明趨優(yōu)算子與Levy Flight算子融合是有效的，能很好地平衡全局和局部搜索能力，使得算法整體優(yōu)化性能得到了大幅度的提高。

通過(guò)求解6個(gè)平移和旋轉(zhuǎn)函數(shù)以檢驗(yàn)ILFPSO解決復(fù)雜優(yōu)化問(wèn)題的能力，結(jié)果如表4所示。從表4可以看出，在求解函數(shù)f24、f25、f27、f28時(shí)，在Max、Min、Mean和Std上，ILFPSO均優(yōu)于其他3種對(duì)比算法；在求解函數(shù)f23時(shí)，ELPSO表現(xiàn)出了最佳的尋優(yōu)能力，ILFPSO稍差；而在求解f26時(shí)，在Max、Min和Mean上，ILFPSO最佳。相對(duì)于LFPSO，在所有的6個(gè)復(fù)雜函數(shù)f23～f28上，ILFPSO表現(xiàn)更優(yōu)。這說(shuō)明ILFPSO解決復(fù)雜優(yōu)化問(wèn)題的能力具有較強(qiáng)的競(jìng)爭(zhēng)力。

綜上所述，本文提出的ILFPSO算法在28個(gè)benchmark函數(shù)中的25個(gè)函數(shù)上都獲得了最優(yōu)的性能，充分證明了ILFPSO的普適性較強(qiáng)。雖然對(duì)于求解個(gè)別benchmark函數(shù)仍存在相對(duì)較差的性能，但在求解所有28個(gè)benchmark函數(shù)上，ILFPSO優(yōu)于LFPSO，整體上說(shuō)明本文提出的3點(diǎn)改進(jìn)可行。

3.3 收斂性分析

為更清晰地看出ILFPSO算法的收斂性能，實(shí)驗(yàn)給出了4種算法在求解所有函數(shù)時(shí)的收斂曲線圖，如圖3所示。因版面限制，只從4類(lèi)benchmark函數(shù)中選取6個(gè)函數(shù)進(jìn)行展示，將平均適應(yīng)度值(對(duì)于函數(shù)f25，每次的結(jié)果減去Fmin再進(jìn)行平均)作為評(píng)估算法性能的主要參考值，測(cè)試迭代次數(shù)為2 500時(shí)算法的收斂性能。

圖3 4種算法在4類(lèi)benchmark函數(shù)上的收斂曲線圖

從圖3可以看出，ILFPSO在對(duì)f5、f7、f27等函數(shù)進(jìn)行優(yōu)化時(shí)收斂速度大幅度優(yōu)于其他3種對(duì)比算法；而針對(duì)f1、f10、f25等函數(shù)，ILFPSO收斂性能也明顯優(yōu)于其他對(duì)比算法。另外，雖然ILFPSO在優(yōu)化f21、f23等函數(shù)時(shí)收斂性能稍差，ELPSO最好，但I(xiàn)LFPSO緊跟其后，排在第2位。從整體情況來(lái)看，ILFPSO在28個(gè)函數(shù)上的收斂性能都優(yōu)于LFPSO，這些再一次證明ILFPSO的改進(jìn)策略是有效的。

3.4 運(yùn)行時(shí)間對(duì)比

4種優(yōu)化算法的運(yùn)行時(shí)間結(jié)果如表5所示。從表5可以看出，當(dāng)求解單峰函數(shù)f1～f6、f19時(shí)，ELPSO的運(yùn)行速度最快，ILFPSO的運(yùn)行速度次之，但I(xiàn)LFPSO大幅度領(lǐng)先另外2種對(duì)比算法LFPSO和SRPSO。

表5 4種優(yōu)化算法運(yùn)行時(shí)間對(duì)比

續(xù)表

在求解多峰函數(shù)f7、f8、f10、f15、f17、f18、f21和f22時(shí)，ELPSO運(yùn)行速度最快，而求解f9、f11～f14、f16和f20時(shí)，ILFPSO運(yùn)行速度最快；當(dāng)求解平移和旋轉(zhuǎn)函數(shù)f23～f25和f27時(shí)，ILFPSO耗時(shí)最少，求解旋轉(zhuǎn)函數(shù)f26和f28時(shí)，ELPSO耗時(shí)最少，但二者相差不大。從表5最后一行看，ILFPSO的平均運(yùn)行時(shí)間是0.833 5 s，是4種算法中耗時(shí)最少的，約為L(zhǎng)FPSO(1.797 7 s)的50%，其主要原因見(jiàn)3.5節(jié)計(jì)算復(fù)雜度分析。

3.5 復(fù)雜度分析

一般來(lái)講，一個(gè)優(yōu)化算法的計(jì)算復(fù)雜度由兩部分組成：目標(biāo)函數(shù)的計(jì)算復(fù)雜度和優(yōu)化算法自身的計(jì)算復(fù)雜度，本文重點(diǎn)分析ILFPSO與LFPSO計(jì)算復(fù)雜度。因?yàn)閮煞N算法的目標(biāo)函數(shù)評(píng)價(jià)次數(shù)相同，目標(biāo)函數(shù)的計(jì)算復(fù)雜度相同，所以在此僅分析兩種算法自身的復(fù)雜度。LFPSO中Levy Flight算子的計(jì)算復(fù)雜度高，當(dāng)嵌入計(jì)算復(fù)雜度較低的趨優(yōu)算子時(shí)，兩個(gè)算子交替運(yùn)行，如此降低了ILFPSO的整體計(jì)算復(fù)雜度。另外，ILFPSO消除無(wú)效解也在一定程度上提高了算法的計(jì)算效率。

3.6 ILFPSO與RLPSO的性能對(duì)比

為進(jìn)一步說(shuō)明ILFPSO算法的尋優(yōu)能力，選取f1、f3、f7、f9、f11、f19作為測(cè)試函數(shù)。將ILFPSO算法與國(guó)內(nèi)目前最優(yōu)秀的具有反向?qū)W習(xí)和局部學(xué)習(xí)能力的PSO算法(RLPSO)[2]進(jìn)行對(duì)比。兩種算法的參數(shù)：維數(shù)n為30，種群數(shù)量為20。兩種算法的實(shí)驗(yàn)數(shù)據(jù)如表6所示，RLPSO的實(shí)驗(yàn)數(shù)據(jù)直接來(lái)自文獻(xiàn)[2]。

從表6可以看出，不管是Mean還是Std，ILFPSO大幅度優(yōu)于RLPSO，說(shuō)明ILFPSO全局搜索能力更好，收斂速度更快以及收斂精度更高，而且對(duì)比實(shí)驗(yàn)中本文提出ILFPSO的最大目標(biāo)函數(shù)評(píng)價(jià)次數(shù)(maxEFs)比RLPSO少得多，前者為5×104，后者為1×105，這更說(shuō)明ILFPSO比RLPSO優(yōu)化性能好。

表6 ILFPSO與RLPSO算法的結(jié)果對(duì)比

通過(guò)以上仿真實(shí)驗(yàn)及結(jié)果對(duì)比，ILFPSO很好地避免了LFPSO中出現(xiàn)的收斂速度慢、易產(chǎn)生無(wú)效解、搜索效率不高以及普適性不強(qiáng)等問(wèn)題。這些問(wèn)題的解決主要因?yàn)椋?/p>

1) ILFPSO為平衡原始算法的全局和局部搜索能力以及加快算法的收斂速度而引進(jìn)了趨優(yōu)算子；

2) 對(duì)速度的邊界進(jìn)行動(dòng)態(tài)更新，提高了ILFPSO的前期全局搜索能力和后期局部搜索能力；

3) 改進(jìn)的Levy Flight算子避免出現(xiàn)無(wú)效解。因此，與LFPSO、ELPSO、SRPSO和RLPSO相比，ILFPSO具有更高的優(yōu)化效率，更好的普適性。

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

針對(duì)LFPSO中出現(xiàn)的搜索效率不高和普適性不強(qiáng)等問(wèn)題，本文提出了一種趨優(yōu)算子與Levy Flight混合的粒子群優(yōu)化算法。首先改進(jìn)Levy Flight算子，解決了LFPSO中易產(chǎn)生無(wú)效解的問(wèn)題。然后控制趨優(yōu)算子與Levy Flight的交替運(yùn)行，更好地平衡了算法的全局與局部搜索能力，提高了算法的普適性。最后在每次迭代時(shí)對(duì)速度的邊界進(jìn)行動(dòng)態(tài)更新，用于提高前期全局搜索能力和后期局部搜索能力。28個(gè)benchmark函數(shù)仿真實(shí)驗(yàn)結(jié)果表明本文提出的方法是有效的，與當(dāng)前最優(yōu)秀的PSO改進(jìn)算法相比，ILFPSO更具有競(jìng)爭(zhēng)性和普適性。

[1]張新明, 涂強(qiáng), 尹欣欣, 等. 嵌入趨化算子的PSO算法及其在多閾值分割中的應(yīng)用[J]. 計(jì)算機(jī)科學(xué), 2016, 43(2)：311-315.ZHANG Xin-ming, TU Qiang, YIN Xin-xin, et al.Chemotaxis operator embedded particle swarm optimization algorithm and its application to multilevel thresholding[J].Computer Science, 2016, 43(2)： 311-315.

[2]夏學(xué)文, 劉經(jīng)南, 高柯夫, 等. 具備反向?qū)W習(xí)和局部學(xué)習(xí)能力的粒子群算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2015, 38(7)：1397-1407.XIA Xue-wen, LIU Jing-nan, GAO Ke-fu, et al. Partucle swarm optimization algorithm with reverse-learning and local-learning behavior[J]. Chinese Journal of Computers,2015, 38(7)： 1397-1407.

[3]LIM W H, ISA N A M. Adaptive division of labor particle swarm optimization[J]. Expert System with Application,2015, 42(14)： 5887-5903.

[4]TANWEER M R, SURESH S, SUNDARARAJAN N. Self regulating particle swarm optimization algorithm[J].Information Science, 2015, 294： 182-202.

[5]JORDEHI A R. Enhanced leader PSO (ELPSO)： a new PSO variant for solving global optimization problems[J]. Applied Soft Computing, 2015, 26： 401-417.

[6]HAKLI H, UGUZ H. A novel particle swarm optimization algorithm with Levy Flight[J]. Applied Soft Computing,2014, 23： 333-345.

[7]倪慶劍, 鄧建明, 邢漢承. 基于異構(gòu)多種群策略的動(dòng)態(tài)概率粒子群優(yōu)化算法[J]. 模式識(shí)別與人工智能, 2014, 27(2)：146-152.NI Qing-jian, DENG Jian-ming, XING Han-cheng.Dynamic probabilistic particle swarm optimization based on heterogeneous Multiple population strategy[J]. Pattern Recognition and Artificial Intelligence, 2014, 27(2)：146-152.

[8]艾兵, 董明剛. 基于高斯擾動(dòng)和自然選擇的改進(jìn)粒子群優(yōu)化算法[J]. 計(jì)算機(jī)應(yīng)用, 2016, 36(3)： 687-691.AI Bing, DONG Ming-gang. Improved particle swarm optimization algorithm based on Gaussian disturbance and natural selection[J]. Journal of Computer Applications, 2016,36(3)： 687-691.

[9]ZHANG W, LIU J, FAN L B, et al. Control strategy PSO[J].Applied Soft Computing, 2016, 38： 75-86.

[10]TAHERKHANI M, SAFABAKHSH R. A novel stabilitybased adaptive inertia weight for particle swarm optimization[J]. Applied Soft Computing, 2016, 38：281-295.

[11]OMRAM M G H, MAHDAVI M. Global-best harmony search[J]. Applied Mathematics and Computation, 2008,198(2)： 643-656.

[12]李景陽(yáng), 王勇, 李春雷. 采用雙模飛行的粒子群優(yōu)化算法[J]. 模式識(shí)別與人工智能, 2014, 27(6)： 533-539.LI Jing-yang, WANG Yong, LI Chun-lei. Particle swarm optimization algorithm with double-flight modes[J].Pattern Recognition and Artificial Intelligence, 2014, 27(6)：533-539.

[13]KIRAN M S, HAKLI H, GUNDUZ M, et al. Artificial bee colony algorithm with variable search strategy for continuous optimization[J]. Information Science, 2015, 300：140-157.