帶全局判據(jù)的改進量子粒子群優(yōu)化算法

徐珊珊, 金玉華, 張慶兵

(中國航天科工防御技術(shù)研究院, 北京 100854)

0 引 言

工程優(yōu)化問題通常具有優(yōu)化參數(shù)較多、非線性較強和同時存在多個局部最優(yōu)解的特點。因此,優(yōu)化算法需要在較短時間內(nèi),促使多個優(yōu)化參數(shù)同時收斂到全局最優(yōu)位置,以增大得到全局最優(yōu)解的概率。近年來,研究人員已針對該問題開展了大量研究。

粒子群優(yōu)化(particle swarm optimization,PSO)算法是由Eberhart和Kennedy等人于1995年提出的基于種群并行全局優(yōu)化算法。其源于對鳥群群體協(xié)作的捕食行為模擬,通過種群間個體的協(xié)作,引導整個群體向可能解的方向移動[1-3]。與其他全局優(yōu)化算法相比,PSO算法具有程序簡單,多維并行優(yōu)化,優(yōu)化速度較快的優(yōu)點,已獲得廣泛的應用[4-6]。但其也具有一定局限,比如容易局部收斂、收斂速度較慢等。文獻[7-8]等綜合前人工作[9-10],將粒子速度或位置小概率隨機變異與自適應逃逸策略相結(jié)合,提出了全局搜索性能較優(yōu)的改進PSO算法,并將其運用在氣動力計算、高超聲速飛行器設計等方面。但這些算法收斂速度較慢,導致迭代步數(shù)較多(文獻[7]為2 000步),計算成本大大增加。

為增大粒子搜索范圍,文獻[11]從量子力學的角度出發(fā),認為種群中的粒子具有量子行為,在某種吸引勢能場的作用下會以一定的概率密度出現(xiàn)在設計空間的任意一點,因此提出了優(yōu)化時間僅為PSO算法1/3的量子PSO(quantum-behaved particle swarm optimization,QPSO)算法。QPSO算法具有魯棒性強,計算速度快的優(yōu)勢,已運用在2D火焰溫度測量[12]、超光譜圖像端元提取[13-14]、正電子發(fā)射斷層顯像建模[15]、腦電圖信號分類[16]、經(jīng)濟調(diào)度[17]等領(lǐng)域,并發(fā)展到多目標優(yōu)化[18-19]和動態(tài)優(yōu)化[20-23]方向。但由于QPSO算法在粒子進化過程中,慣性權(quán)值β隨進化代數(shù)增加而線性減少,易出現(xiàn)早熟收斂,且易導致算法收斂過慢。文獻[24]等采用適應度加權(quán)重組算子改進了QPSO算法;文獻[25]等引入服從高斯概率分布的局部因子,以增大粒子全局性;文獻[26]等發(fā)展了根據(jù)粒子適應度分布情況進行粒子位置搜索范圍變化的自適應QPSO方法;文獻[27]結(jié)合云模型,發(fā)展了自適應云QPSO改進方法;文獻[28]將自適應云QPSO算法與圖像識別技術(shù)結(jié)合,提高了圖像識別準確率;文獻[29]采用改進的混合蛙跳算法進行局部搜索,將參數(shù)自適應和精英學習策略引入優(yōu)化狀態(tài)評估;文獻[30]利用布洛赫球體上一個軸的旋轉(zhuǎn)來更新粒子,提出了布洛赫球面改進(bloch sphere-based QPSO,BQPSO)算法;文獻[31]提出了一種基于列維飛行的量子粒子群優(yōu)化算法;文獻[32]采用分層協(xié)同進化的方法改進QPSO算法, 并應用于新生兒腦組織的研究;文獻[33]提出了慣性權(quán)重自適應調(diào)整的QPSO(dynamically changing weight’s QPSO,DCWQPSO)算法,并研究了單參數(shù)優(yōu)化問題算法收斂的參數(shù)設置。但當優(yōu)化參數(shù)增多時,以上改進算法極易收斂到局部最優(yōu)解,對于較為復雜的測試函數(shù),20和30維粒子的優(yōu)化結(jié)果仍有較大提升空間[24-31],將無法符合實際工程問題對多參數(shù)優(yōu)化的需求。

不僅如此,由于粒子具有量子行為,QPSO算法具有很強的隨機性。對于未知問題,工程人員無法判定優(yōu)化結(jié)果是否為全局最優(yōu)解?，F(xiàn)有辦法僅依靠優(yōu)化算法對優(yōu)化算法Benchmark測試函數(shù)的優(yōu)化能力,進行粗略判斷,或者采用“多次獨立優(yōu)化,選取最優(yōu)解”的方法。顯然,采用這些人工篩選的方法不僅將消耗大量計算時間,全局最優(yōu)解的判定還仍然無法準確得到。所以,針對工程應用,優(yōu)化算法更需要在優(yōu)化過程中自行判定優(yōu)化結(jié)果的全局性,直接輸出全局最優(yōu)解。

因此,本文首先針對多參數(shù)優(yōu)化問題的全局搜索能力,對DCWQPSO算法進行了粒子位置周期性變異及隨進化速度和粒子聚集度變化的搜索范圍變異,并依據(jù)Benchmark函數(shù)優(yōu)化結(jié)果進行了參數(shù)討論。然后,針對未知問題無法判定優(yōu)化結(jié)果全局性的問題,本文建立了全局收斂判據(jù)。最后,針對乘波體最大升阻比的前緣線多參數(shù)優(yōu)化問題,本文采用帶全局判據(jù)的改進QPSO(improved QPSO with global criterion,GCIQPSO)算法進行了參數(shù)優(yōu)化。結(jié)果證明,對于多參數(shù)優(yōu)化問題,本文算法的全局搜索性能大大提高,全局判據(jù)實用性強,優(yōu)化結(jié)果可靠。

1 DCWQPSO算法

QPSO算法引入δ勢阱模型,通過求解薛定諤方程得到相關(guān)波函數(shù)Ψ(x,t),進而計算出粒子在設計空間內(nèi)某一處的概率密度函數(shù),最后由蒙特卡羅方法確定粒子的新位置。位置方程x(t)的第i維表達式為

(1)

DCWQPSO算法把慣性權(quán)重β的表達式改進為與進化速度因子sd和粒子聚集度因子jd有關(guān)的自適應權(quán)重。其表達式為

β=f(sd,jd)=β0-sdβ1+jdβ2

(2)

2 帶全局判據(jù)的改進QPSO算法

對于多維參數(shù)優(yōu)化問題,粒子的搜索范圍需要大大增加,才能保證各維粒子尋找到全局最優(yōu)位置的概率增大,優(yōu)化結(jié)果收斂于全局最優(yōu)解的概率才能有所增加。因此,本文提出了帶全局判據(jù)的改進QPSO算法(global criterion improved QPSO,GCIQPSO)算法,不僅提高粒子群搜索范圍,增大得到全局最優(yōu)解的概率,還對優(yōu)化結(jié)果進行全局性判斷,無需人工篩選,直接得到全局最優(yōu)解。

2.1 改進DCWQPSO算法

由式(2)可知,β1代表進化速度快慢在慣性權(quán)重中的占比,β2表示粒子聚集度大小的占比,β的大小直接影響了粒子更新的范圍。若優(yōu)化陷于局部最優(yōu)解,則粒子群的全局最優(yōu)位置固定,sd=1,無論粒子聚集度jd大小如何,β只能在[0.5,0.7]范圍內(nèi)變化,產(chǎn)生的粒子搜索范圍下降,較難尋找到全局最優(yōu)解。不僅如此,從式(2)可以發(fā)現(xiàn),一旦優(yōu)化過程陷入局部最優(yōu)狀態(tài),隨著迭代步數(shù)的增加,粒子群將逐步靠近該局部最優(yōu)位置,使得jd也不斷趨于定值,β隨之固定,新粒子尋找到全局最優(yōu)解的概率進一步下降。由此可見,隨著局部收斂的出現(xiàn),DCWQPSO算法的粒子種群多樣性將不斷惡化,直至失效。

為增大粒子多樣性,避免粒子群陷入局部最優(yōu),本文首先加入粒子位置周期性變異,每迭代T步變異一次，即

xi(t)=xi(t)[1+(0.5-randi(0,1))δ]

為得到較為通用的結(jié)論,本文選擇CEC2005函數(shù)中結(jié)果較不理想[7,11,24-33]的測試函數(shù)及其復合形式,并添加兩種復雜函數(shù)[30]組成8個優(yōu)化測試函數(shù)(函數(shù)形式見表1),并采用30個30維粒子[7,30]組成優(yōu)化粒子群(f6(x)函數(shù)取32維粒子)。由于QPSO算法隨機性較大,為體現(xiàn)優(yōu)化結(jié)果的平均性,本文采用100次獨立優(yōu)化的結(jié)果,具體數(shù)據(jù)如表2所示。

表1 8個優(yōu)化測試函數(shù)

表2 不同函數(shù)的30維30個粒子的粒子群100次獨立優(yōu)化平均值

從DCWQPSO優(yōu)化結(jié)果可見,優(yōu)化參數(shù)增多后,除f1(x)和f5(x)外,其他函數(shù)的β1=0.7優(yōu)化結(jié)果更穩(wěn)定,明顯優(yōu)于β1=0.5,與文獻[32]的單參數(shù)優(yōu)化研究結(jié)論有所不同。增加位置周期性變異后,8種函數(shù)的粒子群全局搜索能力均有提高:f1(x)、f3(x)、f5(x)、f6(x)函數(shù)的優(yōu)化結(jié)果提高幅度最大;由于f8(x)函數(shù)本身精度較好,改進后提升空間最小;f2(x)和f7(x)(f2(x)函數(shù)的非連續(xù)型)次之。而隨著變異周期從30減小至10,8種函數(shù)的優(yōu)化結(jié)果精確度均有提升,但若進一步減小(T=5),粒子的繼承性無法體現(xiàn),不利于全局搜索能力的提升。對f1(x)、f2(x)、f4(x)～f8(x)函數(shù)而言,T=10優(yōu)化結(jié)果最佳;對f3(x)函數(shù)而言,T=30周期的平均優(yōu)化值最佳,T=10的優(yōu)化結(jié)果次之。綜合而言,本文選擇T=10為位置變異周期。

從表2可發(fā)現(xiàn),粒子位置周期變異能有效增加多樣性,單峰二次函數(shù)f1(x)的100次獨立優(yōu)化平均值有較大提升,優(yōu)化結(jié)果精度較高。但其余7個函數(shù)優(yōu)化結(jié)果仍有一定提升空間。

由第1節(jié)可知,粒子搜索范圍主要由勢阱的特征長度L決定,擴大β的取值范圍最為關(guān)鍵。本文研究了位置變異后全局收斂提升較小的f2(x)函數(shù)優(yōu)化結(jié)果的β值變化趨勢(見圖1)。

圖1 不同優(yōu)化結(jié)果的βFig.1 β curve with various optimization results

從圖1可見,局部收斂越明顯,β值越容易集中于一點,極大地影響了粒子群的搜索范圍。因此,本文在粒子位置周期變異的基礎(chǔ)上,增加了β值變異。具體方法為

βi(t)=βi(t)[1+(0.5-randi(0,1))δ]

粒子位置變異直接改變粒子位置,具有一定隨機性,但往往無法有效增大全局搜索范圍。而β變異直接對粒子的搜索能力進行判斷和變異,以擴大搜索范圍。因此,在粒子達到一定搜索能力后,β變異啟動較為有效,Nb不宜過小,但過大的Nb又無法有效提升已陷入局部最優(yōu)的粒子全局搜索能力。而β在Tb步內(nèi)是否保持不變代表了粒子全局搜索范圍是否持續(xù)增加,β變異周期Tb需不大于粒子位置變異周期T,但過小的Tb會使粒子無法有效繼承前粒子的優(yōu)化成果,自適應慣性權(quán)重優(yōu)勢無法體現(xiàn)。

為研究Nb和Tb的設置,本文同樣采用8個測試函數(shù)進行30維30個粒子的100次獨立優(yōu)化,優(yōu)化結(jié)果列于表2,每個函數(shù)的最佳值均用黑體標出。從結(jié)果可見,雙重優(yōu)化降低了f2(x)～f8(x)函數(shù)優(yōu)化結(jié)果與全局最優(yōu)解的距離,f1(x)函數(shù)的精確度仍滿足要求。當參數(shù)Nb=50和Tb=5時,除f1(x)和f7(x)外,β值變異最有效。

綜上,粒子位置周期變異與β變異結(jié)合的方法,能有效增大粒子群全局搜索能力,多維函數(shù)優(yōu)化結(jié)果收斂于全局最優(yōu)解的概率大為增加,且參數(shù)選擇T=10、Nb=50和Tb=5效果最好。

2.2 全局收斂判據(jù)

優(yōu)化算法的全局搜索能力越強,優(yōu)化結(jié)果收斂于全局最優(yōu)解的概率越大,而每一迭代步的粒子分布范圍大小則代表了全局搜索能力的強弱,不僅如此,其也可以表征粒子位置周期變異能否擴大粒子的全局搜索能力。由第1節(jié)定義可知,粒子聚集度jd表示當前迭代步下,各粒子歷史最優(yōu)解和當前全局最優(yōu)解的比值。其物理含義包括:①jd值不斷變化直觀體現(xiàn)了粒子的全局搜索能力是否持續(xù)擴大。隨著迭代步數(shù)增加,若其值不斷變化,則表明新粒子搜索到了更優(yōu)解;若保持不變,則表示新粒子無法得到更優(yōu)解;②jd值大小表示迭代過程的收斂程度。其值在0～1范圍內(nèi)變化,數(shù)值越大表示各維粒子局部最優(yōu)解的均值越趨近于全局最優(yōu)解,迭代過程越趨于收斂;③jd值的變化劇烈程度直接體現(xiàn)了整個尋優(yōu)過程粒子群的多樣性大小,若均值和方差均較低,則表示整個迭代過程粒子群無明顯收斂,且離散度較大,一直保持尋優(yōu)狀態(tài),全局搜索能力高,變異方法較為有效。所以,本文研究了jd的變化劇烈程度,并以此作為優(yōu)化結(jié)果是否收斂到全局最優(yōu)解的依據(jù)。

圖2 不同函數(shù)和優(yōu)化結(jié)果下,jd的變化曲線Fig.2 jd Curve of different functions with various optimization results

由圖2可見,其優(yōu)化結(jié)果最趨近于全局最優(yōu)解的算例,jd曲線變化最為劇烈(如Sphere函數(shù)曲線1和2,Rastrigin函數(shù)曲線2,Rosenbrock函數(shù)曲線3);優(yōu)化結(jié)果越偏離全局

最優(yōu)解時,jd曲線變化越平緩(如Rastrigin函數(shù)曲線1和4,Rosenbrock函數(shù)曲線2);且優(yōu)化結(jié)果的好壞與jd值最終的大小無關(guān),僅與其均值和方差有關(guān),jd值變化越劇烈,均值和方差越小。統(tǒng)計100 000次獨立優(yōu)化結(jié)果發(fā)現(xiàn),當jd均值小于0.5,且標準差小于0.3時,2 000迭代步的優(yōu)化結(jié)果99.8%為全局最優(yōu)。

鑒于實際優(yōu)化問題的復雜程度帶來了較大的計算成本,迭代步數(shù)應盡量降低,本文選用200迭代步,再次進行了100 000次獨立優(yōu)化。結(jié)果顯示,當jd均值小于0.5,且標準差小于0.3時,優(yōu)化結(jié)果99.1%為全局最優(yōu)。

因此,本文建立了針對優(yōu)化參數(shù)大于5的多參數(shù)優(yōu)化全局判據(jù)。其分為兩個部分:①優(yōu)化迭代中,粒子聚集度jd變化越劇烈,粒子的全局搜索能力越強,若其連續(xù)10步(粒子位置變異周期為10步,β變異周期為5步)均保持不變,說明雙重變異對擴大全局搜索能力無效,則跳出此次優(yōu)化,重新初始化種群,并將此次全局最優(yōu)粒子作為其中一個初始粒子;②迭代結(jié)束時,若優(yōu)化過程沒有中斷,迭代步數(shù)達到最大迭代值,則判斷粒子聚集度jd是否滿足“均值小于0.5且標準差小于0.3”的條件。若以上兩個條件均滿足,則存儲優(yōu)化結(jié)果,本次優(yōu)化結(jié)束;若不滿足,將本次全局最優(yōu)粒子作為一個初始粒子,重新開始優(yōu)化,直至滿足條件(即可篩選局部最優(yōu)解,也可保留不滿足條件的全局最優(yōu)解)。

某些低維參數(shù)優(yōu)化問題較易收斂,導致jd值不變或其均值偏大,則儲存每次全局優(yōu)化結(jié)果。若5次均跳出且迭代結(jié)果不變,表示優(yōu)化結(jié)果為全局最優(yōu)解。對于未知問題,需獨立優(yōu)化3次,選取最優(yōu)值。

2.3 GCIQPSO算法

GCIQPSO算法采用β值和粒子位置雙重變異,jd變化劇烈程度、均值及標準差作為全局判據(jù),每次獨立迭代滿足迭代步要求后,判斷優(yōu)化結(jié)果是否符合全局判據(jù)條件,若不符合重新初始化優(yōu)化程序。

為驗證全局判據(jù)的通用性,本文對8個測試函數(shù),進行了30次獨立優(yōu)化,不同優(yōu)化算法的結(jié)果如表3所示。

表3 測試函數(shù)的不同優(yōu)化算法結(jié)果

由表3可見,與2 000步[7,30]優(yōu)化結(jié)果相比,縮短迭代步數(shù)后,改進PSO[7](improved particle swarm optimization,IPSO)算法和BQPSO[30]全局搜索性能大為降低;而計算時間較短的QPSO和DCWQPSO算法,由于隨機性較大,導致優(yōu)化結(jié)果極不穩(wěn)定,平均值偏離全局最優(yōu)解的程度也較大。不同測試函數(shù)下,本文全局判據(jù)依然有效,優(yōu)化精度遠好于前4種算法。相比其他函數(shù),f5(x)出現(xiàn)局部最優(yōu)點的概率較大,優(yōu)化精度不佳。因此,本文以2 000步為迭代步數(shù),重新進行了30次獨立優(yōu)化,均值為0.064,平均時間為7.48 s。

經(jīng)過試驗發(fā)現(xiàn),本文全局判據(jù)同樣適用于前3種算法。但全局判據(jù)僅作為判斷優(yōu)化結(jié)果全局性的依據(jù),不會擴大算法搜索范圍。是否可與BQPSO結(jié)合,仍需進一步研究。

表3的GCIQPSO(a)列顯示了迭代步數(shù)降低為150步的結(jié)果。雖然測試函數(shù)優(yōu)化均值精度有所下降,但誤差均在3%以內(nèi)。但若迭代步數(shù)進一步降低,則全局判據(jù)需進一步收緊。GCIQPSO(b)列為粒子維度=4的150步優(yōu)化結(jié)果,可見對于低維優(yōu)化問題,全局判據(jù)依然有效。

3 乘波體前緣線多參數(shù)優(yōu)化

為驗證GCIQPSO算法對工程問題的實用性,本文選用了乘波體外形優(yōu)化作為算例,設計方法、設計參數(shù)和優(yōu)化參數(shù)與文獻[34-35]保持一致,即:采用錐導乘波體設計方法和面元法的氣動力估算方法;設計參數(shù)采用來流馬赫數(shù)為6,飛行高度H=30 km,激波角β=12°,截止平面設定為單位長度;優(yōu)化參數(shù)選取(x5,y1,y2,y3,y4),前緣線采用5個點的3次擬合曲線,目標函數(shù)為升阻比最大,約束條件為容積率大于0.07小于0.12,若優(yōu)化結(jié)果不滿足約束條件,則返回非數(shù)值(not a nuber,NaN)。乘波體前緣線優(yōu)化流程如圖3所示。

圖3 乘波體氣動外形優(yōu)化流程Fig.3 Flowchart of cone-derived waverider configuration optimization

為節(jié)省計算時間,本文選擇迭代步為150步,為防止不確定因素干擾優(yōu)化結(jié)果,獨立迭代3次,取最大值。迭代結(jié)束時,粒子聚集度jd標準差為0.28,均值為0.42,最大升阻比為6.28,比文獻34的最大升阻比增大了20%,且與多次200步遺傳算法(文獻[34]采用)最優(yōu)值一致。

4 結(jié) 論

針對多參數(shù)(參數(shù)個數(shù)不少于5)優(yōu)化問題極易收斂到局部最優(yōu)點和優(yōu)化結(jié)果無法判斷是否為全局最優(yōu)解的問題,本文提出了改進的量子粒子群優(yōu)化算法。具體結(jié)論如下:

(1) 在DCWQPSO算法基礎(chǔ)上,本文增加了β值和粒子位置的雙重變異,大大增強了粒子的全局收斂能力。Benchmark測試函數(shù)的優(yōu)化結(jié)果全局性明顯提升;

(2) 以粒子聚集度jd作為判斷粒子全局搜索能力的依據(jù),依據(jù)粒子周期變化是否對擴大粒子搜索范圍有效和迭代結(jié)束所有粒子的全局分散情況為標準,建立了優(yōu)化結(jié)果全局性的判據(jù),使得優(yōu)化過程去除人工篩選環(huán)節(jié),直接輸出全局最優(yōu)解。本文通過Benchmark函數(shù)的大量試驗驗證,相較于其他優(yōu)化方法,迭代步驟為150步的GCIQPSO算法優(yōu)化結(jié)果均為全局最優(yōu)解,遠好于其他3種算法,且平均優(yōu)化時間均少于IPSO算法。由此可見,本文全局判據(jù)簡單可行,優(yōu)化結(jié)果全局性十分突出;

(3) 為進一步驗證GCIQPSO算法的工程應用價值,本文對乘波體前緣線優(yōu)化問題進行了計算。結(jié)果表明,GCIQPSO算法得到的優(yōu)化結(jié)果較文獻[34]有了明顯提高,滿足全局判據(jù),與遺傳算法的多次試驗結(jié)果一致。由此可見,對于多維優(yōu)化的實際工程問題,GCIQPSO算法的全局搜索能力較好,全局判據(jù)可行,優(yōu)化結(jié)果真實可信;

綜上所述,本文提出的GCIQPSO算法是對多參數(shù)優(yōu)化全局性判斷問題的補充;其具有收斂速度快、全局搜索能力強、全局判據(jù)簡單可行、優(yōu)化結(jié)果真實可靠的優(yōu)點;在較短時間內(nèi)得到較為可信的全局最優(yōu)解。GCIQPSO算法的優(yōu)化效率較高,優(yōu)化結(jié)果精度較好,可削減大量重復優(yōu)化時間,省略人工篩選環(huán)節(jié),具有一定學術(shù)價值和較大工程應用價值,可進一步拓展實際運用范圍。