遺傳算法存在問(wèn)題分析

孫俊麗

摘要：基于遺傳算法，分析了遺傳算法中早熟現(xiàn)象和重復(fù)基因問(wèn)題出現(xiàn)的原因，歸納了傳統(tǒng)的解決辦法，提出了有效的解決辦法。

關(guān)鍵詞：遺傳算法；早熟現(xiàn)象；重復(fù)基因

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）17-0163-02

1 遺傳算法存在問(wèn)題

1.1早熟現(xiàn)象

遺傳算法實(shí)質(zhì)上就是在基因上進(jìn)行的一系列的相關(guān)操作，即選擇、交叉和變異操作，通過(guò)選擇操作，將本代種群中適應(yīng)度較高的個(gè)體遺傳到下一代，交叉操作可以實(shí)現(xiàn)基因的重組，探索適應(yīng)度更高的個(gè)體，變異操作主要實(shí)現(xiàn)基因的突變。通過(guò)一系列的操作之后，按照進(jìn)化論中的優(yōu)勝劣汰原則，較好的個(gè)體逐漸地被進(jìn)化，較差的個(gè)體逐漸地被淘汰，得到遺傳算法所尋找的最優(yōu)解。隨著遺傳算法的進(jìn)行，部分較高適應(yīng)度的個(gè)體將會(huì)保留下來(lái)，如此進(jìn)行下去，種群中個(gè)體大部分的基因?qū)?huì)趨于一致，種群中也會(huì)存在很多相似的個(gè)體，減小了種群的多樣性。從遺傳理論上分析，遺傳算法能夠保證操作的精確度，而且算法中的群體規(guī)?？梢噪S機(jī)選取，通過(guò)一系列操作之后，種群中個(gè)體的優(yōu)秀基因肯定能夠遺傳到下一代，種群最終能夠得出最優(yōu)解。但實(shí)際上，遺傳算法實(shí)現(xiàn)是有時(shí)間限制的，而且實(shí)現(xiàn)資源也是有限的，所以實(shí)現(xiàn)過(guò)程中要考慮到群體規(guī)模的大小，遺傳算法中的這些限制可能會(huì)使群體中的個(gè)體過(guò)早地喪失多樣性。

綜上所述，遺傳算法的早熟現(xiàn)象指在遺傳算法實(shí)現(xiàn)過(guò)程中，喪失了種群個(gè)體的多樣性，使個(gè)體中的基因趨于一致，導(dǎo)致算法的搜索停止在局部，無(wú)法實(shí)現(xiàn)在全局的搜索，最終得到的是局部最優(yōu)解。

1.2重復(fù)基因問(wèn)題

遺傳算法在實(shí)現(xiàn)時(shí)，編碼方案如果采用了實(shí)數(shù)編碼，容易出現(xiàn)重復(fù)基因的問(wèn)題。重復(fù)基因主要是指在進(jìn)行交叉操作的兩個(gè)染色體中存在相同的基因，選擇交叉點(diǎn)進(jìn)行交叉之后，產(chǎn)生的新的染色體中有兩個(gè)相同的基因。

以自動(dòng)組卷問(wèn)題為例，重復(fù)基因問(wèn)題就是指在同一套試卷中有完全相同試題的出現(xiàn)。在實(shí)現(xiàn)遺傳算法時(shí)，首先要進(jìn)行初始化群體，初始群體中每個(gè)個(gè)體的產(chǎn)生都是隨機(jī)的，所以每個(gè)個(gè)體選中的試題也是隨機(jī)的，不同的個(gè)體可能會(huì)選中同一道試題。當(dāng)兩套試卷進(jìn)行交叉操作時(shí)，如果兩套試卷中含有相同的試題，而且該試題在試卷中的位置不同，或是試題在兩個(gè)個(gè)體的基因位不同，交叉點(diǎn)選在兩個(gè)基因位之間，交叉操作之后產(chǎn)生的新個(gè)體中必定會(huì)出現(xiàn)兩個(gè)相同的基因。

2 早熟現(xiàn)象原因分析及解決

遺傳算法在實(shí)際應(yīng)用中經(jīng)常出現(xiàn)早熟現(xiàn)象，出現(xiàn)早熟現(xiàn)象的原因主要有以下三點(diǎn)：

1） 群體規(guī)模

群體規(guī)模主要是指種群中的個(gè)體數(shù)量，其取值的大小影響著遺傳算法早熟現(xiàn)象的發(fā)生。當(dāng)群體規(guī)模取值較小時(shí)，雖然算法的收斂速度會(huì)很快，但是生成的具有較高適應(yīng)度的個(gè)體的數(shù)量會(huì)很少，容易造成早熟現(xiàn)象的發(fā)生；當(dāng)群體規(guī)模取值較大時(shí)，保證了參加遺傳算法的群體的多樣性，能夠產(chǎn)生具有較高適應(yīng)度的個(gè)體，增大了得到全局最優(yōu)解的可能性，但是增大了算法的計(jì)算量，降低了收斂速度。綜合考慮，群體規(guī)模的取值可以在50-100之間。

2） 選擇操作

在自然界中，選擇過(guò)程遵循著優(yōu)勝劣汰的規(guī)律，在遺傳算法中，這種規(guī)律是通過(guò)選擇算子來(lái)實(shí)現(xiàn)的。選擇操作主要是在本代種群中選擇適應(yīng)度較高的個(gè)體保留到下一代，保證遺傳算法得到最優(yōu)解。選擇操作通常使用輪盤賭選擇方法，增大了較高適應(yīng)度值的個(gè)體被遺傳的概率，但是這樣有可能淘汰掉本代種群中的最佳個(gè)體，也有可能本代中的最佳個(gè)體通過(guò)交叉和變異操作之后，以前良好的基因組合被破壞，容易出現(xiàn)早熟現(xiàn)象。

3） 交叉概率和變異概率

在遺傳算法中，通過(guò)交叉和變異的操作，保證了種群個(gè)體的多樣性。傳統(tǒng)的遺傳算法中，交叉概率和變異概率采用了固定值。如果交叉概率取值較大，提高了交叉操作的速度，同時(shí)也破壞了原來(lái)個(gè)體，算法的尋優(yōu)速度就會(huì)降低；如果交叉概率取值較小，會(huì)降低遺傳個(gè)體的破壞性，但是算法可能會(huì)過(guò)早地得到局部最優(yōu)解。如果變異概率較小，通過(guò)變異操作產(chǎn)生的新個(gè)體的數(shù)量也會(huì)變小，隨著遺傳操作的進(jìn)行，適應(yīng)度較高個(gè)體就會(huì)在群體中快速繁殖，從而出現(xiàn)局部最優(yōu)解，出現(xiàn)早熟現(xiàn)象。因此，在遺傳算法實(shí)現(xiàn)中的交叉和變異概率采用自適應(yīng)遺傳算法中的動(dòng)態(tài)交叉概率和動(dòng)態(tài)變異概率，這樣會(huì)降低早熟現(xiàn)象出現(xiàn)的概率。

3 重復(fù)基因問(wèn)題解決

解決重復(fù)基因問(wèn)題的傳統(tǒng)方法有兩種：

第一種方法是在創(chuàng)建數(shù)據(jù)表時(shí)，在試題表中增加一個(gè)字段，在初始化群體時(shí)，用該字段標(biāo)志試題是否被某個(gè)個(gè)體選中，已經(jīng)被選中的試題不能再次被選中，這樣在種群個(gè)體中避免了重復(fù)題的出現(xiàn)。但是這樣做違背了初始化的隨機(jī)性原則。

第二種方法是移動(dòng)交叉點(diǎn)，即在進(jìn)行交叉時(shí)，先判斷兩個(gè)個(gè)體中是否有重復(fù)基因出現(xiàn)，如果有重復(fù)基因的出現(xiàn)，將交叉點(diǎn)選在兩個(gè)重復(fù)基因的基因位區(qū)間之外，如果區(qū)間選在了重復(fù)基因的基因位之內(nèi)，則通過(guò)左移交叉點(diǎn)，將交叉點(diǎn)移到兩個(gè)重復(fù)基因的基因位范圍之外。

使用移動(dòng)交叉點(diǎn)的方法存在以下問(wèn)題：一是交叉操作的交叉點(diǎn)具有不確定性，如果控制交叉點(diǎn)的位置，則對(duì)交叉算子產(chǎn)生一定的破壞性；二是在本次遺傳操作中，通過(guò)移動(dòng)交叉點(diǎn)的位置避免了重復(fù)基因的出現(xiàn)，但是當(dāng)產(chǎn)生的新個(gè)體再次進(jìn)行交叉操作時(shí)，可能還會(huì)出現(xiàn)重復(fù)基因，所以此種方法對(duì)以后的交叉操作沒(méi)有作用，在以后生成的子代之間進(jìn)行交叉時(shí)，重復(fù)基因問(wèn)題還會(huì)出現(xiàn)。

在本文中，根據(jù)遺傳學(xué)中等位基因的知識(shí)，提出了一種等位基因法解決交叉操作中重復(fù)基因問(wèn)題，在進(jìn)行交叉操作時(shí)，判斷出現(xiàn)重復(fù)基因之后，將出現(xiàn)的

的重復(fù)基因換到兩個(gè)個(gè)體中相同的基因位，然后再進(jìn)行交叉操作，這樣就避免了新生成的子代中出現(xiàn)重復(fù)基因，可以不用考慮交叉點(diǎn)的位置，在任何交叉點(diǎn)都可以進(jìn)行交叉操作，等值基因法對(duì)個(gè)體的適應(yīng)度的值也沒(méi)有影響，解決了重復(fù)基因的問(wèn)題。

4 結(jié)束語(yǔ)

本文主要介紹了遺傳算法中經(jīng)常出現(xiàn)的早熟現(xiàn)象和重復(fù)基因問(wèn)題，從多方面分析了出現(xiàn)這些問(wèn)題的原因，歸納了傳統(tǒng)的解決辦法，提出了新的解決辦法，通過(guò)這些辦法，能有效地降低遺傳算法早熟現(xiàn)象和重復(fù)基因問(wèn)題的出現(xiàn)概率。

參考文獻(xiàn)：

[1] 毛秉毅.基于遺傳算法的智能組卷系統(tǒng)數(shù)據(jù)庫(kù)結(jié)構(gòu)的研究[J].計(jì)算機(jī)工程與應(yīng)用， 2003（28）：230-232.

[2] 王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社， 2002：37-38.

[3] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2001：35-36.

[4] 陳宇，陳治平.遺傳算法中編碼方案研究[J].計(jì)算機(jī)技術(shù)與自動(dòng)化，2006，25（1）：50-52.

[5] 熊偉清，魏平，趙杰退.遺傳算法的早熟現(xiàn)象研究[J].計(jì)算機(jī)應(yīng)用研究，2001（9）：83-87.