遺傳算法原理與應用課件

遺傳算法一、生物學知識點

二、遺傳算法概述

三、遺傳算法原理四、遺傳算法應用一、生物學知識點1.1達爾文的自然選擇說(thetheoryofnaturalselection)遺傳（heredity）：子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異（variation）：子代與父代，子代不同個體之間總有差異，是生命多樣性的根源；生存斗爭和適者生存：具有適應性變異的個體被保留，不具適應性變異的個體被淘汰。自然選擇過程是長期的、緩慢的、連續(xù)的過程。1.2遺傳學基本概念與術(shù)語染色體（chromosome）：遺傳物質(zhì)的載體；脫氧核糖核酸（DNA）：大分子有機聚合物，雙螺旋結(jié)構(gòu)；遺傳因子（gene）：DNA或RNA（核糖核酸）長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；基因型（genotype）：遺傳因子組合的模型；表現(xiàn)型（phenotype）：由染色體決定性狀的外部表現(xiàn)；個體（individual）：指染色體帶有特征的實體；種群（population）：生活在一定區(qū)域的同種生物的全部個體；進化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進化；適應度（fitness）：度量某個物種對于生存環(huán)境的適應程度。對生存環(huán)境適應程度較高的物種將獲得更多的繁殖機會，而對生存環(huán)境適應程度較低的物種，其繁殖機會就會相對較少，甚至逐漸滅絕;選擇（selection）：指決定以一定的概率從種群中選擇若干個體的操作；復制（reproduction）：細胞在分裂時，遺傳物質(zhì)DNA通過復制而轉(zhuǎn)移到新產(chǎn)生的細胞中，新的細胞就繼承了舊細胞的基因;交叉（crossover）：在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體;變異（mutation）：在細胞進行復制時可能以很小的概率產(chǎn)生某些復制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀;2.2遺傳算法的基本思想（1）產(chǎn)生初始種群（2）根據(jù)問題的目標函數(shù)構(gòu)造適值函數(shù)（3）根據(jù)適值的好壞不斷選擇和繁殖（4）若干代后得到適應值最好的個體即為最優(yōu)解2.3遺傳算法的本質(zhì)

遺傳算法本質(zhì)上是對染色體模式所進行的一系列運算，即通過選擇算子將當前種群中的優(yōu)良模式遺傳到下一代種群中，利用交叉算子進行模式重組，利用突變算子進行模式突變。通過這些遺傳操作，模式逐步向較好的方向進化，最終得到問題的最優(yōu)解。2.4遺傳算法的操作

基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA，又稱簡單遺傳算法或標準遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。

1、SGA的基本流程框圖產(chǎn)生初始群體是否滿足停止準則是輸出結(jié)果并結(jié)束計算個體適應度值比例選擇運算單點交叉運算基本位突變運算否產(chǎn)生新一代群體2、基本遺傳算法的組成

（1）產(chǎn)生初始種群（1）產(chǎn)生初始種群（1）產(chǎn)生初始種群（1）產(chǎn)生初始種群（4）遺傳算子（2）編碼（3）適應度函數(shù)（5）選擇策略（1）產(chǎn)生初始種群（2）編碼（1）產(chǎn)生初始種群（2）編碼（1）產(chǎn)生初始種群（2）編碼（1）產(chǎn)生初始種群（2）編碼（1）產(chǎn)生初始種群（2）編碼（1）產(chǎn)生初始種群（4）遺傳算子（2）編碼（4）遺傳算子（2）編碼（4）遺傳算子（4）遺傳算子（2）編碼（3）適應度函數(shù)（5）選擇策略（2）編碼（2）編碼（2）編碼（2）編碼（2）編碼（4）遺傳算子（2）編碼（4）遺傳算子（2）編碼（4）遺傳算子（4）遺傳算子（2）編碼（2）編碼（2）編碼（2）編碼（2）編碼（2）編碼（4）遺傳算子（2）編碼（4）遺傳算子（1）編碼（2）產(chǎn)生初始種群（6）停止準則（3）適值函數(shù)（5）選擇策略（4）遺傳算子（1）編碼

遺傳算法是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進制串進行編碼。SGA二進制編碼染色體表示為：X=(x1,x2,…xn),1≤i≤n染色體的每一位，即xi是一個基因。每位的取值稱為位值。n為染色體的長度。如：X=（0010010）表示一個染色體，長度為。適用于三種情況：背包問題、實優(yōu)化問題、指派問題。缺點：編碼長不利于計算。優(yōu)點：便于位值計算，包括的實數(shù)范圍大。有關(guān)術(shù)語

基因型：001000111

表現(xiàn)型：71

編碼解碼個體（染色體）基因

在遺傳算法運行時，遺傳運算是對編碼后的染色體進行操作，即在編碼空間操作。而染色體進行評估與選擇要在解空間進行。（2）產(chǎn)生初始種群

初始種群是隨機產(chǎn)生的，具體的產(chǎn)生方式依賴于編碼方法，種群的大小依賴于計算機的計算能力和計算復雜度。例如：隨機產(chǎn)生ζi∈U(0,1)若ζi>0.5，則xi=1

若ζi≤0.5，則xi=0（3）適值函數(shù)

在遺傳算法中，使用適值函數(shù)來表征種群中每個個體對其生存環(huán)境的適應能力，每個個體具有一個適應值。適應值是群體中個體生存機會的唯一確定性指標。個體的適應值越大，該個體被遺傳到下一代的概率越大；反之，均越小。目標函數(shù)適值函數(shù)（4）遺傳算子

即遺傳操作，是關(guān)于染色體的運算。遺傳算法中有三種遺傳操作:

●

選擇-復制(selection-reproduction)

●

交叉(crossover，有單切點和雙切點交叉)

●

變異(mutation，亦稱突變)1）選擇算子遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應度高的個體被遺傳到下一代群體中的概率大；適應度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。2）交叉算子

所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。SGA中交叉算子采用單點交叉算子。交叉率(crossoverrate)Pc是指參加交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例。單點交叉運算

隨機選擇一個切點：交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點注：并不是所有的被選中的父代都有進行交叉操作，要設(shè)定一個交叉概率Pc，一般取為一個較大的數(shù)，比如0.9。3）突變算子

所謂突變運算，是指依據(jù)突變概率Pm將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。SGA中突變算子采用基本位突變算子。變異率Pm是指種群中變異基因數(shù)在總基因數(shù)的百分比。其控制著新基因?qū)敕N群的比例。基本位突變算子：

基本位突變算子是指對個體編碼串隨機指定的某一位或某幾位基因作突變運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行突變操作的某一基因座上的原有基因值為0，則突變操作將其變?yōu)?；反之，若原有基因值為1，則突變操作將其變?yōu)??；疚煌蛔兯阕拥膱?zhí)行過程

即改變?nèi)旧w某個(些)位上的基因。突變前：000001110000000010000突變后：000001110001000010000突變點(5)選擇策略

最常用的選擇策略是正比選擇（ProportionalSelection）策略，即每個個體被選中進行遺傳運算的概率為該個體的適應值和群體中所有個體適應值總和的比例。對于個體i，設(shè)其適應值為,種群規(guī)模為NP，則該個體的選擇概率為(5)選擇策略

得到選擇概率后，采用旋輪法來實現(xiàn)選擇操作。令共輪轉(zhuǎn)NP次。每次輪轉(zhuǎn)時，隨機產(chǎn)生，當，則選擇個體。旋輪法

當NP=10時的旋輪法示意圖旋轉(zhuǎn)著的轉(zhuǎn)輪停在的那一個扇面上的概率與其圓心角成正比。如圖：的適應值較高，作為優(yōu)良的個體，其將獲得較多的繁殖機會，后代很像。(6)停止準則

遺傳算法的停止準則一般是采用設(shè)定最大代數(shù)的方法，最大代數(shù)常表示為NG。2.5遺傳算法的特點

（1）群體搜索，易于并行化處理；（2）不是盲目窮舉，而是啟發(fā)式搜索；（3）適應度函數(shù)不受連續(xù)、可微等條件的約束，適用范圍很廣。三、遺傳算法原理

3.1模板理論

模板是若干位取確定值，其他位不確定的一類個體的總稱，用S來表示。它用來描述基因串中某些特征位相同的結(jié)構(gòu)。在二進制編碼中，模板是基于三個字符集(0,1,*)的字符串，符號“*”代表任意字符，即0或者1。

模式示例：10**1兩個定義定義1：模板S中確定位置的個數(shù)稱為模板S的階，記作。例如：。定義2：模板S中第一個確定位置和最后一個確定位置之間的距離稱為模板S的定義距，即模板的長度，記作。。例如：

。

二者的含義

模板階用來反映不同模板間確定性的差異，模板階數(shù)越高，模板的確定性就越高，所匹配的樣本數(shù)就越少。在遺傳操作中，即使階數(shù)相同的模板，也會有不同的性質(zhì)，而模板的定義距就反映了這種性質(zhì)的差異。

模板理論常識：

n位編碼的總長度為n-1。階數(shù)為的模板，模板S中的個體總數(shù)為。對于一個n位的二進制表達，染色體長度為n，有模板數(shù)>個體數(shù)即分類方法數(shù)>個體總數(shù)因為模板中每一位的取值可以為0,1或者*，所以模板總數(shù)為，而個體中每一位只能取0或者1，所以個體總數(shù)為。

模板定理：具有低階、短定義距以及平均適應度高于種群平均適應度的模板在子代中呈指數(shù)增長。

引理3.2.1：在正比選擇下，模板在第代的期望個體數(shù)為其中，是第代模板中所有個體的適應值均值與種群中所有個體適應值均值的比。是第代屬于模板的個體數(shù)。3.2模板定理模板定理:對于使用單切點交叉操作的遺傳算法：引理3.2.2：第代以概率做交叉，對長度為的模板中的個體，則在第代中該個體仍為中個體的概率下界為其中，為第代個體為的概率。模板定理:對于使用簡單基因位變異方式的遺傳算法：引理3.3.3：若第代以概率做變異，對于一個階數(shù)為的模板中的個體，則在第代仍為的概率的下界為

模板定理:主定理：第代以概率和做交叉和變異時，長度為，階數(shù)為，適應值均值比為的模板在第代的期望個體數(shù)的下界為如果則隨代數(shù)的增加而增加。3.3遺傳算法的收斂性分析

遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和突變概率。

1、種群規(guī)模對收斂性的影響

通常，種群太小則不能提供足夠的采樣點，以致算法性能很差；種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。2、選擇操作對收斂性的影響

選擇操作使高適應度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和突變操作，使之直接進入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。3、交叉概率對收斂性的影響

交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應度值的個體很快被破壞掉；概率太小時，交叉操作很少進行，從而會使搜索停滯不前，造成算法的不收斂。

4、突變概率對收斂性的影響

突變操作是對種群模式的擾動，有利于增加種群的多樣性。但是，突變概率太小則很難產(chǎn)生新模式，突變概率太大則會使遺傳算法成為隨機搜索算法。

3.4遺傳算法的改進

在遺傳算法進化過程中，有時會產(chǎn)生一些超常的個體，這些個體因競爭力太突出而控制了選擇運算過程，從而影響算法的全局優(yōu)化性能，導致算法獲得某個局部最優(yōu)解。遺傳算法的改進途徑（1）對編碼方式的改進（2）對適值函數(shù)的改進（3）對遺傳算子的改進（4）對控制參數(shù)的改進（5）對執(zhí)行策略的改進（6）對停止準則的改進（1）對編碼方式的改進

二進制編碼的優(yōu)點在于編碼和解碼的操作簡單，交叉、突變等操作便于實現(xiàn)。0-1編碼之外的其他三種重要的編碼方法：1）順序編碼2）實數(shù)編碼3）整數(shù)編碼

對于遺傳運算中的問題有兩種應對策略：1）拒絕2）修復使用拒絕策略，需要在遺傳操作中出現(xiàn)不合法編碼的比例很小。如果使用修復策略，可能使后代部分丟失父代基因。

修復策略：

修復順序編碼實數(shù)編碼交叉修復變異修復部分映射交叉順序交叉循環(huán)交叉換位變異移位變異交叉變異單切點交叉雙切點交叉位值變異向梯度方向變異（2）對適值函數(shù)的改進1）標定的定義：從目標函數(shù)映射到適值函數(shù)的過程為標定。2）標定的目的：a）將目標函數(shù)映射為適值函數(shù)。b）可以調(diào)節(jié)選擇壓力大小。而通過調(diào)節(jié)選擇壓力大小能夠?qū)崿F(xiàn)遺傳算法中局部搜索和廣域搜索的調(diào)節(jié)。例如：五個染色體構(gòu)成的一個種群，其目標函數(shù)值分別為

f1=1010f2=1008f3=1002f4=1005f5=1015選擇壓力：指種群中好、壞個體被選中的概率之差。如果差別較大，則稱選擇壓力大。

各個染色體被選中的概率為P1=0.2P2=0.2P3=0.2P4=0.2P5=0.2對目標函數(shù)進行標定，調(diào)節(jié)選擇壓力。標定：F=f-1000顯然標定后，各個染色體被選中的概率差別大幅度增加，即選擇壓力增大了。各染色體的適值：F1=f1-1000=10F2=f2-1000=8F3=f3-1000=2F4=f4-1000=5F5=f5-1000=15標定后各個染色體被選中的概率為：P'1==0.25P'2==0.2P'3==0.05P'4==0.15P'5==0.3753）適值的標定方法

線性標定正規(guī)化技術(shù)窗口技術(shù)對數(shù)標定指數(shù)標定冪律標定動態(tài)性標定標定方法（3）對遺傳算子的改進排序選擇均勻交叉逆序突變（1）對群體中的所有個體按其適應度大小進行降序排序；（2）根據(jù)具體求解問題，設(shè)計一個概率分配表，將各個概率值按上述排列次序分配給各個個體；（3）以各個個體所分配到的概率值作為其遺傳到下一代的概率，基于這些概率用賭盤選擇法來產(chǎn)生下一代群體。輪盤賭選擇又稱比例選擇算子，它的基本思想是：各個個體被選中的概率與其適應度函數(shù)值大小成正比。設(shè)群體大小為n，個體i的適應度為Fi，則個體i被選中遺傳到下一代群體的概率為：賭盤選擇法（1）計算群體中所有個體的適應度函數(shù)值（需要解碼）；（2）利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3）采用模擬賭盤操作（即生成0到1之間的隨機數(shù)與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。賭盤選擇法的實現(xiàn)步驟排序選擇均勻交叉逆序突變（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個基因。排序選擇均勻交叉逆序突變突變前：348|7965|21突變后：348|5697|21（4）對控制參數(shù)的改進Schaffer建議的最優(yōu)參數(shù)范圍是：種群規(guī)模：NP=20--100遺傳運算的終止進化代數(shù)：

T=100--500交叉概率：Pc=0.4--0.9突變概率：Pm=0.001--0.01。

參數(shù)分析交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性；Pc越大，新個體產(chǎn)生的速度就越快，但過大會使優(yōu)秀個體的結(jié)構(gòu)很快被破壞；Pc過小，搜索過程緩慢，以至停止不前；Pm過小，不易產(chǎn)生新個體結(jié)構(gòu)，Pm過大，變成純粹的隨機搜索；自適應策略Srinvivas等提出一種自適應遺傳算法，Pc和Pm能夠隨適應度自動改變：當種群各個體適應度趨于一致或趨于局部最優(yōu)時，使Pc和Pm增加；而當群體適應度比較分散時，使Pc和Pm減少；對于適應度較高的個體，對應于較低的Pc和Pm

；而較低適應度的個體，對應于較高的Pc和Pm

。（5）對執(zhí)行策略的改進混合遺傳算法免疫遺傳算法小生境遺傳算法單親遺傳算法并行遺傳算法（6）停止準則的改進

在算法的執(zhí)行過程中保留歷史上最好的個體，觀察指標如下：當上述指標趨近于1時，說明種群收斂。指種群中所有個體適應值的平均值個體適應值的最大值四、遺傳算法的應用4.1遺傳算法的應用領(lǐng)域(1)組合優(yōu)化(2)函數(shù)優(yōu)化(3)智能控制

(4)圖像處理(5)機器學習(6)人工生命(1)組合優(yōu)化

組合優(yōu)化是指在給定約束條件下,求解目標函數(shù)的最優(yōu)值。實踐證明，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、網(wǎng)絡路由等具有NP難度的組合優(yōu)化問題上取得了成功的應用。(2)函數(shù)優(yōu)化

工程上經(jīng)常會遇到在多準則或多設(shè)計目標下設(shè)計和決策的問題，如果這些目標是相背的，需要找到滿足這些目標的最佳設(shè)計方案。通常的做法是根據(jù)某有效函數(shù)將多目標合成單一目標來進行優(yōu)化。簡單函數(shù)優(yōu)化的實例

例:利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。y=x2

31

XY簡單函數(shù)優(yōu)化的實例

分析:

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，[0,31］中的點x就是個體,函數(shù)值

f(x)恰好就可以作為x的適應度，區(qū)間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就可以用遺傳算法來解決。

解:(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進制數(shù)編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定義適應度函數(shù),

取適應度函數(shù)：f(x)=x2(3)計算各代種群中的各個體的適應度,并對其染色體進行遺傳操作,直到適應度最高的個體(即31（11111）)出現(xiàn)為止。首先計算種群S1中各個體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應度f(si)

。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361

再計算種群S1中各個體的選擇概率。由此可求得

P(s1)=P(13)=0.14

P(s2)=P(24)=0.49

P(s3)=P(8)=0.06P(s4)=P(19)=0.31選擇概率的計算公式為：賭輪選擇法

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個均勻分布的隨機數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),

則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為s40.31s20.49s10.14s30.06

賭輪選擇示意輪盤賭選擇方法

積累概率:00.140.630.691q1q2

q3

q4

0.140.490.060.31概率積累概率選擇-復制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個隨機數(shù)如下:r1=0.450126,

r2=0.110347

r3=0.572496,r4=0.98503

染色體

適應度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，經(jīng)復制得群體：s1’=11000（24）,s2’=01101（13）s3’=11000（24）,s4’=10011（19）交叉設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運算。設(shè)s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）變異設(shè)變異率pm=0.001。這樣，群體S1中共有5×4×0.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

第二代種群S2中各染色體的情況

染色體

適應度選擇概率積累概率

估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.44

1s3=110117290.410.85

1s4=100002560.151.001假設(shè)這一輪選擇-復制操作中，種群S2中的4個染色體都被選中，則得到群體：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得：s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍然不會發(fā)生變異。

于是得第三代種群S3：s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

第三代種群S3中各染色體的情況

染色體

適應度選擇概率積累概率

估計的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001設(shè)這一輪