改進遺傳算法及性能測試

尚宇晴，左錢，王騰，李亦民，夏津

(上海機電工程研究所，上海 201100)

0 引言

遺傳算法(genetic algorithm, GA)是由自然界生物遺傳進化準則“物競天擇、適者生存”得到的啟發而進行的計算機模擬研究。由美國Michigan大學的HOLLAND教授創造的一種基于Mendel生物遺傳與Darwin進化機制的能解算復雜體系最優解的優化技術[1-2]。1967年，BAGLEY率先在論文中使用“遺傳算法”這一概念[3]。20世紀70年代，DE Jong運用遺傳算法理論進行數值函數最優值的求解嘗試。20世紀80年代GOLDBERG概括總結得出遺傳算法的基本結構布局。遺傳算法是借用生物遺傳學的觀點[4]，從待解決的問題中可能存在解的一個種群開始，通過選擇、交叉、變異等遺傳操作提高個體的適應度，進化種群，從而得出最佳個體。其中每個個體表現性是由各自攜帶的基因類型而決定的。多個個體組成一個種群，而各個體的最佳程度通過適應度來評價，并將其適應度作為后續遺傳操作的依據。標準遺傳算法采用賭輪選擇機理，每個個體被選擇的概率與其各自適應度的大小有關，適應度越高被選中的幾率越大，以便后續采用固定數值的交叉、變異概率算子進化種群。

由于標準遺傳算法采用賭輪選擇及固定交叉、變異算子使得種群易于出現早熟現象及穩定性差現象。早熟現象即為算法在尋找最優解的過程中過早陷入系統的局部最優中，且很難跳出局部困局尋找到全局最優解。故本文對標準的遺傳算法進行改進，在選擇操作時，將部分較優個體直接復制留下，剩余個體隨機選擇且只留下隨機選擇的兩個個體中適應度較好的個體；對于交叉變異操作，采用了動態自適應的交叉、變異概率。交叉、變異概率的大小與種群適應度的大小有關。最后，利用權威檢測函數對改進前后的遺傳算法進行對比，通過實驗結果顯示，改進后的遺傳算法收斂性及穩定性大大高于標準遺傳算法，且改進后的遺傳算法不會出現早熟現象。

1 改進遺傳算法具體方案

1.1 改進選擇算子

采用常規的輪盤賭選擇法，每個個體被選中的概率與其適應度高低成正比。適應度越高的個體被選中的機會越大，但由于選擇操作過程中的隨機性，可能導致最優個體未被選擇，而適應度較差的個體可能多次被選中，無法實現遺傳算法的優勝劣汰的原則，而且在種群進化一定代數后，因種群中的個體適應度很相近，若再采用輪盤賭選擇種群時會導致種群進化停滯。故現改進種群的選擇操作，在進行選擇個體時，先將種群個體按照適應度的大小進行排序[5]，取位于優勢位置前1/4的個體直接選擇復制于下一代，新種群剩余3/4的個體進行隨機選擇。具體方式為隨機選擇兩個個體，比較其適應度大小，選擇兩者中較優個體。這樣操作大大提高了適應度，較高個體占據了種群的比例且不失種群的多樣性，使得遺傳算法更高效實用。

1.2 改進交叉與變異算子

遺傳算法中的交叉概率Pc和變異概率Pm對算法的收斂性有很大的影響[6-7]。Pc、Pm值較大易于產生新的個體，但過大使得個體的基因易于破壞，可能會改變適應度較高個體的基因，從而使得原本適應度較高的個體適應度變差，不易于種群的進化；而Pc、Pm過小不易產生新的個體，可能無法保證種群的多樣性。根據種群進化的特點，在進化的初期，種群平均適應度普遍偏低，需要產生較多的新個體以便快速地尋找到最佳個體。在進化的后期，種群平均適應度普遍偏高，個體很接近于最佳個體，若再采用較大的交叉、變異概率會使得適應度高的個體特征被破壞。故采用固定的交叉、變異概率不利于根據種群的實際情況而進行進化種群。

現對標準遺傳算法中固定的交叉、變異概率進行改進，采用動態自適應的交叉、變異概率值進行進化[8-9]。在進化的前期，種群的差異性很大，即種群適應度的方差較大，故可通過增大交叉概率Pc保證種群的多樣性，而此時種群在進化過程無需變異概率Pm很高，以保證種群在進化過程的高效性；在進化的后期，種群差異較小，種群適應度很接近，即種群適應度的方差較小，為了找到全局最優解、避免種群尋優陷入局部最值中，應使得種群的變異概率Pm提高，以便獲得不同的個體，而此時由于個體很接近，種群進化的交叉概率Pc無需過高。故可根據種群在進化過程適應度的變化特點，利用方差來滿足種群進化過程前后期對交叉、變異概率值的不同要求。現引入了S型增長曲線sigmoid函數，函數圖形如圖1所示，從圖中可以明顯看出該函數的非線性，其表達式如式(1)所示。

(1)

圖1 sigmoid函數曲線

sigmoid函數當自變量>0時，值域為[0.5,1)。當自變量為0時，函數值為0.5；當自變量趨于10時，該函數值趨于1，且該函數呈現明顯的非線性：在自變量>0的情況下，自變量較小時，斜率較大；隨著自變量增加，函數斜率減小。故可利用sigmoid函數的非線性，結合遺傳算法進化特點與sigmoid函數值域情況，編制進化過程中的交叉概率公式如式(2)，變異概率公式如式(3)所示。

(2)

(3)

其中：Pc、Pm為需要進行交叉、變異操作個體的交叉、變異概率；Pc max、Pm max為該個體所在種群最大交叉、變異概率；Pc min、Pm min為該個體所在種群最小交叉、變異概率；k2的取值根據sigmoid函數的特點可選為10，k1的取值可根據需要解決的實際問題自行定義，用于修飾種群的方差。交叉概率Pc和變異概率Pm根據種群適應度方差的改變而作動態的自適應調整。在進化初期，種群個體差異性較大即種群適應度的方差較大，故交叉概率Pc較大、變異概率Pm較小，種群通過較大的交叉概率增加種群的多樣性；在進化后期，種群個體差異性較小即種群適應度的方差較小，故交叉概率Pc較小、變異概率Pm較大，種群通過較高的變異概率產生新個體。

從公式中可以看出，不同代個體的交叉、變異的概率并不相同，它們的交叉、變異概率與種群適應度緊密相關。個體的交叉、變異概率根據種群適應度的變化作動態的自適應調節。

2 算法的收斂性(精英保留)

在遺傳算法中，通過交叉、變異操作產生新的個體，隨著群體的進化會產生越來越多的優良個體，但由于選擇、交叉及變異操作的隨機性會使得當前最優個體有可能被破壞，而這種情況對進化是不利的，影響算法的運行效率與收斂性。故為了確保種群在進化過程的收斂性，DE Jong博士針對遺傳算法提出精英選擇(elitist selection or elitism)策略，也稱精英保留(elitist preservation)策略[10-11]。該策略的思想是迄今出現的最優個體，且不進行交叉、變異操作直接復制到下一代中。精英個體是迄今為止所有個體中適應度最高的個體，該個體所代表的特征就是解決問題的最優解，而采用精英保留策略可以很大程度上改善算法的收斂性，能夠確保最優個體的特征在進化的過程中不會被破壞。RUDOLPH已經從理論上證明了采用精英保留策略可以保證算法的全局收斂性。其中，遺傳算法流程圖如圖2所示。

圖2 遺傳算法流程圖

3 性能測試

3.1 常見的測試函數

常見的測試函數很多[4,12]，本文通過Rastrigin函數、shubert函數及schaffer函數這3個典型測試函數對改進后的遺傳算法進行檢測。從函數的三維圖可以看出這3個函數都存在很多的局部最值，若算法存在早熟現象的話，很容易收斂于這些局部最值中且停止進化。故可以通過此3個函數對改進后的遺傳算法與標準遺傳算法的收斂性及穩定性進行比較并測試改進后的遺傳算法的性能。3個測試函數的表達式如表1所示。

表1 測試函數表達式

1) Rastrigin函數

Rastrigin函數有許多局部最小值，但該函數只有1個全局最小值在(0，0)點處取得，其對應最小函數值為0，對于其他異于點(0，0)的Rastrigin函數值均>0。Rastrigin函數的三維圖如圖3所示。

圖3 Rastrigin函數三維圖

2) shubert函數

shubert函數為復雜函數，存在760個局部極小值，只有在點(-1.42513，-0.80032)處取得全局最小值為-186.34。shubert函數的三維示意圖如圖4所示。

圖4 shubert函數三維圖

3) schaffer函數

schaffer函數有無數個極大值點，只有在點(0，0)處取得全局最大值，其最大值為1。且函數在最大值周圍存在一圓脊，它們的取值均為0.990283，故很容易陷入此局部極小值中。schaffer函數的三維示意圖如圖5所示。

圖5 schaffer函數三維圖

3.2 測試結果

對于標準遺傳算法采用輪盤賭進行選擇、0.9的交叉概率和0.3的變異概率進行編程。對于改進后的遺傳算法交叉概率范圍為0.9～0.5，其中Pc max=0.9、Pc min=0.5；變異概率范圍為0.2～0.001，其中Pm max=0.2、Pm min=0.001；用改進后的遺傳算法與標準遺傳分別對Rastrigin函數、shubert函數及schaffer函數3個函數尋找最值。為了使實驗具有說服力，每種算法分別對每個函數實驗15次，每次實驗均隨機產生50個種群個體進化40代，得出每代最佳個體的適應值隨進化代數的變化曲線圖，其中個體的適應度即為每個個體對應的函數值，從而通過實驗結果比較改進前后遺傳算法的差距并得出改進后遺傳算法的性能。

1) Rastrigin函數測試結果

標準算法與改進后的算法均隨機產生50個種群個體進化40代，每代最佳個體的適應值隨進化代數的變化曲線如圖6、圖7所示。圖6為標準遺傳算法的進化過程，圖7為改進后的遺傳算法的進化過程。改進前后算法均仿真15次，觀察15次算法尋優過程。

圖6 標準遺傳算法的進化過程

圖7 改進后遺傳算法的進化過程

從Rastrigin函數的三維圖可以看出，函數在最優值附近有很多小峰值且最優值很接近于全局最優值，若算法不具備很好的收斂性，會在最優解附近停滯，極易收斂于局部最優值中。從實驗仿真結果可以看出，雖然標準遺傳算法尋找到的最優值很接近于全局最優值，但根據此函數的特點可以看出該算法非收斂該函數的全局最優值，而是尋找到Rastrigin函數最優值附近小峰值的局部最優值。而改進后的算法尋找最優值均為0與該函數最優值一致，且多次仿真均在進化20代時趨于穩定，說明改進后的遺傳算法具有很好的全局收斂性且收斂速度較快，而且具有很好的穩定性。

2) shubert函數

兩種算法均循環15次，每次循環隨機產生的50個種群個體進化40代，其中每代最佳個體的適應值隨進化代數的變化曲線圖如圖8、圖9所示，圖中每條曲線代表一次算法的尋優過程。圖8為標準遺傳算法的進化過程，圖9為改進后的遺傳算法的進化過程。

圖8 標準遺傳算法的進化過程

圖9 改進后遺傳算法的進化過程

從shubert函數的三維圖可以看出，該函數有無數個極小值，且每個最小值都是很高的峰值，對于檢測算法是否具有全局收斂性具有很好的權威性，若算法的進化不能實現全局搜索，進化過程中個體易陷入局部最值中。通過實驗最佳個體適應度值隨進化代數的曲線圖可以看出，標準遺傳算法15次的進化結果，尋找到的最優解并不收斂，結果停滯在不同的值，而改進后的遺傳算法15次的仿真最終結果均收斂于shubert函數的全局最優解值-186.34，且均在進化35代左右趨于穩定。結果表明標準遺傳算法存在早熟現象，對于復雜問題并不能很好地尋找到全局最優，而改進后的遺傳算法具有很好的收斂性，不會陷入局部最優。

3) schaffer函數

改進前后兩種算法均循環15次，每次循環隨機產生50個種群個體然后進化40代，其中每代最佳個體的適應值隨進化代數的變化曲線圖如圖10、圖11所示。圖中每條曲線代表一次算法的尋優過程。圖10為標準遺傳算法的進化過程，圖11為改進后的遺傳算法的進化過程。

圖10 標準遺傳算法的進化過程

圖11 改進后遺傳算法的進化過程

從schaffer函數的三維圖可以看出，該函數有無數個極大值，且存在于最優點(0，0)周圍一圈，無論算法從任何方向進行進化至最優值均會通過此圓脊，若函數進化能力有限會很容易收斂至局部最值0.990283而停止進化至全局最優值1。從實驗結果可以看出，標準遺傳算法多次進化收斂于局部最值0.990283，說明標準遺傳算法存在早熟現象。而改進后的遺傳算法在進化>35代之后均收斂于全局最優值1。

從3個權威檢測函數可以看出標準遺傳算法[13-14]對于處理復雜問題存在很大的局限性，而改進后的遺傳算法均能快速準確地尋找到全局最優值，能夠很好地處理求解復雜問題。

4 結語

本文通過改變遺傳算法中選擇、交叉、變異3個算子對標準遺傳算法進行改進，并利用Rastrigin函數、shubert函數及shaffer函數3個典型測試函數對改進的遺傳算法與標準遺傳算法進行比較，實驗結果表明，標準算法對于處理較復雜問題存在很大的局限性，而改進后的遺傳算法具有更快的收斂速度和更好的穩定性，比標準遺傳算法更易快速尋找全局最優解而且不易陷入局部最優中。