遺傳算法簡介課件

第七章遺傳算法與控制簡介第七章遺傳算法與控制簡介模擬進(jìn)化計(jì)算（SimulatedEvolutionaryComputation)是近十幾年來信息科學(xué)、人工智能與計(jì)算機(jī)科學(xué)的一大研究領(lǐng)域，由此所派生的求解優(yōu)化問題的仿生類算法（遺傳算法、演化策略、進(jìn)化程序），由于其鮮明的生物背景、新穎的設(shè)計(jì)原理、獨(dú)特的分析方法和成功的應(yīng)用實(shí)踐，正日益形成全局搜索與多目標(biāo)優(yōu)化理論的一個(gè)嶄新分支。遺傳算法（GeneticAlgorithm,簡稱GA）是通過模擬生物進(jìn)化過程來完成優(yōu)化搜索的。模擬進(jìn)化計(jì)算（SimulatedEvolutionary

科學(xué)研究、工程實(shí)際與國民經(jīng)濟(jì)發(fā)展的眾多問題可歸結(jié)為“最大效益、最小代價(jià)”這類典型的優(yōu)化模型。求解這類模型導(dǎo)致尋求某個(gè)目標(biāo)函數(shù)（有解析表達(dá)式或無解析表達(dá)式）在特定區(qū)域上的最優(yōu)解，傳統(tǒng)的建立在梯度計(jì)算基礎(chǔ)上的非線性規(guī)劃類方法，當(dāng)目標(biāo)函數(shù)僅具有單極點(diǎn)時(shí)，通常表現(xiàn)出較高的計(jì)算效率，但當(dāng)目標(biāo)函數(shù)具有多極值點(diǎn)時(shí)，由于其本身固有的局部優(yōu)化性及不穩(wěn)健等缺陷，而被廣泛認(rèn)為不適于全局優(yōu)化問題的求解。近二十年來，人們相繼發(fā)展了許多求解全局優(yōu)化問題的方法，一般可分為確定型與非確定型（如隨機(jī)搜索）算法。Monto-Carlo方法及模擬退火算法都?xì)w屬后者。當(dāng)目標(biāo)函數(shù)具有為數(shù)不多的極值點(diǎn)時(shí)，確定型算法常表現(xiàn)出較高的計(jì)算效率，但同時(shí)也暴露出算法復(fù)雜、對(duì)目標(biāo)函數(shù)的性質(zhì)要求高、可靠性差等缺點(diǎn)。相比而言，隨機(jī)搜索方法具有較強(qiáng)的魯棒性，算法容易實(shí)現(xiàn)，但常有計(jì)算效率低的缺點(diǎn)?？茖W(xué)研究、工程實(shí)際與國民經(jīng)濟(jì)發(fā)展的眾多問題可歸結(jié)為“最大效仿生類算法是近十幾年來才發(fā)展起來的一類新型全局優(yōu)化搜索技術(shù)，它們通過向自然界學(xué)習(xí)，借鑒生物進(jìn)化機(jī)制求解問題。這類算法的主要優(yōu)點(diǎn)在于其本質(zhì)上的并行性、廣泛的可適用性（如對(duì)目標(biāo)函數(shù)的性態(tài)無特殊要求，特別可以沒有明確的表達(dá)式）和較強(qiáng)的魯棒性、簡明性與全局優(yōu)化性能。雖然從基本思想的產(chǎn)生至今已有二、三十年的歷史，但廣泛用于求解優(yōu)化問題還是近十幾年的事。初步研究及廣泛的應(yīng)用實(shí)踐已顯示出它們作為可靠、有效的全局優(yōu)化算法的巨大潛力和誘人前景。仿生類算法，就其目前發(fā)展而言，可分為仿生過程算法與仿生結(jié)構(gòu)算法兩大類，前者以模擬進(jìn)化算法為代表，后者以神經(jīng)網(wǎng)絡(luò)為典型。仿生類算法是近十幾年來才發(fā)展起來的一類新型全局優(yōu)化搜索技術(shù)遺傳算法的生物學(xué)背景適者生存：最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群體。

生物進(jìn)化的基本過程：染色體(chromosome)：生物的遺傳物質(zhì)的主要載體?；?gene)：擴(kuò)展生物性狀的遺傳物質(zhì)的功能單元和結(jié)構(gòu)單位?；蜃╨ocus）：染色體中基因的位置。等位基因（alleles）：基因所取的值。遺傳算法的生物學(xué)背景適者生存：最適合自然環(huán)境的群體往往產(chǎn)生了生物遺傳概念遺產(chǎn)算法中的應(yīng)用適者生存目標(biāo)值比較大的解被選擇的可能性大個(gè)體（Individual）解染色體（Chromosome）解的編碼（字符串、向量等）基因（Gene）解中每一分量的特征適應(yīng)性（Fitness）適應(yīng)函數(shù)值群體（Population）根據(jù)適應(yīng)函數(shù)值選定的一組解（解的個(gè)數(shù)為群體的規(guī)模）婚配（Marry）交叉（Crossover）選擇兩個(gè)染色體進(jìn)行交叉產(chǎn)生一組新的染色體的過程變異（Mutation）編碼的某一分量發(fā)生變化的過程生物遺傳概念遺產(chǎn)算法中的應(yīng)用適者生存目標(biāo)值比較大的解被選擇的遺傳算法的基本思想：在求解問題時(shí)從多個(gè)解開始，然后通過一定的法則進(jìn)行逐步迭代以產(chǎn)生新的解。遺傳算法的基本思想：遺傳算法的發(fā)展歷史1962年，F(xiàn)raser提出了自然遺傳算法。1965年，Holland首次提出了人工遺傳操作的重要性。1967年，Bagley首次提出了遺傳算法這一術(shù)語。1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別中。1971年，Hollstien在論文《計(jì)算機(jī)控制系統(tǒng)中人工遺傳自適應(yīng)方法》中闡述了遺傳算法用于數(shù)字反饋控制的方法。1975年，美國J.Holland出版了《自然系統(tǒng)和人工系統(tǒng)的適配》；DeJong完成了重要論文《遺傳自適應(yīng)系統(tǒng)的行為分析》。20世紀(jì)80年代以后，遺傳算法進(jìn)入興盛發(fā)展時(shí)期。遺傳算法的發(fā)展歷史1962年，F(xiàn)raser提出了自然遺傳算法設(shè)計(jì)遺傳算法的基本原則與內(nèi)容

設(shè)計(jì)的基本原則：

適用性：算法所能適用的問題種類?？煽啃裕核惴▽?duì)于所設(shè)計(jì)的問題，以適當(dāng)?shù)木惹蠼馄渲写蠖鄶?shù)問題的能力。收斂性：算法能否收斂到全局最優(yōu)。穩(wěn)定性：算法對(duì)其控制參數(shù)及問題數(shù)據(jù)的敏感度。生物類比：通過類比的方法引入在生物界被認(rèn)為是有效的方法及操作。

設(shè)計(jì)遺傳算法的基本原則與內(nèi)容設(shè)計(jì)的基本原則：適用性：算法所設(shè)計(jì)的基本內(nèi)容：

設(shè)計(jì)遺傳算法的基本原則與內(nèi)容

編碼方案：編碼表示方式。適應(yīng)度函數(shù)：目標(biāo)函數(shù)。選擇策略：優(yōu)勝劣汰。控制參數(shù)：種群的規(guī)模、算法執(zhí)行的最大代數(shù)、執(zhí)行不同遺傳操作的概率等。遺傳算子：選擇(selection)；交叉(crossover)；變異(mutation)。算法的終止準(zhǔn)則：規(guī)定一個(gè)最大的演化代數(shù)，或算法在連續(xù)多少代以后解的適應(yīng)值沒有改進(jìn)。設(shè)計(jì)的基本內(nèi)容：設(shè)計(jì)遺傳算法的基本原則與內(nèi)容編碼方案遺傳算法的搜索機(jī)制遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。

遺傳算法的搜索機(jī)制遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生

基本遺傳算法基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。基本遺傳算法基本遺傳算法（SimpleGenetic基本遺傳算法的組成遺傳算法的五個(gè)基本要素：參數(shù)編碼初始群體的設(shè)定適應(yīng)度函數(shù)的設(shè)計(jì)遺傳操作設(shè)計(jì)控制參數(shù)設(shè)定基本遺傳算法的組成遺傳算法的五個(gè)基本要素：編碼位串編碼一維染色體編碼方法：將問題空間的參數(shù)編碼為一維排列的染色體的方法。二進(jìn)制編碼：用若干二進(jìn)制數(shù)表示一個(gè)個(gè)體，將原問題的解空間映射到位串空間B={0，1}上，然后在位串空間上進(jìn)行遺傳操作。

（1）二進(jìn)制編碼編碼位串編碼一維染色體編碼方法：將問題空間的參數(shù)編編碼(1)二進(jìn)制編碼（續(xù)）優(yōu)點(diǎn)：類似于生物染色體的組成，算法易于用生物遺傳理論解釋，遺傳操作如交叉、變異等易實(shí)現(xiàn)；算法處理的模式數(shù)最多。

缺點(diǎn)：①相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離，降低了遺傳算子的搜索效率。

15：01111

16：10000②要先給出求解的精度。③求解高維優(yōu)化問題的二進(jìn)制編碼串長，算法的搜索效率低。編碼(1)二進(jìn)制編碼（續(xù)）優(yōu)點(diǎn)：缺點(diǎn)：編碼（2）Gray編碼Gray編碼:將二進(jìn)制編碼通過一個(gè)變換進(jìn)行轉(zhuǎn)換得到的編碼。二進(jìn)制串

Gray

二進(jìn)制編碼Gray編碼Gray編碼二進(jìn)制編碼編碼（2）Gray編碼Gray編碼:將二進(jìn)制編碼編碼2.實(shí)數(shù)編碼

采用實(shí)數(shù)表達(dá)法不必進(jìn)行數(shù)制轉(zhuǎn)換，可直接在解的表現(xiàn)型上進(jìn)行遺傳操作。

多參數(shù)映射編碼的基本思想：把每個(gè)參數(shù)先進(jìn)行二進(jìn)制編碼得到子串，再把這些子串連成一個(gè)完整的染色體。

多參數(shù)映射編碼中的每個(gè)子串對(duì)應(yīng)各自的編碼參數(shù)，所以，可以有不同的串長度和參數(shù)的取值范圍。

編碼2.實(shí)數(shù)編碼采用實(shí)數(shù)表達(dá)法不必進(jìn)行數(shù)制轉(zhuǎn)換，編碼3.有序串編碼

有序問題：目標(biāo)函數(shù)的值不僅與表示解的字符串的值有關(guān)，而且與其所在字符串的位置有關(guān)。4．結(jié)構(gòu)式編碼

Goldberg等提出MessyGA(mGA)的遺傳算法編碼方法。

編碼3.有序串編碼有序問題：目標(biāo)函數(shù)的值不僅與表初始種群的產(chǎn)生群體設(shè)定

（1）根據(jù)問題固有知識(shí)，把握最優(yōu)解所占空間在整個(gè)問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。（2）隨機(jī)產(chǎn)生一定數(shù)目的個(gè)體，從中挑選最好的個(gè)體加到初始群體中。這種過程不斷迭代，直到初始群體中個(gè)體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。

初始種群的產(chǎn)生群體設(shè)定（1）根據(jù)問題固有知識(shí)，把握最優(yōu)解所2.種群規(guī)模的確定群體設(shè)定

模式定理表明：若群體規(guī)模為M，則遺傳操作可從這M個(gè)個(gè)體中生成和檢測個(gè)模式，并在此基礎(chǔ)上能夠不斷形成和優(yōu)化積木塊，直到找到最優(yōu)解。群體規(guī)模太小，遺傳算法的優(yōu)化性能不太好，易陷入局部最優(yōu)解。群體規(guī)模太大，計(jì)算復(fù)雜。2.種群規(guī)模的確定群體設(shè)定模式定理表明：若群體規(guī)模為將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法

適應(yīng)度函數(shù)

若目標(biāo)函數(shù)為最大化問題，則若目標(biāo)函數(shù)為最小化問題，則將目標(biāo)函數(shù)轉(zhuǎn)換為求最大值的形式,且保證函數(shù)值非負(fù)！

若目標(biāo)函數(shù)為最大化問題，則若目標(biāo)函數(shù)為最小化問題，則將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法適應(yīng)度函數(shù)若目標(biāo)函數(shù)為將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法(續(xù)）

適應(yīng)度函數(shù)

存在界限值預(yù)選估計(jì)困難或者不能精確估計(jì)的問題！

若目標(biāo)函數(shù)為最大化問題，則若目標(biāo)函數(shù)為最小化問題，則：目標(biāo)函數(shù)界限的保守估計(jì)值。將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法(續(xù)）適應(yīng)度函數(shù)存在界限適應(yīng)度函數(shù)的尺度變換

在遺傳算法中，將所有妨礙適應(yīng)度值高的個(gè)體產(chǎn)生，從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題（deceptiveproblem）。

過早收斂：縮小這些個(gè)體的適應(yīng)度，以降低這些超級(jí)個(gè)體的競爭力。

停滯現(xiàn)象：改變?cè)歼m應(yīng)值的比例關(guān)系，以提高個(gè)體之間的競爭力。適應(yīng)度函數(shù)的尺度變換（fitnessscaling）或者定標(biāo)：對(duì)適應(yīng)度函數(shù)值域的某種映射變換。適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的尺度變換在遺傳算法中，將所有妨礙適應(yīng)度值高的適應(yīng)度函數(shù)的尺度變換(續(xù)）

（1）線性變換：滿足滿足最小適應(yīng)度值非負(fù)適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的尺度變換(續(xù)）（1）線性變換：滿足滿足最小適應(yīng)適應(yīng)度函數(shù)的尺度變換(續(xù)）

（2）冪函數(shù)變換法：

（3）指數(shù)變換法：適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的尺度變換(續(xù)）（3）指數(shù)變換法：適應(yīng)度函數(shù)選擇

個(gè)體選擇概率分配方法選擇操作也稱為復(fù)制（reproduction）操作：從當(dāng)前群體中按照一定概率選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代繁殖下一代子孫。判斷個(gè)體優(yōu)良與否的準(zhǔn)則是各個(gè)個(gè)體的適應(yīng)度值：個(gè)體適應(yīng)度越高，其被選擇的機(jī)會(huì)就越多。

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

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

選擇

個(gè)體ff2P12.56.250.1821.01.000.0333.09.000.2641.21.440.0452.14.410.1360.80.640.0272.56.250.1881.31.690.0590.90.810.02101.83.240.09個(gè)體選擇概率分配方法各個(gè)個(gè)體被選擇的概率和其適應(yīng)度值成比1.個(gè)體選擇概率分配方法（2）排序方法（rank-basedmodel）①線性排序：J.E.Baker群體成員按適應(yīng)值大小從好到壞依次排列：個(gè)體按轉(zhuǎn)盤式選擇的方式選擇父體選擇

1.個(gè)體選擇概率分配方法①線性排序：J.E.Ba1.個(gè)體選擇概率分配方法（2）排序方法（rank-basedmodel）②非線性排序：Z.Michalewicz

將群體成員按適應(yīng)值從好到壞依次排列，并按下式分配選擇概率：選擇

1.個(gè)體選擇概率分配方法②非線性排序：Z.Mic1.個(gè)體選擇概率分配方法（2）排序方法（rank-basedmodel）

可用其他非線性函數(shù)來分配選擇概率，只要滿足以下條件：

選擇

1.個(gè)體選擇概率分配方法可用其他非線性函數(shù)來分配選擇概率2.選擇個(gè)體方法（1）轉(zhuǎn)盤賭選擇（roulettewheelselection）

按個(gè)體的選擇概率產(chǎn)生一個(gè)輪盤，輪盤每個(gè)區(qū)的角度與個(gè)體的選擇概率成比例。產(chǎn)生一個(gè)隨機(jī)數(shù)，它落入轉(zhuǎn)盤的哪個(gè)區(qū)域就選擇相應(yīng)的個(gè)體交叉。第1輪產(chǎn)生一個(gè)隨機(jī)數(shù)：0.81

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

選擇

2.選擇個(gè)體方法按個(gè)體的選擇概率產(chǎn)生一個(gè)輪盤，輪盤每2.選擇個(gè)體方法（2）錦標(biāo)賽選擇方法（tournamentselectionmodel）

錦標(biāo)賽選擇方法：從群體中隨機(jī)選擇個(gè)個(gè)體，將其中適應(yīng)度最高的個(gè)體保存到下一代。這一過程反復(fù)執(zhí)行，直到保存到下一代的個(gè)體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)量為止。

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

選擇

2.選擇個(gè)體方法錦標(biāo)賽選擇方法：從群體中隨機(jī)選擇個(gè)個(gè)2.選擇個(gè)體方法（3）和選擇從規(guī)模為的群體中隨機(jī)選取個(gè)體通過重組和變異生成個(gè)后代，再選取個(gè)最優(yōu)的后代作為新一代種群。從個(gè)后代與其父體共中選取個(gè)最優(yōu)的后代。選擇

2.選擇個(gè)體方法從規(guī)模為的群體中隨機(jī)選取個(gè)體通過2.選擇個(gè)體方法（4）Boltzmann錦標(biāo)賽選擇

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

隨機(jī)選取兩個(gè)個(gè)體，若則選擇適應(yīng)值好的作為勝者，否則計(jì)算概率，若，選擇差解，否則選擇好解。選擇

2.選擇個(gè)體方法最佳個(gè)體（elitistmodel交叉

1.基本的交叉算子（1）一點(diǎn)交叉（single-pointcrossover）一點(diǎn)交叉：在個(gè)體串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，實(shí)行交叉時(shí)，該點(diǎn)前或后的兩個(gè)個(gè)體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個(gè)新的個(gè)體。二點(diǎn)交叉：隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，將兩個(gè)交叉點(diǎn)之間的碼串相互交換。（2）二點(diǎn)交叉（two-pointcrossover）交叉1.基本的交叉算子一點(diǎn)交叉：在個(gè)體串中隨機(jī)設(shè)定交叉

基本的交叉算子（續(xù)）均勻交叉：按照均勻概率抽取一些位，每一位是否被選取都是隨機(jī)的，并且獨(dú)立于其他位。然后將兩個(gè)個(gè)體被抽取位互換組成兩個(gè)新個(gè)體。（3）均勻交叉（uniformcrossover）或一致交叉交叉基本的交叉算子（續(xù)）均勻交叉：按照均勻概率抽取一些交叉

2.修正的交叉方法（1）部分匹配交叉PMX：GoldbergD.E.和R.Lingle(1985)

交叉2.修正的交叉方法2.修正的交叉方法(續(xù)）（2）順序交叉OX：DavisL.(1985)

（3）循環(huán)交叉CX：SmithD.(1985)

交叉

2.修正的交叉方法(續(xù)）（3）循環(huán)交叉CX：Smith3.實(shí)數(shù)編碼的交叉方法（1）離散交叉（discretecrossover）

部分離散交叉：在父解向量中選擇一部分分量，然后交換這些分量?！M(jìn)制的點(diǎn)式交叉

整體離散交叉：以0.5的概率交換父體的所有分量?！M(jìn)制編碼的均勻性交叉

21ss與交叉

3.實(shí)數(shù)編碼的交叉方法部分離散交叉：在父解向量中選擇3.實(shí)數(shù)編碼的交叉方法（續(xù)）（2）算術(shù)交叉（arithmeticalcrossover）

部分算術(shù)：先在父解向量中選擇一部分分量，如第個(gè)分量以后的所有分量，然后生成個(gè)[0，1]區(qū)間的隨機(jī)數(shù)，并將兩個(gè)后代定義為：交叉

3.實(shí)數(shù)編碼的交叉方法（續(xù)）部分算術(shù)：先在父解向量中3.實(shí)數(shù)編碼的交叉方法（續(xù)）（2）算術(shù)交叉（arithmeticalcrossover）

整體算術(shù)交叉：先生成n個(gè)區(qū)間的隨機(jī)數(shù)，則后代分別定義為：交叉

3.實(shí)數(shù)編碼的交叉方法（續(xù)）整體算術(shù)交叉：先生成n1.整數(shù)編碼的變異方法（1）位點(diǎn)變異：群體中的個(gè)體碼串，隨機(jī)挑選一個(gè)或多個(gè)基因座，并對(duì)這些基因座的基因值以變異概率作變動(dòng)。（2）逆轉(zhuǎn)變異：在個(gè)體碼串中隨機(jī)選擇兩點(diǎn)（逆轉(zhuǎn)點(diǎn)），然后將兩點(diǎn)之間的基因值以逆向排序插入到原位置中。

（3）插入變異：在個(gè)體碼串中隨機(jī)選擇一個(gè)碼，然后將此碼插入隨機(jī)選擇的插入點(diǎn)中間。變異

1.整數(shù)編碼的變異方法（2）逆轉(zhuǎn)變異：在個(gè)體碼串中隨機(jī)選變異

1.整數(shù)編碼的變異方法（續(xù)）（4）互換變異：隨機(jī)選取染色體的兩個(gè)基因進(jìn)行簡單互換。（5）移動(dòng)變異：隨機(jī)選取一個(gè)基因，向左或者向右移動(dòng)一個(gè)隨機(jī)位數(shù)。（6）自適應(yīng)變異：類似于位點(diǎn)變異，但變異概率隨群體中個(gè)體的多樣性程度而自適應(yīng)調(diào)整。變異1.整數(shù)編碼的變異方法（續(xù)）2.實(shí)數(shù)編碼的變異方法（1）均勻性變異

均勻性變異：在父解向量中隨機(jī)地選擇一個(gè)分量（第個(gè)），然后在中以均勻概率隨機(jī)選擇代替以得到，即變異

2.實(shí)數(shù)編碼的變異方法均勻性變異：在父解向量中隨機(jī)地選2.實(shí)數(shù)編碼的變異方法（續(xù)）（2）正態(tài)性變異（normaldistributedmutation）

變異

2.實(shí)數(shù)編碼的變異方法（續(xù)）變異2.實(shí)數(shù)編碼的變異方法（續(xù)）（3）非一致性變異

Z.Michalewicz首先提出將變異算子的結(jié)果與演化代數(shù)聯(lián)系起來。在演化初期，變異范圍相對(duì)較大，而隨著演化的推進(jìn)，變異范圍越來越小，起著一種對(duì)演化系統(tǒng)的微調(diào)作用。變異

2.實(shí)數(shù)編碼的變異方法（續(xù)）Z.Michalew2.實(shí)數(shù)編碼的變異方法（續(xù)）（4）自適應(yīng)變異

自適應(yīng)變異方式與非一致性變異算子相同，只是將其中的演化代數(shù)改為，函數(shù)表達(dá)式變?yōu)椋?/p>

變異

2.實(shí)數(shù)編碼的變異方法（續(xù)）自適應(yīng)變異方式與非一致性變遺傳算法的一般步驟遺傳算法的一般步驟遺傳算法的簡單實(shí)例簡單實(shí)例產(chǎn)生初始種群計(jì)算適應(yīng)度0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）遺傳算法的簡單實(shí)例簡單實(shí)例0001100000010遺傳算法的簡單實(shí)例簡單實(shí)例選擇個(gè)體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.08695758＋5＋2＋10＋7＋12＋5＋19＋10＋140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174遺傳算法的簡單實(shí)例簡單實(shí)例個(gè)體染色體適應(yīng)度選擇概率累積概率1遺傳算法的簡單實(shí)例簡單實(shí)例選擇個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000遺傳算法的簡單實(shí)例簡單實(shí)例個(gè)體染色體適應(yīng)度選擇概率累積概率1遺傳算法的簡單實(shí)例簡單實(shí)例選擇在0～1之間產(chǎn)生一個(gè)隨機(jī)數(shù)：個(gè)體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！遺傳算法的簡單實(shí)例簡單實(shí)例個(gè)體染色體適應(yīng)度選擇概率累積概率1遺傳算法的簡單實(shí)例0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011簡單實(shí)例交叉00011000001110010110110000000110011101001010101010111001011010010110111001110100110000000100010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011遺傳算法的簡單實(shí)例00011000001110010遺傳算法的簡單實(shí)例簡單實(shí)例變異0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010010101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011遺傳算法的簡單實(shí)例簡單實(shí)例0001100000111遺傳算法的簡單實(shí)例簡單實(shí)例至下一代，適應(yīng)度計(jì)算→選擇→交叉→變異，直至滿足終止條件。遺傳算法的簡單實(shí)例簡單實(shí)例函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：x∈[-1,2]，求解結(jié)果精確到6位小數(shù)。函數(shù)優(yōu)化示例求下列一元函數(shù)的最大值：x∈[-1,2]SGA對(duì)于本例的編碼由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3×106等份。又因?yàn)?21<3×106<222，所以本例的二進(jìn)制編碼長度至少需要22位，本例的編碼過程實(shí)質(zhì)上是將區(qū)間[-1，2]內(nèi)對(duì)應(yīng)的實(shí)數(shù)值轉(zhuǎn)化為一個(gè)二進(jìn)制串（b21b20…b0）。SGA對(duì)于本例的編碼由于區(qū)間長度為3，求解結(jié)果精確到6位小幾個(gè)術(shù)語基因型：1000101110110101000111表現(xiàn)型：0.637197編碼解碼個(gè)體（染色體）基因幾個(gè)術(shù)語基因型：100010111011010100011初始種群SGA采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為初始種群。初始種群中個(gè)體的數(shù)量稱為種群規(guī)模。初始種群SGA采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱為適應(yīng)度函數(shù)

遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動(dòng)力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，它的設(shè)計(jì)應(yīng)結(jié)合求解問題本身的要求而定。適應(yīng)度函數(shù)遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來選擇算子遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度高的個(gè)體被遺傳到下一代群體中的概率大；適應(yīng)度低的個(gè)體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個(gè)體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。選擇算子遺傳算法使用選擇運(yùn)算來實(shí)現(xiàn)對(duì)群體中的個(gè)體進(jìn)行優(yōu)勝劣汰輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個(gè)體i的適應(yīng)度為Fi，則個(gè)體i被選中遺傳到下一代群體的概率為：輪盤賭選擇方法輪盤賭選擇又稱比例選擇算子，它的基本思想是：各輪盤賭選擇方法的實(shí)現(xiàn)步驟（1）計(jì)算群體中所有個(gè)體的適應(yīng)度函數(shù)值（需要解碼）；（2）利用比例選擇算子的公式，計(jì)算每個(gè)個(gè)體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機(jī)數(shù)與每個(gè)個(gè)體遺傳到下一代群體的概率進(jìn)行匹配）來確定各個(gè)個(gè)體是否遺傳到下一代群體中。輪盤賭選擇方法的實(shí)現(xiàn)步驟（1）計(jì)算群體中所有個(gè)體的適應(yīng)度函交叉算子所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。SGA中交叉算子采用單點(diǎn)交叉算子。交叉算子所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體依據(jù)交叉概單點(diǎn)交叉運(yùn)算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點(diǎn)單點(diǎn)交叉運(yùn)算交叉前：交叉點(diǎn)變異算子所謂變異運(yùn)算，是指依據(jù)變異概率Pm將個(gè)體編碼串中的某些基因值用其它基因值來替換，從而形成一個(gè)新的個(gè)體。遺傳算法中的變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。交叉運(yùn)算和變異運(yùn)算的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索。SGA中變異算子采用基本位變異算子。變異算子所謂變異運(yùn)算，是指依據(jù)變異概率Pm將個(gè)體編碼串基本位變異算子基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一位或某幾位基因作變異運(yùn)算。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)?。基本位變異算子基本位變異算子是指對(duì)個(gè)體編碼串隨機(jī)指定的某一基本位變異算子的執(zhí)行過程變異前：000001110000000010000變異后：000001110001000010000變異點(diǎn)基本位變異算子的執(zhí)行過程變異前：變異點(diǎn)運(yùn)行參數(shù)（1）M：種群規(guī)模（2）T：遺傳運(yùn)算的終止進(jìn)化代數(shù)（3）Pc：交叉概率（4）Pm：變異概率運(yùn)行參數(shù)（1）M：種群規(guī)模SGA的框圖產(chǎn)生初始群體是否滿足停止準(zhǔn)則是輸出結(jié)果并結(jié)束計(jì)算個(gè)體適應(yīng)度值比例選擇運(yùn)算單點(diǎn)交叉運(yùn)算基本位變異運(yùn)算否產(chǎn)生新一代群體執(zhí)行M/2次SGA的框圖產(chǎn)生初始群體是否滿足停止準(zhǔn)則是輸出結(jié)果并結(jié)束計(jì)遺傳算法的特點(diǎn)（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應(yīng)度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。遺傳算法的特點(diǎn)（1）群體搜索，易于并行化處理；遺傳算法原理1、遺傳算法的數(shù)學(xué)基礎(chǔ)2、遺傳算法的收斂性分析3、遺傳算法的改進(jìn)遺傳算法原理1、遺傳算法的數(shù)學(xué)基礎(chǔ)遺傳算法的數(shù)學(xué)基礎(chǔ)（1）模式定理（2）積木塊假設(shè)遺傳算法的數(shù)學(xué)基礎(chǔ)（1）模式定理模式模式是指種群個(gè)體基因串中的相似樣板，它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進(jìn)制編碼中，模式是基于三個(gè)字符集(0,1,*)的字符串，符號(hào)*代表任意字符，即0或者1。模式示例：10**1模式模式是指種群個(gè)體基因串中的相似樣板，它用來描述基因串中某兩個(gè)定義定義1：模式H中確定位置的個(gè)數(shù)稱為模式H的階，記作O(H)。例如O(10**1)=3。定義2：模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式H的定義距，記作δ(H)。例如δ(10**1)=4。兩個(gè)定義定義1：模式H中確定位置的個(gè)數(shù)稱為模式H的階模式的階和定義距的含義模式階用來反映不同模式間確定性的差異，模式階數(shù)越高，模式的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模式，也會(huì)有不同的性質(zhì)，而模式的定義距就反映了這種性質(zhì)的差異。模式的階和定義距的含義模式階用來反映不同模式間確定性的差異，模式定理模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。模式定理保證了較優(yōu)的模式（遺傳算法的較優(yōu)解）的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。模式定理模式定理：具有低階、短定義距以及平均適應(yīng)度高于種群平模式定理從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模式，在連續(xù)的后代里獲得至少以指數(shù)增長的串?dāng)?shù)目，這主要是因?yàn)檫x擇使最好的模式有更多的復(fù)制，交叉算子不容易破壞高頻率出現(xiàn)的、短定義長的模式，而一般突變概率又相當(dāng)小，因而它對(duì)這些重要的模式幾乎沒有影響。模式定理從模式定理可看出，有高平均適應(yīng)度、短定義距、低階的模積木塊假設(shè)積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在；而積木塊假設(shè)則指出了在遺傳算子的作用下，能生成全局最優(yōu)解。積木塊假設(shè)積木塊假設(shè)：遺傳算法通過短定義距、低階以及高平均遺傳算法的收斂性分析遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。遺傳算法的收斂性分析遺傳算法要實(shí)現(xiàn)全局收斂，首先要求任意初始種群規(guī)模對(duì)收斂性的影響通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會(huì)增加計(jì)算量，造成收斂時(shí)間太長，表現(xiàn)為收斂速度緩慢。種群規(guī)模對(duì)收斂性的影響通常，種群太小則不能提供足夠的采樣點(diǎn)，選擇操作對(duì)收斂性的影響選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。選擇操作對(duì)收斂性的影響選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率交叉概率對(duì)收斂性的影響交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時(shí)，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會(huì)使搜索停滯不前，造成算法的不收斂。交叉概率對(duì)收斂性的影響交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)變異概率對(duì)收斂性的影響變異操作是對(duì)種群模式的擾動(dòng)，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會(huì)使遺傳算法成為隨機(jī)搜索算法。變異概率對(duì)收斂性的影響變異操作是對(duì)種群模式的擾動(dòng)，有利于增加遺傳算法的本質(zhì)遺傳算法本質(zhì)上是對(duì)染色體模式所進(jìn)行的一系列運(yùn)算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。遺傳算法的本質(zhì)遺傳算法本質(zhì)上是對(duì)染色體模式所進(jìn)行的一系列運(yùn)遺傳算法的改進(jìn)遺傳欺騙問題：在遺傳算法進(jìn)化過程中，有時(shí)會(huì)產(chǎn)生一些超常的個(gè)體，這些個(gè)體因競爭力太突出而控制了選擇運(yùn)算過程，從而影響算法的全局優(yōu)化性能，導(dǎo)致算法獲得某個(gè)局部最優(yōu)解。遺傳算法的改進(jìn)遺傳欺騙問題：在遺傳算法進(jìn)化過程中，有時(shí)會(huì)產(chǎn)生遺傳算法的改進(jìn)途徑（1）對(duì)編碼方式的改進(jìn)（2）對(duì)遺傳算子的改進(jìn)（3）對(duì)控制參數(shù)的改進(jìn)（4）對(duì)執(zhí)行策略的改進(jìn)遺傳算法的改進(jìn)途徑（1）對(duì)編碼方式的改進(jìn)對(duì)編碼方式的改進(jìn)二進(jìn)制編碼優(yōu)點(diǎn)在于編碼、解碼操作簡單，交叉、變異等操作便于實(shí)現(xiàn)，缺點(diǎn)在于精度要求較高時(shí)，個(gè)體編碼串較長，使算法的搜索空間急劇擴(kuò)大，遺傳算法的性能降低。格雷編碼克服了二進(jìn)制編碼的不連續(xù)問題，浮點(diǎn)數(shù)編碼改善了遺傳算法的計(jì)算復(fù)雜性。對(duì)編碼方式的改進(jìn)二進(jìn)制編碼優(yōu)點(diǎn)在于編碼、解碼操作簡單，交叉、對(duì)遺傳算子的改進(jìn)排序選擇均勻交叉逆序變異（1）對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行降序排序；（2）根據(jù)具體求解問題，設(shè)計(jì)一個(gè)概率分配表，將各個(gè)概率值按上述排列次序分配給各個(gè)個(gè)體；（3）以各個(gè)個(gè)體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。對(duì)遺傳算子的改進(jìn)排序選擇（1）對(duì)群體中的所有個(gè)體按其適對(duì)遺傳算子的改進(jìn)排序選擇均勻交叉逆序變異（1）隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼長度相同的二進(jìn)制屏蔽字P=W1W2…Wn；（2）按下列規(guī)則從A、B兩個(gè)父代個(gè)體中產(chǎn)生兩個(gè)新個(gè)體X、Y：若Wi=0，則X的第i個(gè)基因繼承A的對(duì)應(yīng)基因，Y的第i個(gè)基因繼承B的對(duì)應(yīng)基因；若Wi=1，則A、B的第i個(gè)基因相互交換，從而生成X、Y的第i個(gè)基因。

對(duì)遺傳算子的改進(jìn)排序選擇（1）隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼長對(duì)遺傳算子的改進(jìn)排序選擇均勻交叉逆序變異變異前：348|7965|21變異前：348|5697|21對(duì)遺傳算子的改進(jìn)排序選擇變異前：對(duì)控制參數(shù)的改進(jìn)

Schaffer建議的最優(yōu)參數(shù)范圍是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。

對(duì)控制參數(shù)的改進(jìn)Schaffer建議對(duì)控制參數(shù)的改進(jìn)Srinvivas等人提出自適應(yīng)遺傳算法，即PC和Pm能夠隨適應(yīng)度自動(dòng)改變，當(dāng)種群的各個(gè)個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使二者增加，而當(dāng)種群適應(yīng)度比較分散時(shí)，使二者減小，同時(shí)對(duì)適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，采用較低的PC和Pm，使性能優(yōu)良的個(gè)體進(jìn)入下一代，而低于平均適應(yīng)值的個(gè)體，采用較高的PC和Pm，使性能較差的個(gè)體被淘汰。對(duì)控制參數(shù)的改進(jìn)Srinvivas等人提出自適應(yīng)遺傳算法，即對(duì)執(zhí)行策略的改進(jìn)混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法對(duì)執(zhí)行策略的改進(jìn)混合遺傳算法遺傳算法的應(yīng)用1、遺傳算法的應(yīng)用領(lǐng)域2、遺傳算法的應(yīng)用示例遺傳算法的應(yīng)用1、遺傳算法的應(yīng)用領(lǐng)域遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化（2）函數(shù)優(yōu)化（3）自動(dòng)控制（4）生產(chǎn)調(diào)度（5）圖像處理（6）機(jī)器學(xué)習(xí)（7）人工生命（8）數(shù)據(jù)挖掘

遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化遺傳算法的應(yīng)用示例[例]設(shè)有函數(shù)，求其在[0，31]區(qū)間的最大值。（1）確定適當(dāng)?shù)木幋a，把問題的可能解表示為染色體數(shù)字串。因?yàn)橛幸粋€(gè)決策變量，其取值范圍為[0，31]，25=32，使用5位無符號(hào)二進(jìn)制數(shù)組成的染色體數(shù)字串，即可表達(dá)變量x，以及問題的解答方案。（2）選擇初始種群。通過隨機(jī)的方法產(chǎn)生由4個(gè)染色體的數(shù)字串組成的初始種群。遺傳算法的應(yīng)用示例[例]設(shè)有函數(shù)編號(hào)初始種群X值適應(yīng)度x2選擇概率期望值實(shí)際數(shù)（轉(zhuǎn)輪選擇）101101131690.140.581211000245760.491.9723010008640.060.220410011193610.311.231和11701.004.004.0平均2930.251.001.0最大5760.491.972.0編號(hào)初始種群X值適應(yīng)度x2選擇概率期望值實(shí)際數(shù)（轉(zhuǎn)輪選擇）1遺傳算法的應(yīng)用示例（3）計(jì)算適應(yīng)度值及選擇概率。此問題中染色體的適應(yīng)度取為函數(shù)自身，為計(jì)算每個(gè)染色體的適應(yīng)度，先將染色體解碼，求出其二進(jìn)制數(shù)字串等價(jià)的十進(jìn)制數(shù)，即x值。再由x值計(jì)算目標(biāo)函數(shù)的值。在此基礎(chǔ)上計(jì)算選擇概率和適應(yīng)度期望值，計(jì)算結(jié)果如上表所示。遺傳算法的應(yīng)用示例（3）計(jì)算適應(yīng)度值及選擇概率。遺傳算法的應(yīng)用示例（4）選擇進(jìn)入交換集的染色體。按適應(yīng)度比例法，選擇進(jìn)入交換集的染色體，如上表所示，染色體1和4均被選擇了1次；染色體2被選擇了2次；染色體3沒有被選擇。也就是說染色體3被淘汰了。所選擇的4個(gè)染色體被送到交換集，準(zhǔn)備參加交換。遺傳算法的應(yīng)用示例（4）選擇進(jìn)入交換集的染色體。遺傳算法的應(yīng)用示例（5）交換染色體。首先對(duì)進(jìn)入交換集的染色體進(jìn)行隨機(jī)配對(duì)，此例中是染色體2和1配對(duì)，染色體4和3配對(duì)。接著隨機(jī)確定交換位置，結(jié)果是第1對(duì)染色體交換位置是4，第2對(duì)染色體交換位置為2。經(jīng)交換操作后得到的新種群如下表所示。（6）變異。此例中變異概率取為0.001。由于種群中4個(gè)染色體總共有20位代碼，變異的期望次數(shù)為20*0.001=0.02位，這意味著本群體不進(jìn)行變異操作。遺傳算法的應(yīng)用示例（5）交換染色體。復(fù)制后交換集種群交換配對(duì)（