張國(guó)民

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

0 引言

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

1 遺傳算法的基本原理

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

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

（1）編碼：定義問(wèn)題的解空間到染色體編碼空間的映射，一般是用二進(jìn)制將解空間編碼成由0和1組成的有限長(zhǎng)度字符串。一般一個(gè)候選解（個(gè)體）用一串符號(hào)表示。

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

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

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

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

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

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

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

圖1 遺傳算法的運(yùn)行過(guò)程示意圖

2 遺傳算法的特點(diǎn)

遺傳算法繼承了進(jìn)化計(jì)算的特征之外，也有其自身的特點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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

3.2 組合優(yōu)化

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

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

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

3.4 圖像處理

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

3.5 自動(dòng)化控制

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

4 遺傳算法存在的問(wèn)題

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

5 結(jié)束語(yǔ)

遺傳算法不是一種單純的優(yōu)化算法，而是一種以進(jìn)化思想為基礎(chǔ)的全新的一般方法論，是一種解決問(wèn)題的方法。經(jīng)過(guò)多年的研究和發(fā)展，遺傳算法在越來(lái)越多的領(lǐng)域展現(xiàn)出它的優(yōu)勢(shì)，不論是基礎(chǔ)理論研究、算法設(shè)計(jì)還是實(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ìn)展[J].計(jì)算機(jī)應(yīng)用研究,2010，27（7）.

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

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

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

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