第9章遺傳算法及其應用

第9章遺傳算法及其應用第9章遺傳算法及其應用

遺傳算法(GeneticAlgorithms,GA):一類借鑒生物界自然選擇和基因遺傳學原理的隨機搜索算法。

自然選擇：生物在自然界的生存環(huán)境中適者生存，不適者被淘汰的過程。

遺傳：子代總是與親代（父代）相似。

2第9章遺傳算法及其應用

遺傳算法(GeneticAlgorithms,GA):一類借鑒生物界自然選擇和基因遺傳學原理的隨機搜索算法。

自然選擇：生物在自然界的生存環(huán)境中適者生存，不適者被淘汰的過程。

遺傳：子代總是與親代（父代）相似。

染色體(chromosome)：生物的遺傳物質(zhì)的主要載體;

基因(gene)：擴展生物性狀的遺傳物質(zhì)的功能單元和結(jié)構(gòu)單位;

基因座(locus)：染色體中基因的位置;

等位基因(alleles)

：基因所取的值。3第9章遺傳算法及其應用

遺傳算法(GeneticAlgorithms,GA）

實現(xiàn)：在計算機上模擬生物的進化過程和基因的操作（復制、交叉、變異）。

研究目的：抽象和嚴謹?shù)亟忉屪匀唤绲倪m應過程；將自然生物系統(tǒng)的重要機理運用到人工系統(tǒng)的設計中。

4第9章遺傳算法及其應用9.1遺傳算法的產(chǎn)生與發(fā)展

9.2遺傳算法的基本算法9.3遺傳算法的改進算法9.4遺傳算法的應用59.1遺傳算法的產(chǎn)生與發(fā)展

1.遺傳算法的發(fā)展概況

起源（20世紀40年代）：從生物學的角度進行生物的進化過程模擬、遺傳過程等研究工作。

產(chǎn)生（20世紀60年代）：

1962年，F(xiàn)raser提出自然遺傳算法。

1965年，Holland首次提出人工遺傳操作的重要性。

1967年，Bagley首次提出遺傳算法這一術(shù)語。

1970年，Cavicchio把遺傳算法應用于模式識別中。

1971年，Hollstien在論文《計算機控制系統(tǒng)中人工遺傳自適應方法》中闡述了遺傳算法用于數(shù)字反饋控制的方法。69.1遺傳算法的產(chǎn)生與發(fā)展

1.遺傳算法的發(fā)展概況

產(chǎn)生

（20世紀60年代）：

1975年，Holland出版《AdaptioninNaturalandArtificialSystem》，闡述了遺傳算法的基本理論和方法，提出模式定理及其證明，奠定了遺傳算法的理論基礎；

1975年，DeJong

完成重要論文《遺傳自適應系統(tǒng)的行為分析》，進行了大量純數(shù)值函數(shù)優(yōu)化計算實驗，建立DeJong

五函數(shù)測試平臺。

79.1遺傳算法的產(chǎn)生與發(fā)展

1.遺傳算法的發(fā)展概況

發(fā)展(20世紀80年代后):1983年，Holland的學生Goldberg將遺傳算法用于管道煤氣系統(tǒng)的優(yōu)化。

1989年，Goldberg出版《搜索、優(yōu)化和機器學習中的遺傳算法》，奠定了現(xiàn)代遺傳算法的科學基礎。

1991年，Davis出版《遺傳算法手冊》一書，為推廣和普及遺傳算法的應用起到了重要的指導作用。

1992年，Koza將遺傳算法應用于計算機程序的優(yōu)化設計及自動生成，提出遺傳編程的概念。

89.1遺傳算法的產(chǎn)生與發(fā)展

2.遺傳算法的應用

9第9章遺傳算法及其應用9.1遺傳算法的產(chǎn)生與發(fā)展9.2遺傳算法的基本算法

9.3遺傳算法的改進算法9.4遺傳算法的應用9.2.1遺傳算法的基本操作9.2.2遺傳算法的設計與實現(xiàn)109.2.1遺傳算法的基本操作

1．遺傳算法的生物遺傳學基礎

1）遺傳——基礎

2）變異——條件

3）選擇——方向選擇通過遺傳和變異起作用，變異為選擇提供資料，遺傳鞏固與積累選擇的資料；選擇控制變異與遺傳的方向，使變異和遺傳向著適應環(huán)境方向發(fā)展。119.2.1遺傳算法的基本操作生物遺傳概念遺傳算法中的應用環(huán)境問題個體（Individual）/染色體（Chromosome）問題的一個解/解的編碼（字符串、向量等）基因（Gene）編碼的元素群體（Population）被選定的一組解（解的個數(shù)為群體的規(guī)模）交叉（Crossover）選擇兩個染色體進行交叉產(chǎn)生一組新的染色體的過程變異（Mutation）編碼的某些分量發(fā)生變化的過程適應性（Fitness）適應度函數(shù)（對應問題的目標函數(shù)）值選擇（Selection）/適者生存適應度函數(shù)值大的解被保留的概率大12例：用遺傳算法求解下面一個Rastrigin函數(shù)的最小值。x2x1x1x1x2f1314初始種群：例：用遺傳算法求解下面一個Rastrigin函數(shù)的最小值。x2x1x115（染色體）16父代染色體子代染色體17子代染色體父代染色體18染色體1920初始種群第二代種群例：用遺傳算法求解下面一個Rastrigin函數(shù)的最小值。x2x1x2x121在迭代60、80、95、100次時的種群229.2.1遺傳算法的基本操作

2．遺傳算法的基本流程239.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。(1)實數(shù)編碼假設染色體長度n=8，等位基因由{0,1,…,9}組成。

例如染色體為70298267,

則x=7.029,y=8.267249.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。

(2)初始種群的產(chǎn)生（設種群大小N=10,染色體長度n=8

）用隨機數(shù)發(fā)生器產(chǎn)生：產(chǎn)生0～9之間均勻分布的80個隨機數(shù)。初始種群259.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。

(3)計算適應度（要求適應度函數(shù)：非負、求最大化）這里適應度函數(shù)為f(x,y)。初始種群269.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。

(4)選擇（復制，reproduction）選擇操作：從當前群體中按照一定概率選擇優(yōu)良的個體，使它們有機會作為父代繁殖下一代。①個體選擇概率分配(

適應度比例方法或蒙特卡羅法)

個體

i

被選擇的概率：

279.2.1遺傳算法的基本操作

3．遺傳算法的基本操作

(4)選擇（復制，reproduction）①個體選擇概率分配(適應度比例方法或蒙特卡羅法)

個體

i

被選擇的概率：

初始種群選擇概率選擇概率28

3．遺傳算法的基本操作②選擇個體

輪盤賭選擇（RouletteWheelSelection）

計算每個染色體的累計概率

Q1＝0.077

Q2＝Q1+0.265=0.077+0.265=0.332

Q3＝Q2+0.117=0.332+0.117=0.449…Q10＝Q9+0.069=19.2.1遺傳算法的基本操作初始種群選擇概率選擇概率299.2.1遺傳算法的基本操作

3．遺傳算法的基本操作

(4)選擇（復制，reproduction）

輪盤賭選擇（RouletteWheelSelection）

產(chǎn)生一個隨機數(shù)r∈[0,1]；若Qk－1

<

r≤Qk

，則選擇復制第k個染色體

。復制前：復制后：

309.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。

(5)交叉（基因重組recombination）先兩兩配對,后按交叉概率進行交叉

單點交叉(假設交叉概率Pc＝0.85)：319.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。

(6)變異(mutation)

變異在遺傳算法中的作用是第二位，但是必不可少的。設變異概率pm=0.05。329.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。第一代第二代339.2.1遺傳算法的基本操作

3．遺傳算法的基本操作問題：求下列函數(shù)的最大值。第100代349.2遺傳算法的基本算法9.2.1遺傳算法的基本操作9.2.2遺傳算法的設計與實現(xiàn)35編碼方案：編碼表示方式；適應度函數(shù)：目標函數(shù)；選擇策略：優(yōu)勝劣汰；遺傳算子：復制（選擇）、交叉、變異；控制參數(shù)：種群規(guī)模、最大迭代步數(shù)、交叉概率、變異概率等；算法的終止準則：規(guī)定一個最大的迭代步數(shù)、算法在連續(xù)多少代以后最優(yōu)個體的適應度或種群的平均適應度沒有改進。設計的基本內(nèi)容：

9.2.2遺傳算法的設計與實現(xiàn)369.2.2遺傳算法的設計與實現(xiàn)一、編碼

1.

位串編碼（一維染色體編碼方法）

二進制編碼（binaryencoding)

根據(jù)具體問題確定待尋優(yōu)的參數(shù)：f(x1,x2,…,xm

)

對每個參數(shù)xi確定其變化范圍[ximin

,ximax

]和編碼精度則對應二進制數(shù)為

Ai

xi

和Ai的關系:

將二進制數(shù)串接起來組成一個長的二進制字串A1A2…Am。

379.2.2遺傳算法的設計與實現(xiàn)1.

位串編碼（一維染色體編碼方法）二進制編碼優(yōu)點：類似生物染色體結(jié)構(gòu)，易于用生物遺傳理論解釋，各種遺傳操作易實現(xiàn)。

缺點：①造成Hamming懸崖，降低遺傳算子的搜索效率。

例7：0111

，8：

1000則

Hamming距離＝4②要先給出求解精度，缺乏微調(diào)功能。③高維優(yōu)化問題的二進制編碼串長，算法的搜索效率低。389.2.2遺傳算法的設計與實現(xiàn)2.

實數(shù)編碼優(yōu)點：不必進行數(shù)制轉(zhuǎn)換，可直接進行遺傳操作；適合于表示范圍較大的數(shù)；適合于精度要求較高的遺傳算法；改善了計算復雜性，提高了運算效率。

399.2.2遺傳算法的設計與實現(xiàn)3.

有序串編碼有序問題：目標函數(shù)的值不僅與表示解的字符串的值有關，而且與其所在字符串的位置有關。例如5個城市的TSP問題的有序串編碼：3

1524409.2.2遺傳算法的設計與實現(xiàn)二、群體設定

1.

初始種群的產(chǎn)生完全隨機的方法：用隨機數(shù)發(fā)生器產(chǎn)生；基于先驗知識的隨機產(chǎn)生方法；先隨機產(chǎn)生一些個體，從中選取N個最好的個體作為初始種群。2.

種群規(guī)模的確定規(guī)模太小，易陷入局部最優(yōu)解，出現(xiàn)早熟；規(guī)模太大，計算量增加，影響算法效率。一般種群規(guī)模N＝20～200。

41

目標函數(shù)f(x)適應度函數(shù)

Fit(x)

maxf(x),minf(x),9.2.2遺傳算法的設計與實現(xiàn)三、適應度函數(shù)（求最大化，非負）

目標函數(shù)f(x)到適應度函數(shù)Fit(x)的變換

maxf(x)

minf(x)42

目標函數(shù)f(x)適應度函數(shù)

Fit(x)

maxf(x),minf(x),9.2.2遺傳算法的設計與實現(xiàn)三、適應度函數(shù)（求最大化，非負）

目標函數(shù)f(x)到適應度函數(shù)Fit(x)的變換

maxf(x)

minf(x)439.2.2遺傳算法的設計與實現(xiàn)四、選擇（復制）

1.個體選擇概率分配方法(1)適應度比例方法(fitnessproportionalmodel)或蒙特卡羅法(MonteCarlo)

各個個體被選擇的概率和其適應度值成比例。

個體

i

被選擇的概率：

449.2.2遺傳算法的設計與實現(xiàn)1.個體選擇概率分配方法(2)排序方法

(rank-basedmodel)①線性排序:J.E.Baker個體按適應度值從大到小依次排列:

個體xi分配選擇概率②非線性排序:Z.Michalewicz

將群體成員按適應值從大到小依次排列，并按下式分配選擇概率：459.2.2遺傳算法的設計與實現(xiàn)2.選擇個體方法1）轉(zhuǎn)盤賭選擇（roulettewheelselection）

第1輪產(chǎn)生一個隨機數(shù)：0.81

第2輪產(chǎn)生一個隨機數(shù)：0.32

四、選擇（復制）

469.2.2遺傳算法的設計與實現(xiàn)2.選擇個體方法2）錦標賽選擇方法(tournamentselectionmodel)從群體中隨機選擇k

個個體，將其中適應度最高的個體保存到下一代。這一過程反復執(zhí)行，直到保存到下一代的個體數(shù)達到預先設定的數(shù)量為止。

隨機競爭方法（stochastictournament）:每次按輪盤賭選擇方法選取一對個體，然后讓這兩個個體進行競爭，適應度高者獲勝。如此反復，直到選滿為止。

479.2.2遺傳算法的設計與實現(xiàn)2.選擇個體方法3）（μ,λ

）和μ

＋λ選擇

(

μ,λ

)選擇：從規(guī)模為

μ

的群體所生成的λ

(≥μ)個后代中選取μ

個最優(yōu)的后代作為新一代種群。

μ＋λ

選擇：從λ

個后代與其父代中選取μ

個最優(yōu)的后代作為新一代種群。4）最佳個體（elitistmodel）保存方法把群體中適應度最高的個體不進行交叉而直接復制到下一代中，保證遺傳算法終止時得到的最后結(jié)果一定是歷代出現(xiàn)過的最高適應度的個體。

489.2.2遺傳算法的設計與實現(xiàn)1.基本的交叉算子1）一點交叉（單點交叉）2）二點交叉（兩點交叉）五、交叉（基因重組）

499.2.2遺傳算法的設計與實現(xiàn)1.基本的交叉算子3）均勻交叉（uniformcrossover)或一致交叉）

五、交叉（基因重組）

509.2.2遺傳算法的設計與實現(xiàn)2.改進的交叉算子1）部分匹配交叉PMX：GoldbergD.E.和R.Lingle(1985)2）順序交叉OX:DavisL.(1985)519.2.2遺傳算法的設計與實現(xiàn)六、變異整數(shù)編碼的變異方法

529.2.2遺傳算法的設計與實現(xiàn)需要選擇的參數(shù)：種群規(guī)模N，交叉概率pc，變異概率pm等。常用的參數(shù)范圍：N＝20～200pc＝0.5～1.0pm＝0～0.05七、遺傳算法中的參數(shù)選擇

pc越大，產(chǎn)生新個體的速度就越快；pc過大，組塊被破壞的概率也越大；pc過小，使搜索變慢、停滯。pm過小，不易產(chǎn)生新個體；pm過大，變成純粹的隨機搜索算法。53第9章遺傳算法及其應用9.1遺傳算法的產(chǎn)生與發(fā)展9.2遺傳算法的基本算法9.3遺傳算法的改進算法

9.4遺傳算法的應用549.3遺傳算法的改進算法

9.3.1雙倍體遺傳算法9.3.2雙種群遺傳算法9.3.3自適應遺傳算法55

9.3.1雙倍體遺傳算法1.基本思想雙倍體遺傳算法采用顯性和隱性兩個染色體同時進行進化，提供了一種記憶以前有用的基因塊的功能。雙倍體遺傳算法采用顯性遺傳。雙倍體遺傳延長了有用基因塊的壽命，提高了算法的收斂能力，在變異概率低的情況下能保持一定水平的多樣性。56

9.3.1雙倍體遺傳算法

2.雙倍體遺傳算法的設計（1）編碼/解碼：兩個染色體（顯性、隱性）（2）復制算子：計算顯性染色體的適應度，按照顯性染色體的復制概率將個體復制到下一代群體中。（3）交叉算子：兩個個體的顯性染色體交叉、隱性染色體也同時交叉。（4）變異算子：個體的顯性染色體按正常的變異概率變異；隱性染色體按較大的變異概率變異。（5）雙倍體遺傳算法顯隱性重排算子：個體中適應值較大的染色體設為顯性染色體，適應值較小的染色體設為隱性染色體。579.3遺傳算法的改進算法

9.3.1雙倍體遺傳算法9.3.2雙種群遺傳算法9.3.3自適應遺傳算法589.3.2雙種群遺傳算法

基本思想在遺傳算法中使用多種群同時進化，并交換種群之間優(yōu)秀個體所攜帶的遺傳信息，以打破種群內(nèi)的平衡態(tài)達到更高的平衡態(tài)，有利于算法跳出局部最優(yōu)。

雙種群遺傳算法：建立兩個遺傳算法群體，分別獨立地運行復制、交叉、變異操作，同時當每一代運行結(jié)束以后，選擇兩個種群中的隨機個體及最優(yōu)個體分別交換。599.3.2雙種群遺傳算法

2.雙種群遺傳算法的設計（1）編碼/解碼設計（2）交叉算子、變異算子（3）雜交算子設種群A與種群B，當A與B種群都完成了選擇、交叉、變異算子后，產(chǎn)生一個隨機數(shù)num，隨機選擇A中num個個體與A中最優(yōu)個體，隨機選擇B中num個個體與B中最優(yōu)個體，交換兩者，以打破平衡態(tài)。609.3遺傳算法的改進算法

9.3.1雙倍體遺傳算法9.3.2雙種群遺傳算法9.3.3自適應遺傳算法619.3.3自適應遺傳算法

1.基本思想

SrinvivasM.，PatnaikL.M.等在1994年提出一種自適應遺傳算法(adaptivegeneticalgorithms，AGA)：能隨適應度自動改變。

AGA：當種群各個體適應度趨于一致或者趨于局部最優(yōu)時，使增加，以跳出局部最優(yōu)；而當群體適應度比較分散時，使