自適應遺傳算法的研究

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

關鍵詞：自適應遺傳算法；改進方法；性能

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

一、引言

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

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

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

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

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

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

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

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

三、自適應遺傳算法的基本步驟

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

四、自適應遺傳算法存在的問題

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

五、自適應遺傳策略的研究與改進方法

1.編碼

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

2.群體規(guī)模

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

3.適應度函數(shù)

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

4.選擇算子

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

5.交叉算子

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

6.變異算子

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

六、自適應遺傳算法的應用

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

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

2.在運籌學中的應用

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

3.機器學習

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

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

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

參考文獻：

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

[2]李敏強，寇紀淞，林丹，李書全，遺傳算法的基本理論與應用[M]，北京：科學出版社，2002