免疫遺傳雙優(yōu)化的粒子群算法

成都理工大學(xué)信息科學(xué)與技術(shù)學(xué)院　李　鑫　韓均雷　蘇勇勇

免疫遺傳雙優(yōu)化的粒子群算法

成都理工大學(xué)信息科學(xué)與技術(shù)學(xué)院李鑫韓均雷蘇勇勇

標(biāo)準(zhǔn)的粒子群算法在進(jìn)行迭代尋優(yōu)解時易發(fā)生局部最優(yōu)、全局尋優(yōu)能力弱、收斂速度慢和搜索精度不足的情況，為此本文提出一種基于遺傳算法和免疫算法優(yōu)化的帶動態(tài)慣性權(quán)重因子和學(xué)習(xí)因子的智能粒子群算法。該算法結(jié)合“遺傳”、“免疫”和“動態(tài)因子”的思想，經(jīng)過4個經(jīng)典函數(shù)的測試，表明該算法兼顧局部和全局搜索，并具有更快的收斂速度和更高的搜索精度。

粒子群算法；遺傳算法；免疫算法；因子優(yōu)化

0　引言

粒子群（Particle Swarm Optimization，PSO）算法是現(xiàn)在科研中經(jīng)常用的智能算法，該算法具有群體智能，內(nèi)在并行性、迭代格式簡單、可快速收斂到最優(yōu)解所在區(qū)域等優(yōu)點。PSO算法是模擬一個群體系統(tǒng)。系統(tǒng)中每個可能產(chǎn)生的解表述為群體中的一個微粒，每個粒子有自己的位置向量和速度向量，每個微粒的位置和速度將按照一定的準(zhǔn)則變化，由目標(biāo)函數(shù)決定的適應(yīng)度進(jìn)行微粒的迭代判斷。PSO算法有實行簡單、迭代格式簡單、準(zhǔn)確率高等優(yōu)點，但是不可避免的也存在瑕疵，在迭代尋優(yōu)中易于陷入局部最優(yōu)、“早熟”，導(dǎo)致無法獲得真正最優(yōu)解。為此本文擬結(jié)合遺傳算法和免疫算法，對PSO進(jìn)行改進(jìn)。

1　標(biāo)準(zhǔn)PSO

其中：i=1，2，…，M，d=1，2，…D，c1和c2是學(xué)習(xí)因子，rand（）是［0，1］范圍內(nèi)的隨機函數(shù)。種群規(guī)模依據(jù)搜索空間維度D和問題的難易程度，一般微粒數(shù)M選取30左右，遇到特別復(fù)雜且搜索空間過大的情況，微粒數(shù)可以增加。

2　擬遺傳算法和免疫算法優(yōu)化的粒子群算法

2.1 PSO慣性權(quán)重因子和學(xué)習(xí)因子調(diào)整策略

確保局部最優(yōu)和粒子搜索能力，對慣性權(quán)重進(jìn)行調(diào)整，把慣性的權(quán)重與目標(biāo)函數(shù)結(jié)合起來。非線性遞減策略的慣性權(quán)更新公式如下：

對于學(xué)習(xí)因子，要提高其算法的全局搜索能力和最優(yōu)局部的精確搜索能力，這里采用A.Ratnawecra等提出了線性調(diào)整學(xué)習(xí)因子，該算法的學(xué)習(xí)因子調(diào)整公式如下：

算法的關(guān)鍵在于控制微粒速度算法，讓算法達(dá)到全局最優(yōu)與局部開發(fā)間的有效平衡。所有對速度引入收縮因子，速度表達(dá)式如下：

2.2遺傳算法與免疫算法對PSO的改進(jìn)

將遺傳算法中的交叉和變異因子引入PSO算法，通過判斷是否出現(xiàn)“早熟”現(xiàn)象，對已經(jīng)產(chǎn)生的優(yōu)秀個體與隨機產(chǎn)生的微粒個體進(jìn)行交叉變異操作使產(chǎn)生的微粒跳出局部最優(yōu)點，并且又保留了優(yōu)秀個體的特性。遺傳免疫PSO的基本步驟如下：

Step1：將在迭代過程中計算的全局極值進(jìn)行存儲，形成極值庫。

Step2：在迭代過程中對粒子是否進(jìn)入“早熟”進(jìn)行判定，同時判斷粒子是否陷入局部最優(yōu)。

Step3：當(dāng)判斷到微粒陷入局部最優(yōu)時，根據(jù)微粒的適應(yīng)度和濃度賦予相應(yīng)的選擇規(guī)則，保證其能跳出局部最優(yōu)，濃度與適應(yīng)度成反比，即期望：

其中：Q為微粒的濃度，C為適應(yīng)度。

微粒發(fā)生變異的概率也與其相似為：

由這兩部分微粒進(jìn)行交叉和變異產(chǎn)生新的微粒群替代陷入局部最優(yōu)的微粒群。

Step4：通過變異和交叉形成的微粒群繼續(xù)進(jìn)行循環(huán)尋優(yōu)過程，當(dāng)達(dá)到終止條件時，循環(huán)結(jié)束。

3　實驗檢驗與結(jié)果分析

本實驗環(huán)境：軟件環(huán)境：Windows7.0，編譯軟件：Matlab2012。硬件環(huán)境：CPU Inter（R）Pentium（R）2.00 GHz，內(nèi)存：4.00GB。

下面分別對標(biāo)準(zhǔn)PSO和遺傳免疫PSO進(jìn)行程序運行，得出以下兩幅圖，從中可以看出遺傳免疫PSO收斂速度快。

圖1 標(biāo)準(zhǔn)PSO算法收斂曲線

圖2 遺傳免疫PSO算法收斂曲線

下面將基于Matlab進(jìn)行實驗驗證，采用經(jīng)典測試函數(shù)Sphere函數(shù)、Rastrigin函數(shù)、Rosenb函數(shù)、Ackley函數(shù)分別對標(biāo)準(zhǔn)PSO和遺傳免疫PSO進(jìn)行對比仿真。測試標(biāo)準(zhǔn)PSO和遺傳免疫PSO在收斂速度和精度上的區(qū)別。粒子矢量維度D=4，種群規(guī)模M=30，最大迭代次數(shù)，慣性權(quán)重因子最大值，最小值，加速因子取2.0。

表2　精度測試對比（精度提高率=（標(biāo)準(zhǔn)PSO-遺傳免疫PSO）/標(biāo)準(zhǔn)PSO）

從試驗結(jié)果上可以看出，Sphere函數(shù)和Ackley函數(shù)基本一致，但遺傳免疫PSO的收斂速度更快；對于Rosenbrock函數(shù)和Rastrigin函數(shù)，遺傳免疫PSO在收斂速度和搜索精度都優(yōu)于標(biāo)準(zhǔn)PSO；從實驗上可以得出遺傳免疫PSO具有收斂速度快，搜索精度高的特點。

4　結(jié)束語

本文對粒子群算法進(jìn)行陳述及權(quán)重策略的改變，并結(jié)合遺傳算法和免疫算法中的優(yōu)化思想對PSO算法進(jìn)行了優(yōu)化，使其既能夠快速收斂于全局最優(yōu)又能有效防止早熟退化跳出局部，構(gòu)成新的帶動態(tài)慣性權(quán)重因子和學(xué)習(xí)因子的遺傳免疫PSO，極大的提高了性能。最后采用經(jīng)典測試函數(shù)對該算法的優(yōu)化性能進(jìn)行測試，與標(biāo)準(zhǔn)PSO的優(yōu)化性能進(jìn)行比較，遺傳免疫PSO具有更快的收斂速度和更高的搜索精度。優(yōu)化的算法將在神經(jīng)網(wǎng)絡(luò)，模糊系統(tǒng)控制，數(shù)據(jù)的聚類，動態(tài)系統(tǒng)分析中發(fā)揮更大的作用。

［1］呂振肅，候志榮.自適應(yīng)變異的粒子群優(yōu)化算法［J］.電子學(xué)報，2004（03）.

［2］高鷹，謝勝利.免疫粒子群優(yōu)化算法［J］.計算機工程與應(yīng)用，2004（06）.

［3］許義海，李曉東.一種快速尋優(yōu)的新型改進(jìn)遺傳算法［J］.中山大學(xué)學(xué)報（自然科學(xué)版），2006，45（2）：36-40.

［4］胡旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法［J］.軟件學(xué)報，2007，18（4）：861-868.

［5］趙志剛，張振文，張福剛.自適應(yīng)擴展的簡化粒子群優(yōu)化算法［J］.計算機工程與應(yīng)用，2011，47（18）：45-47.

［6］武研，徐敏.一種改進(jìn)的粒子群優(yōu)化算法［J］.計算機工程與應(yīng)用，2006，42（43）：40-42.