董文永，康嵐蘭,2，劉宇航，李康順

(1.武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430072；2.江西理工大學(xué)應(yīng)用科學(xué)學(xué)院，江西 贛州 341000;3.華南農(nóng)業(yè)大學(xué)信息學(xué)院，廣東 廣州 510642)

DONG Wen-yong1,KANG Lan-lan1,2,LIU Yu-hang1,LI Kang-shun3

(1.Computer School,Wuhan University,Wuhan 430072,China;2.Faculty of Applied Science,Jiangxi University of Science and Technology,Ganzhou 341000,China;3.College of Information,South China Agricultural University,Guangzhou 510642,China)

帶自適應(yīng)精英擾動(dòng)及慣性權(quán)重的反向粒子群優(yōu)化算法

董文永1，康嵐蘭1,2，劉宇航1，李康順3

(1.武漢大學(xué)計(jì)算機(jī)學(xué)院，湖北 武漢 430072；2.江西理工大學(xué)應(yīng)用科學(xué)學(xué)院，江西 贛州 341000;3.華南農(nóng)業(yè)大學(xué)信息學(xué)院，廣東 廣州 510642)

針對(duì)反向粒子群優(yōu)化算法存在的易陷入局部最優(yōu)、計(jì)算開銷大等問題，提出了一種帶自適應(yīng)精英粒子變異及非線性慣性權(quán)重的反向粒子群優(yōu)化算法（OPSO-AEM&NIW），來克服該算法的不足。OPSO-AEM&NIW算法在一般性反向?qū)W習(xí)方法的基礎(chǔ)上，利用粒子適應(yīng)度比重等信息，引入了非線性的自適應(yīng)慣性權(quán)重（NIW）調(diào)整各個(gè)粒子的活躍程度，繼而加速算法的收斂過程。為避免粒子陷入局部最優(yōu)解而導(dǎo)致搜索停滯現(xiàn)象的發(fā)生，提出了自適應(yīng)精英變異策略（AEM）來增大搜索范圍，結(jié)合精英粒子的反向搜索能力，達(dá)到跳出局部最優(yōu)解的目的。上述2種機(jī)制的結(jié)合，可以有效克服反向粒子群算法的探索與開發(fā)的矛盾。實(shí)驗(yàn)結(jié)果表明，與主流反向粒子群優(yōu)化算法相比，OPSO-AEM&NIW算法無論是在計(jì)算精度還是計(jì)算開銷上均具有較強(qiáng)的競爭能力。

一般性反向?qū)W習(xí)；粒子群優(yōu)化；自適應(yīng)精英變異；非線性慣性權(quán)重

1 引言

粒子群優(yōu)化算法(PSO,particle swarm optimization)是一種基于群體進(jìn)化的隨機(jī)仿生優(yōu)化算法，由Kennedy和Eberhart等[1]于1995年提出，其思想源于對(duì)魚群及鳥類等群體覓食行為的模擬。算法自提出以來，由于其概念簡單且易于理解和實(shí)現(xiàn)，在解決復(fù)雜優(yōu)化問題，如非線性、多峰等問題性能表現(xiàn)突出，從而吸引了大批科研人員對(duì)其展開研究。目前，PSO已成功應(yīng)用于交通、制造、通信工程、國防等多個(gè)不同學(xué)科及工程領(lǐng)域[2～4]，并取得了良好的效果。

傳統(tǒng)PSO自提出以來，存在著幾個(gè)天然缺陷，如參數(shù)依賴過大、局部搜索能力不足且易陷入局部最優(yōu)、搜索精度低等。因此，大量科研人員從參數(shù)設(shè)置、自適應(yīng)調(diào)整、算法混合或融合等多個(gè)角度對(duì)傳統(tǒng)PSO進(jìn)行改良。PSO中每個(gè)粒子通過一個(gè)簡單的運(yùn)動(dòng)向量公式來控制其飛行方向，該運(yùn)動(dòng)向量公式主要由3個(gè)關(guān)鍵參數(shù)控制：慣性權(quán)重(w)、認(rèn)知學(xué)習(xí)因子(c1)與社會(huì)學(xué)習(xí)因子(c2)。因此，如何控制慣性大小、設(shè)定參數(shù)，如何更好地獲取搜索環(huán)境的有效信息，避免粒子陷入局部最優(yōu)的同時(shí)加快算法收斂速度是改進(jìn)傳統(tǒng)PSO的關(guān)鍵。

本文提出了一種帶自適應(yīng)精英擾動(dòng)及慣性權(quán)重的反向粒子群優(yōu)化算法(OPSO-AEM&NIW,opposition-based PSO with adaptive elite mutation and nonlinear inertia weight)。OPSO-AEM&NIW算法取當(dāng)前全局最優(yōu)位(gbest)為精英粒子，將針對(duì)精英粒子的自適應(yīng)變異策略(AEM)融入到反向?qū)W習(xí)中，使各粒子的自身歷史最優(yōu)位(pbest)趨向收斂于精英粒子(gbest)時(shí)，依據(jù)粒子的聚集程度，自適應(yīng)產(chǎn)生變異位，從而幫助粒子跳出局部最優(yōu)。同時(shí)，為加快算法的收斂，一種非線性動(dòng)態(tài)慣性權(quán)重策略(NIW)被引入到新算法中，該策略使慣性權(quán)重隨著粒子適應(yīng)度值的變化而自適應(yīng)改變。本文將新算法與多種基于反向?qū)W習(xí)PSO算法在14個(gè)典型測試函數(shù)上進(jìn)行數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明OPSO-AEM&NIW算法在大部分測試函數(shù)上取得最優(yōu)解的同時(shí)，收斂速度得到了顯著的提高。

2 相關(guān)工作

2.1 基本PSO

PSO算法是仿生算法家族中的又一種群智能隨機(jī)搜索算法，群體中個(gè)體被看作是搜索空間中沒有質(zhì)量和體積的粒子，每個(gè)粒子表征問題的一個(gè)候選解，具有速度與位置2個(gè)特征。在解空間中，粒子以一定的速度向自身歷史最優(yōu)位與全局最優(yōu)位運(yùn)動(dòng)，不斷進(jìn)化候選解。

設(shè)群體在D維空間中包含N個(gè)粒子，第i個(gè)粒子在第j維的速度分量vi,j和位置分量xi,j在t+1時(shí)刻的更新式如下[5]

其中，i=1,2,…,N,j=1,2,…,D，ω是慣性權(quán)值，ω∈[0,1]，c1和c2分別稱為認(rèn)知學(xué)習(xí)因子和社會(huì)學(xué)習(xí)因子，通常，c1,c2∈[0,2]，rand1和rand2是在[0,1]上服從均勻分布的2個(gè)隨機(jī)數(shù)。

2.2 一般化的反向?qū)W習(xí)策略

2005年，Tizhoosh[6]首次提出了反向?qū)W習(xí)(OBL,opposition-based learning)的概念。其主要思想是同時(shí)評(píng)估一個(gè)可行解與其反向解，將其中較優(yōu)解保留，進(jìn)入下一代進(jìn)化。設(shè)是粒子xj的反向解，則為

其中，xj的范圍為[aj,bj]。依據(jù)概率論，解空間中個(gè)體反向解等概率優(yōu)于原粒子，如對(duì)原粒子解與其反向解所構(gòu)造的解空間同時(shí)進(jìn)行搜索，將大大提高最優(yōu)解的搜索效率。

2007年，Wang等[7]將OBL應(yīng)用到PSO中，提出了一種基于OBL的PSO算法(OPSO)。2011年，Wang等在OBL的基礎(chǔ)上進(jìn)一步提出了一般性反向?qū)W習(xí)(GOBL,generalized OBL)的概念，在GOBL基礎(chǔ)上提出了一種改進(jìn)的反向?qū)W習(xí)粒子群算法GOPSO[8]。2013年，周新宇等[9]將精英思想引入到反向?qū)W習(xí)中，提出了精英反向粒子群算法(EOPSO)，該算法取群體中每個(gè)粒子的pbest作為精英粒子群，求其每一位的反向解，在其與原粒子群合并空間中選取適應(yīng)值最優(yōu)的前N個(gè)粒子進(jìn)入下一次迭代中。同時(shí)，對(duì)當(dāng)前全局最優(yōu)位采用了差分變異(DEM,differential evolutionary mutation)進(jìn)行擾動(dòng)。為防止粒子越出搜索區(qū)域，文獻(xiàn)[10]采用一種速度閥(velocity clamping)來控制粒子速度大小，從而進(jìn)一步平衡算法的全局搜索與局部探測能力。Kaucic[11]針對(duì)邊界約束問題提出了一種自適應(yīng)速度的多始發(fā)反向粒子群優(yōu)化算法(MSOPSOAV)，算法設(shè)計(jì)了一個(gè)基于差分操作的自適應(yīng)速度更新公式來加強(qiáng)粒子優(yōu)化能力，并采用一個(gè)超反向原則(super-opposition paradigm)對(duì)出現(xiàn)早熟的粒子重新初始化。Pehlivanoglu在文獻(xiàn)[12]中提出了一種多頻振動(dòng)PSO算法。該算法通過一種周期性變異策略，結(jié)合人工神經(jīng)網(wǎng)絡(luò)方法保持了種群多樣性，從而有效防止早熟現(xiàn)象的發(fā)生，使算法收斂速度得到大大的提高?；趨?shù)的控制對(duì)進(jìn)化算法的重要性，文獻(xiàn)[13]在2015年對(duì)進(jìn)化算法中參數(shù)的控制方法、趨勢及挑戰(zhàn)做出了綜合性的討論。接下來，給出一般反向?qū)W習(xí)的定義。

定義1一般反向?qū)W習(xí)策略(GOBL,generalized opposition-based learning)[8,14]。設(shè)是D維空間中的一個(gè)普通粒子，其對(duì)應(yīng)的反向解為，每一維定義為

其中，k∈U(0,1)的隨機(jī)數(shù)，該設(shè)定使粒子獲得更好的反向解[9]，xi,j∈[aj,bj]，[daj,dbj]為第j維搜索空間的動(dòng)態(tài)范圍，取值為

依據(jù)演化算法收斂性理論，為增強(qiáng)算法的頑健性，randn(daj,dbj)取在動(dòng)態(tài)邊界[daj,dbj]上服從高斯分布的隨機(jī)數(shù)。這一設(shè)定在實(shí)驗(yàn)過程已被驗(yàn)證取得了較好的算法穩(wěn)定性。高斯分布函數(shù)定義為

3 OPSO-AEM&NIW算法

種群在進(jìn)化過程中，每個(gè)粒子搜索潛力不盡相同，為充分發(fā)揮優(yōu)勢粒子潛力，進(jìn)一步提高算法效率，本文采取“精英策略(elite strategy)”，給予群體中適應(yīng)值占優(yōu)的粒子(稱為“精英粒子(elite particle)”)更多的進(jìn)化機(jī)會(huì)。若精英粒子在試探過程中探索到新的優(yōu)勢點(diǎn)，則將其替代群體中被選擇的劣勢個(gè)體。然而，過度采取精英策略可能導(dǎo)致易陷入局部最優(yōu)及最優(yōu)值振蕩等問題。為了克服上述問題，本文引入一種非線性自適應(yīng)慣性策略來自適應(yīng)調(diào)節(jié)各個(gè)粒子的活躍程度，增大算法跳出局部最優(yōu)解的能力，和精英策略相互配合來調(diào)節(jié)算法全局探索與局部開采之間的平衡，提升反向PSO的性能。

3.1 自適應(yīng)精英變異策略(AEM)

在精英策略中，精英粒子入選比例的確立對(duì)問題的求解起到關(guān)鍵的作用。一方面，比例過大，種群多樣性隨著進(jìn)化過程的深入而大幅降低，從而易陷入局部最優(yōu)；另一方面，一些理論分析表明，在未收斂前，粒子群搜尋的全局最優(yōu)位總是在先前已知的幾個(gè)候選解之間來回振蕩[13,15]。因此，本文算法僅將種群中g(shù)best位作為精英粒子，在每一代進(jìn)化過程中，根據(jù)式(11)和式(14)對(duì)gbest做自適應(yīng)變異操作，由其產(chǎn)生的新個(gè)體對(duì)環(huán)境做進(jìn)一步試探。若新個(gè)體適應(yīng)值優(yōu)于原gbest適應(yīng)值，則取代之成為新的gbest位參與到新一輪的進(jìn)化過程中。本文將這種融入精英思想的自適應(yīng)變異方法稱為自適應(yīng)精英變異策略(AEM,adaptive elite mutation strategy)。

AEM變異操作中，將通過自適應(yīng)生成變異種子xm及自適應(yīng)選取變異常量C，產(chǎn)生真實(shí)變異量F(xm)代入到式(14)中，實(shí)現(xiàn)對(duì)精英粒子gbest自適應(yīng)擾動(dòng)的目的。具體地，xm的生成綜合考慮個(gè)體pbest與精英粒子gbest的距離r以及進(jìn)化代數(shù)t的關(guān)系，依據(jù)式(9)分別計(jì)算pbest到gbest在各維上的距離，距離越大，表示群體間相似性越小，再依據(jù)適應(yīng)度標(biāo)準(zhǔn)差st_d的取值不同(見式(13))，自適應(yīng)取得較大的變異常量C，生成較大變異量F(xm)代入式(14)，使原gbest位自適應(yīng)獲得較大的變異位gbest*。若變異后的f(gbest*)優(yōu)于f(gbest) (f(·)為問題適應(yīng)度函數(shù))，gbest將被gbest*取代。新全局最優(yōu)個(gè)體gbest在后續(xù)的進(jìn)化過程中將吸引群體粒子從而幫助粒子跳出局部最優(yōu)位。由此可見，AEM在算法初期能夠自適地使gbest獲得足夠的擾動(dòng)，達(dá)到擴(kuò)大搜索空間，增強(qiáng)算法的全局搜索能力的目的；反之，在迭代后期，逐漸減小的變異率使最優(yōu)解在避免振蕩的同時(shí)加速了算法的收斂。

在AEM變異中，首先根據(jù)式(8)計(jì)算變異種子xm在各維上的值。

其中，i=1,2,…,D，λ是常數(shù)，根據(jù)4.2.3節(jié)中對(duì)參數(shù)λ的實(shí)驗(yàn)分析結(jié)果，在后續(xù)算法性能分析實(shí)驗(yàn)中取建議值λ=30；t為進(jìn)化代數(shù)，tmax是最大進(jìn)化代數(shù)；r(i)是N個(gè)個(gè)體的pbest在各維上的平均值avg_pbest(i)到gbest的距離；rmax是各維間最大距離。

其中，pbest[j][i]是第j個(gè)粒子在第i維上的位置。

將xm代入式(11)，自適應(yīng)產(chǎn)生變異量。

其中，C是一個(gè)待定常量，它將根據(jù)適應(yīng)度標(biāo)準(zhǔn)差st_d的不同而自主選取不同的值，具體取值如下

st_d將根據(jù)式(13)來判斷種群聚集度，其值被分成(0,10?2]、(10?2,10?1]及(10?1,+∞)3段(不同分段點(diǎn)內(nèi)取值分布情況在本文4.2.3節(jié)中做出統(tǒng)計(jì)分析)。其中，fi為第i個(gè)個(gè)體的適應(yīng)值，fgbest為gbest的適應(yīng)值。當(dāng)個(gè)體越相似，即fi→fgbest，則st_d取值越小，表示群體越聚集，個(gè)體之間的距離越小，C取得的值將越大，對(duì)應(yīng)式(11)產(chǎn)生的變異量越大。圖1展示了當(dāng)C=0.5時(shí)變異量F(xm)與xm中變量之間的對(duì)應(yīng)關(guān)系。

如圖1所示，一方面，當(dāng)r較小，即群體極值趨于一致時(shí)，當(dāng)前全局最優(yōu)位將獲得較大的變異值(F較大)，算法的搜索能力獲得提高；反之，當(dāng)r逐漸增大，即群體較分散時(shí)，變異值的減少(F較小)可避免最優(yōu)值搜尋過程的回蕩，從而加速算法的收斂。另一方面，在迭代初期(t較小)，由于先驗(yàn)認(rèn)知的不足，種群獲得較大的變異值(F較大)，對(duì)解空間進(jìn)行充分的搜索；反之，隨著進(jìn)化的深入(t逐漸增大)，變異值F隨之減小，從而確保問題能夠平滑地收斂到最優(yōu)值。

結(jié)合上述分析結(jié)論，得到自適應(yīng)精英變異操作如下

圖1 自適應(yīng)精英變異三維空間

AEM在每一次迭代中，式(14)根據(jù)F(xm)對(duì)gbest進(jìn)行擾動(dòng)，產(chǎn)生變異位gbest*，若f(gbest*)優(yōu)于f(gbest)，則gbest=gbest*。

3.2 非線性自適應(yīng)慣性權(quán)重更新策略

在速度更新中，本文采用一種如式(15)所示的非線性的自適應(yīng)策略對(duì)粒子慣性權(quán)值進(jìn)行動(dòng)態(tài)調(diào)整[16]為

其中，wmin、wmax分別為w的最小值與最大值；fi為粒子i的適應(yīng)值；fmin、favg分別為當(dāng)前粒子群的最小適應(yīng)值和平均適應(yīng)值。由式(15)可知，當(dāng)粒子適應(yīng)值優(yōu)于平均適應(yīng)值時(shí)，取得最大慣性權(quán)重，從而增加粒子的活躍度；反之，取得較小慣性權(quán)重，使粒子更多地被精英粒子吸引，從而向優(yōu)勢搜索空間靠攏。同時(shí)，當(dāng)所有粒子趨于一致(此時(shí)較小)，w隨之增加；較分散時(shí)(此時(shí)較大)，w隨之減小。以上非線性自適應(yīng)慣性權(quán)重更新策略將進(jìn)一步平衡算法的全局搜索與局部探測能力。

3.3 OPSO-AEM&NIW

本文將AEM與NIW策略同時(shí)應(yīng)用于反向?qū)W習(xí)PSO算法中，給出了一種帶自適應(yīng)精英擾動(dòng)及慣性權(quán)重的反向粒子群優(yōu)化算法，算法1用偽代碼描述了OPSO-AEM&NIW的基本步驟。其中，OP為當(dāng)前種群P的反向種群，jr為使用GOBL策略的概率。

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

對(duì)算法1分析可知，OPSO-AEM&NIW算法主要由初始化種群、GOBL策略、速度與位置更新操作、NIW策略以及AEM策略5個(gè)部分組成。對(duì)于初始化種群和GOBL策略2個(gè)部分，除前者包含隨機(jī)化種群，后者包含邊界動(dòng)態(tài)更新外，兩者還包含共同部分：反向種群生成及群體選擇機(jī)制，顯然，隨機(jī)化種群與反向種群的生成，以及邊界動(dòng)態(tài)更新部分的時(shí)間復(fù)雜度均為O(ND)，對(duì)于群體選擇機(jī)制，排序是其主要操作，計(jì)算復(fù)雜度為O(N2)。特別注意，在低維空間中，通常種群規(guī)模N取近似于維度D的數(shù)，即N≈D，若維度較高，如D≥100，則通常可取N＜D，計(jì)算復(fù)雜度O(N2)可計(jì)為O(ND)。因此，初始化種群和GOBL策略2個(gè)部分的計(jì)算復(fù)雜度為O(ND)；在OPSO-AEM&NIW中，不難得出，NIW策略、AEM策略以及速度與位置更新操作的計(jì)算復(fù)雜度均為O(ND)。綜上所述，OPSO-AEM&NIW的計(jì)算復(fù)雜度為O(ND)。

算法1OPSO-AEM&NIW算法

4 數(shù)值實(shí)驗(yàn)及分析

本文實(shí)驗(yàn)將被分成3個(gè)部分。1) 算法性能測試，除基本PSO外，OPSO-AEM&NIW還與其他4種基于反向?qū)W習(xí)的PSO算法(OBL-based PSO)進(jìn)行比較，分別是OPSO[8]、GOPSO[8]、OVCPSO[10]和EOPSO[9]。實(shí)驗(yàn)中，參與對(duì)比算法的種群規(guī)模N均取40，其他參數(shù)保持與原文獻(xiàn)一致的設(shè)置。2) 策略分析，分析AEM和NIW這2種策略為提高OPSO-AEM&NIW算法性能各自產(chǎn)生的影響，以及兩者共同作用下為避免陷入局部最優(yōu)策略所發(fā)揮的作用。3) 參數(shù)敏感性分析，觀察參數(shù)λ(AEM)取不同值時(shí)對(duì)算法OPSO-AEM&NIW性能的變化情況；并分析AEM策略中待定參數(shù)C取不同常量值的平均概率情況；同時(shí)，對(duì)NIW策略中參數(shù)w自適應(yīng)取值分布進(jìn)行分析。依據(jù)文獻(xiàn)[7,17]中對(duì)參數(shù)c1、c2、jr取值分析，以及本文對(duì)參數(shù)w、λ的敏感性分析，在后續(xù)實(shí)驗(yàn)中，若無特別說明，OPSO-AEM&NIW默認(rèn)參數(shù)設(shè)置如表1所示。

表1 OPSO-AEM&NIW參數(shù)設(shè)置

4.1 實(shí)驗(yàn)設(shè)置

所有實(shí)驗(yàn)針對(duì)表2所列14個(gè)測試函數(shù)展開。按其屬性分為單峰(f1～f5)和多峰(f6～f14)兩大類，其中，多峰函數(shù)又被細(xì)分為3類：簡單多峰函數(shù)(f6～f8)、帶旋轉(zhuǎn)的多峰函數(shù)(f9～f11)和移位多峰函數(shù)(f12～f14)。為使所有測試函數(shù)在零點(diǎn)位，均取全局最優(yōu)值0，本文參考CEC 2010[18]中的函數(shù)定義，將移位多峰函數(shù)中的參數(shù)f_bias統(tǒng)一設(shè)定為0。具體測試函數(shù)如表2所示。

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

4.2.1 算法對(duì)比分析

在6種PSO算法的對(duì)比實(shí)驗(yàn)中，算法最大迭代次數(shù)為10 000，每個(gè)測試函數(shù)分別運(yùn)行30次，記錄全局最優(yōu)值的均值。實(shí)驗(yàn)采用雙尾t檢驗(yàn)對(duì)各算法結(jié)果進(jìn)行顯著性差異統(tǒng)計(jì)分析，顯著水平為0.05。表3給出了6種對(duì)比算法的實(shí)驗(yàn)結(jié)果，最好結(jié)果用黑體顯示，下同，表中用“－”、“+”、“～”這3種符號(hào)表示OPSO-AEM&NIW算法的性能“劣于”、“優(yōu)于”、“相當(dāng)于”對(duì)應(yīng)比較算法。

從表3中可得出OPSO-AEM&NIW在6種算法中都取得了較好的結(jié)果。實(shí)驗(yàn)結(jié)果顯示，OPSOAEM&NIW在所有測試函數(shù)上均優(yōu)于OVCPSO；與PSO和OPSO比較，除在f3上處取得相當(dāng)結(jié)果，OPSO-AEM&NIW在其他函數(shù)上均取得較優(yōu)解；EOPSO雖然在f3上取最優(yōu)解，但在其他12個(gè)函數(shù)上均劣于OPSO-AEM&NIW。特別地，OPSO-AEM&NIW與GOPSO在大多數(shù)函數(shù)中取得了相當(dāng)?shù)淖顑?yōu)解，但在4個(gè)測試函數(shù)f2～f5上，OPSO-AEM&NIW優(yōu)于GOPSO。

表2 數(shù)值實(shí)驗(yàn)中使用的14個(gè)測試函數(shù)

表3 PSO、OPSO、GOPSO、OVCPSO、EOPSO和OPSO?AEM&NIW算法在14個(gè)測試函數(shù)上的平均適應(yīng)值

為進(jìn)一步比較OPSO-AEM&NIW與GOPSO這2種算法性能上的差異，2類實(shí)驗(yàn)分別展開。首先除去平均適應(yīng)值(表3中已記錄)，將2種算法運(yùn)行30次后的另外3個(gè)性能指標(biāo)：標(biāo)準(zhǔn)方差、最佳及最差值分別記錄在表4中，結(jié)果顯示，OPSO-AEM&NIW在12個(gè)測試函數(shù)中的最差值均優(yōu)于GOPSO，說明新算法相對(duì)GOPSO性能整體較為穩(wěn)定。另外，2種算法在求解精度為10?16以及最大迭代次數(shù)為10 000次的條件下再次進(jìn)行實(shí)驗(yàn)，獲得的適應(yīng)值(fval)及適應(yīng)值函數(shù)評(píng)估次數(shù)(NFC)如表5所示。通過對(duì)NFC值的比較可見，OPSOAEM&NIW (除f10和f13)明顯小于GOPSO，實(shí)驗(yàn)結(jié)果表明OPSO-AEM&NIW大大提升了反向PSO算法的收斂速度。

表4 GOPSO和OPSO-AEM&NIW算法在14個(gè)測試函數(shù)上的運(yùn)行結(jié)果

表5 GOPSO和OPSO-AEM&NIW算法在14個(gè)測試函數(shù)上函數(shù)評(píng)估次數(shù)比較

4.2.2 2種策略有效性分析

為研究自適應(yīng)精英變異策略與非線性自適應(yīng)慣性策略在融入到反向?qū)W習(xí)(GOBL)中后對(duì)反向PSO算法性能所產(chǎn)生的影響，以測試函數(shù)f2、f9與f14為例，將AEM與NIW這2種策略分別與GOBL結(jié)合，形成GOBL+AEM和GOBL+NIW兩類算法，與新算法OPSO-AEM&NIW展開性能對(duì)比實(shí)驗(yàn)。特別指出，在GOBL+ AEM實(shí)驗(yàn)中，w取固定值0.729 84[19]。實(shí)驗(yàn)結(jié)果如圖2所示，NIW策略能夠充分調(diào)動(dòng)粒子在不同階段的活躍性，有效平衡算法的全局探索與局部開采能力，加快了算法的收斂速度；AEM策略則通過對(duì)精英粒子gbest的擾動(dòng)，有效避免粒子陷入局部最優(yōu)的可能性，確保算法得到快速平滑收斂。

圖2 AEM與NIW 2種策略對(duì)算法的影響

為從另一側(cè)面了解上述2種策略引入到反向粒子群中為避免算法陷入局部最優(yōu)所起到的作用，表6分別記錄了OPSO算法[7]與OPSO-AEM&NIW算法在30次運(yùn)行中陷入局部最優(yōu)的平均次數(shù)(MNLO,mean number of local optimum)，以及對(duì)應(yīng)全局最優(yōu)結(jié)果的均值(mean)。實(shí)驗(yàn)結(jié)果表明，除f4以外，OPSO-AEM&NIW在其他測試函數(shù)上的MNLO值均少于OPSO的MNLO值，表明AEM與NIW策略能使粒子在進(jìn)化過程中有效地避免陷入局部最優(yōu)的次數(shù)，一旦發(fā)生，也能采用自適應(yīng)精英變異策略更成功地跳出局部最優(yōu)，從而快速地收斂到全局最優(yōu)值，并表現(xiàn)出較好的穩(wěn)定性。同時(shí)注意到，雖然f4的MNLO在OPSO中更小，但它并沒有收斂到全局最優(yōu)，原因是OPSO算法在處于某個(gè)局部最優(yōu)時(shí)無法通過自身的變異操作跳出，進(jìn)而出現(xiàn)早熟收斂現(xiàn)象。

4.2.3 參數(shù)敏感性分析

通過策略分析，對(duì)3種策略(GOBL、AEM與NIW)在OPSO-AEM&NIW算法基本PSO性能改進(jìn)中起到的作用有了清晰的了解。策略中各個(gè)參數(shù)的設(shè)置對(duì)算法的性能往往有著很大的影響，文獻(xiàn)[7]中已通過實(shí)驗(yàn)得出結(jié)論：當(dāng)OBL使用概率jr為0.3時(shí)，算法達(dá)到最佳性能，本文引用了這一結(jié)論。

為檢驗(yàn)AEM策略中參數(shù)λ的取值對(duì)算法性能是否具有一定的影響，通過對(duì)14個(gè)測試函數(shù)上λ在10～60之間取不同的6個(gè)整數(shù)值時(shí)算法OPSOAEM&NIW收斂過程的觀測可知，當(dāng)λ＝30時(shí)，所有測試問題都能較平穩(wěn)而快速地收斂到全局最優(yōu)解。介于篇幅的限制，圖3僅給出了在測試函數(shù)f3、f9和f12中OPSO-AEM&NIW參數(shù)λ取不同值時(shí)算法收斂到全局最優(yōu)值的進(jìn)化過程。

圖3 λ在不同取值下OPSO-AEM&NIW全局收斂過程

除此之外，表7統(tǒng)計(jì)了AEM策略的另一個(gè)待定參數(shù)C對(duì)14個(gè)測試函數(shù)在30次實(shí)驗(yàn)中自適應(yīng)取不同常量值時(shí)各自的平均概率情況。其中，Mut為變異位占優(yōu)的次數(shù)。特別注意，當(dāng)C=0.5時(shí)，變異式(11)將退化成柯西變異[7]。實(shí)驗(yàn)數(shù)據(jù)表明，相比于柯西變異，自適應(yīng)精英變異策略將增加25%的概率獲得更優(yōu)的變異位，雖然這看似遠(yuǎn)小于C=0.5的概率，但其對(duì)于算法是否能成功跳出局部最優(yōu)位是非常關(guān)鍵的。

由4.2.2節(jié)分析可知，NIW策略的引入相對(duì)于w取固定值時(shí)能顯著加快算法的收斂速度，而對(duì)于其中參數(shù)w取值范圍(wmax與wmin)，通過反復(fù)實(shí)驗(yàn)可知，當(dāng)w取值在0.2～0.5之間時(shí)，算法在所有測試函數(shù)上取得最好結(jié)果。圖4以f6為例，展示了算法進(jìn)化前1 000代過程中w自適應(yīng)取值的變化情況。由圖4可知，隨著進(jìn)化的深入，w取值將趨于0.5，使算法以較大的慣性快速收斂到全局最優(yōu)值。

表7 AEM變異策略在14個(gè)測試函數(shù)上取值概率

圖4 w取值自適應(yīng)變化情況

5 結(jié)束語

本文提出了一種帶自適應(yīng)精英擾動(dòng)及慣性權(quán)重的反向粒子群優(yōu)化算法。該算法將自適應(yīng)精英變異和非線性自適應(yīng)慣性權(quán)重2種策略融入到一般性反向?qū)W習(xí)策略中。為提高全局探索能力，GOBL策略在每代中對(duì)解空間與其反向解空間同時(shí)進(jìn)行搜索。AEM策略將全局最優(yōu)粒子選為精英粒子，根據(jù)當(dāng)前群體聚集程度的不同，自適應(yīng)選取變異量，使精英粒子獲得足夠的擾動(dòng)，并吸引其他粒子向其運(yùn)動(dòng)，從而幫助粒子跳出局部最優(yōu)。NIW策略的引入可進(jìn)一步克服算法全局探索與局部開采之間的矛盾。它通過自適應(yīng)獲取慣性權(quán)值，根據(jù)需求調(diào)節(jié)各個(gè)粒子在不同階段的活躍程度。進(jìn)化初期，w在一定區(qū)間內(nèi)自適應(yīng)地變化，以擴(kuò)大算法的全局搜索空間；隨著迭代次數(shù)的增加，w取值逐漸趨于平穩(wěn)，從而有效避免算法最優(yōu)值的振蕩，提高算法的局部開采能力，確保算法平滑快速地收斂到全局最優(yōu)值。

通過對(duì)多種函數(shù)的測試結(jié)果表明，新算法在獲得高精度解的同時(shí)，顯著提高了算法的收斂速度。在未來的工作中，如何使算法適應(yīng)更多的問題還需展開更多的實(shí)驗(yàn)。另外，算法在高維問題中是否適用及可能存在的問題還需進(jìn)一步的實(shí)驗(yàn)。如何將算法與實(shí)際問題相結(jié)合是未來研究工作的重點(diǎn)。

[1]KENNEDY J,EBERHART R C.Particle swarm optimization[C]// IEEE International Conference on Neural Networks.Perth,Australia,1995:1942-1948.

[2]史霄波,張引,趙杉,等.基于離散多目標(biāo)優(yōu)化粒子群算法的多移動(dòng)代理協(xié)作規(guī)劃[J].通信學(xué)報(bào),2016,37(6):29-37.SHI X B,ZHANG Y,ZHAO S,et al.Discrete multi-objective optimization of particle swarm optimizer algorithm for multi-agents collaborative planning [J].Journal on Communications,2016,37(6):29-37.

[3]INBARANI H H,AZAR A T,JOTHI G.Supervised hybrid feature selection based on PSO and rough sets for medical diagnosis [J].Computer Methods and Programs in Biomedicine,2014,113(1):175-185.

[4]ZAD B B,HASANVAND H,LOBRY J,et al.Optimal reactive power control of DGs for voltage regulation of MV distribution systems using sensitivity analysis method and PSO algorithm [J].International Journal of Electrical Power and Energy System,2015,68:52-60.

[5]SHI Y,EBERHART R C.A modified particle swarm optimizer[C]//The IEEE Congress on Evolutionary Computation (CEC 1998).1998:69-73.

[6]TIZHOOSH H R.Opposition-based learning:a new scheme for machine intelligence[C]//The IEEE International Conference of Intelligent for Modeling,Control and Automation.PiscatNIWay:Inst of Elec.and Elec Eng Computer Society.2005:695-701.

[7]WANG H,LI H,LIU Y,et al.Opposition-based particle swarm algorithm with Cauchy mutation [C]//The IEEE Congress on Evolutionary Computation.2007:356-360.

[8]WANG H,WU Z J,RAHNAMAYAN S,et al.Enhancing particle swarm optimization using generalized opposition-based learning [J].Information Sciences,2011,181:4699-4714.

[9]周新宇,吳志健,王暉,等.一種精英反向?qū)W習(xí)的粒子群優(yōu)化算法[J].電子學(xué)報(bào),2013,41(8):1647-1652.ZHOU X Y,WU Z J,WANG H,et al.Elite opposition-based particle swarm optimization[J].Acta Electronica Sinica,2013,41(8):1647-1652.

[10]SHAHZAD F,BAIG A R,MASOOD S,et al.Opposition-based particle swarm optimization with velocity clamping (OVCPSO) [J].Advances in Computational Intell,2009:339-348.

[11]KAUCIC M.A multi-start opposition-based particle swarm optimization algorithm with adaptive velocity for bound constrained global optimization[J].J Glob Optim,2013,55:165-188

[12]PEHLIVANOGLU Y V.A new particle swarm optimization method enhanced with a periodic mutation strategy and neural networks [J].IEEE Trans Evol Comput.2013,17:436-452.

[13]KARAFOTIAS G,HOOGENDOORN M,EIBEN A E.Parameter control in evolutionary algorithms:trends and challenges[J].IEEE Transactions on Evolutionary Computation,2015,19:167-187.

[14]汪慎文,丁立新,謝承旺,等.應(yīng)用精英反向?qū)W習(xí)策略的混合差分演化算法[M].武漢大學(xué)學(xué)報(bào)(理學(xué)版),2013,59(2):111-116.WANG S W,DING L X,XIE C W,et al.A hybrid differential evolution with elite opposition-based learning [J].Journal of Wuhan University,2013,59(2):111-116.

[15]OZCAN E,MOHAN C K.particle swarm optimization:surfing and waves[C]//Congress on Evolutionary Computation (CEC1999).1999:1939-1944.

[16]龔純,王正林.精通MATLAB最優(yōu)化計(jì)算[M].電子工業(yè)出版社,2012:283-285.GONG C,WANG Z L.Proficient optimization calculation in MATLAB [M].Electronic Industry Press,2012:283-285.

[17]FRANS V D B.An analysis of particle swarm optimizers[D].Department of Computer Science,University of Pretoria,South Africa,2002.

[18]TANG K,LI X D,SUGANTHAN P N,et al.Benchmark functions for the CEC’2010 special session and competition on large-scale global optimization[R].Nature Inspired Computation and Applications Laboratory,USTC,China,20092,1.

[19]BERGH F,ENGELBRECHT A P.Effect of swarm size on cooperative particle swarm optimizers[C]//Genetic and Evolutionary Computation Conference.2001:892-899.

董文永（1973-），男，河南南陽人，博士，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)檠莼?jì)算、智能仿真優(yōu)化、系統(tǒng)控制、機(jī)器學(xué)習(xí)等。

康嵐蘭（1979-），女，江西贛州人，武漢大學(xué)博士生，江西理工大學(xué)講師，主要研究方向?yàn)檠莼?jì)算、機(jī)器學(xué)習(xí)等。

劉宇航（1979-），男，湖北孝感人，武漢大學(xué)博士生，主要研究方向?yàn)榻y(tǒng)計(jì)機(jī)器學(xué)習(xí)及相關(guān)應(yīng)用。

李康順（1962-），男，江西興國人，博士，華南農(nóng)業(yè)大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橹悄苡?jì)算、多目標(biāo)優(yōu)化、視頻流圖像識(shí)別等。

Opposition-based particle swarm optimization with adaptive elite mutation and nonlinear inertia weight

An opposition-based particle swarm optimization with adaptive elite mutation and nonlinear inertia weight (OPSO-AEM&NIW) was proposed to overcome the drawbacks,such as falling into local optimization,slow convergence speed of opposition-based particle swarm optimization.Two strategies were introduced to balance the contradiction between exploration and exploitation during its iterations process.The first one was nonlinear adaptive inertia weight (NIW),which aim to accelerate the process of convergence of the algorithm by adjusting the active degree of each particle using relative information such as particle fitness proportion.The second one was adaptive elite mutation strategy (AEM),which aim to avoid algorithm trap into local optimum by trigging particle’s activity.Experimental results show OPSO-AEM&NIW algorithm has stronger competitive ability compared with opposition-based particle swarm optimizations and its varieties in both calculation accuracy and computation cost.

generalized opposition-based learning,particle swarm optimization,adaptive elite mutation,nonlinear inertia weight

The National Natural Science Foundation of China (No.61170305，No.61672024)

TP181

A

10.11959/j.issn.1000-436x.2016224

DONG Wen-yong1,KANG Lan-lan1,2,LIU Yu-hang1,LI Kang-shun3

(1.Computer School,Wuhan University,Wuhan 430072,China;2.Faculty of Applied Science,Jiangxi University of Science and Technology,Ganzhou 341000,China;3.College of Information,South China Agricultural University,Guangzhou 510642,China)

2015-09-22；

2016-09-09

康嵐蘭，victorykll@163.com

資助項(xiàng)目（No.61170305，No.61672024）