摘要：遺傳算法（Genetic Algorithms，GA）是一種模擬自然選擇和遺傳機制的尋優(yōu)程序，遺傳算法本身固有的并行處理性和開放性，使得它在優(yōu)化識別的效率非常之高，而且受到越來越廣泛的研究。然而，遺傳算法自身也有一些缺點。論文研究了遺傳算法的起源，發(fā)展，原理及自身的缺點。以便對這種算法深入了解，靈活應用，以及做進一步的研究開發(fā)。

關鍵詞：遺傳算法；發(fā)展；原理；缺陷

中圖分類號：TP183文獻標識碼：A文章編號：1009-3044(2008)14-20917-02

1 引言

近年來，遺傳算法以其高效實用的特點迎來了興盛發(fā)展的時期，無論是理論研究還是應用研究都成了十分熱門的課題。尤其是在應用研究方面，眾多的研究者在組合優(yōu)化、模式分類、預測控制等領域都取得了豐碩的成果。對于大自然生物演化的行為準則，達爾文給出了“物競天擇，適者生存”的有力概括，這一學說也成為人們向大自然學習的一個依據。

2 國內外研究現狀

遺傳算法研究的興起是在80年代末和90年代初期，但它的歷史起源可追溯至60年代初期。早期的研究大多以對自然系統的計算機模擬為主。如raser的模擬研究，他提出了和現在的遺傳算法十分相似的概念和思想。Holland和DeJong的創(chuàng)造性研究成果改變了早期遺傳算法研究的無目標性和理論指導的缺乏。其中，Holland于1975年出版的著作《自然系統和人工系統的適配》系統地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極為重要的模式理論。它使用群體搜索技術，通過對目標群體實施選擇、交叉、變異等一系列遺傳操作，從而產生新一代的群體，并使群體進化包含或接近最優(yōu)的狀態(tài)。

自1985年以來，國際上已多次召開了遺傳算法的學術會議和研討會，國際遺傳算法學會組織召開的ICGA（International Conference on Genetic Algorithms）會議和FOGA(Workshop on Foundation of Genetic Algorithms)會議，為研究和應用遺傳算法提供了國際交流的機會。

3 遺傳算法的產生及發(fā)展

遺傳算法(Genetic Algorithms，GA)是一類借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，20世紀60年紀末期到70年代初期，主要由美國著名學者密西根大學教授John.Holland其同事、學生們研究形成了一個較完整的理論和方法，從試圖解釋自然系統中生物的復雜適應過程入手，模擬生物進化的機制來構造人工系統的模型。它采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導學習和確定搜索方向。遺傳算法的操作對象是一群二進制串（稱為染色體、個體），即種群。這里每一個染色體都對應問題的一個解。從初始種群出發(fā)，采用基于適應值比例的選擇策略在當前種群中選擇個體，使用雜交和變異來產生下一代種群。如此模仿生命的進化一代代演化下去，直到滿足期望的終止條件為止。由于它采用種群（即一組表示）的方式組織搜索，這使得它可以同時搜索空間內的多個區(qū)域。而且用種群組織搜索的方式使得遺傳算法特別適合大規(guī)模并行。在賦予遺傳算法自組織、自適應、自學習等特征的同時，優(yōu)勝劣汰的自然選擇和簡單的遺傳操作使遺傳算法具有不受其搜索空間限制性條件（如可微、連續(xù)、單峰等）的約束及不需要其它輔助信息（如導數）的特點。這些嶄新的特點使得演化算法不僅能獲得較高的效率而且具有簡單、易于操作和通用的特征，而這些特征正是遺傳算法越來越受到人們青睞的主要原因之一。

4 遺傳算法的基本原理

遺傳算法GA把問題的解表示成“染色體”，在算法中也即是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設解。然后，把這些假設解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應環(huán)境的“染色體”進行復制，再通過交叉，變異過程產生更適應環(huán)境的新一代“染色體”群。這樣，一代一代地進化，最后就會收斂到最適應環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。

遺傳算法的實施過程包括編碼、產生初始群體、計算適應度、復制、交換、突變、反復迭代、終止等操作。我們用Gen代表遺傳（迭代）的代次，遺傳算法從Gen=0開始。根據所研究問題的表達方式確定字符串長度L，接著隨機產生M個初始群體。剛開始時，終止條件不會被滿足，于是依次計算群體中各個個體的適應度。根據計算結果，依次進行復制、交換、突變等遺傳操作。

遺傳算法的思想簡要給出如下：（1）初始化群體；（2）計算群體上每個個體的適應度值；（3）按由個體適應度值所決定的某個規(guī)則選擇將進入下一代的個體；（4）按概率Pc進行交叉操作；（5）按概率Pc進行突變操作；（6）沒有滿足某種停止條件，則轉第（2）步，否則進入（7）；（7）輸出種群中適應度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。

5 遺傳算法的缺點及改進

盡管遺傳算法有許多優(yōu)點，但目前存在的問題依然很多，如：（1）適應度值標定方式多種多樣，沒有一個簡潔、通用的方法，不利于對遺傳算法的使用；（2）遺傳算法的早熟現象（即很快收斂到局部最優(yōu)解而不是全局最優(yōu)解）是迄今為止最難處理的關鍵問題；（3）快要接近最優(yōu)解時在最優(yōu)解附近左右擺動，收斂較慢。

因此，遺傳算法通常需要解決以下問題，如確定編碼方案，適應度函數標定，選擇遺傳操作方式及相關參數，停止準則確定等。相應的，為改進簡單遺傳算法的實際計算性能，很多學者的改進工作分別從參數編碼、初始群體設定、適應度函數標定、遺傳操作算子、控制參數的選擇以及遺傳算法的結構等方面提出的。

6 總結

遺傳算法是將生物學原理應用于計算機科學的仿生學理論成果。由于它具有極強的解決問題的能力，引起了眾多學者的興趣與參與，已成為學術界跨學科的熱門專題之一。遺傳算法提供了一種求解復雜系統優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多優(yōu)化領域。據不完全統計，進化算法已經在16 個大領域、250 多個小領域中獲得了應用。遺傳算法在機器學習、過程控制、經濟預測、工程優(yōu)化等領域取得的成功，己引起了數學、物理學、化學、生物學、計算機科學、社會科學、經濟科學及工程應用等領域專家的極大興趣和廣泛關注。在遺傳算法應用中，應先明確其特點和關鍵問題，才能對這種算法深入了解，靈活應用，以及進一步研究開發(fā)。

參考文獻：

[1] Holland J H(1975).Adaptation in natural and artificial systems. University of Michigan Press.

[2] 田延碩.遺傳算法的研究與應用[D].電子科技大學碩士論文.

[3] 李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用[M].科學出版社，2003.

[4] Walter Cenedo，Venuri Vrao.Analysis of speciation and niching in the multiniche crowding GA[J].Theoretical Computer Science，1999，(229):177-197.

[5] 劉嵩.改進的并行遺傳算法應用研究[D].大連交通大學碩士學位論文，2006.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文