模擬退火—免疫粒子群融合算法研究

范偉倫，衛鑫，熊威

（中國人民解放軍91550部隊，遼寧 大連 116023）

1 前言

當前，遺傳（GA）算法、模擬退火（SA）算法、人工免疫（AIA）算法、蟻群（ACA）算法、粒子群（PSO）算法等智能優化算法越來越廣泛地應用于軍事領域和民用領域。而隨著人們的不斷研究探索，傳統的智能優化算法在都顯現出了一定的局限和不足。國內外學者對此進行了大量改進和創新，主要有以下兩個改進方向：一是從算法自身的特性進行研究，對參數設置、算法流程進行改進，提高算法性能；二是基于算法融合的思想，通過對不同算法之間優缺點的分析比較，取長補短，產生新的融合算法來提升算法性能。

2 算法簡介

2.1 粒子群算法

粒子群（Particle Swarm Optimization，PSO）算法最初是由Kennedy和Eberhart兩位學者，通過觀察現實中鳥群尋找食物的行為，經過抽象、總結進而模擬出的一種智能優化算法。該算法與基于進化思想的GA算法不同，PSO算法主要通過群體內個體之間的信息共享來完成尋優。PSO算法原理簡單，易于實現。但同時，PSO算法也存在著后期收斂速度減緩甚至停滯，且容易存在“過早熟”的缺陷。PSO算法中，先在解空間中初始化一群固定數量的粒子，每個粒子隨機出現在空間中的任意位置，并帶有隨機的初始速度和運動方向，同時設定一個適應度函數來評判每個粒子當前位置的優劣，得到每個粒子的適應度值（Fitness Value），之后所有粒子都追隨當前位置最好的粒子，在其周圍搜尋。PSO算法深入來講可以看作社會模型的簡化，個體之間協作競爭，通過信息共享機制不斷提高自身認知水平和社會認知水平，進而搜索到全局最優解。

2.2 人工免疫算法

生物免疫系統（Biological Immune System，BIS）能夠自動識別外來有害抗原，并通過一系列的免疫應答反應將其清除，而不會傷害生物自身組織。其具備的識別、學習、記憶、選擇、調節等能力受到了學術界的廣泛關注。著名免疫學家J.D.Farmer于20世紀80年代后期明確指出，在生物免疫系統與優化算法之間有著某種特定聯系。至此，人們借鑒、利用BIS中的各種規則、原理，提出了新的智能優化算法——人工免疫算法（Artificial Immune Algorithm，AIA）。在AIA算法中，BIS中的抗原與優化問題中的目標函數相對應，抗體則與可行解相對應。用抗原與抗體之間的親和度大小，來表示可行解和最優解之間的接近水平。如此一來，便可以通過模擬免疫反應來解決優化問題。BIS其高超的學習記憶能力、調節自適應機制、抗體多樣性等特點，是AIA算法從中借鑒、抽取的重要原理。

2.3 模擬退火算法

1953年，Metropolis從熱力學中的物質退火得到靈感，首次模擬了退火的思想；之后，Kirkpatrick等進行了擴展，并于1983年把模擬退火思想借鑒到優化問題中，提出了模擬退火算法（Simulated Annealing，SA），目前廣泛應用于工程領域，并解決了很多大規模優化問題。SA算法作為局部搜索方法的拓展，具有很強的跳出局部極值的能力，近年來，許多學者將SA算法進行改進，或與不同的智能優化算法融合使用，也收到了很不錯的效果。SA算法應用到優化問題時，內能代表目標函數，溫度則代表優化問題的控制參數。首先從某一給定的解作為初始解，在其附近隨機產生一個新解，計算二者的目標函數值差，并按Metropolis準則（以一定概率同意惡化的結果）判定新解能否使用，這樣一個“產生新解——計算目標函數值差——判定新解能否使用”的流程就與固態物質于每個溫度下達到熱平衡的過程向對應。在得到該溫度下的“最優解”后，降溫，重復上述迭代過程，直至溫度達到最低點，系統達到內能最低的基態，對應于優化問題的全局最優解。

3 算法融合策略

3.1 基于退火思想的個體極值更新

SA算法中的核心思想就是不強求新解優于當前解，如此可有效提高搜索的靈活性，提升跳出局部極值的水平。PSO算法的關鍵機制之一在于粒子“記住”個體極值、群體“記住”全局極值。因此，考慮將退火思想借鑒到PSO算法中的“個體極值更新”這一過程，通過以一定概率接受“惡化”的個體極值，從而影響全局極值的取值，進而影響粒子速度與位置的更新，增強粒子的多樣性，提升全局尋優水平，改善易于“過早熟”的問題。

3.2 慣性權重線性遞減

本文采用Y.Shi和R.C.Eberhart給出的線性遞減ω的改進策略。即ωt=ωmax-×t這種ω的變化方式，簡單清晰，便于操作，相比于固定不變的ω，提升了算法的尋優水平，提高了后期收斂速度。

3.3 免疫記憶

AIA算法中的免疫記憶機理，就是將與抗原發生反應的部分抗體作為記憶細胞存入記憶庫，當再次感染同種抗原時，記憶細胞被激活并快速產生大量抗體。因此，可將免疫記憶機理借鑒到PSO算法中，用來保存優秀粒子，即將每代粒子群體中的全局極值，作為記憶細胞存入記憶庫，并參與粒子群體的迭代更新中。如此一來，可以提高粒子群體的整體質量，提升算法的尋優速度，提高算法的運算效率。

3.4 免疫調節

AIA算法中的免疫調節機理，即根據抗體與抗原間的親和度以及抗體的濃度，在進化過程中調節抗體。親和度較強或者濃度較低的抗體會得到促進，反之，則會受到抑制，這樣的協同調節機制，既保證了抗體的質量，又不會因為某種抗體濃度過高影響整體機能。因此，可以將免疫調節機制借鑒到PSO算法中，參與粒子的更新中，由于親和度和濃度雙重選擇機制的存在，粒子群體在更新后，能在保持粒子群體整體質量的同時，也在一定程度上保持粒子的多樣性，不會因為某一粒子濃度過高而出現“過早熟”問題，提升了算法的全局尋優水平。

對應到優化問題中，粒子（抗體）適應度較高時，親和度也較強，反之亦然，則親和力公式可以表示為適應度函數的倒數，即，則由親和力決定的選擇概率為：。而粒子濃度公式則為，則由濃度決定的選擇概率為：。因此，粒子被選擇的概率為：Pi=βPi1+(1-β)Pi2，β為[0,1]內的權重系數，本文取β為0.5。

3.5 SA算法、IPSO算法協同搜索

由前文可知，SA算法具有很強的跳出局部極值的能力。因此，考慮在上述改進措施的基礎上，將PSO算法與SA算法進行過程融合，二者協同搜索，即在改進后的免疫PSO算法求得全局極值，且經過x次迭代全局極值間的差距均小于計算精度ε后，便認為PSO算法陷入了局部（全局）最優解，此時，調用SA算法，以求得全局極值作為初始解開始搜索，如果SA算法結束，該值仍為最優解，則認為該值就是最優解；如果經過SA算法得到了優于該值的新解，則將新解替換粒子群中的某一粒子，繼續PSO算法的迭代中，直至搜索到全局最優解。

如此進行過程融合，有效地利用了兩類算法的優勢，取長補短，利用SA算法強大的跳出局部極值的能力，保證所得結果為全局最優解。

4 SA-IPSO融合算法流程圖

SA-IPSO融合算法流程如圖1。

圖1 SA-IPSO融合算法流程圖

5 算例驗證與結果分析

實驗環境：Windows10，Intel(R)Core(TM)i7-6700HQ CPU@2.60GHz，內存8G。

編譯工具：Matlab 2015b。

實驗算例：

（1）Rosenbrock函數（記為F1）

該函數有1個全局最小值0，相應自變量x*=(1,1,…，1)。

（2）Rastrigrin函數（記為F2）

該函數為一多峰函數，存在許多局部極值點，但只有1個全局最小值0，相應自變量x*=(0,0,…,0)。

（3）Griewank函數（記為F3）

該函數為一多峰函數，有1個全局最小值0，相應自變量 x*=(0,0,…,0)。

結果分析：

取100次實驗中三個算法的最優適應度值和平均適應度值進行比較，具體實驗結果如表1所示。

表1 實驗結果對比

實驗結果顯示，SA-IPSO相比其他兩類算法，最優適應度和平均適應度都有明顯優勢，說明SA-IPSO算法的全局尋優水平更高，相比其他兩類算法有更好的優化性能。當SAIPSO算法迭代超過20000次時，每次運行實驗都能得到全局最優解。

為了更直觀地表示各個算法的性能，取100次實驗的平均最優適應度值的對數（lg（F））為y軸，迭代次數為x軸，具體如圖2～4所示。

圖2 Rosenbrock函數優化過程

圖3 Rastrigrin函數優化過程

由以上3個圖可以看出，SA-IPSO算法相比其他兩類算法，曲線下降速率更快，說明該算法收斂速度較快；曲線整體更加平滑，沒有明顯的跳動，說明該算法在引入“免疫記憶”后，能夠充分利用尋優經驗搜索最優解；曲線在迭代后期穩定在最優適應度值，且經試驗發現，當迭代次數超過20000次時，每次實驗都能得到全局最優解，說明SA-IPSO算法引入的“免疫調節”“SA算法協同搜索”的策略較為成功，大幅提升了全局尋優水平。

圖4 Griewank函數優化過程

6 結語

本文詳細分析了PSO算法、AIA算法、SA算法的優缺點，并基于算法融合的思想，從基于退火思想的個體極值更新、慣性權重線性遞減、免疫記憶、免疫調節與模擬退火算法協同搜索五個方面進行改進融和，提出了SA-IPSO算法，并用3個經典算例進行仿真實驗。實驗結果表明，該算法較PSO算法、IPSO算法而言，收斂速度明顯加快，全局尋優水平大幅提高，當迭代次數較大時，可以穩定地收斂到全局最優解。