遺傳算法的綜述

張國民

（浙江海洋學(xué)院 數(shù)理與信息學(xué)院，浙江 舟山 316000）

0 引言

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

1 遺傳算法的基本原理

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

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

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

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

（3）設(shè)計適應(yīng)度函數(shù)：將種群中的每一個染色體解碼成適于計算機適應(yīng)度函數(shù)的形式，并計算其數(shù)值。設(shè)計適應(yīng)度函數(shù)的主要方法是將問題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù)。

（4）選擇：根據(jù)適應(yīng)度大小選擇優(yōu)秀個體繁殖下一代，適應(yīng)度越高，則被選中的概率也越大。選擇是遺傳算法的關(guān)鍵，它體現(xiàn)了自然界中適者生存的思想。

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

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

從步驟四開始重復(fù)進行，知道滿足某一性能指標(biāo)或者規(guī)定的遺傳代數(shù)。

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

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

2 遺傳算法的特點

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

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

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

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

（4）遺傳算法利用概率轉(zhuǎn)移規(guī)則，而不是確定性的規(guī)定。遺傳算法采用的概率僅僅是作為一種工具來引導(dǎo)其搜索過程朝著搜索空間的更優(yōu)化的解區(qū)域移動。

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

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

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

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

3 遺傳算法的應(yīng)用

遺傳算法是多學(xué)科結(jié)合與滲透的產(chǎn)物，已經(jīng)發(fā)展成為一種自組織、自適應(yīng)的綜合技術(shù)。其提供了一種解決復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，但不是沒用固定的方法，它不依賴于問題的具體領(lǐng)域，所以廣泛應(yīng)用于很多學(xué)科。

3.1 函數(shù)優(yōu)化

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

3.2 組合優(yōu)化

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

3.3 生產(chǎn)調(diào)度問題

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

3.4 圖像處理

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

3.5 自動化控制

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

4 遺傳算法存在的問題

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

5 結(jié)束語

遺傳算法不是一種單純的優(yōu)化算法，而是一種以進化思想為基礎(chǔ)的全新的一般方法論，是一種解決問題的方法。經(jīng)過多年的研究和發(fā)展，遺傳算法在越來越多的領(lǐng)域展現(xiàn)出它的優(yōu)勢，不論是基礎(chǔ)理論研究、算法設(shè)計還是實際應(yīng)用。應(yīng)用研究是遺傳算法的主要方向，開發(fā)遺傳算法的商業(yè)軟件、開拓更廣泛的遺傳算法應(yīng)用領(lǐng)域是今后應(yīng)用研究的主要任務(wù)。

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

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

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

［4］周國華.遺傳算法及其在生產(chǎn)調(diào)度中的應(yīng)用[J].西南交通大學(xué)學(xué)報：社會科學(xué)版，2000,1（2）.

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

［6］馬嵐，張燕東.多目標(biāo)遺傳算法及其在自動控制系統(tǒng)設(shè)計中的應(yīng)用[J].系統(tǒng)工程與電子技術(shù)，1997.