遺傳算法的改進(jìn)——IGA

吳偉

摘要：針對基本遺傳算法（SGA）存在的缺點，分別從參數(shù)編碼，采用三層遞階結(jié)構(gòu)的染色體編碼；適應(yīng)度函數(shù)的選取，適應(yīng)值指數(shù)比例系數(shù)自適應(yīng)調(diào)整；遺傳操作，采用最優(yōu)保存策略，自適應(yīng)選擇和交叉概率。提出了改進(jìn)的遺傳算法（IGA）。

關(guān)鍵詞：遺傳算法；編碼；適應(yīng)度函數(shù)；遺傳操作

中圖分類號：TP301文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)01-0123-03

Improved Genetic Algorithm—IGA

WU Wei1,2

(1.School of Computer Science & Technology, Soochow University, Suzhou 215104, China; 2.Suzhou Vocational University, Suzhou 215104, China)

Abstract: For the genetic algorithm deficiencies, Separately from the coding parameters, using three layers of hierarchical structure coding; fitness function selection, fitness index proportion coefficient adaptive adjustment; genetic operation, the elitist strategy, adaptive selection and the crossover probability. proposes an improved genetic algorithm(IGA).

Key words: Genetic Algorithm; coding parameters; fitness function; genetic operation

遺傳算法是一種模擬生物界自然遺傳操作的算法，該算法通過模擬生物界自然選擇、遺傳機理，在群體中進(jìn)行隨機搜索。遺傳算法的核心思想是生物界的“生存競爭，優(yōu)勝劣汰，適者生存”的機制，算法的主要特征是：遺傳操作不依賴于任何梯度信息，適合于一些傳統(tǒng)優(yōu)化算法不能解決的多目標(biāo)優(yōu)化問題和復(fù)雜優(yōu)化問題，它可以實現(xiàn)群體中個體之間的信息融合，優(yōu)勝劣汰。通過不斷的迭代，從初始種群進(jìn)化到最終的種群，從而尋找到最優(yōu)解或次優(yōu)解。遺傳算法被認(rèn)為是21世紀(jì)最為優(yōu)秀的智能優(yōu)化算法之一。

1基本遺傳算法(SGA)

SGA最主要的思想是“適者生存”，群體中適應(yīng)度值大的個體進(jìn)行選擇、遺傳操作的可能性大，群體中適應(yīng)度值小的個體就容易被淘汰，群體中的個體通過不停的進(jìn)行選擇、遺傳操作直到達(dá)到設(shè)定的迭代次數(shù)或達(dá)到設(shè)置的閾值，則結(jié)束遺傳操作，保存結(jié)果為其解或次優(yōu)解。SGA中包含如下幾個基本要素：1)染色體編碼；2)適應(yīng)度函數(shù)的設(shè)計；3)遺傳操作設(shè)計。

群體的染色體編碼是遺傳算法中第一個要解決的問題，因為它直接決定著算法的迭代次數(shù)、是否收斂、訓(xùn)練學(xué)習(xí)的效率等問題。傳統(tǒng)的二進(jìn)制編碼隨著問題加深碼串加長降低了算法的效率，而且二進(jìn)制編碼本身也不直觀、精度也不高。符號編碼不太容易實現(xiàn)交叉和變異操作。

群體適應(yīng)度函數(shù)的確定問題是一個關(guān)鍵問題，因為它的好壞直接決定遺傳算法的成功與否，即尋找到最優(yōu)解或次優(yōu)解。一般做法是將所要進(jìn)行求解的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，此法簡單易實現(xiàn)，但有一部分求解問題很難給出目標(biāo)函數(shù)的具體函數(shù)關(guān)系，即使能表達(dá)，有的函數(shù)值域分布跨度大，平均適應(yīng)度小，群體的整體適應(yīng)度低，從而增加遺傳迭代的次數(shù)，增加計算量。

遺傳操作主要是選擇、交叉和變異的設(shè)置。選擇操作是把最適應(yīng)環(huán)境的個體保存下來，遺傳給下一代來保證種群的整體適應(yīng)性。目前所采用的方法的主要思想是：若個體適應(yīng)度值越大則被選中遺傳給下一代的的概率就越大，相反個體適應(yīng)度值越小則被遺傳給下一代的的概率就越小，但此方法有可能破壞群體新個體的產(chǎn)生。遺傳操作包括交叉和變異兩項操作，其中兩者是相輔相成的關(guān)系，其中交叉是主要的操作，變異是次要的。但傳統(tǒng)的交叉和變異都是事先設(shè)定好的，不具有個體的交叉和變異概率隨適應(yīng)度值的變化而自動調(diào)節(jié)的能力。

2改進(jìn)的遺傳算法(IGA)

遺傳算法的參數(shù)編碼、適應(yīng)度函數(shù)的設(shè)計、遺傳操作，每個環(huán)節(jié)的實現(xiàn)策略的改變都會對整個遺傳算法的尋優(yōu)性能產(chǎn)生重要影響，而且需要其它環(huán)節(jié)做出相應(yīng)的調(diào)整，才能達(dá)到比較理想的提高遺傳算法尋優(yōu)能力的目的。

2.1編碼方案:將染色體設(shè)計成三層遞階結(jié)構(gòu)

在生物醫(yī)學(xué)領(lǐng)域，染色體是由控制基因和序列基因組成，控制基因來表明此染色體的作用和功能，而序列基因來實現(xiàn)它的作用和功能。我們借用此想法來實現(xiàn)遺傳算法中染色體的編碼，控制基因一般采用二進(jìn)制編碼，“1”表示下層基因被激活，其中的序列基因參加遺傳操作。“0”表示下層基因未被激活，其中的序列基因不參加任何遺傳操作。序列基因一般采用實數(shù)編碼，可根據(jù)具體

2.3遺傳操作

2.3.1最優(yōu)保存策略

采取優(yōu)秀個體策略(elitist strategy)，每代都保留幾個最為優(yōu)秀的個體不參與選擇和變異操作，但參與交叉操作。這樣能保證優(yōu)秀基因傳遞給下一代，從而群體整體性能得到提升。

遺傳算法是一個不斷迭代產(chǎn)生新個體的過程，在這個過程中可以產(chǎn)生優(yōu)秀個體，但傳統(tǒng)遺傳操作隨機性很大，可能破壞群體中最為優(yōu)秀的個體，導(dǎo)致整體性能下降。采取優(yōu)秀個體策略可以避免這個問題的出現(xiàn)，它可以把當(dāng)代中適應(yīng)度最大的個體保存下來，直接傳遞到下一代，用它來替換下一代中適應(yīng)度最小的個體。

具體操作過程如下：

第一步：當(dāng)前群體按適應(yīng)度大小進(jìn)行排序，找到適應(yīng)度最大和最小的個體。

第二步：若當(dāng)代中適應(yīng)度最大的個體比迄今為止的個體的適應(yīng)度大,則以當(dāng)代適應(yīng)度最大的個體作為新的適應(yīng)度最大的個體。第三步：用迄今為止適應(yīng)度最大的個體替代掉群體中適應(yīng)度最小的個體。

3結(jié)論

本文針對基本遺傳算法，分別從參數(shù)編碼，采用三層遞階結(jié)構(gòu)的染色體編碼；適應(yīng)度函數(shù)的選取，適應(yīng)值指數(shù)比例系數(shù)自適應(yīng)調(diào)整；遺傳操作，采用最優(yōu)保存策略，自適應(yīng)選擇和交叉概率。提出了改進(jìn)的遺傳算法（IGA）。后序工作是把IGA算法應(yīng)用到實際工作中去，來檢驗此算法的性能。

參考文獻(xiàn)：

[1] John H.Holland.Adaptation in Natural and Artificial Systems[M].MIT Press,1975

[2]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社施普林格出版社.2001.

[3]李偉超，宋大猛，陳斌，基于遺傳算法的人工神經(jīng)網(wǎng)絡(luò)[J].計算機工程與設(shè)計，2006，27(2):316-318.

[4]趙宏偉,藏雪柏,王立江,凌興宏.用于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化的改進(jìn)遺傳算法[J].計算機研究與發(fā)展(增刊).2000,37(10):244-248.

[5]李方方,趙英凱,許必熙.基于遞階遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)的研究[J].機械與電子，2006，(2):41-44.

[6]趙淑海,邱洪澤,馬自謙.基于偽并行混合遺傳算法的神經(jīng)網(wǎng)絡(luò)優(yōu)化[J].計算機工程與設(shè)計,2006,27(13):2345-2347.

[7]王清,馬廣富,彌曼.一種基于遺傳算法的神經(jīng)網(wǎng)絡(luò)控制方法研究[J].系統(tǒng)真學(xué)報，2006，18(4):1070-1077.

[8]何燕,肖芳,何小苑.基于自適應(yīng)遞階遺傳算法的洪水預(yù)報模型[J].微計算機信息,2007,23(16):311-313.

[9]何小娟,曾建潮,徐玉斌.基于思維進(jìn)化算法的神經(jīng)網(wǎng)絡(luò)權(quán)值與結(jié)構(gòu)優(yōu)化[J].計算機工程與科學(xué),2004,26(5):38-42.