基于高斯函數(shù)和自適應(yīng)精英策略的遺傳算法

李清霞

(東莞城市學(xué)院 計算機(jī)與信息學(xué)院，廣東東莞 523419)

遺傳算法(Genetic algorithms，簡稱GA)是由Holland等人提出的[1]，20世紀(jì)六七十年代最流行、應(yīng)用最廣泛的算法。它的靈感來源于達(dá)爾文的自然選擇理論[2]。遺傳算法是一種基于群體的，依賴于偶然搜索的優(yōu)化方法。在遺傳算法中，群體由一組稱為染色體的n個個體組成，主要包括兩種表示方式：1)基因型(二進(jìn)制表示)或2)表型(實數(shù)表示)。由于遺傳算法的參數(shù)簡單，所以在解決優(yōu)化問題具有較強(qiáng)的優(yōu)勢。然而，根據(jù)“沒有免費的午餐”定理[3]，在解決不同的優(yōu)化問題時，甚至在進(jìn)化的不同階段，任何算法都沒有適合所有情況的特定參數(shù)設(shè)置或策略。因此，有大量的研究工作者致力于基于現(xiàn)有的遺傳算法設(shè)計出新的變異和交叉操作算子，或者通過調(diào)整參數(shù)的方法來提高算法的魯棒性和準(zhǔn)確性。其中，大多數(shù)研究者提出的遺傳算法變種旨在開發(fā)適應(yīng)性或自適應(yīng)性改進(jìn)操作算子或控制參數(shù)設(shè)置方式來改進(jìn)遺傳算法性能[4-7]。

Srinivas等[8]首次提出了改進(jìn)的自適應(yīng)性遺傳算法，該算法采用自適應(yīng)性交叉和變異概率改進(jìn)操作算子以實現(xiàn)種群的多樣性，提高算法收斂速度。王儲等[4]提出了一種基于精英策略的多種群自適應(yīng)遺傳算法，該算法通過融入一種混合精英策略，提高算法的收斂性能,精英選擇算子選擇當(dāng)前種群的最優(yōu)解并進(jìn)行精英備份，不斷迭代選出最優(yōu)解。徐逸帆等[9]針對傳統(tǒng)遺傳算法具有收斂速度慢、易陷入局部最優(yōu)解的問題，分析種群個體特別是精英個體的特征，使用最小一乘法重新定義適應(yīng)度函數(shù)，提出了基于精英保留策略的遺傳算法。袁帥鵬等[10]提出了一種基于自適應(yīng)網(wǎng)格法的擇優(yōu)策略來改進(jìn)帶精英策略的快速非支配排序遺傳算法，有效克服了使用傳統(tǒng)Pareto支配法擇優(yōu)策略在解決離散問題時容易丟失有用信息的缺陷。郭軍[11]指出帶精英策略的非支配排序遺傳算法是目前最流行的多目標(biāo)優(yōu)化算法之一，具有較高的求解效率，可在一次運行過程中得出多個高質(zhì)量的解，成為了其它多目標(biāo)優(yōu)化算法進(jìn)行性能對比的基準(zhǔn)算法。王磊等[12]等通過分析簡單遺傳算法中精英個體的特征，提出了一種應(yīng)用于功能驗證的精英策略，該算法將本代優(yōu)秀個體和本代適應(yīng)度高的歷史優(yōu)秀個體視為精英個體，給予額外交叉機(jī)會。王福才等[13]提出了一種混合精英策略的元胞多目標(biāo)遺傳算法，該算法在分析元胞種群結(jié)構(gòu)的特點基礎(chǔ)上，融入一種混合精英策略，提高了算法的收斂性能。趙鑫寧等[14]提出了一種基于高斯分布和柯西分布的概率選擇算子，該算法在執(zhí)行選擇操作時，分別根據(jù)當(dāng)前種群生成高斯和柯西分布，通過對分布采樣獲得參加遺傳操作的個體，從而保證了種群多樣性，避免早熟收斂。

在遺傳算法中，當(dāng)子代不能代替當(dāng)前個體進(jìn)行多次迭代時，就會出現(xiàn)停滯現(xiàn)象，面對停滯現(xiàn)象，很多改進(jìn)的遺傳算法就會顯得無能為力，這也意味著現(xiàn)有的改進(jìn)機(jī)制可能會出現(xiàn)暫時性的失效。一般地，停滯的主要原因可能是缺乏多樣性或陷入局部最優(yōu)。

為了解決種群進(jìn)化停滯問題，筆者提出一種基于高斯函和自適應(yīng)精英策略的遺傳算法，該算法基于標(biāo)準(zhǔn)遺傳算法，采用精英種群選擇策略以引導(dǎo)停滯個體繼續(xù)進(jìn)化，在交叉操作算子中引入高斯函數(shù)以實現(xiàn)種群的多樣性。精英策略是指從動態(tài)變化的精英群體中隨機(jī)抽取精英個體進(jìn)行生存選擇，高斯函數(shù)主要是采用高斯函數(shù)的正態(tài)分布交叉操作算子來實現(xiàn)種群的多樣性。整個進(jìn)化過程由全局和局部參數(shù)控制，這些參數(shù)能夠適應(yīng)整個種群和個體自身的變化。為了證明本文算法的健壯性和有效性，將本文算法和傳統(tǒng)遺傳算法及其變種、其他改進(jìn)的進(jìn)化算法對于CEC 2014基準(zhǔn)函數(shù)和兩個實際優(yōu)化問題進(jìn)行了實驗測試，仿真結(jié)果表明，本文算法提高了遺傳算法的多樣性，具有更高的求解精度和更好的收斂性。

1 遺傳算法

遺傳算法是一種基于種群的算法，種群中的個體都被編碼為二進(jìn)制值的字符串或染色體，即0或1。每一個個體都代表了一個可能的解，并且可以用編碼表示解的許多特征，包括數(shù)值、結(jié)構(gòu)特征、備選解之間的選擇等等。遺傳算法通過種群的選擇、交叉和變異操作產(chǎn)生后代及子代替換，使種群朝著目標(biāo)函數(shù)定義的更好適應(yīng)度值的方向發(fā)展。

遺傳算法主要包括選擇、交叉和變異操作算子，分別定義如下：

選擇：定義哪些個體將把他們的遺傳信息傳遞給下一代，一般采用基于概率的選擇機(jī)制來決定群體中哪些個體被選擇。目前比較流行的三種選擇機(jī)制分別是：比例選擇、基于排名的選擇和錦標(biāo)賽選擇。

交叉：用來混合父代的遺傳信息，而不引入任何新的信息。交叉操作一般包括單點交叉、兩點交叉和均勻交叉。在單點交叉中，選擇染色體中的一個點，交換它們的尾部。在兩點交叉中，選擇兩個點，個體交換中間部分。在均勻交叉中，每一個比特都可以從一個父節(jié)點或另一個節(jié)點中選擇。

變異：對種群中個體的基因信息進(jìn)行變動，以增加算法的局部搜索能力。根據(jù)個體編碼方式，可以把變異操作分為實數(shù)變異和二進(jìn)制變異。一般來說，變異操作的基本步驟包括：1)對群中所有個體以事先設(shè)定的變異概率判斷是否進(jìn)行變異；2)對進(jìn)行變異的個體隨機(jī)選擇變異位進(jìn)行變異。

2 基于高斯函數(shù)和自適應(yīng)精英策略的遺傳算法

2.1 算法思想

基于高斯函數(shù)和自適應(yīng)精英策略的遺傳算法(ESG-GA)的主要思想是利用動態(tài)變化的精英個體和基于高斯分布的交叉操作算子來更新停滯的個體，以平衡開發(fā)和探索能力。

為了檢測進(jìn)化過程的狀態(tài)，引入了一個全局控制參數(shù)GCP和個體狀態(tài)參數(shù)ISP，其中GCP用來控制種群的搜索空間，ISP用來統(tǒng)計個體在整個種群中的適應(yīng)度情況，這兩個定義為

(1)

(2)

其中，Tmax是最大的代數(shù)，t表示當(dāng)前代數(shù)。GCP的值隨著迭代的進(jìn)行而減小。f(xi,t)是t代第i個個體目標(biāo)函數(shù)的值，fmax和fmin是當(dāng)前種群目標(biāo)函數(shù)的最大值和最小值。對于最小值優(yōu)化，ISP值越小就表示個體更優(yōu)。對于這兩個檢測參數(shù)，GCP用于全局控制，ISP用于局部控制，同時GCP也直接決定了精英個體的規(guī)模。

在自適應(yīng)精英策略中，是從精英種群中隨機(jī)選擇一個精英個體，而不是從當(dāng)前種群中擇優(yōu)選擇個體。精英種群是由當(dāng)前種群中具有最佳適應(yīng)度值的個體組成的種群。精英種群的大小ENP根據(jù)全局控制參數(shù)GCP的變化而動態(tài)地變化。

ENP=floor((GCP-1)*Tmax+NP),

(3)

其中NP是種群大小，floor函數(shù)用于保證ENP是整數(shù)。當(dāng)前的精英種群是根據(jù)適應(yīng)度值從當(dāng)前種群中選擇最優(yōu)秀的ENP個個體組成的。需要注意的是，每次使用當(dāng)前GCP值計算ENP值時，精英種群都會被重建，因此精英種群能夠始終保持最新，也就不需要再保存歷史精英種群。隨著迭代次數(shù)的增加，ENP動態(tài)減少，種群多樣性降低，搜索的重心將逐漸從全局探索轉(zhuǎn)移到局部開發(fā)，從而提高算法后期的搜索精度。還需注意的是，一個精英個體是從精英種群中隨機(jī)挑選出來的，而不是從精英種群中擇優(yōu)選擇的最優(yōu)個體，這樣做主要是為了減少貪婪，增加除了最優(yōu)個體之外發(fā)現(xiàn)有用信息的機(jī)會。

為了創(chuàng)建一個更多樣化的后代種群以提高遺傳算法的性能，在遺傳算法的迭代中，通過應(yīng)用一個基于高斯函數(shù)的正態(tài)分布交叉操作算子來實現(xiàn)種群的多樣性。

(4)

其中μ表示適應(yīng)度值，σ2表示變量。

σ2可由下式計算：

σ2=(GCP×(xi,t-ej,t))2，

(5)

其中xi,t表示第t代的個體，ej,t表示第t代精英種群中隨機(jī)選擇的個體。全局控制參數(shù)GCP可以保證搜索空間逐漸縮小，意味著進(jìn)化是朝向精英區(qū)域發(fā)展，這有助于提高收斂精度。

針對μ的計算，如果當(dāng)前個體優(yōu)于精英個體，則μ用當(dāng)前個體代替，否則μ用精英個體代替，定義如下：

(6)

ESG-GA算法在最初的進(jìn)化階段，搜索過程集中在對當(dāng)前個體的開發(fā)上，隨著代數(shù)的增加，搜索的焦點轉(zhuǎn)移到精英個體上。當(dāng)前個體越好，它所占的權(quán)重就越大，因此ESG-GA算法可以有效地利用個體的信息。

ESG-GA算法的自適應(yīng)精英策略主要表現(xiàn)為：在進(jìn)化的早期階段，精英策略并沒有過多的干擾種群的選擇過程，當(dāng)種群個體開始停滯不前時，精英策略逐步占主導(dǎo)作用，給予個體進(jìn)化更多的引導(dǎo)，使進(jìn)化朝著精英區(qū)域發(fā)展。因此ESG-GA算法比其他改進(jìn)的GA算法能夠發(fā)揮更好的收斂精度。

2.2 算法描述

根據(jù)算法思想，ESG-GA算法執(zhí)行過程的偽代碼如下。

輸入:初始種群初始化種群P(種群大小為NP);while t

采用式(6)計算個體狀態(tài)參數(shù)ISP;采用式(7)計算精英種群的大小ENP;按照適應(yīng)度值優(yōu)先級從種群個體中選擇出EPN個精英個體組成精英種群;for i=NP do 采用式(6)計算μ; 采用式(5)計算變量σ2; 采用式(4)執(zhí)行交叉操作產(chǎn)生高斯分布的個體; 執(zhí)行變異操作; 產(chǎn)生下一代種群;endend輸出:最優(yōu)種群

2.3 算法復(fù)雜度分析

由于ESG-GA算法主要是針對傳統(tǒng)遺傳算法的交叉算子進(jìn)行改進(jìn)，并沒有增加迭代次數(shù)，也沒有增加適應(yīng)度評估數(shù)量，因此ESG-GA算法的時間復(fù)雜度與傳統(tǒng)GA算法基本上一致。具體分析如下：

在算法中，對于外層循環(huán)，最多執(zhí)行Tmax次，對于內(nèi)層循環(huán)，需要執(zhí)行NP次。由于在兩個嵌套循環(huán)內(nèi)的其他操作都是順序執(zhí)行語句，所以ESG-GA算法時間復(fù)雜度為O(Tmax·NP)。

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

為了驗證ESG-GA算法的有效性，在軟件環(huán)境為MATLAB 2018b，硬件環(huán)境為8G內(nèi)存、64位Intel(R)I5 2.60GHz處理器上對該算法進(jìn)行了仿真實驗。將ESG-GA算法與傳統(tǒng)遺傳算法及7種改進(jìn)進(jìn)化算法對于CEC 2014基準(zhǔn)函數(shù)和2個實際優(yōu)化問題進(jìn)行比較實驗。

對比實驗中的8種進(jìn)化算法包括標(biāo)準(zhǔn)GA和3種具有競爭力的GA變種算法(GCSGA[11]，NRGA[15]，GA-RTS[16])以及4種其他進(jìn)化算法(JADE-sort[17]，M_PSO_MA[18]，MABCM[19]和EIR-DE[20])。CEC 2014的30個基準(zhǔn)函數(shù)根據(jù)功能可分為4類：

1)f1-f3：單峰函數(shù)；

2)f4-f16：簡單多峰函數(shù)；

3)f17-f22：混合函數(shù)；

4)f23-f30：合成函數(shù)。

實驗中的實際優(yōu)化問題為文獻(xiàn)[21]中常用于評價各種算法性能的兩個現(xiàn)實優(yōu)化問題：調(diào)頻聲波參數(shù)估計(rf1)和擴(kuò)頻雷達(dá)多相碼設(shè)計(rf2)。所有問題都經(jīng)過測試，最大評估次數(shù)設(shè)置為5×105。對于統(tǒng)一性，所有算法的種群大小都相同，即NP=100。一般情況下，設(shè)交叉概率為0.4，變異概率為0.005。對于基準(zhǔn)測試函數(shù)，其維度分別等于50D和100D。當(dāng)最大評估次數(shù)用完或者到達(dá)最大的迭代代數(shù)時，進(jìn)化過程將終止。每種算法運行50次，得到誤差值的平均值和標(biāo)準(zhǔn)差用表格數(shù)據(jù)顯示。

3.1 基準(zhǔn)函數(shù)的仿真結(jié)果

表1記錄了標(biāo)準(zhǔn)GA、3種GA變體算法在50D基準(zhǔn)函數(shù)與ESG-GA算法的比較統(tǒng)計。對于每一種算法，適應(yīng)度值誤差較小的平均值以粗體顯示。

表1 GA及其變種算法與ESG-GA算法在50D基準(zhǔn)函數(shù)上的比較

從表1可以看出，ESG-GA算法只有在函數(shù)f3、f17處于劣勢(其中在函數(shù)f23中相等)，在其他27個函數(shù)中均超越了其他4種算法。

由于篇幅限制，隨機(jī)地選擇了兩個50D基準(zhǔn)函數(shù)畫出了算法的收劍圖，如圖1和圖2所示，分別顯示了所有算法對于50D基準(zhǔn)函數(shù)f3和f20的收斂圖。從圖1和圖2明顯可以看出，ESG-GA算法的收斂速度和收斂精度明顯高于其他4種算法。

圖1 各算法對于50D基準(zhǔn)函數(shù)f1的收斂圖

圖2 各算法對于50D基準(zhǔn)函數(shù)f20的收斂圖

表2顯示了其他4種進(jìn)化算法在100D基準(zhǔn)函數(shù)與ESG-GA算法的比較統(tǒng)計。同樣，對于每一種算法，適應(yīng)度值誤差較小的平均值以粗體顯示。

從表2可以看出，ESG-GA算法在函數(shù)f8、f17、f23、f26和f28上分別與MABCM、JADE-sort和EIR-DE算法取得相等成績，只有在函數(shù)f4、f12和f22上比MABCM、JADE-sort和EIR-DE算法稍處于劣勢，但在其他23個基準(zhǔn)函數(shù)上，都超越了MABCM、JADE-sort和EIR-DE算法。另外，ESG-GA算法在所有基準(zhǔn)函數(shù)上都超越了M_PSO_MA算法。

表2 其他進(jìn)化算法與ESG-GA算法在100D基準(zhǔn)函數(shù)上的比較

圖3和圖4分別顯示了所有算法對于100D基準(zhǔn)函數(shù)f5和f30的收斂圖，從圖3和圖4明顯可以看出，與其他4種算法相比，ESG-GA算法雖然收斂精度相差不大，但收斂速度還是明顯占優(yōu)。

圖3 各算法對于100D基準(zhǔn)函數(shù)f5的收斂圖

圖4 各算法對于100D基準(zhǔn)函數(shù)f30的收斂圖

3.2 真實問題的仿真結(jié)果

從表3總結(jié)的仿真結(jié)果可以看出，ESG-GA算法在處理第一個實際優(yōu)化問題中，遠(yuǎn)超于其他進(jìn)化算法，具有顯著的優(yōu)勢。在處理第二個問題時，與某些進(jìn)化算法差距不算太明顯，但也優(yōu)于其他進(jìn)化算法。

表3 ESG-GA算法與8種進(jìn)化算法與在實際優(yōu)化問題上的比較

實驗結(jié)果表明，ESG-GA算法能夠適應(yīng)整個種群和個體自身的變化，引導(dǎo)個體進(jìn)化到潛在的搜索空間。

4 結(jié)語

針對遺傳算法中存在的停滯問題，提出了一種基于高斯函數(shù)和自適應(yīng)精英策略的遺傳算法，該算法先是基于種群個體適應(yīng)度值排序，然后從排好序的種群個體中隨機(jī)選擇一些精英個體組成精英種群，用來引導(dǎo)停滯的個體繼續(xù)進(jìn)化以解決遺傳算法中存在的個體進(jìn)化停滯問題，最后在交叉操作算子中引入高斯函數(shù)以實現(xiàn)種群的多樣性。在測試CEC 2014中50D、100D和兩個實際優(yōu)化問題的基準(zhǔn)函數(shù)后，驗證了ESG-GA算法相對于其他8種進(jìn)化算法的優(yōu)越性，同時給出了適應(yīng)度值誤差的均值、標(biāo)準(zhǔn)差和收斂圖的比較。所有的實驗結(jié)果表明，所提出的算法能夠有效地幫助處于停滯狀態(tài)的個體繼續(xù)進(jìn)化，具有更高的求解精度和更好的收斂性。