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

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

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

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

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

2第9章遺傳算法及其應(yīng)用

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

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

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

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

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

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

等位基因(alleles)

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

遺傳算法(GeneticAlgorithms,GA）

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

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

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

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

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

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

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

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

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

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

1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別中。

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

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

產(chǎn)生

（20世紀(jì)60年代）：

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

1975年，DeJong

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

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

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

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

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

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

1991年，Davis出版《遺傳算法手冊(cè)》一書，為推廣和普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。

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

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

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

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

9.3遺傳算法的改進(jìn)算法9.4遺傳算法的應(yīng)用9.2.1遺傳算法的基本操作9.2.2遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)109.2.1遺傳算法的基本操作

1．遺傳算法的生物遺傳學(xué)基礎(chǔ)

1）遺傳——基礎(chǔ)

2）變異——條件

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

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

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

例如染色體為70298267,

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

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

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

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

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

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

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

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

適應(yīng)度比例方法或蒙特卡羅法)

個(gè)體

i

被選擇的概率：

279.2.1遺傳算法的基本操作

3．遺傳算法的基本操作

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

個(gè)體

i

被選擇的概率：

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

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

輪盤賭選擇（RouletteWheelSelection）

計(jì)算每個(gè)染色體的累計(jì)概率

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)選擇（復(fù)制，reproduction）

輪盤賭選擇（RouletteWheelSelection）

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

<

r≤Qk

，則選擇復(fù)制第k個(gè)染色體

。復(fù)制前：復(fù)制后：

309.2.1遺傳算法的基本操作

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

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

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

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

(6)變異(mutation)

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

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

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

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

1.

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

二進(jìn)制編碼（binaryencoding)

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

)

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

,ximax

]和編碼精度則對(duì)應(yīng)二進(jìn)制數(shù)為

Ai

xi

和Ai的關(guān)系:

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

379.2.2遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)1.

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

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

例7：0111

，8：

1000則

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

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

399.2.2遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)3.

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

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

1.

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

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

41

目標(biāo)函數(shù)f(x)適應(yīng)度函數(shù)

Fit(x)

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

目標(biāo)函數(shù)f(x)到適應(yīng)度函數(shù)Fit(x)的變換

maxf(x)

minf(x)42

目標(biāo)函數(shù)f(x)適應(yīng)度函數(shù)

Fit(x)

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

目標(biāo)函數(shù)f(x)到適應(yīng)度函數(shù)Fit(x)的變換

maxf(x)

minf(x)439.2.2遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)四、選擇（復(fù)制）

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

各個(gè)個(gè)體被選擇的概率和其適應(yīng)度值成比例。

個(gè)體

i

被選擇的概率：

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

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

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

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

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

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

四、選擇（復(fù)制）

469.2.2遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)2.選擇個(gè)體方法2）錦標(biāo)賽選擇方法(tournamentselectionmodel)從群體中隨機(jī)選擇k

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

隨機(jī)競爭方法（stochastictournament）:每次按輪盤賭選擇方法選取一對(duì)個(gè)體，然后讓這兩個(gè)個(gè)體進(jìn)行競爭，適應(yīng)度高者獲勝。如此反復(fù)，直到選滿為止。

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

）和μ

＋λ選擇

(

μ,λ

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

μ

的群體所生成的λ

(≥μ)個(gè)后代中選取μ

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

μ＋λ

選擇：從λ

個(gè)后代與其父代中選取μ

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

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

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

五、交叉（基因重組）

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

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

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

9.4遺傳算法的應(yīng)用549.3遺傳算法的改進(jìn)算法

9.3.1雙倍體遺傳算法9.3.2雙種群遺傳算法9.3.3自適應(yīng)遺傳算法55

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

9.3.1雙倍體遺傳算法

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

9.3.1雙倍體遺傳算法9.3.2雙種群遺傳算法9.3.3自適應(yīng)遺傳算法589.3.2雙種群遺傳算法

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

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

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

9.3.1雙倍體遺傳算法9.3.2雙種群遺傳算法9.3.3自適應(yīng)遺傳算法619.3.3自適應(yīng)遺傳算法

1.基本思想

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

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