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

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

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

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

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

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

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

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

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

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

2.2 改進(jìn)的量子粒子群算法

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

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

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

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

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

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

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

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

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

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

（2）

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

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

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

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

4 仿真實(shí)驗(yàn)與分析

4.1 測(cè)試函數(shù)

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

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)：

[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ìn)展[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2007，17（05）：249-253.

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

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

[5]叢琳，沙宇恒，焦李成. 組織進(jìn)化粒子群數(shù)值優(yōu)化算法[J].模式識(shí)別與人工智能，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頁(yè)）

（上接第231頁(yè)）

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

[7]虞斌能，連志剛，焦斌.動(dòng)態(tài)慣性權(quán)重粒子群優(yōu)化算法[J].上海機(jī)電學(xué)院學(xué)報(bào)，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]王曉鵬，高正紅.跨音速翼型和機(jī)翼的氣動(dòng)優(yōu)化設(shè)計(jì)[J].應(yīng)用力學(xué)學(xué)報(bào)，2001，11（02）：90-93.

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