甘 地

（中南大學(xué)機(jī)電工程學(xué)院，湖南 長沙 410000）

粒子群算法[1]是模擬群體智能所建立起來的一種算法，最早在1995 年由美國的Eberhart 和Kennedy 兩人提出。由于它運(yùn)行邏輯簡單、需要調(diào)試的參數(shù)少、容易實現(xiàn)，因此受到大量學(xué)者的研究與應(yīng)用。如今，在NP 問題求解、圖像處理[2]、人工神經(jīng)網(wǎng)絡(luò)建模[3]和車輛路徑優(yōu)化[4]等領(lǐng)域時常可以見到對粒子群算法的使用。然而粒子群優(yōu)化算法也存有一些缺點，如，易陷入局部最優(yōu)解，運(yùn)行末期收斂速度減緩、收斂精度低等。為改善這些缺陷，學(xué)者們進(jìn)行了大量的研究。文獻(xiàn)[5]將研究重心放置在粒子群算法的慣性權(quán)重上，提出一種按正弦變化慣性權(quán)重的粒子群優(yōu)化算法。文獻(xiàn)[6]提出對慣性權(quán)重的自適應(yīng)變化方案，即自適應(yīng)權(quán)重的粒子群算法。文獻(xiàn)[7]在研究了細(xì)菌覓食算法（BFO）的特點后，將BFO 算法中的趨化和遷徙算子引入粒子群算法，提出了PSO-BFO 混合算法。文獻(xiàn)[8]將模擬退火的思想融入粒子群算法中，提出了基于模擬退火的粒子群算法。上述文獻(xiàn)通過改善權(quán)重系數(shù)，或?qū)⒘Ｗ尤核惴ㄅc其他算法相結(jié)合，或多或少地對算法性能進(jìn)行了加強(qiáng)。

本文在分析了粒子群算法的優(yōu)缺點，以及模擬退火算法的運(yùn)算原理后，將模擬退火的思想引入粒子群算法中，提出基于模擬退火的粒子群算法?；趹T性權(quán)重對算法運(yùn)行效果的重要作用，提出一種正弦自適應(yīng)變化的慣性權(quán)重。該算法結(jié)合了粒子群優(yōu)化算法的全局搜索能力模擬退火算法的一定概率跳出局部最優(yōu)解的優(yōu)點以及正弦自適應(yīng)變化的慣性權(quán)重，改善了粒子群算法易陷入局部最優(yōu)解的問題，增強(qiáng)了運(yùn)算末期的收斂速度和收斂精度。

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

Eberhart 博士和Kennedy 博士基于對鳥群覓食行為的學(xué)習(xí)和模擬，創(chuàng)建了粒子群優(yōu)化算法。該算法的核心思想是在問題求解空間中，通過個體間信息互相流通，使得群體的運(yùn)動逐漸從無序演化為有序，從而求解出最優(yōu)值。在運(yùn)算前，粒子群算法會初始化若干個粒子，每個粒子都代表目標(biāo)函數(shù)的一個解，具有位置向量和速度向量。將粒子的位置向量帶入目標(biāo)函數(shù)，求得的值被稱為粒子的適應(yīng)度值。在每次迭代中，群體中粒子位置的更新會受到自身歷史最優(yōu)解和群體當(dāng)前最優(yōu)解的影響，有朝向這兩個最優(yōu)解移動的趨勢，從而確定粒子在下一次迭代時的位置和速度如何改變，并更新自身歷史最優(yōu)解以及群體當(dāng)前最優(yōu)解。最終通過不斷地迭代，尋得目標(biāo)函數(shù)的最優(yōu)值。

假設(shè)在一個D 維空間中有N 個粒子，粒子i 在t 時刻的位置為xi（t）=[xi1（t），xi2（t），...xiD（t）]，飛行速度為vi（t）=[vi1（t），vi2（t），...viD（t）]。將粒子i 的位置xi帶入目標(biāo)函數(shù)得到適應(yīng)度值，對比該粒子歷史最佳適應(yīng)度值，得到該粒子從迭代運(yùn)算以來的歷史最優(yōu)解，記為pi=（pi1，pi2，…piD）。比較空間中所有粒子的個體最優(yōu)解，取最小的那個粒子的位置作為整個粒子群迄今為止的群體最優(yōu)解，記為pg=（pg1，pg2，...pgD）。粒子群算法對粒子速度和位置的更新采用以下公式：

式中：i=1，2，3...N；d=1，2，3...D；ω 為慣性權(quán)重因子；C1和C2為學(xué)習(xí)因子，也稱加速因子，一般取負(fù)數(shù)；r1和r2為兩個介于[0，1]的隨機(jī)數(shù)；

上式中，公式1 為速度更新公式，公式2 為位置更新公式。其中速度更新公式分為3 個部分，第1 部分是慣性部分，粒子受慣性影響，會向著粒子上一時刻的速度方向移動；第2 部分是自我認(rèn)知部分，由于受到自身歷史最優(yōu)位置的影響，粒子有回到該位置的傾向；第3 部分是社會認(rèn)知部分，粒子處在種群中，受到當(dāng)前最優(yōu)粒子的吸引，有去到當(dāng)前最優(yōu)粒子位置的趨勢。種群中的粒子通過公式1 和2 進(jìn)行更新，經(jīng)過多次迭代，逐漸向全局最優(yōu)解靠近，最終在粒子空間中搜索到函數(shù)最優(yōu)解。

2 模擬退火算法

1953 年，N.Metropolis 等人提出模擬退火算法，隨后S.Kirkpatrick 等人在1983 年首次將其引入組合優(yōu)化問題的求解之中。由于一般組合優(yōu)化問題類似于物理中固體的退火過程，從而以此為出發(fā)點引出該算法。算法起初給定一個較高的溫度T0，隨機(jī)生成一個初始解，然后采用Monte-Carlo 迭代求解策略不斷產(chǎn)生新解，利用Metropolis 準(zhǔn)則有一定概率接收較差的解的方法，判斷是否用產(chǎn)生的新解代替上一代的舊解，并在迭代過程中不斷降低退火溫度，最終得到問題的最優(yōu)解。Metropolis 準(zhǔn)則定義了在某個溫度T 下物體從狀態(tài)i 轉(zhuǎn)移到狀態(tài)j 的能量概率：

式中：Ei和Ej分別為固體在狀態(tài)i 和j 下的內(nèi)能；K 為玻爾茲曼常數(shù)。

全局搜索算法一般都會有陷入局部最優(yōu)解的問題的存在，而模擬退火算法采用Metropolis 準(zhǔn)則，使得算法在搜索運(yùn)行過程中有接收較差解可能性，從而有利于算法跳出局部最優(yōu)解，克服該問題。然而，模擬退火算法收斂速度慢、參數(shù)調(diào)整困難等缺點，使其應(yīng)用并不普遍。

3 基于模擬退火的粒子群算法

3.1 正弦自適應(yīng)權(quán)重

慣性權(quán)重是粒子群算法中需要調(diào)節(jié)的重要參數(shù)。慣性權(quán)重值越大，粒子在更新過程中的搜索步長越大，全局搜索能力越強(qiáng)；反之，粒子的局部搜索能力越強(qiáng)。因此為提高粒子的搜索能力，使用正弦自適應(yīng)權(quán)重的策略如下：

式中，wmax和wmin為慣性權(quán)重的最大值與最小值；f 為粒子的當(dāng)前適應(yīng)度值；favg為當(dāng)前全部粒子的平均適應(yīng)度值；fmin為當(dāng)前全部粒子適應(yīng)度值的最小值。

正弦變化的慣性權(quán)重[5]讓算法在運(yùn)算初期能夠有較小的權(quán)重值，粒子具有較強(qiáng)的局部搜索能力，使得粒子獲得個體最優(yōu)解。在算法運(yùn)行的中期，隨著正弦函數(shù)的變化特性，權(quán)重值慢慢變大，粒子開始進(jìn)行全局最優(yōu)解的搜索。而在算法運(yùn)行的后期，慣性權(quán)重又慢慢變小，粒子進(jìn)行細(xì)致的局部搜索，尋找該區(qū)域的最優(yōu)解，及全局最優(yōu)解。自適應(yīng)變化是指在每一次迭代過程中，以每個粒子的適應(yīng)度值和所有粒子的平均適應(yīng)度值的大小做判斷，決定該粒子的權(quán)重該如何變化的方式。引入正弦自適應(yīng)權(quán)重策略，有利于粒子在局部和全局空間中動態(tài)的搜索。

3.2 算法流程

由于粒子群算法存在易陷入局部最優(yōu)解的問題，而模擬退火算法具有一定概率接收較差解的特性，因此將其與粒子群算法進(jìn)行融合，提出基于正弦自適應(yīng)權(quán)重的模擬退火粒子群算法，該算法融合方式有利于改善粒子群算法的全局搜索能力。采用正弦自適應(yīng)權(quán)重策略，提高收斂速度和精度。該算法基本流程如下：

（1）設(shè)置種群大小N、粒子維度D，初始化粒子的速度和位置；

（2）計算每個粒子的適應(yīng)度值fitness（xt），并將每個粒子的個體最優(yōu)解存儲在pi中，所有粒子中的全局最優(yōu)解存儲在pg中；

（3）設(shè)置初始溫度T0=pg/ln5；

（4）根據(jù)式（4）對慣性權(quán)重進(jìn)行更新；

（5）依據(jù)公式1 和2 對粒子進(jìn)行更新，并計算適應(yīng)度值fitness（xt+1）；

（6）采用模擬退火算法的Metropolis 機(jī)制，若fitness（xt+1）fitness（pi），但exp（（fitness（pi）-fitness（xt+1））/Tt）>random，其中random 為0～1 之間的隨機(jī)數(shù)，則也接受xt+1作為粒子新的個體最優(yōu)解pi。同理更新生成種群的全局最優(yōu)解pg；

（7）進(jìn)行退溫操作Tt+1=0.9*Tt；

（8）判斷是否滿足終止條件，如果滿足則輸出pg；否則，轉(zhuǎn)到第4 步。

4 仿真實驗

為驗證上述基于正弦自適應(yīng)權(quán)重的模擬退火粒子群算法（SASAPSO）的性能，采用文獻(xiàn)[1]的4 個基準(zhǔn)函數(shù)對其進(jìn)行測試，并與標(biāo)準(zhǔn)粒子群算法（PSO）、一種改進(jìn)的粒子群算法[9]（SAPSO）和基于自適應(yīng)權(quán)重的粒子群算法[6]（AWPSO）進(jìn)行仿真實驗比較。分別利用這4 種算法對每個基準(zhǔn)函數(shù)進(jìn)行50 次最優(yōu)值求解，通過實驗仿真得到4 種算法下各個基準(zhǔn)函數(shù)的平均適應(yīng)度值與迭代次數(shù)的關(guān)系。

4 個基準(zhǔn)函數(shù)如下。

其仿真結(jié)果如圖1、圖2、圖3、圖4 所示。

圖1 Griewank 函數(shù)的迭代曲線

圖2 Rastringin 函數(shù)的迭代曲線

圖3 Sphere 函數(shù)的迭代曲線

圖4 Schaffer 函數(shù)的迭代曲線

由圖示可以看出，在Griewank 函數(shù)的迭代曲線中，SASAPSO 算法收斂到最優(yōu)值的迭代次數(shù)為20 次，收斂的迭代次數(shù)略大于AW-PSO 算法，但SASAPSO 算法的收斂精度是4 個算法中最高的；在Rastringin 函數(shù)的迭代曲線中，SASAPSO 算法收斂到最優(yōu)值的迭代次數(shù)為100次，是4 個算法中最少的，并且收斂精度最高；在Sphere函數(shù)的迭代曲線中，4 個算法的收斂精度相當(dāng)，但SASAPSO 算法收斂到最優(yōu)值的迭代次數(shù)為18 次，是4 個算法中最少的；在Schaffer 函數(shù)的迭代曲線中，AW-PSO 算法和SASAPSO 算法收斂到最優(yōu)值的迭代次數(shù)同為200次，但SASAPSO 算法的收斂精度明顯高于AW-PSO 算法。因此，綜合4 個算法在4 個測試函數(shù)下的仿真結(jié)果，SASAPSO 算法的收斂速度和收斂精度是4 個算法中最高的。

5 結(jié)論

本文提出的基于模擬退火的粒子群算法（SASAPSO），以粒子群算法為主體框架，為改善粒子群算法易陷入局部最優(yōu)解的問題，引入模擬退火機(jī)制，增強(qiáng)了粒子群算法的全局搜索能力。采用正弦自適應(yīng)慣性權(quán)重的策略，有效地提高了算法的收斂速度和收斂精度。在4 種基準(zhǔn)函數(shù)的仿真測試下，與他人提出的3 種算法進(jìn)行對比。仿真結(jié)果表明，SASAPSO 算法的收斂速度和收斂精度更高。