遺傳算法的綜述

張國民

（浙江海洋學院 數理與信息學院，浙江 舟山 316000）

0 引言

遺傳算法（Genetic Algorithm，簡稱GA）起源于對生物系統所進行的計算機模擬研究。是由美國Michi遺傳算法n大學的John Holland教授創建的，并于1975年出版了第一本系統論述遺傳算法和人工自適應系統的專著《Adaptation in Natural and artificial Systems》。它提出的基礎是達爾文的進化論、魏慈曼的物種選擇學說和孟德爾的群體遺傳學說：其基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優解的算法。遺傳算法以其具有并行搜索、簡單通用、魯棒性強等優點，受到國內外學者的關注。自1985年以來，國際上已召開了多次遺傳算法學術會議和研討會，并組織了國際遺傳算法學會。

1 遺傳算法的基本原理

在自然界中，由于同一個生物群體中各個體之間也存在差異，且對所處環境有的適應和生存能力也參差不齊，遵照進化論所提出的自然界生物進化的基本原則：適者生存、優勝劣汰，自然界將淘汰那些適應能力較差的個體。但是通過交配繼承了父本優秀的染色體和遺傳基因的，或者通過染色體核基因的重新組合產生的生物的生命力往往會更強，適應能力也更強。在自然界中，基因會發生突變，染色體核基因的重組是無法控制的，但這種無法控制的，小概率的變異，也可能產生新基因和生命力更強的新個體。在此基礎上，遺傳算法真實的模擬自然界生物進化機制進行對問題的最優化搜索。遺傳算法是建立在自然選擇和種群遺傳學基礎上的隨機迭代和進化，具有廣泛適用性的搜索方法，同時具有很強的全局優化搜索能力。對于某個給定的優化問題，目標函數為：

要求（X0，Y0，Z0）使得 H為極大值和極小值，以適應優化的需要。此外，Ω 是（X，Y，Z……）的定義域，H 為實數，f為解空間（X，Y，Z……）∈Ω到實數域H∈R的一種映射。遺傳算法要根據目標函數H設定一個適應性函數f，用以判斷某個樣本的優劣程度。遺傳算法的基本步驟如下：

（1）編碼：定義問題的解空間到染色體編碼空間的映射，一般是用二進制將解空間編碼成由0和1組成的有限長度字符串。一般一個候選解（個體）用一串符號表示。

（2）初始化種群：在一定的限制條件下初始化種群，該種群的解空間的一個子空間。算法將從初始化種群開始模擬優勝劣汰的選擇過程，最后選擇出優秀的群體和個體。

（3）設計適應度函數：將種群中的每一個染色體解碼成適于計算機適應度函數的形式，并計算其數值。設計適應度函數的主要方法是將問題的目標函數轉換成合適的適應度函數。

（4）選擇：根據適應度大小選擇優秀個體繁殖下一代，適應度越高，則被選中的概率也越大。選擇是遺傳算法的關鍵，它體現了自然界中適者生存的思想。

（5）交叉：隨機選擇兩個用于繁殖下一代的個體的相同位置，在選中的位置進行交換。

（6）變異：對某個串中的某一位進行取反操作。變異模擬了自然界中偶然基因突變現象。

從步驟四開始重復進行，知道滿足某一性能指標或者規定的遺傳代數。

步驟1、2和3是實際應用中關鍵，步驟4、5和6進行三種基本基因操作。對新生成一代群體進行重復評價、選擇、交叉和變異，如此循環往復，使得群體中最優個體的適應度和群體的平均適應度不斷提高，直到最優個體的適應度達到某個界限或者最優個體的適應度和平均適應度不能再提高。

圖1 遺傳算法的運行過程示意圖

2 遺傳算法的特點

遺傳算法繼承了進化計算的特征之外，也有其自身的特點：

（1）遺傳算法不是直接作用在參數變量集上，而是在求解問題的決定因素和控制參數的編碼(即染色體的0、1編碼)上進行操作，從中找到適應值較高的子串。而且遺傳算法不受約束條件的限制。

（2）遺傳算法并不是從單個點出發執行算法，而是從一個點的群體開始，這樣就可以提高算法的效率和程序的運行速率，也大大減少了陷入局部最優解的可能性。

（3）遺傳算法利用了適應值的信息，適應值是根據不同問題設計所得，針對的是這個問題，從而減少了其他輔助信息的導入，即只需要對象函數和編碼串。因此，遺傳算法幾乎可以處理任何問題。

（4）遺傳算法利用概率轉移規則，而不是確定性的規定。遺傳算法采用的概率僅僅是作為一種工具來引導其搜索過程朝著搜索空間的更優化的解區域移動。

（5）遺傳算法在搜索過程中不容易陷入局部最優，即使在所定義的適應度函數是不連續的非規則的或有噪聲的情況下，也能以很大的概率找到全局最優解。

（6）遺傳算法采用自然進化機制來表現現實復雜的現象，能夠快速可靠地解決非常困難的問題。

（7）遺傳算法具有固有的并行性，具有并行計算的能力。

（8）遺傳算法具有可擴展性，易于同別的技術混合、結合使用。

3 遺傳算法的應用

遺傳算法是多學科結合與滲透的產物，已經發展成為一種自組織、自適應的綜合技術。其提供了一種解決復雜系統優化問題的通用框架，但不是沒用固定的方法，它不依賴于問題的具體領域，所以廣泛應用于很多學科。

3.1 函數優化

函數優化是遺傳算法的一個經典應用領域，也是對遺傳算法進行性能評價的常用算例。很多學者構造出了各種各樣的復雜形式的測試函數，有連續函數也有離散函數，有凸函數也有凹函數，有確定函數也有隨機函數，有單峰值函數也有多峰值函數等。用這些幾何性質各具特色的函數來評價遺傳算法的性能，更能反映算法的本質效果。而對于一些非線性、多模型、多目標的函數優化問題，用其他優化方法較難求解，而遺傳算法卻可以方便地得到較好的結果。

3.2 組合優化

隨著問題規模的增大，組合優化問題的搜索空間也急劇擴大。有時在現有的的計機上用枚舉法很難或甚至不可能求出其精確最優解。對這類復雜問題，學者們已意識到應把主要精力放在尋求其滿意解上，二不是一定要尋找精確的最優解，而遺傳算法是尋求這種滿意解的最佳工具之一。有實踐證明，遺傳算法已經在求解旅行商問題、背包問題、裝箱問題、布局優化、圖形有劃分問題等各種具有NP難度的問題上得到成功應用。

3.3 生產調度問題

在許多情況下所建立起來的數學模型難以精確求解，即使經過了一些簡化之后可以進行求解，也會因為簡化太多而使得求解結果與實際相差甚遠。因此，目前在解決生產中的調度問題時還是主要依靠一些經驗。1985年Davis首次將遺傳算法引入到調度問題。從此在調度問題的解決過程中，遺傳算法使得調度的總流程時間，平均流程時間等大大降低，提高了生產的效率。

3.4 圖像處理

圖像處理是計算機視覺中的一個重要的研究領域，其前景十分樂觀。但在圖像處理的掃描、特征提取、圖像分割等過程中不可避免的會產生誤差。而遺傳算法則可以很好的解決這些問題。在圖像分割的時候可以利用遺傳算法來發現最優解從而幫助確定分割閾值；利用遺傳算法在圖像增強過程中尋找控制參數的最優解或者是近似最優解；利用遺傳算法對圖像進行特征提取再對所提取的特征進行優化，從而提高圖像的識別率等。

3.5 自動化控制

隨著現代技術和科學技術的不斷發展，人工成本的不斷提高，機器的自動化要求越來越高，工程師所要考慮的是選擇合適的控制結構，然后對其參數進行一定的優化使得滿足特定的實際性能要求。遺傳算法具有魯棒性和廣泛適用性的全局優化方法，能更好的為其控制器降價，更好的控制機器人手臂，優化機器人手臂的運動軌跡。遺傳算法的優化功能在越來越多的機器自動化領域得到關注。

4 遺傳算法存在的問題

隨著學科技術的迅速發展，遺傳算法也應用到更多的領域。由于遺傳算法來源于進化論和群體遺傳學，缺乏嚴格的數學基礎，收斂性證明比較困難，雖然可以利用馬爾科夫鏈的性質證明在保留最優值情況下，遺傳算法可以收斂到全局最優解，但是對其收斂速率估計是當前需要深入研究和討論的問題。因為它能從理論上對遺傳算法的任何修正形式提供評判標準，指明改進算法性能的正確方向。另外，利用馬爾科夫鏈分析對遺傳算法的具體應用和參數設計所提供的指導信息非常少。如何選擇遺傳算法的參數，才能得到最優結果，到目前還沒有理論指導。以上這兩個方面還需要需找更有效的分析手段和嚴格的數學證明。

5 結束語

遺傳算法不是一種單純的優化算法，而是一種以進化思想為基礎的全新的一般方法論，是一種解決問題的方法。經過多年的研究和發展，遺傳算法在越來越多的領域展現出它的優勢，不論是基礎理論研究、算法設計還是實際應用。應用研究是遺傳算法的主要方向，開發遺傳算法的商業軟件、開拓更廣泛的遺傳算法應用領域是今后應用研究的主要任務。

［1］Holland J.H.Adaptation in Natural and Artificial Systems[M].Ann Arbor：University of Michigan Press,1975.

［2］邊霞,米良.遺傳算法理論及其應用研究進展[J].計算機應用研究,2010，27（7）.

［3］王東生.遺傳算法及其應用[M].人民郵電出版社，1996.

［4］周國華.遺傳算法及其在生產調度中的應用[J].西南交通大學學報：社會科學版，2000,1（2）.

［5］田瑩,苑瑋琦.遺傳算法在圖像處理中的應用[J].中國圖象圖形學報,2007,12(3).

［6］馬嵐，張燕東.多目標遺傳算法及其在自動控制系統設計中的應用[J].系統工程與電子技術，1997.