遺傳算法及其應(yīng)用

摘要：遺傳算法是智能優(yōu)化方法中應(yīng)用最為廣泛也最為成功的算法，在各個(gè)領(lǐng)域得到廣泛應(yīng)用。該文在介紹了遺傳算法的發(fā)展歷史和具體操作步驟的基礎(chǔ)上，總結(jié)出遺傳算法的特點(diǎn)，并對(duì)它的各個(gè)應(yīng)用領(lǐng)域進(jìn)行了詳細(xì)闡述。

關(guān)鍵詞： 遺傳算法；交叉；變異；選擇；應(yīng)用

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)34-1874-03

Application and Theory of Genetic Algorithm

HUANG Shao-rong

(Department of Information Management， Guangdong Justice Police Vocational College， Guangzhou 510520， China)

Abstract: Genetic algorithm (GA) is an intelligent optimization algorithm that has been used the most extensively， and has the most influential effect. This paper introduces the GA’s history of the development and the process of operation， sums up its characteristics and introduces its application in various fields in detail.

Key words: genetic algorithm; crossover; mutation; selection; application

1 引言

遺傳算法（Genetic Algorithm）是一類借鑒生物界的進(jìn)化規(guī)律（適者生存，優(yōu)勝劣汰）演化而來(lái)的一種自適應(yīng)全局優(yōu)化概率搜索方法，它以一種群體中的所有個(gè)體為對(duì)象，并利用隨機(jī)化技術(shù)指導(dǎo)對(duì)一個(gè)被編碼的參數(shù)空間進(jìn)行高效搜索。

近幾年來(lái)，遺傳算法主要在復(fù)雜優(yōu)化問(wèn)題求解和工業(yè)工程領(lǐng)域應(yīng)用方面，取得了一些令人信服的結(jié)果，使其成為一個(gè)多領(lǐng)域、多學(xué)科的重要研究方向。

2 遺傳算法的發(fā)展

遺傳算法起源于本世紀(jì)40年代對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究，從生物學(xué)的角度進(jìn)行生物的進(jìn)化過(guò)程模擬、遺傳過(guò)程模擬等操作。60年代，美國(guó)的Holland教授認(rèn)識(shí)到生物的遺傳和自然進(jìn)化現(xiàn)象與人工自適應(yīng)系統(tǒng)的相似性，提出研究人工自適應(yīng)系統(tǒng)時(shí)，可借鑒生物的遺傳機(jī)制以群體的方法進(jìn)行自適應(yīng)搜索。1975年Holland出版了《自然系統(tǒng)和人工系統(tǒng)的適配》[1]系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極為重要的模式定理，這一理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對(duì)于獲得隱并行性的重要性。與此同時(shí)，De Jong基于遺傳算法的思想并結(jié)合模式定理在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算機(jī)實(shí)驗(yàn)，并提出了諸如代溝等新的遺傳操作技術(shù)，樹立了遺傳算法的工作框架[2]，Holland和De Jong的創(chuàng)造性研究成果改變了早期遺傳算法研究的無(wú)目標(biāo)性和理論指導(dǎo)的缺乏。80年代由Goldberg進(jìn)行歸納總結(jié)，對(duì)遺傳算法的基本原理及其應(yīng)用進(jìn)行了全面而完整的論述，奠定了現(xiàn)代遺傳算法的科學(xué)基礎(chǔ)[3]。

進(jìn)入80年代，遺傳算法迎來(lái)了興盛發(fā)展時(shí)期，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門的課題，尤其是遺傳算法的應(yīng)用領(lǐng)域也不斷擴(kuò)大。

3 基本遺傳算法

遺傳算法是一種迭代的算法，它首先隨機(jī)生成一個(gè)初始種群，這個(gè)初始種群由經(jīng)過(guò)基因編碼的一定數(shù)目的個(gè)體組成。這個(gè)初始種群按照一定的操作規(guī)則，如選擇，復(fù)制，交叉，變異等，不斷地演化出新的一代。并根據(jù)個(gè)體的適應(yīng)度，按適者生存和優(yōu)勝劣汰的原則，引導(dǎo)搜索過(guò)程向最優(yōu)解逼近，末代種群的最優(yōu)個(gè)體經(jīng)過(guò)解碼，可以作為問(wèn)題近似最優(yōu)解。

3.1 遺傳算法的步驟

Holland提出的遺傳算法常被稱為“簡(jiǎn)單遺傳算法（SGA）”，主要步驟如下：

1) 初始化群體；

2) 計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值；

3) 按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體；

4) 按概率Pc進(jìn)行交叉操作；

5) 按概率Pm進(jìn)行變異操作；

6) 沒(méi)有滿足某種停止條件，則轉(zhuǎn)第2)步，否則進(jìn)入7)。

7) 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿意解或最優(yōu)解。

根據(jù)上述算法思想可得其算法框圖如圖1所示。

1) 編碼

遺傳算法中，種群中的每個(gè)個(gè)體（染色體）是由基因構(gòu)成的，所以個(gè)體要與優(yōu)化問(wèn)題的解如何對(duì)應(yīng)，就需要通過(guò)基因來(lái)表示，即對(duì)個(gè)體進(jìn)行正確編碼。遺傳算法的進(jìn)化過(guò)程是建立在編碼機(jī)制基礎(chǔ)上的，編碼對(duì)于算法的性能影響很大。常用的編碼技術(shù)有[4]：

二進(jìn)制編碼：

使用固定長(zhǎng)度的0，1二進(jìn)制字符串來(lái)表示一個(gè)染色體，例如：

X=（110110111）

就可以表示一個(gè)染色體，該個(gè)體的染色體長(zhǎng)度為n=7。

浮點(diǎn)數(shù)編碼：

個(gè)體的基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的染色體長(zhǎng)度等于其決策變量的個(gè)數(shù)。例如某優(yōu)化問(wèn)題含有4個(gè)變量xi（i=1，2，3，4），xi∈[0，10]，則：

X=（3.2，8.7，6.4，2.1）

就可以表示一個(gè)染色體，該個(gè)體的染色體長(zhǎng)度為n=4。

二進(jìn)制編碼優(yōu)點(diǎn)是編碼解碼簡(jiǎn)單，交叉，變異等遺傳操作便于實(shí)現(xiàn)，而且易于運(yùn)用理論（如模式定理等）進(jìn)行分析。浮點(diǎn)編碼則在變異操作上能夠保持更好的種群多樣性，不過(guò)，其搜索能力比二進(jìn)制要弱一些。后來(lái)，又提出了格雷編碼、符號(hào)編碼、整數(shù)編碼、樹編碼等編碼策略。

2) 初始群體的生成

遺傳算法是一種基于群體尋優(yōu)的方法，算法運(yùn)行時(shí)是以一個(gè)種群在搜索空間進(jìn)行搜索，一般采用隨機(jī)法產(chǎn)生一個(gè)初始種群，即隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)個(gè)體， N個(gè)個(gè)體構(gòu)成了一個(gè)群體。

3) 適應(yīng)性評(píng)估檢測(cè)

為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，稱適應(yīng)度。適應(yīng)度是群體中個(gè)體生存機(jī)會(huì)的唯一確定性指標(biāo)，表明個(gè)體或解的優(yōu)劣性，其選取直接影響到遺傳算法的收斂速度以及能否找到最優(yōu)解，基本上依據(jù)優(yōu)化的目標(biāo)函數(shù)來(lái)確定。

4) 選擇

從當(dāng)前群體中選擇適應(yīng)度高的個(gè)體以生成交配池。選擇原則是適應(yīng)性強(qiáng)的個(gè)體為下一代貢獻(xiàn)一個(gè)或多個(gè)后代的概率大，選擇之前必須計(jì)算每個(gè)個(gè)體的適應(yīng)度。常用選擇算法有：

輪盤賭選擇：是最知名的選擇方式，基本原理是根據(jù)每個(gè)染色體適應(yīng)度的比例來(lái)確定該個(gè)體的選擇概率或生存概率。個(gè)體適應(yīng)度按比例轉(zhuǎn)化為選中概率，為了選擇交配個(gè)體，需要進(jìn)行多輪選擇。每一輪產(chǎn)生一個(gè)[0，1]的均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來(lái)確實(shí)被選個(gè)體。

錦標(biāo)賽選擇：隨機(jī)地從種群中挑選一定數(shù)目的個(gè)體，然后將最好個(gè)體選做父?jìng)€(gè)體，重復(fù)這個(gè)過(guò)程直至得到足夠的個(gè)體。

另外，還有一些其他的選擇方法，如隨機(jī)遍歷抽樣法、（μ+λ）選擇、穩(wěn)態(tài)選擇、排序與比例變換、隨機(jī)剩余選擇、基因池選擇、分裂選擇等。

5) 交叉

是最主要的遺傳操作，同時(shí)對(duì)兩個(gè)染色體進(jìn)行操作，組合兩者的特性產(chǎn)生新的后代。算法性能很大程度上取決于采用的交叉運(yùn)算，雙親的染色體是否進(jìn)行交叉由交叉率來(lái)控制交叉一般可分為實(shí)值替換和二進(jìn)制交叉兩種：

實(shí)值替換：包括離散重組，中間重組和線性重組。

二進(jìn)制交叉重組：最簡(jiǎn)單的二進(jìn)制交叉是單點(diǎn)交叉，它的交叉原理如下：

父?jìng)€(gè)體p1：01110011010

父?jìng)€(gè)體p2：10101100101

交叉點(diǎn)的位置為5，則交叉后產(chǎn)生的兩個(gè)子個(gè)體為：

子個(gè)體q1：01110│100101

子個(gè)體q2：10101│011010

除了單點(diǎn)交叉，還有兩點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等。

6) 變異

在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。變異使算法具有一定的局部的隨機(jī)搜索能力，也可防止發(fā)生因遺漏最優(yōu)值而無(wú)法再找到最優(yōu)解的情況，保持了算法的有效性和種群的多樣性，是算法的一個(gè)重要操作過(guò)程。染色體是否變異由變異率來(lái)控制。常用的變異有：

二進(jìn)制變異：

對(duì)每個(gè)個(gè)體染色體上的二進(jìn)制編碼串進(jìn)行操作，每一位以很小的概率從1變?yōu)?，或從0變?yōu)?。比如有如下二進(jìn)制編碼表示：

■

其碼長(zhǎng)為8，隨機(jī)產(chǎn)生一個(gè)1至8之間的數(shù)K，假如現(xiàn)在K=5，對(duì)從右往左的第5位進(jìn)行變異操作，將原來(lái)的0變?yōu)?，得到如下數(shù)碼串（第四個(gè)1是被變異操作后出現(xiàn)的）：

■

向梯度方向變異：

對(duì)于目標(biāo)函數(shù)可微的最大化問(wèn)題，可采用如下變異操作：

Z=X+▽f(X).α α∈U(0，a)

其中，▽f(X)是目標(biāo)函數(shù)在X處的梯度。

對(duì)于最小化問(wèn)題，則采用如下變異：

Z=X-▽f(X).α α∈U(0，a)

另外，還有實(shí)值變異、基本位變異、均勻變異、邊界變異、非均勻變異以及高斯變異等。

7) 參數(shù)控制

遺傳算法有4個(gè)運(yùn)行參數(shù)需要提前設(shè)定，并且實(shí)際應(yīng)用中，需要多次測(cè)試后才能確定這些參數(shù)合理的取值：

M：種群大小。它對(duì)算法的效率有明顯的影響，規(guī)模太小不利于進(jìn)化，而規(guī)模太大將導(dǎo)致程序運(yùn)行時(shí)間過(guò)長(zhǎng)。不同問(wèn)題，種群規(guī)模不同，通常為20～100。

T：終止進(jìn)化代數(shù)。一般取100～500。

Pc：交叉概率。并不是所有被選擇的染色體都要進(jìn)行交叉或變異操作，而是以一定的概率進(jìn)行。在程序設(shè)計(jì)中交叉發(fā)生的概率要比變異發(fā)生的概率選取得大若干個(gè)數(shù)量級(jí)，一般取0.4～0.99。

Pm：變異概率。一般取0.0001～0.1。

8) 中止條件控制

遺傳算法的終止條件通常可以從兩方面進(jìn)行控制：一個(gè)是預(yù)先設(shè)定最大的進(jìn)化代數(shù)，另一個(gè)是當(dāng)算法在規(guī)定的代數(shù)內(nèi)還沒(méi)有找到更優(yōu)解則終止算法。

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

遺傳算法是解決搜索問(wèn)題的一種通用算法，對(duì)于各種通用問(wèn)題都可以使用。搜索算法的共同特征為： ① 首先組成一組候選解； ② 依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度； ③ 根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解； ④ 對(duì)保留的候選解進(jìn)行某些操作，生成新的候選解。遺傳算法將上述特征組合在一起：基于染色體群的并行搜索，帶有猜測(cè)性質(zhì)的選擇操作、交換操作和突變操作。此外，還具有以下特點(diǎn)：

1) 搜索過(guò)程從一群初始點(diǎn)開始，而不是單一的初始點(diǎn)。覆蓋面大，可有效防止陷入局部最優(yōu)，利于全局擇優(yōu)。

2) 僅用適應(yīng)度來(lái)評(píng)估個(gè)體并在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定，大大擴(kuò)展了其應(yīng)用范圍。

3) 使用概率搜索技術(shù)，而非確定性規(guī)則。

4) 具有潛在的并行性。采用種群的方式組織搜索，可同時(shí)搜索多個(gè)有效區(qū)域并相互交流信息，能以較少的計(jì)算獲得較高的效率。

5) 具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過(guò)程獲得的信息自行組織搜索時(shí)，硬度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。

6) 結(jié)構(gòu)簡(jiǎn)單明了，容易與其他方法結(jié)合，而且算法內(nèi)在的并行性使它適合大規(guī)模的運(yùn)算，可以有效對(duì)復(fù)雜系統(tǒng)進(jìn)行模擬和優(yōu)化。

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

由于遺傳算法提供了一種求解復(fù)雜系統(tǒng)問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類具有很強(qiáng)的魯棒性，前面描述是簡(jiǎn)單的遺傳算法模型，可以在這一基本型上加以改進(jìn)，使其在科學(xué)和工程領(lǐng)域得到廣泛應(yīng)用。下面列舉了一些遺傳算法的應(yīng)用領(lǐng)域[5]：

1)優(yōu)化

優(yōu)化問(wèn)題在運(yùn)籌學(xué)、管理學(xué)和工程設(shè)計(jì)中處于非常重要的地位，遺傳算法在優(yōu)化問(wèn)題的上應(yīng)用包括：

① 函數(shù)優(yōu)化問(wèn)題：是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。

② 組合優(yōu)化問(wèn)題：組合優(yōu)化問(wèn)題的本質(zhì)可歸納為下列類型之一[6]：

確定與問(wèn)題相關(guān)的某些項(xiàng)的排列（如資源約束的項(xiàng)目調(diào)度問(wèn)題、車輛路徑和調(diào)度問(wèn)題等）

確定某些項(xiàng)的組合（如集覆蓋問(wèn)題和群體問(wèn)題等）

確定某些項(xiàng)的排列和組合（如并行機(jī)器調(diào)度問(wèn)題等）

任何帶有約束的上述類型

組合優(yōu)化理論上可通過(guò)牧舉法找到最優(yōu)解，但隨著問(wèn)題規(guī)模的增大，探索空間也急劇增大，在目前的計(jì)算機(jī)上很難求出最優(yōu)解。遺傳算法作為復(fù)雜問(wèn)題優(yōu)化方法的潛質(zhì)已經(jīng)受到了普遍的關(guān)注，實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問(wèn)題非常有效。

③ 多目標(biāo)優(yōu)化

該類問(wèn)題存在多個(gè)目標(biāo)需要同時(shí)優(yōu)化，由于目標(biāo)之間的無(wú)法比較和矛盾等現(xiàn)象，導(dǎo)致不一定存在使所有目標(biāo)最優(yōu)的解。由于遺傳算法具有多方向和全局搜索特點(diǎn)，在解決這類問(wèn)題上具有優(yōu)勢(shì)。

2) 自動(dòng)控制

對(duì)大規(guī)?？刂葡到y(tǒng)進(jìn)行綜合設(shè)計(jì)并建立數(shù)學(xué)模型，在對(duì)數(shù)學(xué)模型的優(yōu)化上，遺傳算法具有其它進(jìn)化算法無(wú)法比擬的優(yōu)點(diǎn)，已取得一定成績(jī)。例如用遺傳算法對(duì)自動(dòng)控制系統(tǒng)數(shù)學(xué)模型尋優(yōu)、用遺傳算法優(yōu)化PID控制系統(tǒng)、遺傳算法在加工過(guò)程智能最優(yōu)自適應(yīng)控制的應(yīng)用、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計(jì)等。

3) 人工生命

人工生命是用計(jì)算機(jī)模擬自然界的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對(duì)象，與遺傳算法有密切關(guān)系。遺傳算法已經(jīng)在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力。

4) 圖像處理和模式識(shí)別

遺傳算法可以對(duì)圖像進(jìn)行優(yōu)化，使圖像處理中產(chǎn)生的一些誤差達(dá)到最小。目前已經(jīng)圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識(shí)別等方面得到了應(yīng)用。

5) 機(jī)器人智能控制

是遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域，已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到了應(yīng)用。（下轉(zhuǎn)第1882頁(yè)）

（上接第1876頁(yè)）

6) 程序設(shè)計(jì)

遺傳算法可以用于某些特殊任務(wù)的計(jì)算機(jī)程序設(shè)計(jì)。

7) 機(jī)器學(xué)習(xí)

遺傳算法可用于許多機(jī)器學(xué)習(xí)的應(yīng)用，包括分類問(wèn)題和預(yù)測(cè)問(wèn)題等，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。

8) 經(jīng)濟(jì)學(xué)與社會(huì)經(jīng)濟(jì)問(wèn)題

應(yīng)用遺傳算法對(duì)經(jīng)濟(jì)創(chuàng)新的過(guò)程建立模型，可以研究投標(biāo)的策略，還可以建立市場(chǎng)競(jìng)爭(zhēng)的模型。

9) 免疫系統(tǒng)

應(yīng)用遺傳算法可以對(duì)自然界中免疫系統(tǒng)的多個(gè)方面建立模型，研究個(gè)體的生命過(guò)程中的突變現(xiàn)象以及發(fā)掘進(jìn)化過(guò)程中的基因資源。

10) 進(jìn)化現(xiàn)象和學(xué)習(xí)現(xiàn)象

遺傳算法可以用來(lái)研究個(gè)體是如何學(xué)習(xí)生存技巧的，一個(gè)物種的進(jìn)化對(duì)其他物種會(huì)產(chǎn)生何種影響等等。

5 結(jié)論

遺傳算法作為強(qiáng)有力且應(yīng)用廣泛的隨機(jī)搜索和優(yōu)化方法，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門的課題，尤其是遺傳算法的應(yīng)用研究顯得格外活躍。本文首先介紹遺傳算法的發(fā)展與操作步驟，并總結(jié)出遺傳算法的特點(diǎn)，最后詳細(xì)介紹了遺傳算法的各個(gè)應(yīng)用領(lǐng)域。

參考文獻(xiàn)：

[1] Holland J H.Adaptation in Nature and Artificial Systems[M].MIT Press，1992.

[2] De Jong K A.An Analysis of the Behavior of a Class of Genetic Adaptive Systems. Ph. D Dissertation[D].University of Michigan，No.76-9381，1975.

[3] Goldberg D E.Genetic Algorithms in Search， Optimization and Machine Learning[M].Addison-Wesley，1989.

[4] 汪定偉.智能優(yōu)化方法[M].北京:高等教育出版社，2007:21-23.

[5] 周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國(guó)防工業(yè)出版社， 2005:15-17.

[6] 玄光男，程潤(rùn)偉.遺傳算法與工程優(yōu)化[M].北京:清華大學(xué)出版社，2003.