遺傳算法簡介課件

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

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

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

設計的基本原則：

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

設計遺傳算法的基本原則與內容設計的基本原則：適用性：算法所設計的基本內容：

設計遺傳算法的基本原則與內容

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

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

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

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

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

15：01111

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

Gray

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

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

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

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

編碼2.實數(shù)編碼采用實數(shù)表達法不必進行數(shù)制轉換，編碼3.有序串編碼

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

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

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

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

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

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

適應度函數(shù)

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

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

適應度函數(shù)

存在界限值預選估計困難或者不能精確估計的問題！

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

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

過早收斂：縮小這些個體的適應度，以降低這些超級個體的競爭力。

停滯現(xiàn)象：改變原始適應值的比例關系，以提高個體之間的競爭力。適應度函數(shù)的尺度變換（fitnessscaling）或者定標：對適應度函數(shù)值域的某種映射變換。適應度函數(shù)

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

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

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

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

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

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

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

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

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

選擇

個體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個體選擇概率分配方法各個個體被選擇的概率和其適應度值成比1.個體選擇概率分配方法（2）排序方法（rank-basedmodel）①線性排序：J.E.Baker群體成員按適應值大小從好到壞依次排列：個體按轉盤式選擇的方式選擇父體選擇

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

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

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

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

選擇

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

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

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

選擇

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

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

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

選擇

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

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

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

隨機選取兩個個體，若則選擇適應值好的作為勝者，否則計算概率，若，選擇差解，否則選擇好解。選擇

2.選擇個體方法最佳個體（elitistmodel交叉

1.基本的交叉算子（1）一點交叉（single-pointcrossover）一點交叉：在個體串中隨機設定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結構進行互換，并生成兩個新的個體。二點交叉：隨機設置兩個交叉點，將兩個交叉點之間的碼串相互交換。（2）二點交叉（two-pointcrossover）交叉1.基本的交叉算子一點交叉：在個體串中隨機設定交叉

基本的交叉算子（續(xù)）均勻交叉：按照均勻概率抽取一些位，每一位是否被選取都是隨機的，并且獨立于其他位。然后將兩個個體被抽取位互換組成兩個新個體。（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ù)編碼的交叉方法（1）離散交叉（discretecrossover）

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

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

21ss與交叉

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

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

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

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

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

（3）插入變異：在個體碼串中隨機選擇一個碼，然后將此碼插入隨機選擇的插入點中間。變異

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

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

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

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

變異

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

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

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

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

變異

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

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

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

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

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

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