基于模擬退火的改進粒子群算法研究及應用

薛永生，吳立堯

（1.海軍裝備部飛機辦公室，北京100000；2.海軍航空大學，山東煙臺264001）

文獻[9]研究了基于模擬退火混沌粒子群優(yōu)化的盲檢測算法，改進的算法在全局收斂性上有較好的改善。文獻[10]根據(jù)層次分析法的特點引入了特征粒子來求解判斷矩陣排序權重，提出了模擬退火改進粒子群優(yōu)化算法。文獻[11]提出了混沌模擬退火粒子群優(yōu)化算法，并將其應用于Job Shop調度問題。文獻[12]將粒子群算法與模擬退火算法相結合，應用于圖像分割問題。文獻[13]將GPSO與SA算法相結合形成新的混合算法，前期用GPSO，在GPSO陷入停滯時利用SA算法跳出局部最優(yōu)尋找全局最優(yōu)。文獻[14]利用SAPSO算法規(guī)劃無人機三維航跡，改善航跡效果明顯。在PID參數(shù)整定方面，文獻[15]提出了一種改進的粒子群優(yōu)化分數(shù)階PID參數(shù)整定方法，并應用在隨動電氣伺服控制系統(tǒng)中。文獻[16]提出了一種蝙蝠算法整定PID控制參數(shù)，較優(yōu)的系統(tǒng)性能和運算效率。文獻[17]提出了一種基于免疫選擇粒子群算法，并應用在PID控制器參數(shù)整定與自適應中。文獻[18]針對工業(yè)過程中PID參數(shù)整定難問題，提出了基于個性化慣性權重的粒子群算法，優(yōu)化效果明顯。

本文從2個方面對PSO算法進行了改進：一方面從對PSO控制參數(shù)進行改進，增加了收縮因子；另一方面，將模擬退火算法與粒子群算法有機結合，該改進算法增強了局部搜索能力，通過仿真模擬對比，證明了混合算法的有效性。利用新混合算法整定PID控制參數(shù)，并與標準PSO和Z-N法相比較，優(yōu)化后的系統(tǒng)性能指標變優(yōu)。

1 算法分析

1.1 帶收縮因子的粒子群算法（CPSO）分析

PSO中粒子的飛行行為類似于鳥類運動，從而使整個粒子群的運動表現(xiàn)出與鳥類覓食類似的特性，進而求解復雜的優(yōu)化問題，即通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解。粒子群優(yōu)化算法中的粒子速度和位置更新依賴2點：第一，粒子的個體歷史最優(yōu)值；第二，粒子群中的群體當前最優(yōu)值。在D維空間中粒子i的速度和位置更新公式為：

式（1）中：vi.j(t)為粒子的當前速度；xi.j(t)為粒子的當前位置；c1和c2為學習因子；r1和r2為[0，1]之間均勻分布的隨機數(shù)；pi.j為粒子到目前為止的最優(yōu)位置；pg.j為所有粒子到目前為止的最優(yōu)位置。

學習因子c1和c2決定了粒子本身經(jīng)驗信息和其他威力的經(jīng)驗信息對粒子運行軌跡的影響。設置較大c1時，會使粒子過多地在局部范圍內徘徊；而設置較大c2值，則會促使粒子過早收斂到局部最小值。通過引入收縮因子，選取合適參數(shù)，可確保PSO算法的收斂性，并可取消對速度的邊界限制。速度公式為：

式（2）中，φ為收縮因子，且，C=c1+c2。

1.2 模擬退火算法分析

模擬退火算法（SA）是基于Monte-Carlo迭代求解策略的一種隨機尋優(yōu)算法，即通過在搜索區(qū)間隨機游走，再利用Metropolis抽樣準則使隨機游走逐漸收斂于局部最優(yōu)解。Metropolis準則定義了某一溫度下系統(tǒng)從狀態(tài)i變化到狀態(tài)j的能量概率為：

在圖3（c）中，將重心d0（電勢待定為v0）作為代理點，用Wi表示子區(qū)域d0didi+1的能量（通過v0表示）。通過使得局部能量最小化，可求解下面的等式得到v0。

式（3）中：Ei和Ej為固體在狀態(tài)i和狀態(tài)j下的能量；K為波爾茲曼常數(shù)。

模擬退火算法可以以一種概率接受“變差的”解，這種行為看似不合理，實則在一定程度上提高了算法的靈活性，擴大了算法的搜索范圍，增加了粒子的多樣性。這種模擬退火的策略使算法避免在迭代搜索過程中因陷入局部最優(yōu)解的弊端，提高了搜索到全局最優(yōu)解的可能性和可靠性。但主要的不足是收斂速度太慢，尤其是問題的規(guī)模增大時，算法的效率更是低的令人無法忍受。如此一來，求解問題的近似最優(yōu)解，需要花費較長時間，如此低的效率致使算法可行性降低，工程價值喪失，因而算法的應用并不廣泛。

2 基于模擬退火的改進粒子群算法

為獲得更高精度解和更快的收斂速度，基于上述算法得到新的混合算法。新的混合算法在CPSO進化陷入停滯狀態(tài)時，利用SA算法跳出局部陷阱繼續(xù)搜索更好的解。SACPSO混合算法基本流程如下。

Step 1：對粒子的位置和速度初始化。確定粒子種群大小N和維數(shù)D，設置當前迭代次數(shù)和最大迭代次數(shù)M。

Step 2：計算每個粒子的適應度，并將當前各個粒子的適應度賦值給pi中，將所有粒子的最優(yōu)適應度值存儲于pg中。

Step 3：判斷全局最優(yōu)值是否停滯或到達指定迭代次數(shù)，如果滿足轉到Step 6。

Step 4：進行下一次迭代計算，若達到最大迭代次數(shù)轉到Step 6。

Step 5：據(jù)輪盤賭策略，從各個粒子中確定全局最優(yōu)的某個替代值p′g，而后根據(jù)下式更新各個粒子的速度與位置。

Step 6：設置初始溫度和結束溫度。

Step 7：在當前溫度下，計算各個粒子的適應度值，根據(jù)Metropolis準則更新解。

Step 8：根據(jù)是否滿足停止條件（停止條件一般為預先設定的運算精度或者程序迭代次數(shù)），判斷是否搜索停止，不滿足則轉到Step 7。

Step 9：降溫，返回Step 7直到得到最優(yōu)解或達到最低溫度。

3 仿真實驗及分析

3.1 測試函數(shù)

為了證明基于模擬退火的粒子群優(yōu)化算法的可用性和性能優(yōu)越性，以及具有較好解決實際問題能力，本文特選出一些經(jīng)典的標準測試函數(shù)進行驗證。

1）Ackley函數(shù)

2）Schaffer函數(shù)

3）Griewank函數(shù)

4）Rastrigrin函數(shù)

3.2 優(yōu)化曲線

優(yōu)化曲線是使用優(yōu)化算法獲得函數(shù)極值的過程描述，下面是利用模擬退火粒子群算法對標準測試函數(shù)進行優(yōu)化的過程，并與傳統(tǒng)粒子群算法進行了對比。仿真參數(shù)為：N=40，M=200，c1=c2=2.05，λ=0.5。從圖1～4結果對比圖可知，SACPSO算法隨著進化過程的進行，溫度逐漸下降，接受差解的概率逐漸減小，從而提高了收斂性能。該算法不僅基本保持了粒子群優(yōu)化算法的簡單、容易實現(xiàn)的特點，而且增強了粒子群優(yōu)化算法的全局尋優(yōu)能力，加快了算法的進化速度，提高了收斂精度。仿真結果表明，該算法的性能明顯優(yōu)于傳統(tǒng)粒子群優(yōu)化算法。

圖1 Ackley函數(shù)適應度曲線對比圖Fig.1 Ackley fitness function curve comparison

圖2 Schaffer函數(shù)適應度曲線對比圖Fig.2 Schaffer fitness function curve comparison

圖3 Griewank函數(shù)適應度曲線對比圖Fig.3 Griewank fitness function curve comparison

圖4 Rastrigrin函數(shù)適應度曲線對比圖Fig.4 Rastrigrin fitness function curve comparison

4 算法應用

本文針對二階時滯系統(tǒng)對象，分別利用本文提出SACPSO混合算法、PSO優(yōu)化算法和Z-N法對PID控制器參數(shù)進行整定。選取被控對象的傳遞函數(shù)為：

圖5為改進優(yōu)化算法與傳統(tǒng)PID參數(shù)整定方法對系統(tǒng)階躍響應輸出對比曲線圖。其中，3種方法的超調量分別為0.18%、9.63%和24.99%。由圖5可以看出SACPSO算法優(yōu)化后的系統(tǒng)性能指標最好，標準PSO算法優(yōu)化后的系統(tǒng)性能指標次之，而Z-N法相對較差。綜合上述可得，SACPSO算法用于PID參數(shù)整定，不僅系統(tǒng)穩(wěn)定，而且收斂性能好。

圖5 3種算法階躍響應輸出曲線對比圖Fig.5 Step response output curve comparison

5 小結

本文對改進粒子群算法的原理、步驟以及測試函數(shù)進行了分析和仿真，并將改進算法應用在二階時滯控制系統(tǒng)PID參數(shù)整定問題。本文算法利用模擬退火算法的優(yōu)勢以一定的概率改變粒子的位置更新，使優(yōu)化進入搜索空間的其他區(qū)域進行搜索，這樣可以有效地提高粒子群算法跳出局部最優(yōu)解的能力，從而搜索到函數(shù)的全局最優(yōu)解。仿真分析驗證了SACPSO算法的有效性和優(yōu)越性，用于PID參數(shù)整定問題得到很好的效果，優(yōu)化后的系統(tǒng)性能指標明顯優(yōu)于傳統(tǒng)參數(shù)整定方法。SACPSO算法結構簡單、收斂速度快、收斂性能好等優(yōu)點可用于工程優(yōu)化問題。

[1]KENNEDY J，EBERHART R C.Particle swarm optimization[C]//Proceedings of the 1995 IEEE International Conference on Neural Networks.Peth，Australia，IEEE，1995.

[2]KARAKUZU C.Parameter tuning of fuzzy sliding mode controller using particle swarm optimization[J].International Journal of Innovative Computing，Information and Control，2010，6（10）：4755-4770.

[3]ZHANG LEI，GAO SHANG.An image segmentation method based on elite-improved particle swarm optimization[J].Computer applications and Software，2009，26（12）：89-92.

[4]余偉龍，吳慶憲，姜長生.粒子群法在三維航跡規(guī)劃及優(yōu)化中的應用[J].電光與控制，2008，15（5）：1-6.YU WEILONG，WU QINGXIAN，JIANG CHANGSHENG.Application of particle swarm algorithm in 3D route planning and optimization of air vehicles[J].Electronics Optics and Control，2008，15（5）：1-6.（in Chinese）

[5]陳冬，周德云，馮琦，等.基于粒子群優(yōu)化算法的無人機航跡規(guī)劃[J].彈箭與制導學報，2007，27（4）：340-342.CHEN DONG，ZHOU DEYUN，F(xiàn)ENG QI，et al.Route planning for unmanned vehicles based on particle swarm optimization[J].Journal of Projectiles，Rockets，Missiles and Guidance，2007，27（4）：340-342.（in Chinese）

[6]METROPOLIS N，ROSENBLUTH A，ROSENBLUTH M，et al.Equation of state calculations by fast computing machines[J].Journal of Chemical Physics，1953，21（6）：1087-1092.

[7]吳坤鴻，詹世賢.分布式遺傳模擬退火算法的火力打擊目標分配優(yōu)化[J].火力與指揮控制，2016，41（3）：89-92.WU KUNHONG，ZHAN SHIXIAN.Optimization for target assignment in fire strike based on distributed genetic simulated annealing algorithm[J].Fire Control and Command Control，2016，41（3）：89-92.（in Chinese）

[8]何慶，吳意樂，徐同偉.改進遺傳模擬退火算法在TSP優(yōu)化中的應用[J].控制與決策，2018，33（2）：219-225.HE QING，WU YILE，XU TONGWEI.Application of improved genetic simulated annealing algorithm in TSP optimization[J].Control and Decision，2018，33（2）：219-225.（in Chinese）

[9]王京，于舒娟.模擬退火粒子群算法的盲檢測[J].計算機技術與發(fā)展，2011，21（1）：35-37.WANG JING，YU SHUJUAN.Blind detection based on simulated annealing chaotic particle swarm optimization[J].Computer Technology and Development，2011，21（1）：35-37.（in Chinese）

[10]胡建悅，嚴洪森，劉楠楠.基于模擬退火粒子群算法的AHP排序權值計算[J].計算機技術與發(fā)展，2012，22（6）：14-18.HU JIANYUE，YAN HONGSEN，LIU NANNAN.Computing rank weights in AHP of simulated annealing-particle swarm optimization algorithm[J].Computer Technology and Development，2012，22（6）：14-18.（in Chinese）

[11]張捍東，廖天紅，岑豫皖.用模擬退火思想的粒子群算法實現(xiàn)圖像分割[J].計算機技術與發(fā)展，2010，20（5）：83-87.ZHANG HANDONG，LIAO TIANHONG，CEN YUWAN.Image segmentation through particle swarm optimization based on simulated annealing[J].Computer Technology and Development，2010，20（5）：83-87.（in Chinese）

[12]劉愛軍，楊育，李斐，等.混沌模擬退火粒子群優(yōu)化算法研究及應用[J].浙江大學學報，2013，47（10）：1722-1730.LIU AIJUN，YANG YU，LI FEI，et al.Chaotic simulated annealing particle swarm optimization algorithm research and its application[J].Journal of Zhejiang University，2013，47（10）：1722-1730.（in Chinese）

[13]鄭申海，胡小兵，鄭滿滿，等.改進粒子群和模擬退火混合算法及其應用[J].計算機技術與發(fā)展，2013，23（7）：26-30.ZHENG SHENHAI，HU XIAOBING，ZHENG MANMAN，et al.An improved hybrid algorithm based on particle swarm optimization and simulated annealing and its application[J].Computer Technology and Development，2013，23（7）：26-30.（in Chinese）

[14]唐匯禹，彭世蕤，孫經(jīng)蛟，等.基于SAPSO算法的無人機三維航跡規(guī)劃[J].戰(zhàn)術導彈技術，2017（2）：62-68.TANG HUIYU，PENG SHIRUI，SUN JINGJIAO，et al.3-D route planning of UAV based on SAPSO algorithm[J].Tactical Missile Technology，2017（2）：62-68.（in Chinese）

[15]高嵩，王磊，陳超波，等.一種改進粒子群優(yōu)化的分數(shù)階PID參數(shù)整定[J].控制工程，2017，24（10）：2010-2015.GAO SONG，WANG LEI，CHEN CHAOBO，et al.An improved particle swarm optimization algorithm for fractional order PID parameter tuning[J].Control Engineering of China，2017，24（10）：2010-2015.（in Chinese）

[16]呂磊，章國寶，黃永明.基于蝙蝠算法的PID參數(shù)整定[J].控制工程，2017，24（3）：548-553.LV LEI，ZHANG GUOBAO，HUANG YONMING.BA-based PID tuning method[J].Control Engineering of China，2017，24（3）：548-553.（in Chinese）

[17]鄧麗，蔣婧，費敏銳.基于免疫粒子群算法的PID參數(shù)整定與自適應[J].自動化儀表，2013，34（2）：65-67.DENG LI，JIANG JING，F(xiàn)EI MINRUI.PID parameters tuning and adaptation based on immunity particle swarm optimization[J].Process Automation Instrumentation，2013，34（2）：65-67.（in Chinese）

[18]楊智，陳穎.改進粒子群算法及其在PID整定中的應用[J].控制工程，2016，23（2）：161-166.YANG ZHI，CHEN YING.Improved particle swarm optimization and its application in PID tuning[J].Control Engineering of China，2016，23（2）：161-166.（in Chinese）