自適應(yīng)遺傳算法的研究

摘要：本文首先介紹了自適應(yīng)遺傳算法的發(fā)展史和基本步驟，然后對自適應(yīng)遺傳算法的編碼、適應(yīng)度計算、選擇、自適應(yīng)交叉、自適應(yīng)變異這些階段的具體實(shí)現(xiàn)方法以及近些年來對這些方面的一些經(jīng)驗(yàn)和改進(jìn)策略進(jìn)行了詳細(xì)介紹，最后，對自適應(yīng)遺傳算法的研究現(xiàn)狀以及對未來的展望做了一個簡單總結(jié)。

關(guān)鍵詞：自適應(yīng)遺傳算法；改進(jìn)方法；性能

中圖分類號：P731.2 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-3315(2011)2-175-002

一、引言

遺傳算法是由美國Michigan大學(xué)的Holland教授在1975年提出來的，它來源于達(dá)爾文的進(jìn)化理論和孟德爾、摩根的遺傳學(xué)理論，目前已在函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、圖像識別、網(wǎng)絡(luò)構(gòu)造等許多領(lǐng)域得到了廣泛的應(yīng)用。它的優(yōu)越性得到學(xué)術(shù)界的一致認(rèn)可，然而，基本遺傳算法也存在諸如局部搜索能力差，收斂速度慢等缺點(diǎn)。因此，尋找性能更優(yōu)越的新算法是研究的難點(diǎn)與熱點(diǎn)問題之一。

二、遺傳算法的發(fā)展

1.20世紀(jì)60年代，John Holland教授和他的數(shù)位博士受到生物模擬技術(shù)的啟發(fā)，認(rèn)識到自然遺傳可以轉(zhuǎn)化為人工遺傳算法。1962年John Holland提出了利用群體進(jìn)化模擬適應(yīng)性系統(tǒng)的思想，引進(jìn)了群體適應(yīng)值、選擇，變異、交叉等基本概念。

2.1967年，J.D.Ba-ely在其論文中首次提出了“遺傳算法”的概念。

3.1975年，Holland出版了《自然與人工系統(tǒng)中的適應(yīng)性行為》。該書系統(tǒng)地闡述了遺傳算法的基本理論和方法，提出了遺傳算法的基本定理—模式定理，從而奠定了遺傳算法理論基礎(chǔ)。

4.20世紀(jì)80年代初，Holland教授實(shí)現(xiàn)了第一個基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)——分類器系統(tǒng)(classifier System簡稱cs)，開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。

5.1989年，David Goldber-出版了《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》。該書全面系統(tǒng)地總結(jié)了當(dāng)時關(guān)于遺傳算法的研究成果，結(jié)合大量的實(shí)例，完整的論述了遺傳算法的基本原理及應(yīng)用，奠定了現(xiàn)代遺傳算法的基礎(chǔ)。

6.1992年，John R.Koza出版了專著，提出了遺傳編程概念，并成功把遺傳編程的方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號處理等方面。

三、自適應(yīng)遺傳算法的基本步驟

(1)初始化運(yùn)行參數(shù)；(2)初始化種群，對染色體進(jìn)行編碼；(3)計算個體的適應(yīng)度等關(guān)鍵參數(shù)；(4)判斷結(jié)束條件，當(dāng)條件滿足時，結(jié)束操作。當(dāng)不滿足時進(jìn)行以下操作：①按照某種策略從父代中選出與父代相同數(shù)目的個體形成交配池；②進(jìn)行自適應(yīng)交叉操作；③進(jìn)行自適應(yīng)變異操作；④產(chǎn)生新一代種群；(5)轉(zhuǎn)到第(3)步。

四、自適應(yīng)遺傳算法存在的問題

(1)編碼問題；(2)早熟問題；(3)收斂速度慢；(4)參數(shù)選擇；(5)不穩(wěn)定性；(6)參數(shù)計算式的選取

五、自適應(yīng)遺傳策略的研究與改進(jìn)方法

1.編碼

編碼就是把自然問題描述為編碼的形式，生成編碼的原則是：所定編碼應(yīng)當(dāng)易于生成與所求問題相關(guān)的最小字符集。目前主要的編碼技術(shù)有：一維染色體編碼、多參數(shù)映射編碼、可變?nèi)旧w長度編碼等。

2.群體規(guī)模

對于種群的規(guī)模，一般是在初始階段設(shè)定好的。復(fù)雜程度不同的問題，相應(yīng)的初始種群的設(shè)定也不同。

3.適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是評價個體適應(yīng)環(huán)境的能力，在進(jìn)行選擇操作時經(jīng)常用到，它的選取是否恰當(dāng)直接影響到遺傳算法的性能，所以就形成了很多計算適應(yīng)度的函數(shù)，改進(jìn)這些適應(yīng)度函數(shù)是為了使適應(yīng)度能更好的反應(yīng)個體的優(yōu)劣，使得適應(yīng)度低的個體被淘汰，適應(yīng)度高的個體被保留。

4.選擇算子

選擇的作用是確定將要進(jìn)行交叉的個體，現(xiàn)在常用的選擇方法很多，但是，它們大多有一個共同的特點(diǎn)，就是都是基于適應(yīng)度的選擇，適應(yīng)度大的個體被選中的概率就大，適應(yīng)度小的個體被選中的概率就小。

5.交叉算子

交叉操作是把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。基本遺傳算法的交叉概率是固定的，自適應(yīng)交叉概率是隨著進(jìn)化過程的進(jìn)行自適應(yīng)調(diào)整的，在進(jìn)化的開始階段，交叉概率要選的大一些，這樣的粗搜過程有利于保持種群的多樣性，而在后期，則需要進(jìn)行細(xì)搜，也就是減小交叉概率，防止破化最優(yōu)解，加快收斂速度。

6.變異算子

自適應(yīng)變異是變異概率依照種群的進(jìn)化特征而變化的過程。一般的變異概率都在0.5以內(nèi)選取，變異概率過大，對解的破化性也比較大，容易使得到的最優(yōu)解丟失，變異概率太小，會使算法收斂到最優(yōu)解的速度減慢。所以，自適應(yīng)的變異概率一般采取從大到小的變化方式。

六、自適應(yīng)遺傳算法的應(yīng)用

1.函數(shù)優(yōu)化

函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評價的常用算例，許多人構(gòu)造出了各種各樣復(fù)雜形式的測試函數(shù)。對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其它優(yōu)化方法較難求解，而遺傳算法可以方便的得到較好的結(jié)果。

2.在運(yùn)籌學(xué)中的應(yīng)用

傳統(tǒng)的運(yùn)籌學(xué)理論缺乏對變動環(huán)境的適應(yīng)性，所以很多情況下求解耗費(fèi)的時間比最優(yōu)解維持最優(yōu)的壽命還要長，遺傳算法卻能很好的解決傳統(tǒng)方法難以求解的高維或大計算量的問題，比如說旅行商問題等。

3.機(jī)器學(xué)習(xí)

機(jī)器學(xué)習(xí)針對的是維數(shù)很高、總體很大、環(huán)境復(fù)雜、問題結(jié)構(gòu)不十分清楚的問題。學(xué)習(xí)系統(tǒng)要具有隨時間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)其環(huán)境，更好完成目標(biāo)的能力。

七、現(xiàn)狀與展望

隨著遺傳算法的發(fā)展以及其應(yīng)用領(lǐng)域的擴(kuò)大，近些年來，許多新的改進(jìn)的算法不斷被提出。遺傳算法也與一些別的經(jīng)典算法相結(jié)合，比如說粒子群算法、魚群算法、單純算法等。通過結(jié)合，使得算法的性能不斷提高。也有很多算法在不同的遺傳步驟中添加一些新的策略來提高算法性能。總之，改進(jìn)的算法目標(biāo)是為了使遺傳算法通過改進(jìn)以后能夠更快更好地應(yīng)用于實(shí)際問題中。

參考文獻(xiàn)：

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

[2]李敏強(qiáng)，寇紀(jì)淞，林丹，李書全，遺傳算法的基本理論與應(yīng)用[M]，北京：科學(xué)出版社，2002