基于代理模型的雙層粒子群優化算法

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

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

關鍵詞：粒子群優化算法；量子行為；Kriging代理模型；繁殖；多樣性

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

1 引言

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

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

2 標準粒子群與量子粒子群算法

2.1 標準粒子群算法

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

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

粒子群算法還應限制粒子最大速度以防止粒子運動發散，一般做法是當速度超過規定最大速度時將粒子速度調整為最大速度，本文用粒子當前速度對最大速度求余。有學者對粒子飛出變量邊界的情況采用在邊界上反彈的方式將粒子重新歸到變量區域內。本文編制了線性減小慣性權重因子的標準粒子群算法（SPSO），并采用反彈方式約束邊界以及求余方法約束最大速度。

2.2 改進的量子粒子群算法

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

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

3 基于代理模型的優化框架

3.1 Kriging代理模型與傳統代理模型優化框架

實際的工程優化問題往往需要付出巨大的計算代價，因此出現了二次響應面、Kriging模型、徑向基函數模型、人工神經網絡模型等近似模型預測真實解的代理模型方法。

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

3.2 基于Kriging代理模型的雙層量子粒子群優化算法

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

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

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

（2）

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

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

3.3 KMQPSO算法參數設置

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

4 仿真實驗與分析

4.1 測試函數

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

（1）Alpine二維多峰值函數。

（3）

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

（2）Sphere單峰值函數。

（4）

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

（3）Griewank函數。

（5）

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

（4）Rastrigrin函數。

（6）

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

（5）Rosenbrock函數。

（7）

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

（6）Ackley函數。

（8）

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

4.2 仿真結果與分析

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

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

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

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

4.3 翼型優化算例

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

5 結論

本文提出基于代理模型的雙層粒子群算法KMQPSO，在父級改進的量子粒子群MQPSO中引入繁殖篩選與嵌入子級MQPSO策略，對子代粒子進行基于Kriging代理模型的精準更新，從而實現快速有效的搜索。對多種基準函數仿真測試表明，該算法避免了傳統的代理模型優化方法易陷入局部最優的缺點，與SPSO、QPSO和MQPSO等相比可大幅度降低優化的計算次數。翼型優化算例表明KMQPSO可大大提高優化算法的工程實用性。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]蘇守寶，汪繼文，方杰.粒子群優化技術的研究與應用進展[J]. 計算機技術與發展，2007，17（05）：249-253.

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

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

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

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

（下轉第276頁）

（上接第231頁）

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

[7]虞斌能，連志剛，焦斌.動態慣性權重粒子群優化算法[J].上海機電學院學報，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].應用力學學報，2001，11（02）：90-93.

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