基于最優(yōu)保留策略的改進(jìn)遺傳算法

梁興建，詹志輝，譚 偉，彭建新

（1.四川理工學(xué)院 計算機學(xué)院，四川 自貢643000；2.中山大學(xué) 計算機科學(xué)系，廣東 廣州510006；3.東莞理工學(xué)院 計算機學(xué)院，廣東 東莞523106；4.廣東警官學(xué)院 計算機系，廣東 廣州510230）

0 引 言

遺傳算法 （genetic algorithm，GA）過程簡單、易于操作，具有較強的健壯性和普適性，在多個領(lǐng)域取得了成功的應(yīng)用。但是作為以群體進(jìn)化為基礎(chǔ)的算法，收斂速度慢和易早熟收斂兩個缺陷不可避免［1－8］。因此，改進(jìn)遺傳算法成為近年來研究的熱點，改進(jìn)策略可歸結(jié)為以下幾個方面：對選擇算子的改進(jìn)［3，4］、對交配算子的改進(jìn)［5］、對變異算子的改進(jìn)［6］、對交配和變異參數(shù)自適應(yīng)控制［7］、與其它優(yōu)化算法混合［2，8，9］等。從文獻(xiàn)結(jié)果上看，大多數(shù)改進(jìn)方法對加快收斂速度和提升求解精度都有一定幫助，但是有的改進(jìn)方法對求解精度的提高仍然不大，有的則花費較大的系統(tǒng)開銷來提升算法效果，遺傳算法在上述問題中還有較大的改進(jìn)空間。

為了進(jìn)一步提升收斂速度和提高解的精度，本文提出了一種基于最優(yōu)保留策略的改進(jìn)遺傳算法 （elitist reserved GA，ERGA），算法首先對選擇算子進(jìn)行改進(jìn)，在進(jìn)化過程中加強個體優(yōu)勝劣汰的思想，保障最優(yōu)個體的基因能迅速向后代傳播，從而使整個群體逐步朝著最優(yōu)方向發(fā)展。然而，保留最優(yōu)個體策略通常存在種群多樣性快速降低的問題。因此，本文在保留最優(yōu)策略的基礎(chǔ)上進(jìn)一步通過對變異算子的優(yōu)化，不斷產(chǎn)生優(yōu)質(zhì)基因，既能提高個體的適應(yīng)值，又能提升種群多樣性。本文提出的改進(jìn)遺傳算法通過對選擇算子和變異算子的改進(jìn)，能更好地平衡算法收斂性和多樣性，在保證種群多樣性的同時加快算法的收斂速度，最終能快速找到高質(zhì)量的解。本文對8個基準(zhǔn)測試函數(shù)進(jìn)行了仿真實驗，數(shù)據(jù)的比較和分析結(jié)果表明，本文改進(jìn)算法在收斂速度與全局尋優(yōu)上有較大的改善。

1 遺傳算法的基本思想

作為生物進(jìn)化論和遺傳規(guī)律在計算機上的模擬，標(biāo)準(zhǔn)遺傳算法 （standard GA，SGA）主要涉及染色體編碼、群體初始化、適應(yīng)值評價、種群選擇算子、染色體交配算子、變異算子等概念。

（1）染色體編碼

染色體通常用于表示問題的解空間，染色體編碼方法主要有：雷格碼編碼、字母編碼、二進(jìn)制編碼、浮點數(shù)編碼、多參數(shù)交叉編碼等，根據(jù)不同的問題采用不同的編碼方式。本文用于求解函數(shù)優(yōu)化問題，因而采用浮點數(shù)編碼，此時，染色體的長度為問題定義的解的變量個數(shù)，每個基因即為每一維變量，如待求解問題的一個有效解為Xi＝ （，，…，，），其中D 為變量的維數(shù)（即染色體長度），則該解的對應(yīng)的染色體編碼為（，，…，，）。

（2）群體初始化

初始化是對染色體的每一個基因賦初值，通常采用的是隨機數(shù)初始方法，依次為染色體每一維變量設(shè)定初始值，初始值應(yīng)處于一個合理的空間范圍。假設(shè)上述問題的每一個維度的搜索范圍都是 ［－10，10］，則某個染色體初始值隨機取值可能為Xi＝（3.21，－4.18，…，－6.25，2.47）。

（3）適應(yīng)值評價

適應(yīng)值評價主要是通過評估函數(shù)計算各個染色體的適應(yīng)值，從而區(qū)分染色體的優(yōu)劣，評估函數(shù)通常根據(jù)問題的優(yōu)化目標(biāo)來確定［10］。對于求解函數(shù)優(yōu)化問題，直接可利用問題定義的目標(biāo)函數(shù)作為評估函數(shù)的原型。由于標(biāo)準(zhǔn)遺傳算法采用輪盤賭的方法對種群進(jìn)行篩選，因此染色體的適應(yīng)值越大越容易被選擇。然而本文主要針對最小值優(yōu)化的函數(shù)進(jìn)行求解，因此對于此類目標(biāo)函數(shù)f（X），應(yīng)采用取負(fù)數(shù)、取倒數(shù)等方式得到評估函數(shù)Eval（C），為了使后一步輪盤賭的概率更合理，本文采用文獻(xiàn) ［11］提供的公式計算適應(yīng)值

式中：X——一個有效解，C——X 對應(yīng)的染色體，op——f（X）的理論最小值。

（4）種群選擇算子

種群的選擇是一個非常重要的步驟，需要從現(xiàn)有種群擇優(yōu)選出下一代染色體的群體 ｛C1，C2，C3，…，Cn｝，原則是既要保證讓下一代的種群更優(yōu)，又要保證種群多樣化。通常的選擇算法有輪盤賭選擇算法、錦標(biāo)賽選擇算法等。輪盤賭選擇的核心思想是根據(jù)染色體的適應(yīng)值，計算出每個染色體適應(yīng)值與群體種適應(yīng)值總和的比P，然后以P 為概率隨機選擇下一代種群。錦標(biāo)賽選擇的核心思想則是，一次隨機抽出若干個染色體，并將這組染色體中適應(yīng)值最大的一個選入下一代。這2種選擇算子各有優(yōu)缺點，輪盤賭選擇的優(yōu)點是根據(jù)隨機概率，既能保證優(yōu)先選擇適應(yīng)值大的，又能給較差的染色體一些生存空間，但事實上，由于選擇的隨機性，可能最優(yōu)的染色體一次都沒有選擇，而最差的卻多次被選擇。錦標(biāo)賽選擇能最大的保證優(yōu)勝劣汰，但是由于適應(yīng)值較小的染色體淘汰速度過快，而容易使種群多樣化迅速減小從而產(chǎn)生早熟。本文結(jié)合保留最優(yōu)策略和輪盤賭選擇方法對種群選擇算子進(jìn)行改進(jìn)。

（5）染色體交配算子

染色體根據(jù)交配概率Pc決定是否參與交配，不參與的直接放入下一代，需參與交配的，每2個染色體交換各自的部分基因形成2個新的子代染色體。交配算子的改進(jìn)主要從2個方面進(jìn)行：其一是交配概率Pc的取值，Pc一般取值0.4～0.99，也有研究人員采用自適應(yīng)方法在運行過程中臨時調(diào)整Pc值；其二是交配方式，主要有單點交配、多點交配、均勻交配、循環(huán)交配等。本文對交配概率Pc采用固定值，交配方式采用隨機單點交配。

（6）種群變異算子

在交配過程結(jié)束后，所有染色體根據(jù)變異概率Pm決定是否變異，需要變異的染色體，隨機抽取一個位置的基因，將其數(shù)值改為新的隨機值。變異的優(yōu)點是能提高種群的多樣性，有效防止早熟，但是在已經(jīng)有較優(yōu)解的時候，隨意變異常常又會使結(jié)果變差。因此變異概率Pm通常設(shè)為0.001～0.1之間，本文改進(jìn)的另一個重點就是如何讓變異既能防止早熟，又能使子代變得更優(yōu)。

2 改進(jìn)具體方案

本改進(jìn)算法的思路是基于最優(yōu)保留策略對選擇算子進(jìn)行改進(jìn)，然后采用對變異算子的優(yōu)化，在全局范圍不斷探索最優(yōu)解，并且保持種群多樣性。本算法的總體流程如圖1所示。

2.1 基于最優(yōu)保留策略的改進(jìn)選擇算子

圖1 改進(jìn)遺傳算法總體流程

采用常規(guī)輪盤賭選擇過程，從概率角度上看，個體被選擇機會與適應(yīng)值高低成正比，適應(yīng)值高的選擇機會大，適應(yīng)值低的也有一定的被選擇的機會。但事實上由于個體選擇概率具有不準(zhǔn)確性和選擇過于隨機性，可能導(dǎo)致最優(yōu)個體一次都沒有選上，而較差個體卻被選上多次。這與生物進(jìn)化理論背道而馳，因此本算法在新群體選擇中注重優(yōu)勝劣汰思想，使群體朝著更優(yōu)化的方向發(fā)展。選擇過程改進(jìn)思路如下：

（1）保留最優(yōu)個體策略

為了有效保留上一代的最優(yōu)個體，并能讓最優(yōu)個體參與交配，以探索出更優(yōu)個體，改進(jìn)以往保存最優(yōu)的策略，要求C1、C2、Cn都選擇上一代的最優(yōu)個體，其中：C1不參與交配，主要用于保存上代最優(yōu)個體并完成更優(yōu)變異；C2將必須參與交配；Cn按交配概率Pc參與交配。C2與Cn分開是為了將上代最優(yōu)個體的優(yōu)秀基因散播得更廣。

（2）其它個體選擇策略

對新的 ｛C3，C4，…，Cn－1｝個體群，采用輪盤賭方式依次選擇，但如果選擇到上一代最差個體，則放棄重選，以達(dá)到優(yōu)勝劣汰的目的。選擇后的 ｛C3，C4，…，Cn－1｝個體群將按交配概率Pc決定是否參與交配。

2.2 變異算子改進(jìn)

在個體交配完畢之后，需要對某些個體進(jìn)行變異操作。采用常規(guī)變異方法，由于數(shù)據(jù)取值范圍大，如果變更某個體的基因太過隨機，反而會造成個體的適應(yīng)值變低，尤其是隨著進(jìn)化代數(shù)的增加，隨機變異所起的負(fù)面作用將越來越高，因此通常采用降低遺傳概率Pm來解決這個問題，但降低遺傳概率實際上也會降低種群數(shù)量，導(dǎo)致早熟收斂。

為了解決此矛盾，本算法除了常規(guī)變異以外，還針對上一代最優(yōu)個體C1進(jìn)行優(yōu)化變異，使該個體適應(yīng)值能優(yōu)于上一代，從而加快收斂速度。變異過程改進(jìn)思路如下：

（1）首先對群體 ｛C2，C3，…，Cn｝依次變異，按照變異概率Pm隨機選擇參加變異的個體，在隨機位置進(jìn)行基因修改，這有利于搜索到更好地基因，又不會造成對最優(yōu)個體的破壞；

（2）C1保存的是上一代最優(yōu)個體，進(jìn)行優(yōu)化變異，變異過程通過以下4個步驟完成：

步驟1 確立變異基因位置。C1本是保留的上代最優(yōu)個體，隨機位置變異很容易造成適應(yīng)值降低，因此對最優(yōu)個體不再適合采用隨機位置變異，同時為了使C1在前幾代變異的基因得以保留，本改進(jìn)采用基因循環(huán)變異方式，即選擇上一代結(jié)束變異位置Lflag作為本次變異初始位置Lmutate。

步驟2 重新確定變異數(shù)據(jù)搜索空間S。為了避免全局范圍盲目取值破壞到優(yōu)秀基因，本算法對取值范圍逐漸縮減，即首先在整個群體中搜索Lmutate位置的基因最小值gmin和最大值gmax。由gmin和gmax構(gòu)成搜索空間，能很大程度地縮小范圍，但隨著進(jìn)化代數(shù)的增加，很容易收斂到局部最優(yōu) （即gmin＝gmax）。為了避免該問題，通過式 （2）、式（3）將搜索范圍的進(jìn)行擴大，得到最終的搜索空間為S∈（rangemin，rangemax）

步驟3 得到變異數(shù)據(jù)并執(zhí)行變異。在搜索空間S 中隨機得到一個變異數(shù)據(jù)r，由數(shù)據(jù)r去替換Lmutate位置的基因數(shù)據(jù)。

步驟4 確定變異是否成功。通過步驟3 執(zhí)行變異之后，對個體C1進(jìn)行一次適應(yīng)值評價，并與上一代最優(yōu)適應(yīng)值Vmax比較，若優(yōu)于Vmax，則變異成功，記錄本代變異位置為Lflag＝Lmutate＋1，結(jié)束整個變異過程；反之，若變異之后適應(yīng)值比上一代更差，則先將該位置基因還原，調(diào)整變異位置Lmutate＝Lmutate＋1，轉(zhuǎn)向步驟2對下一位置的基因進(jìn)行變異，直到所有基因都試探過，回到初始位置 （即Lmutate＝Lflag），則本次變異失敗，結(jié)束整個變異過程。

3 實驗驗證和結(jié)果對比

3.1 基準(zhǔn)函數(shù)說明

表1列出了用于實驗測試的8 個基準(zhǔn)函數(shù)［4］，這些函數(shù)可分為2組，前4個為是單峰函數(shù)，后4個是多峰函數(shù)，其中多峰函數(shù)存在多個局部最優(yōu)解。另外，在表1中還給出了測試的基因維數(shù)D （第三列），基因數(shù)據(jù)的搜索空間（第四列），該函數(shù)對應(yīng)的全局最優(yōu)值fmin（第五列），由于進(jìn)化計算是不確定算法，對每個函數(shù)都設(shè)定了可接受精度（第六列），如果能夠得到介于可接受值和最佳值之間的結(jié)果，都可判定為成功，最后一列是函數(shù)的名稱。

表1 用于實驗測試的8個基準(zhǔn)函數(shù)

由于本改進(jìn)在完成變異的時候會多次調(diào)用適應(yīng)值評價函數(shù)，而調(diào)用適應(yīng)值評價函數(shù)消耗系統(tǒng)資源量較大，因此為了公平的與其它算法比較，所有算法都采用最大適應(yīng)值評價次數(shù)為100萬次作為循環(huán)結(jié)束條件。同時，為了減少統(tǒng)計誤差，每個算法在每個函數(shù)上測試30次，分別取出最優(yōu)值、平均值、最差值進(jìn)行比較。

3.2 結(jié)果比較與分析

為了對比本改進(jìn)算法的優(yōu)化程度，將本算法 （ERGA）的運行結(jié)果與標(biāo)準(zhǔn)遺傳算法 （SGA）、文獻(xiàn) ［4］提出的改進(jìn)算法 （命名為improved GA，IGA）的結(jié)果進(jìn)行比較。本比較所采用的測試函數(shù)、停止準(zhǔn)則均與文獻(xiàn)［4］相同，其中每個函數(shù)對應(yīng)搜索空間詳見表1、基因長度 （維數(shù)）都為30、群體規(guī)模都為50、結(jié)束條件都為評價100 萬次，ERGA 和SGA 的非特殊交配概率Pc為0.9、變異概率Pm為0.09，通過運算30 次統(tǒng)計出平均值、最優(yōu)值、最差值，實驗結(jié)果見表2，其中IGA 的結(jié)果是由文獻(xiàn) ［4］提供的，表2中粗體顯示的數(shù)據(jù)是3種算法運行結(jié)果的最優(yōu)值。

從表2單獨看本改進(jìn)算法 （ERGA）的數(shù)據(jù)情況，ERGA 對單峰函數(shù)的收斂總體上要優(yōu)于多峰函數(shù)，單峰函數(shù)f4能收斂到全局最優(yōu)、f1達(dá)到10－50數(shù)量級、f2接近10－30數(shù)量級，多峰函數(shù)除f5外都在10－10數(shù)量級左右。

從表2對3種算法結(jié)果的數(shù)據(jù)情況比較，ERGA 除了對多峰函數(shù)f5的改進(jìn)效果不如IGA 外，對其它的函數(shù)的改進(jìn)都有較好的效果，同等情況下精確程度能提高多個數(shù)量級。尤其對f1函數(shù)，SGA 和IGA 的精度最多只能達(dá)到10－4數(shù)量 級，而ERGA 能 達(dá) 到10－50數(shù) 量 級。另 外，應(yīng) 用ERGA 算法對f2函 數(shù) 能 收 斂 到10－30數(shù) 量 級 （SGA 和IGA只能達(dá)到10－2數(shù)量級），ERGA 算法對f6～f8函數(shù)均能收斂到10－10數(shù) 量 級 （SGA 是10－3數(shù) 量 級，IGA 是10－4數(shù) 量級），對f3函數(shù)雖然數(shù)量級沒有提升，但是結(jié)果精度也遠(yuǎn)高于IGA 和SGA，經(jīng)以上數(shù)據(jù)比較，說明本改進(jìn)是有利于提升遺傳算法性能的。

圖2 和圖3 是基本遺傳算法 （SGA）和本改進(jìn)算法（ERGA）對8個測試函數(shù) （f1～f8）的求解變化趨勢，圖中橫坐標(biāo)是運行過程中評估函數(shù)的調(diào)用次數(shù)，縱坐標(biāo)是相關(guān)評估次數(shù)對應(yīng)的結(jié)果，由于大部分函數(shù)在進(jìn)化前后期所得結(jié)果數(shù)量級差距太大，為了便于觀察和對比2種算法的收斂情況，除了f5函數(shù)外，都以10的數(shù)量級作為縱坐標(biāo)。

圖2是基本遺傳算法 （SGA）和本改進(jìn)算法 （ERGA）對單峰函數(shù)函數(shù)f1～f4的求解變化趨勢，從圖中可以清晰的看到，SGA 要么收斂速度慢 （如：f4），要么陷入局部最優(yōu) （如：f1～f3），而ERGA 除f3函數(shù)外，其余函數(shù)都沒有陷入局部最優(yōu)，f1和f2函數(shù)一直處于加速尋優(yōu)狀態(tài)，f4函數(shù)收斂速度最快，在7萬次評估 （約1000代）左右快速得到全局最優(yōu)值0。

圖3是SGA 和ERGA 對多峰函數(shù)f5～f8的求解變化趨勢，通過對比可發(fā)現(xiàn)，4個多峰函數(shù)應(yīng)用SGA 算法都存在過早收斂、求解精度不高的情況，而應(yīng)用ERGA 算法，f6和f7函數(shù)在評估60 000 次之后出現(xiàn)加速尋優(yōu)的情況，f8雖然在評估60 000次之后開始收斂，但是結(jié)果精確度數(shù)量級已遠(yuǎn)遠(yuǎn)高于SGA。

表2 SGA、IGA 和ERGA 求解函數(shù)實驗結(jié)果比對

圖2 SGA 和本改進(jìn)算法 （ERGA）對單峰函數(shù)函數(shù)f1～f4 的求解變化趨勢

圖3 SGA 和本改進(jìn)算法 （ERGA）對多峰函數(shù)f5～f8 的求解變化趨勢

4 結(jié)束語

為了解決遺傳算法收斂速度慢和收斂早熟2 個問題，本文提出了一種基于最優(yōu)保留策略的改進(jìn)遺傳算法，該算法同時對選擇算子和變異算子進(jìn)行改進(jìn)。選擇算子采用保留最優(yōu)策略實現(xiàn)了群體優(yōu)勝劣汰，變異算子采用最優(yōu)個體優(yōu)化變異思想，用以解決保留最優(yōu)帶來的種群下降問題，同時提升結(jié)果精度。通過對8個基準(zhǔn)函數(shù) （包括單峰、多峰函數(shù)各4個）進(jìn)行測試對比，實驗結(jié)果表明本改進(jìn)算法收斂速度快，求解精度高，對大多數(shù)函數(shù)都能避免陷入局部最優(yōu)，對遺傳算法的性能有較大的提升。在后續(xù)研究中，我們將嘗試使用自適應(yīng)控制的方法［12］和正交實驗設(shè)計方法［13］對ERGA 進(jìn)行進(jìn)一步的性能提升，并嘗試將ERGA在多目標(biāo)等優(yōu)化問題中［14］進(jìn)行應(yīng)用。

［1］ZHANG Jun，ZHAN Zhihui.Computational intelligence［M］.Beijing：Tsinghua University Press，2009：54－58 （in Chinese）.［張軍，詹志輝.計算智能 ［M］.北京：清華大學(xué)出版社，2009：54－58.］

［2］YAN Taishan.An improved genetic algorithm and its blending application with neural network ［C］／／Second International Workshop on Intelligent Systems and Applications，2010：9－12.

［3］Amarita Ritthipakdee，Arit Thammano，Nol Premasathian，et al.A new selection operator to improve the performance of genetic algorithm for optimization problems ［C］／／IEEE ICMA Conference International Scientific Advisory Board，2013：371－375.

［4］CHEN Youqing，XU Caixing，ZHONG Wenliang，et al.Genetic algorithm with improved selection operator［J］.Computer Engineering and Applications，2008，44 （2）：44－49 （in Chinese）.［陳有青，徐蔡星，鐘文亮，等.一種改進(jìn)選擇算子的遺 傳 算 法 ［J］.計 算 機 工 程 與 應(yīng) 用，2008，44 （2）：44－49.］

［5］Zhang Qiyi，Chang Shuchun.An improved crossover operator of genetic algorithm ［C］／／Second International Symposium on Computational Intelligence and Design，2009：82－86.

［6］SilvaFJM da，Sanchez PerezJM，Pulido JAG，et al.Optimizing multiple sequence alignment by improving mutation operators of a genetic algorithm ［C］／／Ninth International Conference on Intelligent Systems Design and Applications，2009：1257－1262.

［7］ZHANG Jingzhao，JIANG Tao.Improved adaptive genetic algorithm ［J］.Computer Engineering and Applications，2010，46 （11）：53－55 （in Chinese）.［張京釗，江濤.改進(jìn)的自適應(yīng)遺傳算法 ［J］.計算機工程與應(yīng)用，2010，46 （11）：53－55.］

［8］YANG Chao，WANG Zhengyong，WU Xiaohong.A core image matching algorithm based on chaos genetic algorithm and wavelet multi－resolution analysis［J］.Journal of Sichuan Uni－versity of Science ＆ Engineering （Natural Science Edition），2010，23 （6）：704－706 （in Chinese）. ［楊超，王正勇，吳曉紅.基于混沌遺傳算法與小波多分辨率分析的巖心圖像匹配［J］.四 川 理 工 學(xué) 院 學(xué) 報 （自 然 科 學(xué) 版），2010，23 （6）：704－706.］

［9］XING Xiaoshuai，CHEN Yanfang，ZHOU Li，et al.A parallel immune genetic algorithm Based on simulated annealing［C］／／International Conference on Multimedia Technology，2011：3366－3369.

［10］HE Qing，ZENG Huanglin，XIONG Xingzhong.Research on cross－layer resource allocation for OFDMA system based on genetic algorithm ［J］.Journal of Sichuan University of Science ＆ Engineering （Natural Science Edition），2012，25（5）：45－49 （in Chinese）.［何慶，曾黃麟，熊興中.一種基于遺傳算法的OFDMA 系統(tǒng)的跨層資源分配 ［J］.四川理工學(xué)院學(xué)報 （自然科學(xué)版），2012，25 （5）：45－49.］

［11］ZHANG Chen，ZHAN Zhihui.Comparisons of selection strategy in genetic algorithm ［J］.Computer Engineering and Design，2009，30 （23）：5471－5478 （in Chinese）. ［張琛，詹志輝.遺傳算法選擇策略比較 ［J］.計算機工程與設(shè)計，2009，30 （23）：5471－5478.］

［12］ZHAN Zhihui，Zhang Jun，Li Yun，et al.Adaptive particle swarm optimization ［J］.IEEE Transactions on Systems，Man，and Cybernetics－Part B，2009，39 （6）：1362－1381.

［13］ZHAN Zhihui，Zhang Jun，Li Yun，et al.Orthogonal learning particle swarm optimization ［J］.IEEE Transactions on Evolutionary Computation，2011，15 （6）：832－847.

［14］ZHAN Zhihui，Li Jingjing，Cao Jiannong，et al.Multiple populations for multiple objectives：A coevolutionary technique for solving multiobjective optimization problems ［J］.IEEE Transactions on Cybernetics，2013，43 （2）：445－463.