劉文英，張自魯，路慎強(qiáng)，張曉燕

(1.中國石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，山東 青島 266580；2.中國石化勝利油田分公司物探研究院，山東 東營 257000)

0 引 言

優(yōu)化問題存在于日常生活中的很多領(lǐng)域，如時(shí)間序列預(yù)測[1]、金融經(jīng)濟(jì)、生產(chǎn)調(diào)度、模式識別、人工智能、計(jì)算機(jī)工程等，其中函數(shù)優(yōu)化尤為重要，因此研究函數(shù)優(yōu)化方法具有很大的價(jià)值。

遺傳算法是受達(dá)爾文進(jìn)化論的影響提出的一種群智能優(yōu)化算法，模仿生物界的優(yōu)勝劣汰機(jī)制，在進(jìn)化過程中，通過評估染色體的適應(yīng)度來不斷淘汰較差的個(gè)體?；静僮鳛椋哼x擇，交叉，變異。遺傳算法因其搜索簡單、魯棒性強(qiáng)等優(yōu)點(diǎn)廣泛應(yīng)用于優(yōu)化問題中，但是在解決復(fù)雜優(yōu)化問題時(shí)又存在陷入局部最優(yōu)、收斂速度慢等不足。對此。文獻(xiàn)[2]提出一種動態(tài)交叉和動態(tài)變異策略操作，在保持種群多樣性的同時(shí)避免種群過早收斂，并將該方法應(yīng)用在物流路徑的優(yōu)化中；文獻(xiàn)[3]提出一種自適應(yīng)改進(jìn)的遺傳算法，該算法根據(jù)進(jìn)化中的種群適應(yīng)度非線性地自適應(yīng)調(diào)節(jié)交叉概率以及變異概率，使種群擺脫局部極值搜索到全局最優(yōu)解。

粒子群算法最初是由Kennedy和Eberhart等根據(jù)自然界鳥群覓食行為特點(diǎn)，模擬鳥群的行為特點(diǎn)提出的，是一種基于迭代的方法。每只鳥都被看作是一個(gè)粒子，每個(gè)粒子具有自己的位置和速度。粒子根據(jù)同伴的速度和位置調(diào)節(jié)本身，群體保存所有粒子中適應(yīng)值最優(yōu)的作為全局最優(yōu)，通過在個(gè)體最優(yōu)和全局最優(yōu)的指導(dǎo)下飛行，期望粒子收斂到最優(yōu)解。文獻(xiàn)[4]提出采用動態(tài)慣性權(quán)重因子，并引入差分進(jìn)化算法使算法擁有變異與交叉操作，算法在進(jìn)化后期也保持較高的收斂精度，并成功地應(yīng)用在神經(jīng)網(wǎng)絡(luò)的優(yōu)化中；文獻(xiàn)[5]提出了一種以自適應(yīng)權(quán)重粒子群算法為基礎(chǔ)，并引入遺傳交叉算子的混合優(yōu)化算法，用來優(yōu)化SVM參數(shù)的遙感圖像，能夠?qū)ふ业礁训腟VM分類器參數(shù)，獲得更高的分類精度。

在遺傳算法中，進(jìn)行變異操作的是種群中的少數(shù)個(gè)體，并且變異操作不把種群的當(dāng)前狀態(tài)和歷史狀態(tài)考慮在內(nèi)，而粒子群算法能記錄種群的歷史狀態(tài)和當(dāng)前狀態(tài)。針對以上問題，提出了一種新的遺傳-粒子群混合算法，該算法將粒子群算法與遺傳算法相結(jié)合[6-7]，用速度算子替代變異算子。通過實(shí)驗(yàn)驗(yàn)證，該方法在保持種群多樣性的同時(shí)具有較快的收斂速度。

1 粒子群-遺傳混合算法

1.1 種群劃分策略

文中借鑒小生境的思想對初始種群進(jìn)行劃分[8]，用“產(chǎn)優(yōu)率”來動態(tài)調(diào)整各個(gè)子種群的進(jìn)化狀態(tài)以避免進(jìn)化孤島的形成，使種群快速收斂的同時(shí)保證多樣性。文獻(xiàn)[9]中提出了基于個(gè)體編碼的均勻分割策略，該方法可以將種群劃分成若干個(gè)既不重疊又都能反映解空間整體性質(zhì)的子空間。文中將借鑒文獻(xiàn)[9]提到的種群劃分策略。具體操作為：定義算法種群初始數(shù)S，依據(jù)文獻(xiàn)[9]中均勻分割的理論，若定義種群S的階為s，那么種群S將可以劃分成2s個(gè)子種群，每個(gè)子種群內(nèi)個(gè)體的右邊s位編碼是完全相同的。假設(shè)對某種群P，定義它的階為2，就可以將P劃分成4個(gè)子種群：P1，P2，P3，P4，那么各個(gè)子種群的最右邊的編碼串分別為：00，01，10，11，則編碼串基本形式分別為：#00，#01，#10，#11，其中#代表任意長度的二進(jìn)制編碼串，具體如圖1和圖2所示[10-11]。

圖1 種群階為2

圖2 種群階為3

1.2 個(gè)體評價(jià)策略

傳統(tǒng)的遺傳算法主要是通過評價(jià)適應(yīng)度函數(shù)來評價(jià)個(gè)體的好壞，適應(yīng)度函數(shù)的選取跟目標(biāo)函數(shù)有很大的關(guān)系。在算法運(yùn)行的初始階段，群體內(nèi)存在少量適應(yīng)值極高的個(gè)體A(i)，若采用常規(guī)的選擇方法，使這些個(gè)體大量繁殖，在群體中占有很大的比重，而一些適應(yīng)值不錯(cuò)(比A(i)適應(yīng)值低)的個(gè)體過早被淘汰，可能造成群體的多樣性下降，從而可能導(dǎo)致算法過早收斂，即早熟收斂。文中設(shè)計(jì)一種個(gè)體評價(jià)策略，用于防止非最優(yōu)個(gè)體過早淘汰，適應(yīng)度函數(shù)表示為：

F(xi)=f(x)+f(xi)/N(i)

(1)

其中，f(x)為目標(biāo)函數(shù)本身；f(xi)/N(i)為個(gè)體i目標(biāo)函數(shù)本身與該個(gè)體被選擇次數(shù)的比值；N(i)表示該子個(gè)體被選擇的次數(shù)。如果一個(gè)最優(yōu)個(gè)體被選擇過多次，在之后的迭代中適當(dāng)增加非最優(yōu)個(gè)體被選擇的幾率，降低該個(gè)體被選擇的幾率，保證種群的多樣性不會減少。

1.3 交叉操作

交叉操作是對父代個(gè)體進(jìn)行基因交換重組，用于產(chǎn)生大量新的個(gè)體，從而可能產(chǎn)生更優(yōu)的個(gè)體。文中通過判斷相似度大小，設(shè)計(jì)一種新的交叉操作[12]，對不同子個(gè)體采用不同的交叉操作。設(shè)進(jìn)行交叉的兩個(gè)父代個(gè)體為Xi和Xj，計(jì)算其相似度。對任意優(yōu)化問題使用二進(jìn)制編碼[13-14]，編碼空間為{0，1}，個(gè)體Xi與個(gè)體Xj之間的相似度表示如下：

(2)

其中，n表示二進(jìn)制編碼的長度；sm(i,j)表示在m位上的個(gè)體i，j值是否相同。假定i，j個(gè)體在m位上的值相同，則sm(i,j)為1；否則為0。如果i，j個(gè)體有很多位相同，不難算出，相應(yīng)的S(i,j)也會比較大。

當(dāng)i，j個(gè)體相似度S(i,j)大于預(yù)先設(shè)定的相似度閾值su時(shí)，說明i，j個(gè)體在很大程度上相似。這時(shí)采用普通的交叉操作有可能沒有很大的效果，產(chǎn)生新個(gè)體的幾率比較小,所以采用將個(gè)體i前k(k∈rand(1,n))位與個(gè)體j的后k位進(jìn)行交叉的方法，如圖3所示。

圖3 交叉操作

當(dāng)i，j個(gè)體相似度S(i,j)小于預(yù)先設(shè)定的相似度閾值su時(shí)，說明i,j個(gè)體本身差別較大，采用單點(diǎn)交叉產(chǎn)生新的個(gè)體，如圖4所示。

圖4 單點(diǎn)交叉

1.4 速度更新模型改進(jìn)

文中提出的混合算法是將遺傳算法與粒子群算法相結(jié)合，遺傳算法為主，將粒子群算法的更新方式用變異操作代替。該算法既包含由遺傳算法的選擇跟交叉操作主導(dǎo)的個(gè)體更新，也包括粒子群算法本身的自我認(rèn)知和社會認(rèn)知對粒子主導(dǎo)的個(gè)體更新。對任意子種群Pi，假設(shè)進(jìn)化到第i代時(shí)，在第i代之前生成的滿足條件的數(shù)據(jù)總個(gè)數(shù)為Ti，那么子種群Pi內(nèi)個(gè)體的變異影響因子ρi=1-δi。其中δi為種群產(chǎn)優(yōu)率[10]。

“產(chǎn)優(yōu)率”[10]：在種群進(jìn)化到第i代時(shí)，任意子種群j在i代之前生成的最優(yōu)個(gè)體數(shù)量為Tji，整個(gè)種群在第i代之前生成的總的最優(yōu)個(gè)體數(shù)量為：

(3)

那么種群t的產(chǎn)優(yōu)率為：

(4)

由式3和式4可知，生成優(yōu)秀個(gè)體越多，種群的產(chǎn)優(yōu)率越大，相應(yīng)的，變異影響因子越小，種群越穩(wěn)定；生成優(yōu)秀個(gè)體越少，種群產(chǎn)優(yōu)率越低，變異影響因子越大，種群傾向于發(fā)生突變。

文中將上文提到的產(chǎn)優(yōu)率替代傳統(tǒng)粒子群算法中的慣性權(quán)重因子，具體更新方式如下：

(5)

Xi(t+1)=Xi(t)+Vi(t+1)

(6)

從式5和式6可以看出，子種群中個(gè)體的更新速度受種群“產(chǎn)優(yōu)率”的影響，成正向關(guān)系。“產(chǎn)優(yōu)率”的高低直接影響粒子更新速度的高低。

1.5 粒子群-遺傳混合算法

文中混合算法流程與傳統(tǒng)遺傳算法類似[15-16]，算法流程如圖5所示。具體方案如下：

Step1：初始化各實(shí)驗(yàn)參數(shù)：種群規(guī)模、種群產(chǎn)優(yōu)率、交叉概率、相似度閾值、加速因子、慣性權(quán)重因子等；

Step2：依據(jù)1.1節(jié)的策略，將種群劃分為2s個(gè)子種群；

Step3：針對每個(gè)子種群，依據(jù)1.3的內(nèi)容各自進(jìn)行選擇、交叉；

Step4：依據(jù)式1計(jì)算子種群的適應(yīng)度值，更新存儲優(yōu)秀個(gè)體；

Step5：依據(jù)式3、式4，分別計(jì)算每個(gè)子種群內(nèi)個(gè)體的變異概率及產(chǎn)優(yōu)率；

Step6：依據(jù)式5、式6，對各子種群個(gè)體進(jìn)行更新；

Step7：是否達(dá)到最大迭代次數(shù)或滿足終止條件，若滿足，算法結(jié)束；否則，重復(fù)Step2～Step6。

圖5 算法具體流程

2 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證文中提出的算法在解決函數(shù)優(yōu)化問題時(shí)的收斂速度以及收斂精度，實(shí)驗(yàn)采用表1的5個(gè)測試函數(shù)進(jìn)行測試。

表1 測試函數(shù)及x相應(yīng)取值

2.1 h-PSO-GA與PSO、GA算法實(shí)驗(yàn)

參數(shù)設(shè)置如下：將種群劃分為10個(gè)子種群，子種群大小設(shè)為50，最大迭代次數(shù)maxiter設(shè)為100，c1=c2=2.0，交叉概率pc設(shè)為0.35，產(chǎn)優(yōu)率初始值為0.1，相似度閾值su設(shè)置為0.7。實(shí)驗(yàn)結(jié)果如表2所示。

表2 對5個(gè)測試函數(shù)進(jìn)行50次實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果

通過表2可以看出，該實(shí)驗(yàn)在重復(fù)50次之后，得到了平均最優(yōu)值與全局最優(yōu)值。通過與5個(gè)測試函數(shù)理論值進(jìn)行比較，可以發(fā)現(xiàn)，提出的算法在測試函數(shù)上的效果整體來說不錯(cuò)，僅在f5函數(shù)上比PSO原始效果差一些，總體來看，該算法在處理函數(shù)優(yōu)化問題時(shí)的效果較好。

2.2 最優(yōu)解收斂變化

對上述5個(gè)測試函數(shù)比較算法的收斂情況，如圖6～圖10所示。從圖6可以看出，提出算法在f1測試函數(shù)上經(jīng)歷10代左右收斂在理論值附近，而遺傳算法在接近40代左右才進(jìn)行收斂，PSO算法在15代左右進(jìn)行收斂。從圖7可以看出，文中算法與PSO算法在收斂速度上幾乎差不多，但比PSO算法收斂快一些。在圖8～圖10中，文中算法比另外兩種算法收斂速度都快，在f3，f4函數(shù)上，文中算法收斂精度比遺傳算法要高。

綜合比較，文中算法在幾個(gè)測試函數(shù)上的收斂情況都較好，算法最終收斂精度在函數(shù)的理論最優(yōu)值附近。

圖6 函數(shù)f1的測試結(jié)果

圖7 函數(shù)f2的測試結(jié)果

圖8 函數(shù)f3的測試結(jié)果

圖9 函數(shù)f4的測試結(jié)果

圖10 函數(shù)f5的測試結(jié)果

3 結(jié)束語

文中提出一種基于粒子群-遺傳混合算法的函數(shù)優(yōu)化方法，通過借鑒小生境技術(shù)將種群進(jìn)行劃分，并且通過相似度判斷，對不同的父代個(gè)體進(jìn)行不同的交叉操作，并將粒子群算法與遺傳算法相結(jié)合，用速度算子來替代變異算子，進(jìn)而實(shí)現(xiàn)個(gè)體更新。通過與傳統(tǒng)遺傳算法、粒子群算法進(jìn)行比較實(shí)驗(yàn)驗(yàn)證，該方法在保證種群多樣性同時(shí)，避免了早熟收斂情況的發(fā)生，具有較高的效率。