基于代理模型的雙層粒子群優(yōu)化算法

龔德志++孫美建++李澤江

摘 要：為了克服粒子群優(yōu)化算法計算量大和傳統(tǒng)代理模型優(yōu)化方法易陷入局部最優(yōu)的缺點，本文提出一種在父級量子粒子群中引入繁殖篩選與嵌入子級優(yōu)化策略的雙層粒子群優(yōu)化算法，實現(xiàn)了子代粒子基于Kriging代理模型的精準(zhǔn)更新。對多種基準(zhǔn)函數(shù)測試以及翼型優(yōu)化算例表明，該算法可大幅度降低計算量，并有效地保持多樣性提高優(yōu)化精度，大大提高了優(yōu)化算法的工程實用性。

關(guān)鍵詞：粒子群優(yōu)化算法；量子行為；Kriging代理模型；繁殖；多樣性

DOI：10.16640/j.cnki.37-1222/t.2017.15.211

1 引言

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）[1]是由Kennedy和Eberhart于1995年提出的一種模擬鳥群覓食行為的群體智能優(yōu)化算法，該算法實現(xiàn)簡單，操作方便，收斂速度快，能有效解決復(fù)雜優(yōu)化問題，在函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制、模式識別等領(lǐng)域得到了廣泛應(yīng)用[2]。但是與其他隨機優(yōu)化算法一樣，標(biāo)準(zhǔn)粒子群算法（Standard PSO，SPSO）也存在早熟收斂現(xiàn)象。對此，研究人員發(fā)展了很多增加種群多樣性或加強局部搜索的改進算法以提高優(yōu)化精度，例如根據(jù)群體適應(yīng)度方差自適應(yīng)變異的PSO算法[3]，引入克隆選擇思想的免疫PSO算法[4]，組織進化PSO算法[5]，協(xié)同PSO算法[6]等。另外，采用動態(tài)慣性權(quán)重因子[7]或用優(yōu)良粒子替換差的粒子[8]等方法可以加速收斂。

然而各種隨機優(yōu)化算法在解決實際工程問題時仍然面臨著計算量太大的局限性。以航空工程中翼型優(yōu)化為例，現(xiàn)有優(yōu)化算法一般需要對數(shù)千個翼型進行計算才能得到滿意的優(yōu)化結(jié)果[9-10]，而通常對每個翼型數(shù)值計算需耗時數(shù)分鐘，當(dāng)進行變量更多、計算要求更高的三維氣動外形優(yōu)化時總計算量變得更難以接受。對此，研究人員發(fā)展了基于代理模型的優(yōu)化方法，用優(yōu)化算法尋找代理模型的最優(yōu)解，可大幅度降低計算次數(shù)，但是該方法嚴(yán)重依賴于代理模型的精度，容易陷入局部最優(yōu)。因此，本文的研究重點是在保證優(yōu)化精度的前提下，將總計算次數(shù)大幅降低到可接受的范圍以內(nèi)。

2 標(biāo)準(zhǔn)粒子群與量子粒子群算法

2.1 標(biāo)準(zhǔn)粒子群算法

粒子群優(yōu)化算法模擬鳥群飛行覓食行為，在每個粒子發(fā)現(xiàn)的最優(yōu)解和整個粒子群最優(yōu)解的引導(dǎo)下迭代搜索到全局最優(yōu)解。首先隨機初始化粒子種群位置和初速度，然后計算出每個粒子的適應(yīng)值，每個粒子記住自身所找到的個體最優(yōu)粒子pbest以及迄今為止找到的全局最優(yōu)粒子gbest，用粒子當(dāng)前速度、pbest和gbest的位置來更新粒子速度，從而在下一個時刻粒子能飛行到新的位置進行搜尋。

粒子群算法具有認知、社會及平衡功能，簡單高效具有較強的全局搜索能力，但容易陷入局部最優(yōu)。慣性權(quán)重因子對算法收斂性能有很大的影響，較大的值有利于跳出局部最優(yōu)，較小的值有利于算法收斂，因此Shi Y采用隨迭代進行慣性權(quán)重因子減小的方法，在算法初期增強全局搜索能力，而后期加快收斂速度。

粒子群算法還應(yīng)限制粒子最大速度以防止粒子運動發(fā)散，一般做法是當(dāng)速度超過規(guī)定最大速度時將粒子速度調(diào)整為最大速度，本文用粒子當(dāng)前速度對最大速度求余。有學(xué)者對粒子飛出變量邊界的情況采用在邊界上反彈的方式將粒子重新歸到變量區(qū)域內(nèi)。本文編制了線性減小慣性權(quán)重因子的標(biāo)準(zhǔn)粒子群算法（SPSO），并采用反彈方式約束邊界以及求余方法約束最大速度。

2.2 改進的量子粒子群算法

QPSO與標(biāo)準(zhǔn)PSO一樣也存在早熟的趨勢，Kong等人的研究表明每個粒子通過學(xué)習(xí)自身的pbest和其他粒子的pbest以及gbest進行下一步搜索，可以保持種群多樣性，提高算法性能。

本文在此基礎(chǔ)上提出進一步改進的量子粒子群算法（MQPSO）：每個粒子計算完成后立即更新pbest、gbest、mbest，并根據(jù)pbest進行排序，每個粒子僅向優(yōu)于自身pbest的粒子學(xué)習(xí)，而且排名越靠后的粒子向其他粒子學(xué)習(xí)的程度越高。由此通過提高算法對信息的利用率，加快收斂速度。

3 基于代理模型的優(yōu)化框架

3.1 Kriging代理模型與傳統(tǒng)代理模型優(yōu)化框架

實際的工程優(yōu)化問題往往需要付出巨大的計算代價，因此出現(xiàn)了二次響應(yīng)面、Kriging模型、徑向基函數(shù)模型、人工神經(jīng)網(wǎng)絡(luò)模型等近似模型預(yù)測真實解的代理模型方法。

代理模型方法可以根據(jù)已有的點預(yù)測未知點的函數(shù)值分布情況，當(dāng)代理模型達到一定精度時，可代替真實求解用于工程優(yōu)化。優(yōu)化與代理模型相結(jié)合也成為研究熱點，傳統(tǒng)的代理模型優(yōu)化框架如下：首先用一定數(shù)量的樣本點構(gòu)造代理模型，優(yōu)化找到代理模型的最優(yōu)解并與真實值對比，若不滿足收斂要求則用新計算的真實值更新代理模型，直到優(yōu)化結(jié)束。該方法嚴(yán)重依賴于代理模型預(yù)測的精度，對于復(fù)雜的高維度優(yōu)化問題極容易陷入局部最優(yōu)。只有當(dāng)代理模型的樣本點數(shù)量達到一定級別，并且合理地分布在解空間中才能獲得較高的精度，對樣本點數(shù)量的需求將隨著維數(shù)和問題復(fù)雜程度增加而急劇上升，與優(yōu)化問題一樣，代理模型方法的計算量也將變得難以接受。

3.2 基于Kriging代理模型的雙層量子粒子群優(yōu)化算法

雖然代理模型預(yù)測精度有限，但是往往能較好地反映出真實解的大體情況。為了將代理模型獲得的信息充分用于優(yōu)化，本文設(shè)計了如下基于Kriging代理模型的雙層量子粒子群優(yōu)化算法（KMQPSO），該算法由兩層MQPSO算法構(gòu)成，并以Kriging代理模型為聯(lián)系媒介。

首先在變量空間均勻產(chǎn)生具有Q個粒子的粒子池，通過真實計算獲取適應(yīng)值，然后從中選取適應(yīng)值最好的M個粒子作為父級MQPSO的初始種群，對種群中每個粒子按照MQPSO更新位置的方法繁殖X個個體（公式1中為（0，1）的隨機數(shù)，所以該X個個體位于不同的進化位置），此時用已計算的粒子構(gòu)造Kriging代理模型預(yù)測繁殖的粒子，選出適應(yīng)值最優(yōu)的粒子，計算該粒子與父級粒子種群中最近的粒子的“歐氏距離”，據(jù)此確定一個合適的閥值半徑R，以為中心R為半徑產(chǎn)生一個變量區(qū)域，在該區(qū)域中嵌入種群規(guī)模為m迭代代數(shù)為n的子級MQPSO進行優(yōu)化尋找代理模型的最優(yōu)解，將該解作為正式進化的個體進行真實的適應(yīng)值計算，完成后立即更新pbest、gbest、mbest和代理模型，直到N代父級MQPSO優(yōu)化結(jié)束。KMQPO算法流程如圖1所示。endprint

閥值半徑R由公式1確定：

（2）

其中，Dim為變量維數(shù)，為控制半徑的系數(shù)，一般可取0.5到0.8，以各粒子的子級區(qū)域能覆蓋父級的進化區(qū)域，而相互之間又不產(chǎn)生過多的重疊為宜。

KMQPSO算法中具有Q個粒子的粒子池用于獲得初始代理模型樣本點，可以通過實驗設(shè)計方法或約束由“歐氏距離”表述的相似度在解空間產(chǎn)生初始樣本點。根據(jù)適應(yīng)值排序原則選擇M個粒子的方法可獲得優(yōu)良的初始種群而且這些粒子較均勻地分布在解空間，有利于避免陷入局部最優(yōu)。粒子的繁殖策略可以為子級MQPSO篩選優(yōu)良的局部區(qū)域，嵌套的子級優(yōu)化則有助于找到代理模型的局部最優(yōu)。通過粒子的繁殖篩選和局部優(yōu)化，將要進行真實計算的粒子精準(zhǔn)地定位于代理模型的局部最優(yōu)，通過迭代更新不斷提高代理模型在最優(yōu)解附近的預(yù)測精度，從而收斂速度更快，而又能保持多樣性保證優(yōu)化精度。

3.3 KMQPSO算法參數(shù)設(shè)置

KMQPSO算法中引入了較多的設(shè)置參數(shù)，以下討論各參數(shù)對優(yōu)化搜索的影響。該算法從本質(zhì)上可以理解為對代理模型所描述的各個局部最優(yōu)點進行搜索，并且優(yōu)秀的局部得到的搜索更多。代理模型能描述多少個局部最優(yōu)和采用多大的種群規(guī)模M進行搜索需要合理地配置，當(dāng)優(yōu)化對象比較復(fù)雜時設(shè)置較大的M。粒子的繁殖數(shù)量X增加以及子級MQPSO優(yōu)化算法的種群規(guī)模m和代數(shù)n增加都會帶來多樣性的降低，合理地做法是在優(yōu)化的初期進行少量的繁殖和較低精度的子級優(yōu)化以保持多樣性，后期則增加繁殖數(shù)量提高子級優(yōu)化的精度以加快搜索。當(dāng)優(yōu)化對象相對容易時可采用更大的X、m和n來進行快速搜索。

4 仿真實驗與分析

4.1 測試函數(shù)

為了比較KMQPSO與SPSO、QPSO、MQPSO的搜索效果，選取以下6種常用基準(zhǔn)函數(shù)進行測試。

（1）Alpine二維多峰值函數(shù)。

（3）

x在（0，12）上最小值為-1.271

（2）Sphere單峰值函數(shù)。

（4）

其中n=15，x在（-10，10）上最小值為0

（3）Griewank函數(shù)。

（5）

其中n=15，x在（-50，100）上最小值為0

（4）Rastrigrin函數(shù)。

（6）

其中n=30，x在（-2.5，5）上最小值為0

（5）Rosenbrock函數(shù)。

（7）

其中n=10，x在（-5，10）上最小值為0

（6）Ackley函數(shù)。

（8）

其中n=10，x在（-5，10）上最小值為0

4.2 仿真結(jié)果與分析

SPSO慣性權(quán)重因子隨迭代進行由0.8線性減小到0.3，學(xué)習(xí)因子。量子粒子群收縮擴張系數(shù)隨迭代進行由1.0線性減小到0.5，向其他粒子學(xué)習(xí)的程度根據(jù)適應(yīng)度優(yōu)劣排名由0.2增加到0.9。KMQPSO中總共計算次數(shù)Number=初始粒子數(shù)Q+種群規(guī)模M×代數(shù)N，其它算法中Number=種群規(guī)模M×代數(shù)N。

二維Alpine函數(shù)在（0，12）區(qū)域有8個極小值8個極大值，最小的極值點坐標(biāo)為（11.0001，11.0001），大小為-1.271。用該函數(shù)對MQPSO、KMQPSO以及傳統(tǒng)代理模型優(yōu)化框架各進行100次測試，每次優(yōu)化共計算150個粒子。對MQPSO算法而言，150個粒子的計算量還不足以進行有效的搜索，所以找到全局極小值點的概率僅為9%。傳統(tǒng)代理模型優(yōu)化方法以很快的速度找到某個極小值，之后適應(yīng)值幾乎不再變化，找到全局極小值的概率為33%。KMQPSO算法找到全局最優(yōu)的概率為71%。

用SPSO、QPSO、MQPSO算法對公式4-8五種基準(zhǔn)函數(shù)各進行2000次優(yōu)化，用KMQPSO各進行50次。表1給出四種優(yōu)化算法所獲得的統(tǒng)計平均適應(yīng)值。統(tǒng)計結(jié)果表明QPSO對多數(shù)函數(shù)的優(yōu)化性能要優(yōu)于SPSO，MQPSO則有進一步的提高。KMQPSO算法表現(xiàn)出了更為優(yōu)秀的性能，在收斂到相同精度的前提下，對Sphere、Griewank、Rastrigrin函數(shù)優(yōu)化的計算次數(shù)還不到其它算法的7%，對Rosenbrock和Ackley函數(shù)也分別降低到27%和60%。

為了比較不同計算次數(shù)對搜索精度的影響，統(tǒng)計四種算法優(yōu)化10維Rosenbrock多峰值函數(shù)采用不同算次數(shù)所獲得的平均適應(yīng)值，粒子群基本設(shè)置.

4.3 翼型優(yōu)化算例

翼型對飛行器的氣動性能具有重要的影響，采用高精度的數(shù)值計算方法進行翼型優(yōu)化已經(jīng)成為研究熱點。本文采用10個設(shè)計變量的Hicks-Henne函數(shù)參數(shù)化翼型，采用k-ω雷諾平均N-S方程求解繞翼型流場，在筆者的雙核PC機上每個翼型數(shù)值計算需要244秒，以RAE2822為初始翼型，保持翼型最大相對厚度不變，設(shè)計狀態(tài)為巡航馬赫數(shù)0.73，雷諾數(shù)2.1E7，設(shè)計升力系數(shù)Cl=0.70，采用適應(yīng)值加權(quán)組合方法以降低阻力系數(shù)Cd和力矩系數(shù)Cm的絕對值為優(yōu)化目標(biāo)。KMQPSO算法作180次數(shù)值計算的優(yōu)化結(jié)果要優(yōu)于MQPSO作210與540次計算的優(yōu)化結(jié)果，設(shè)計翼型與初始翼型壓力分布對比，設(shè)計翼型具有理想的無激波的壓力分布，說明本文算法是有效的。在整個優(yōu)化過程中KMQPSO算法大約用了5分鐘時間來構(gòu)造代理模型和子級量子粒子群優(yōu)化，在優(yōu)化精度相同的情況下，總的優(yōu)化耗時只有MQPSO算法的1/3。

5 結(jié)論

本文提出基于代理模型的雙層粒子群算法KMQPSO，在父級改進的量子粒子群MQPSO中引入繁殖篩選與嵌入子級MQPSO策略，對子代粒子進行基于Kriging代理模型的精準(zhǔn)更新，從而實現(xiàn)快速有效的搜索。對多種基準(zhǔn)函數(shù)仿真測試表明，該算法避免了傳統(tǒng)的代理模型優(yōu)化方法易陷入局部最優(yōu)的缺點，與SPSO、QPSO和MQPSO等相比可大幅度降低優(yōu)化的計算次數(shù)。翼型優(yōu)化算例表明KMQPSO可大大提高優(yōu)化算法的工程實用性。endprint

參考文獻：

[1]Kennedy J， Eberhart R C. Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks Perth， WA， Australia，1995：1942-1948.

[2]蘇守寶，汪繼文，方杰.粒子群優(yōu)化技術(shù)的研究與應(yīng)用進展[J]. 計算機技術(shù)與發(fā)展，2007，17（05）：249-253.

[3]呂振肅，侯志榮.自適應(yīng)變異的粒子群優(yōu)化算法[J].電子學(xué)報， 2004，32（03）：416-420.

[4]李莉，李洪奇，謝紹龍等.基于克隆選擇的免疫粒子群優(yōu)化算法[J].計算機科學(xué)，2008，35（10）：253-255.

[5]叢琳，沙宇恒，焦李成. 組織進化粒子群數(shù)值優(yōu)化算法[J].模式識別與人工智能，2007，20（02）：145-153.

[6]Van den Bergh，F(xiàn).Engelbrecht A P. Effects of swarm size on cooperative particle swarm optimisers[C].In Proceedingd of

（下轉(zhuǎn)第276頁）

（上接第231頁）

the Genetic and Evolutionary Computiaion Coonference，San Francisco，USA，2001.

[7]虞斌能，連志剛，焦斌.動態(tài)慣性權(quán)重粒子群優(yōu)化算法[J].上海機電學(xué)院學(xué)報，2008，11（03）：169-172.

[8]Angeline P J.Using seleetion to improve partiele swarm optimization[C].In Proceedings of the IEEE InternationalConference on Evolutionary Computation，1998， 84-89.

[9]王曉鵬，高正紅.跨音速翼型和機翼的氣動優(yōu)化設(shè)計[J].應(yīng)用力學(xué)學(xué)報，2001，11（02）：90-93.

[10]夏露，高正紅.一種單親DNA 算法在翼型設(shè)計中的應(yīng)用[J].空氣動力學(xué)學(xué)報，2009，27（03）：335-339.endprint