改進(jìn)遺傳算法及性能測(cè)試

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

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

0 引言

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

由于標(biāo)準(zhǔn)遺傳算法采用賭輪選擇及固定交叉、變異算子使得種群易于出現(xiàn)早熟現(xiàn)象及穩(wěn)定性差現(xiàn)象。早熟現(xiàn)象即為算法在尋找最優(yōu)解的過程中過早陷入系統(tǒng)的局部最優(yōu)中，且很難跳出局部困局尋找到全局最優(yōu)解。故本文對(duì)標(biāo)準(zhǔn)的遺傳算法進(jìn)行改進(jìn)，在選擇操作時(shí)，將部分較優(yōu)個(gè)體直接復(fù)制留下，剩余個(gè)體隨機(jī)選擇且只留下隨機(jī)選擇的兩個(gè)個(gè)體中適應(yīng)度較好的個(gè)體；對(duì)于交叉變異操作，采用了動(dòng)態(tài)自適應(yīng)的交叉、變異概率。交叉、變異概率的大小與種群適應(yīng)度的大小有關(guān)。最后，利用權(quán)威檢測(cè)函數(shù)對(duì)改進(jìn)前后的遺傳算法進(jìn)行對(duì)比，通過實(shí)驗(yàn)結(jié)果顯示，改進(jìn)后的遺傳算法收斂性及穩(wěn)定性大大高于標(biāo)準(zhǔn)遺傳算法，且改進(jìn)后的遺傳算法不會(huì)出現(xiàn)早熟現(xiàn)象。

1 改進(jìn)遺傳算法具體方案

1.1 改進(jìn)選擇算子

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

1.2 改進(jìn)交叉與變異算子

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

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

(1)

圖1 sigmoid函數(shù)曲線

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

(2)

(3)

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

從公式中可以看出，不同代個(gè)體的交叉、變異的概率并不相同，它們的交叉、變異概率與種群適應(yīng)度緊密相關(guān)。個(gè)體的交叉、變異概率根據(jù)種群適應(yīng)度的變化作動(dòng)態(tài)的自適應(yīng)調(diào)節(jié)。

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

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

圖2 遺傳算法流程圖

3 性能測(cè)試

3.1 常見的測(cè)試函數(shù)

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

表1 測(cè)試函數(shù)表達(dá)式

1) Rastrigin函數(shù)

Rastrigin函數(shù)有許多局部最小值，但該函數(shù)只有1個(gè)全局最小值在(0，0)點(diǎn)處取得，其對(duì)應(yīng)最小函數(shù)值為0，對(duì)于其他異于點(diǎn)(0，0)的Rastrigin函數(shù)值均>0。Rastrigin函數(shù)的三維圖如圖3所示。

圖3 Rastrigin函數(shù)三維圖

2) shubert函數(shù)

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

圖4 shubert函數(shù)三維圖

3) schaffer函數(shù)

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

圖5 schaffer函數(shù)三維圖

3.2 測(cè)試結(jié)果

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

1) Rastrigin函數(shù)測(cè)試結(jié)果

標(biāo)準(zhǔn)算法與改進(jìn)后的算法均隨機(jī)產(chǎn)生50個(gè)種群個(gè)體進(jìn)化40代，每代最佳個(gè)體的適應(yīng)值隨進(jìn)化代數(shù)的變化曲線如圖6、圖7所示。圖6為標(biāo)準(zhǔn)遺傳算法的進(jìn)化過程，圖7為改進(jìn)后的遺傳算法的進(jìn)化過程。改進(jìn)前后算法均仿真15次，觀察15次算法尋優(yōu)過程。

圖6 標(biāo)準(zhǔn)遺傳算法的進(jìn)化過程

圖7 改進(jìn)后遺傳算法的進(jìn)化過程

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

2) shubert函數(shù)

兩種算法均循環(huán)15次，每次循環(huán)隨機(jī)產(chǎn)生的50個(gè)種群個(gè)體進(jìn)化40代，其中每代最佳個(gè)體的適應(yīng)值隨進(jìn)化代數(shù)的變化曲線圖如圖8、圖9所示，圖中每條曲線代表一次算法的尋優(yōu)過程。圖8為標(biāo)準(zhǔn)遺傳算法的進(jìn)化過程，圖9為改進(jìn)后的遺傳算法的進(jìn)化過程。

圖8 標(biāo)準(zhǔn)遺傳算法的進(jìn)化過程

圖9 改進(jìn)后遺傳算法的進(jìn)化過程

從shubert函數(shù)的三維圖可以看出，該函數(shù)有無數(shù)個(gè)極小值，且每個(gè)最小值都是很高的峰值，對(duì)于檢測(cè)算法是否具有全局收斂性具有很好的權(quán)威性，若算法的進(jìn)化不能實(shí)現(xiàn)全局搜索，進(jìn)化過程中個(gè)體易陷入局部最值中。通過實(shí)驗(yàn)最佳個(gè)體適應(yīng)度值隨進(jìn)化代數(shù)的曲線圖可以看出，標(biāo)準(zhǔn)遺傳算法15次的進(jìn)化結(jié)果，尋找到的最優(yōu)解并不收斂，結(jié)果停滯在不同的值，而改進(jìn)后的遺傳算法15次的仿真最終結(jié)果均收斂于shubert函數(shù)的全局最優(yōu)解值-186.34，且均在進(jìn)化35代左右趨于穩(wěn)定。結(jié)果表明標(biāo)準(zhǔn)遺傳算法存在早熟現(xiàn)象，對(duì)于復(fù)雜問題并不能很好地尋找到全局最優(yōu)，而改進(jìn)后的遺傳算法具有很好的收斂性，不會(huì)陷入局部最優(yōu)。

3) schaffer函數(shù)

改進(jìn)前后兩種算法均循環(huán)15次，每次循環(huán)隨機(jī)產(chǎn)生50個(gè)種群個(gè)體然后進(jìn)化40代，其中每代最佳個(gè)體的適應(yīng)值隨進(jìn)化代數(shù)的變化曲線圖如圖10、圖11所示。圖中每條曲線代表一次算法的尋優(yōu)過程。圖10為標(biāo)準(zhǔn)遺傳算法的進(jìn)化過程，圖11為改進(jìn)后的遺傳算法的進(jìn)化過程。

圖10 標(biāo)準(zhǔn)遺傳算法的進(jìn)化過程

圖11 改進(jìn)后遺傳算法的進(jìn)化過程

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

從3個(gè)權(quán)威檢測(cè)函數(shù)可以看出標(biāo)準(zhǔn)遺傳算法[13-14]對(duì)于處理復(fù)雜問題存在很大的局限性，而改進(jìn)后的遺傳算法均能快速準(zhǔn)確地尋找到全局最優(yōu)值，能夠很好地處理求解復(fù)雜問題。

4 結(jié)語

本文通過改變遺傳算法中選擇、交叉、變異3個(gè)算子對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行改進(jìn)，并利用Rastrigin函數(shù)、shubert函數(shù)及shaffer函數(shù)3個(gè)典型測(cè)試函數(shù)對(duì)改進(jìn)的遺傳算法與標(biāo)準(zhǔn)遺傳算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明，標(biāo)準(zhǔn)算法對(duì)于處理較復(fù)雜問題存在很大的局限性，而改進(jìn)后的遺傳算法具有更快的收斂速度和更好的穩(wěn)定性，比標(biāo)準(zhǔn)遺傳算法更易快速尋找全局最優(yōu)解而且不易陷入局部最優(yōu)中。