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

范偉倫，衛(wèi)鑫，熊威

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

1 前言

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

2 算法簡介

2.1 粒子群算法

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

2.2 人工免疫算法

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

2.3 模擬退火算法

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

3 算法融合策略

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

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

3.2 慣性權(quán)重線性遞減

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

3.3 免疫記憶

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

3.4 免疫調(diào)節(jié)

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

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

3.5 SA算法、IPSO算法協(xié)同搜索

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

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

4 SA-IPSO融合算法流程圖

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

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

5 算例驗證與結(jié)果分析

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

編譯工具：Matlab 2015b。

實驗算例：

（1）Rosenbrock函數(shù)（記為F1）

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

（2）Rastrigrin函數(shù)（記為F2）

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

（3）Griewank函數(shù)（記為F3）

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

結(jié)果分析：

取100次實驗中三個算法的最優(yōu)適應(yīng)度值和平均適應(yīng)度值進行比較，具體實驗結(jié)果如表1所示。

表1 實驗結(jié)果對比

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

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

圖2 Rosenbrock函數(shù)優(yōu)化過程

圖3 Rastrigrin函數(shù)優(yōu)化過程

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

圖4 Griewank函數(shù)優(yōu)化過程

6 結(jié)語

本文詳細(xì)分析了PSO算法、AIA算法、SA算法的優(yōu)缺點，并基于算法融合的思想，從基于退火思想的個體極值更新、慣性權(quán)重線性遞減、免疫記憶、免疫調(diào)節(jié)與模擬退火算法協(xié)同搜索五個方面進行改進融和，提出了SA-IPSO算法，并用3個經(jīng)典算例進行仿真實驗。實驗結(jié)果表明，該算法較PSO算法、IPSO算法而言，收斂速度明顯加快，全局尋優(yōu)水平大幅提高，當(dāng)?shù)螖?shù)較大時，可以穩(wěn)定地收斂到全局最優(yōu)解。