遺

傳

算

法

原

理

與

應

用趙

鵬pzhao@bjtu.ed1一

、

基

本

原

理1.遺

傳

算

法

起

源遺傳算法是由美國的J.Holland教授于1975年在他的專著《自

然界和人工系統的適應性》中首先提出的，

它是一類借鑒生物

界自然選擇和自然遺傳機制的隨機化搜索算法。2生

物

進

化

循

環

圖淘汰的群體種

群競

爭婚

配群

體子

群變

異3生

物

遺

傳

概

念遺

傳

算

法中的

作

用適者生存在算法停止時

，

最優目標值的解有最大的可能被保留個體(individual)解染色體(chromosome)解的編碼

(

字

符串，向量等)基

因(gene)解中每

一

分

量的

特征(如

各

分

量的

值

)適應性(fitness)適

應函

數

值群

體(population)選定的

一

組

解(

其中

解的

個數為

群

體的

規

模

)種

群(reproduction)根

據

適

應函

數

值

選

取的

一

組

解交

配(crossover)通

過

交

配

原

則

產

生

一

組

新

解的

過

程變

異(mutation)編

碼的

某

一

個

分

量

發

生

變

化的

過

程4生物遺傳概念在遺傳算法中的對應關系遺

傳

算

法

的

主

要

特

征

：進化發生在解的編碼上，

這些編碼按生物學的術語稱為染色體。

由于對解進行了編碼，

優化問題的一切性質都通過編

碼來研究。

編碼和解碼是遺傳算法的一個主題。自然選擇規律決定哪些染色體產生超過平均數的后代。遺傳算法中，通過優化問題的目標而人為地構造適應函數以達

到好的染色體產生超過平均數的后代。當染色體結合時，

雙親的遺傳基因的結合使得子女保持父母的特征。當染色體結合后，

隨機的變異會造成子代同父代的不同。5遺傳算法主要處理步驟首先是對優化問題的解進行編碼，稱一個解的編碼為一個染色

體，組成編碼的元素稱為基因。編碼的目的主要是用于優化問題

解的表現形式和利于之后遺傳算法中的計算。第二是適應函數的構造和應用。適應函數基本上依據優化問題

的目標函數而定。

當適應函數確定以后，

自然選擇規律是以適應

函數值的大小決定的概率分布來確定哪些染色體適應生存，

哪些

被淘汰。

生存下來的染色體組成種群，

形成一個可以繁衍下一代

的

群

體

。第三是染色體的結合。雙親的遺傳基因結合是通過編碼之間的

交配達到下一代的產生。新一代的產生是一個生殖過程，

它產生

了一個新解。最后是變異。新解產生過程中可能發生基因變異，

變異使某些

解的編碼發生變化，

使解有更大的遍歷性。62、

基本

遺

傳算

法基本遺傳算法(

Simple

Genetic

Algorithms,簡稱SGA

,又稱簡單遺傳算法或標準遺傳算法),是由Goldberg

總結

出的一種最基本的遺傳算法，

其遺傳進化操作過程簡單，容易理解，

是其它一些遺傳算法的雛形和基礎?；具z傳算法的組成(

1)

編

碼

(

產

生

初

始

種

群

)(2)

適應

度

函

數(3)

遺傳

算

子

(

選

擇

、

交

叉

、

變

異

)(

4

)

運

行

參

數7編

碼GA是通過某種編碼機制把對象抽象為由特定符號按一定順

序排成的串。正如研究生物遺傳是從染色體著手，

而染色體則是由基因排成的串。SGA使用二進制串進行編碼。函數優化示例求下列一元函數的最大值：x

∈[-1,2],求解結果精確到6位小數。8SGA對

于

本

例

的

編

碼由于區間長度為3,

求解結果精確到6位小數，因此可將

自變量定義區間劃分為3×106等份。又因為221<3×106<222,所

以本例的

二進

制

編

碼

長

度

至

少需

要2

2

位，本

例

的

編

碼

過程實質上是將區間[-1,2]內對應的實數值轉化為一個二進制

串

(b21b20.b0)

。9幾

個

術

語

個體

(

染

色體

)基

因

型

：

1

0

0

0

1

0

1

1

1

0

1

1

0

1

0

1

0

0

0

1

1基因解

碼

編碼表現

型：

0.63719710初始種群SGA

采用隨機方法生成若

干

個

個

體的集合，

該集合稱為初始

種群。初始種群中個體的數量稱為種群規模。適

應

度

函

數遺傳算法對

一個個體(解)的好壞用適應度函數值來評價，適應度函數值越大，

解的質量越好。適應度函數是遺傳算法

進化過程的驅動力，

也是進行自然選擇的唯一標準，

它的設計應結合求解問題本身的要求而定。11選

擇

算

子遺傳算法使用選擇運算來實現對群體中的個體進行優勝劣

汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，

被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，

遺傳到下一代群體。

SGA中選擇算子采用輪盤賭選擇方法。12S40.31/s?0.06●輪

盤

賭

選

擇

法輪

盤

賭

選

擇

示

意S10.14S20.4913輪

盤

賭

選

擇

方

法輪盤賭選擇又稱比例選

擇

算

子，它

的基本思想是

：

各個

個體被選中的概率與其適應度函數值大小成正比。設群體大

小為n,個體i

的適應度為

F,則個體i

被選中遺傳到下一代群體的概率為：14輪盤賭選擇

方

法的實現步

驟(1)

計算群體中所有個體的適應度函數值(需要解碼);(2)利用比例選擇算子的公式，

計算每個個體被選中遺傳到下

一

代

群

體的

概

率

；(3)采用模擬賭盤操作(即生成0到1之間的隨機數與每個個體遺傳到下一代群體的概率進行匹配)來確定各個個體

是否遺傳到下一代群體中。15交

叉

算

子所謂交叉運算，

是指對兩個相互配對的染色體依據交

叉概率Pc按某種方式相互交換其部分基因，從而形成兩個

新的個體。交叉運算是遺傳算法區別于其他進化算法的重要

特征，它在遺傳算法中起關鍵作用，

是產生新個體的主要方

法。SGA中

交叉算子采用單點交叉算子。16單點交叉運算

交

叉

前

：

交叉點

O0000|04TOOO000001000011100|00000111111000101交

叉

后

：O0000|0000011111100010111100|0111000000001000017變

異

算

子所謂變異運算，是指依據變異概率

Pm

將個體編碼串中

的某些基因值用其它基因值來替換，從而形成一個新的個體

。遺傳算法中的變異運算是產生新個體的輔助方法，它決定

了遺傳算法的局部搜索能力，

同時保持種群的多樣性。交叉

運算和變異運算的相互配合，

共同完成對搜索空間的全局搜

索和局部搜索。

SGA

中變異算子采用基本位變異算子。18基

本

位

變

異

算

子基本位變異算子是指對個體編碼串隨機指定的某一位或某

幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0,則變異操作將其變為1;反之，若原有基因

值為1,則變異操作將其變為0。19變

異

前

：000001110000000010000變

異

后

：000001110001000010000基本位

變異

算

子的執行

過

程

變異點

20運

行

參

數(1)M

:

種

群

規

模(2)T:

遺傳運算的終止進化代數(3)Pc:

交叉概率(4)Pm:變異概率21GA

OperatorsMutationCrossoverReproductionEvaluationFitnessvalueEvolution

EnvironmentGenetic

Algorithm

Evolution

Flow初始種群Cost遺

傳

算

法

應

用

舉

例利用遺

傳算

法

求

解區間

[0,31]上的二次函數y=x2的最大值。23分

析原問題可轉化為在區

間

[0,3

1]

中搜索能使

y

取最大值

的

點a

的

問題

。那么

,[0,31]

中

的點x就是個體，函數值f(x)恰好就可以作為x的

適應度，

區間[0,31]就是一個(解)空間。這

樣，只要能給出個體x的適當染色體編碼，該問

題就可以用遺傳算法來解決。24解(1)設定種群規模，編碼染色體，產生初始種

群

。將種群規模設定為4;用5位二進制數編碼

染色體；取下列個體組成初始種群S?:s?=13

(01101),s?=24(11000)s?=8(01000),

s?=19(10011)(2)定義適應度函數，取適應度函數：f(x)=x225(3)計算各代種群中的各個體的適應度，并對其染色體進行遺傳操作，直到適應度最高的個

體(即31(11111))出現為止。26首先計算種群S?中各個體s?=13(01101),

s?=24(11000)

s?=8(01000),

s?=19(10011)的適應度f(s;)。容易求得f(s?)=f(13)=132=169f(s?)=f(24)=242=576f(s?)=f(8)=82=64f(s?)=f(19)=192=36127再計

算

種

群S?中

各

個

體的

選

擇

概

率

。選

擇

概

率的

計

算

公

式

為P(s?)=P(13)=0.14P(s?)=P(24)=0.49P(s?)=P(8)=0.06P(s?)=P(19)=0.31由

此

可

求

得28S40.31/s?0.06●賭

輪

選

擇

法賭

輪

選

擇

示

意S10.14S20.4929在算法中賭輪選擇

法

可

用下

面的子過

程

來

模擬

：①在

[0,

1]

區

間

內產

生

一

個

均

勻

分

布

的

隨

機數

r。②

若r≤q?,則染色體x?被選中。③若qk-?<r≤qμ(2≤k≤N),

則染色體x被選中。其中的q;稱為染色體x;(i=1,2,

...,n)的積累概率，

其計算公

式

為30染色體適應度選擇概率積累概率選中次數S?=011011690.140.141S?=110005760.490.632S?=01000640.060.69OS?=100113610.311.001選擇-復制設從區間[0,1]中產生4個隨機數如下：r?=0.450126,r?=0.110347r?=0.572496,r?=0.9850331于是，

經復

制

得

群

體

：s?

′=11000(24),s?

′=01101(13)s?

′=11000(24),s?

′=10011(19)32交

叉設交叉率p=100%,

即S?中的全體染色體都參

加

交

叉

運

算

。設s?'與s?

'配對，

s?

'與s?'配對。分別交換后兩

位

基因，得

新

染

色

體

：S?

′'=11001(25),s?

′′=01100(12)s?

′'=11011(27),s?

′'=10000(16)33變

異設變異率pm=0.001。這樣，群體S?中共有5×4×0.001=0.02位

基因可以

變

異

。0

.

0

2

位

顯

然

不

足1

位

，

所

以本輪遺傳操作不做

變

異

。34于是，得到第二代種群S?:S?=11001(25),S?=01100(12)S?=11011(27),S?=10000(16)35染色體適應度選擇概率積累概率估計的選中次數S?=110016250.360.361S?=011001440.080.441S?=110117290.410.851S?=100002560.151.001第二代種群S?中各染色體的情況36假設這一輪選擇-

復制操作中，種群S?中

的4個染色體都被選中，則得到群體：S?′=11001(25),s?′=01100(12)S?'=11011(27),s?'=10000(16)做交叉運算，讓s?’與s?’,s?’

與s?’分別交換后三位基因，

得S?”=11100(28),s?”=01001(9)s?”=11000(24),s?”=10011(19)這一輪仍然不

會發生

變

異

。37于是，得第三

代

種

群S3:S?=11100(

28

),S?

=01001(9)S?=11000(24),S?=10011(19)38染色體適應度選擇概率積累概率估計的選中次數S?=111007840.440.442S?=01001810.040.48OS?=110005760.320.801S4=100113610.201.001第三代種群S?中各染色體的情況39設這一輪的選擇-復制結果為：s?'=11100(28),s?

'=11100(28)S?

′=11000(24),s?

′=10011(19)做交叉運算，讓s?

’與s?

’,s?

’與s?

’分別交換后兩

位

基因，

得S?

′'=11111(31),s?

′'=11100(28)s?

′'=11000(24),s?

′′=10000(16)這一

輪仍

然

不

會

發

生

變

異

。40于是，得第四代種群S?:S?=11111(31),S?=11100(28)S?=11000(24),S?=10000(16)41顯然，

在

這

一

代

種

群

中

已

經

出

現

了

適

應

度

最高的染色體s?=11111。

于是，遺傳操作終止，

將

染

色

體

“1

1

1

1

1

”

作

為

最

終

結

果

輸

出

。然后，

將

染

色

體

“

1

1

1

1

1”

解

碼

為

表

現

型

，

即得

所

求

的

最

優

解

：

31。將31代入函數y=x2中，即得原問題的解，

即

函數y=x2的最大值為961。42第三

代

種

群

及

其

適

應

度第四代種群

及

其

適

應

度第一

代種

群

及

其

適

應

度第二

代種

群

及

其

適

應

度43遺傳

算

法的描

述Step1選擇問題的一個編碼；給出一個有N個染色體的初始群體

pop(1),t:=1;Step2

對群體pop(t)中的每一個染色體pop;(t)計算它的適應函數

f=fitness(pop;(t));Step3若停止規則滿足，則算法停止；否則，計算概率P?=f/Zfi,i=1,2,,,N并以概率從pop(t)中隨機選一些染色體構成一個新的種群Newpop(t+1)={pop(t)[j=1,2,...,N};Step4

通過交配，交配概率為p.,得到一個有N個染色體的

crosspop(t+1);Step5

以較小概率pm,

使得一個染色體的基因發生變異，形成

mutpop(t+1);t:=t+1,一個新的體群pop(t)=mutpop(t);返回step2.443、

遺

傳

算

法

的

特

點(1)群體搜索，

易于并行化處理；(2)不是盲目窮舉，而是啟發式搜索；(3)適應度函數不受連續、可微等條件的約束，

適用

范

圍

很廣。45二

、

理

論

基

礎1、

遺傳算法的數學基礎2、

遺傳算法的收斂性分析3、

遺傳算法

的改進461、

遺傳算

法的數學基

礎(

1)模式定理(2)

積

木

塊

假設模

式模式是指種群個體基因串中的相似樣板，它用來描述基

因串中某些特征位相同的結構。在二進制編碼中，

模式是基于三個字符集(0,1,*)的字符串，符號*代表任意字符，

即0或

者1。模式示例：1

0**147兩個定義一定義1:

模

式H中

確定位置的個數稱為

模

式

H

的

階

，

記作

O(H)。例

如O(10**1)=3。一定義2:

模

式H中第一個確定位置

和

最

后

一

個

確定

位

置

之

間

的距離稱為

模

式

H的

定

義距，

記

作δ(H)

。

例如δ(10**1)=4

。模式的階和

定

義

距的

含

義模式階用來

反映

不同

模式間

確

定

性的差

異，

模式階數越高,

模式的確定性就越高，

所匹配的樣本

數

就

越

少。在

遺

傳

操

作中，

即使階數相同的模式，也會有不同的性質，

而模式

的

定義

距

就

反映了這

種

性

質的

差

異

。48模式定理模式定理：

具有低階、短定義距以

及平均適應度高于種群

平均適應度的模式在子代中呈指數增長。模式定理保證了較優的模式(遺傳算法的較優解)的數目呈指數增長，為解釋遺傳算法機理提供了數學基礎。從模式定理可看出，

有高平均適應度、短定義距、低階的

模式，在連續的后代里獲得至少以指數增長的串數目，

這主要

是因為選擇使最好的模式有更多的復制，交叉算子不容易破壞

高頻率出現的、短定義距的模式，

而一般突變概率又相當小，

因而它對這些重要的模式幾乎沒有影響。49積

木

塊

假

設積木塊假設：

遺傳算法通

過

短

定

義距

、

低

階

以

及

高

平

均

適

應

度的模式(積木塊),在遺傳操作下相互結合，

最終接近全局

最優解。模式定理保證了較優模式的樣本數呈指數增長，

從而使遺傳算

法找到全局最優解的可能性存在；

而積木塊假設則指出了在遺

傳算子的作用下，

能生成全局最優解。定理若參數滿足：變異概率0

<pm<1,交配概率O≤Pc≤1,則簡單遺傳算法不收斂于全局最優解。50定理

如果改進簡單遺傳算法按交配、變異、種群選取之后更新當前最優染色體的進化循環過程，則收斂于全局最優解。改進遺傳算法：

進化的每一代中，記錄前面各代最優解并

存放在群體的第一位，

這個染色

體

不參與

遺

傳

運

算

。2、

遺傳算法

的收斂

性

分

析遺傳算法要實現全局收斂，

首先要求任意初始種群經有限步都能到達全局最優解，

其次算法必須由保優操作來防止最優解

的遺失。與算法收斂性有關的因素主要包括種群規模、選擇操

作、交叉概率和變異概率。51種群規模對收斂性的影響通常，種群太小則不能提供足夠的采樣點，

以致算法性能

很差；種群太大，

盡管可以增加優化信息，

阻止早熟收斂的發生，但無疑會增加計算量，

造成收斂時間太長，

表現為收斂速

度

緩

慢

。選擇操作對收斂性的影響選

擇

操

作

使

高

適

應

度

個

體

能

夠

以

更

大

的

概

率

生

存

，

從

而

提

高了遺傳算法的全局收斂性。如果在算法中采用最優保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，

使之直接進入下一代，

最終可使遺傳算法以概率1收

斂于全局最優解。52交叉概

率

對收

斂性的影響交叉操作用于個體對，產生新的個體，

實質上是在解空間中進行有效搜索。交叉概率太大時，

種群中個體更新很快，會造

成高適應度值的個體很快被破壞掉；

概率太小時，交叉操作很少進行，從而會使搜索停滯不前，

造成算法的不收斂。變異概

率

對收

斂

性的影響變異操作是對種群模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產生新模式，變異概率太大則會使

遺傳算法成為隨機搜索算法。53遺

傳

算

法

的

本

質遺傳算法本質上是對染色體模式所進行的一系列運算，

即通過選擇算子

將當前種

群中的優

良模式遺

傳到下一

代

種

群中,

利用交叉算子進行模式重組，

利用變異算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，

最終得

到問題的最優解。54GA的

局

限

性在

于GA在進化搜索過程中，

每代總要維持一定規模的群體，

若群體規模太小，

含有的信息量也少，不能使算法得到充分發揮

,若群體規模大，包含的信息量也大，但計算次數會激劇增加，

因而限制了算法的使用。GA的另一個不足之處是“早熟”。造成這種成熟前收斂的原因，

一方面是

GA中最重要的遺傳算子——交叉算子使群體中的

染色體具有局部相似性，父代染色體的信息交換量小，從而使搜

索停滯不前；

另一方面是變異概率又太小，

以至于不能使搜索轉

向其它的解空間進行搜索。GA的爬山能力差，

也是由于變異概率低造成的。553、

遺

傳

算

法

的

改

進遺傳欺騙問題：

在遺傳算法進化過程中，

有時會產生一些

超常的個體，

這些個體因競爭力太突出而控制了選擇運算過

程，

從而影響算法的全局優化性能，

導致算法獲得某個局部最

優

解

。56遺

傳

算

法

的

改

進

途

徑(

1)對

編碼

方

式

的

改

進

(2)對遺傳算子的改進

(3)對控制參數的改進

(4)對執行策略的改進57對

編

碼

方

式

的

改

進二進制編碼優點在于編碼、

解碼操作簡單，

交叉、

變異等操作便于實現，

缺

點在

于

精

度

要

求

較

高

時

，個

體

編

碼

串

較

長

,

使算法的搜索空間急劇擴大，遺傳算法的性能降低。格雷

編碼克服了二進制編碼的不連續問題，浮點數編碼改善了遺傳算法的計算復雜性。58(1)編碼自然數編碼，

i?izig……in

(2)適應度函數f;:

巡回路長度的倒數

(3)選擇操作①繁殖池；

②賭輪選擇

(4)雜交算子例，基于位置的雜交父代1:

1

2

3

4

5父

代

2

:

5

9

2

4

6所選位置

子

代

1

:

1

9

2

36子代

2

:

9

2

3

4

5(5)變異算子*

*

*例，基于位置的變異、基于次序的變異、打亂變異TSP

問

題

的

基

本

遺

傳

算

法108107938107105187★7864659(1)

對群體中的所有個體按其

適應度大小進行降序排序；(2)

根據具體求解問題，設計

一個概率分配表，將各個概率值

按上述排列次序分配給各個個體(3)

以各個個體所分配到的概

率值作為其遺傳到下一代的概率

,基于這些概率用賭盤選擇法來產生下一代群體。對

遺

傳

算

子

的

改

進排序選探

均

勻

交

叉逆

序

變

異60(1)

隨機產生一個與個體

編碼長度相同的二進制屏蔽

字P

=W?W?…Wn;(2)按

下

列

規

則

從A、

B

兩

個父代個體中產生兩個新個體

X、Y:

若

W;=0,

則

X

的第i個基因繼承A的對應基因

,Y

的第i個基因繼承B

的對應

基因；若W;=1,

則A、B的

第i個基因相互交換，從而生

成X、Y

的第i個基因。對遺傳算子

的

改

進排序選擇均

勻

交

叉逆

序

變

異61排序選擇均勻交叉

逆

序