李清霞

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

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

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

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

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

1 遺傳算法

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

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

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

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

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

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

2.1 算法思想

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

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

(1)

(2)

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

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

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

(3)

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

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

(4)

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

σ2可由下式計(jì)算：

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

(5)

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

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

(6)

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

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

2.2 算法描述

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

對(duì)比實(shí)驗(yàn)中的8種進(jìn)化算法包括標(biāo)準(zhǔn)GA和3種具有競(jìng)爭(zhēng)力的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個(gè)基準(zhǔn)函數(shù)根據(jù)功能可分為4類：

1)f1-f3：?jiǎn)畏搴瘮?shù)；

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

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

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

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

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

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

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

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

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

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

從表2可以看出，ESG-GA算法在函數(shù)f8、f17、f23、f26和f28上分別與MABCM、JADE-sort和EIR-DE算法取得相等成績(jī)，只有在函數(shù)f4、f12和f22上比MABCM、JADE-sort和EIR-DE算法稍處于劣勢(shì)，但在其他23個(gè)基準(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分別顯示了所有算法對(duì)于100D基準(zhǔn)函數(shù)f5和f30的收斂圖，從圖3和圖4明顯可以看出，與其他4種算法相比，ESG-GA算法雖然收斂精度相差不大，但收斂速度還是明顯占優(yōu)。

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

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

3.2 真實(shí)問(wèn)題的仿真結(jié)果

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

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

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

4 結(jié)語(yǔ)

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