遺傳算法講稿

第八章遺傳算法

1

GA的基本思想來源于Darwin的進化論和Mendel的遺傳學說。Darwin的進化論認為每一物種在不斷的發(fā)展過程中都是越來越適應環(huán)境。物種的每個個體的基本特征被后代所繼承，但后代又不完全同于父代，這些新的變化，若適應環(huán)境，則被保留下來。在某一環(huán)境中也是那些更能適應環(huán)境的個體特征能被保留下來，這就是適者生存的原理。遺傳算法的由來2達爾文進化論3同樣的，人類也是一代比一代聰明，可以說人類近百年創(chuàng)造的文明比人類前面幾千年創(chuàng)造的文明還要多。4因此：我們得到的結論是：

生物一代比一代優(yōu)生物雖然一代比一代優(yōu)，但并不是說后一代與前一代沒有任何的關系，后一代或多或少總與前一代有些相同，也有一些不同。生物的后一代總是或多或少的繼承了前一代的一些特性，這就叫遺傳。而后一代又不完全像前一代，這叫變異。生物在進化的過程中既有遺傳，又有變異，生物就是在這樣的遺傳、變異的作用那個下，一代一代的繁衍下去，而且得到的是一代比一代優(yōu)。58.1遺傳算法的基本概念

1.個體與種群

●個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。

●

種群(population)就是模擬生物種群而由若干個體組成的群體,它一般是整個搜索空間的一個很小的子集。6

2.適應度與適應度函數(shù)

●

適應度(fitness)就是借鑒生物個體對環(huán)境的適應程度,而對問題中的個體對象所設計的表征其優(yōu)劣的一種測度。

●適應度函數(shù)(fitnessfunction)就是問題中的全體個體與其適應度之間的一個對應關系。它一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導搜索的評價函數(shù)。

73.染色體與基因

染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個體染色體9

----

1001染色體長度l=4（2，5，6）----010101110l=38遺傳算法基本概念和術語進化（evolution）生物在其延續(xù)生存的過程中，逐漸適應其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進化。生物的進化是以種群的形式進行的。94.遺傳操作亦稱遺傳算子(geneticoperator)，就是關于染色體的運算。遺傳算法中有三種遺傳操作:

●

選擇-復制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

10遺傳算法基本概念和術語選擇（selection）按照一定概率隨機地選擇兩對個體進行繁殖(即生成后繼狀態(tài))遺傳算法在很大程度上是一種偶然性現(xiàn)象，隨機過程在其中起重要作用。一般而言，選擇的過程是一種基于適應度的優(yōu)勝劣汰的過程。11復制(又稱繁殖)是從一個舊種群(oldpopulation)中選擇生命力強的個體位串(或稱字符串)產(chǎn)生新種群的過程?；蛘哒f，復制是個體位串根據(jù)其目標函數(shù)(即適應度函數(shù))拷貝自己的過程。根據(jù)位串的適應度值拷貝位串意味著，具有較高適應度值的位串更有可能在下一代中產(chǎn)生一個或多個后代。顯然，這個操作是模仿自然選擇現(xiàn)象，將達爾文的適者生存理論應用于位串的復制，適應度值是該位串被復制或被淘汰的決定因素。8.1遺傳算法基本原理12

選擇-復制通常做法是：對于一個規(guī)模為N的種群S,按每個染色體xi∈S的選擇概率P(xi)所決定的選中機會,分N次從S中隨機選定N個染色體,并進行復制。

這里的選擇概率P(xi)的計算公式為13遺傳算法基本概念和術語交叉（crossover）

有性生殖生物在繁殖下一代時，兩個同源染色體通過交叉而重組，亦即在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體。這個過程又稱基因重組（recombination），俗稱“雜交”。14交叉操作交叉操作的幾種方式：一點交叉兩點交叉?zhèn)€體A1001┆111→1001000新個體A*個體B0011┆000→0011111新個體B*個體A10┆110┆11→1001011新個體A*個體B00┆010┆00→0011000新個體B*僅對兩個交叉點之間的碼串進行交換15交叉操作多點交叉（廣義交叉）在藍綠兩個染色體隨機選擇4個交叉點四點交叉圖示在紅綠兩個染色體隨機選擇3個交叉點三點交叉圖示16交叉操作一致交叉其他交叉法

舊個體A001111

舊個體B111100——————————————

屏蔽字010101(第246互換)

——————————————新個體A*011110新個體B*101101二維交叉，樹結構交叉等17遺傳算法基本概念和術語變異（mutation）

在細胞進行復制時可能以很小的概率產(chǎn)生某些復制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀。18變異就是改變?nèi)旧w某個(些)位上的基因。（0變?yōu)?或1變?yōu)?）例如,設染色體s=11001101將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。其中變異的位置是隨機的。19遺傳算法各步驟的評價選擇---優(yōu)勝劣汰

選擇操作為種群提供了演進的方向交叉---優(yōu)優(yōu)組合

交叉操作的作用在于匯集散布于不同個體間的局部優(yōu)勢模式變異

---尋找新模式

變異操作是種群向外擴展的觸角(隨機)

好的變異將保留，壞的淘汰20遺傳學相關概念遺傳學遺傳算法數(shù)學1個體要處理的基本對象、結構也就是可行解2群體個體的集合被選定的一組可行解3染色體個體的表現(xiàn)形式可行解的編碼4基因染色體中的元素編碼中的元素5基因位某一基因在染色體中的位置元素在編碼中的位置6適應值個體對于環(huán)境的適應程度，或在環(huán)境壓力下的生存能力可行解所對應的適應函數(shù)值7種群被選定的一組染色體或個體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作保留或復制適應值大的可行解，去掉小的可行解21遺傳學相關概念遺傳學遺傳算法數(shù)學9交叉一組染色體上對應基因段的交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對應基因段交換的概率（可能性大?。╅]區(qū)間[0,1]上的一個值，一般為0.65~0.9011變異染色體水平上基因變化編碼的某些元素被改變12變異概率染色體上基因變化的概率（可能性大?。╅_區(qū)間(0,1)內(nèi)的一個值,一般為0.001~0.0113進化、適者生存?zhèn)€體進行優(yōu)勝劣汰的進化，一代又一代地優(yōu)化目標函數(shù)取到最大值，最優(yōu)的可行解22函數(shù)極值的求解問題由《數(shù)學分析》可知，一個在閉區(qū)間[a,b]上連續(xù)的函數(shù)必存在最大最小值，而且最大最小值可以通過以下方式得到：求出y=f（x）這個函數(shù)在[a,b]上所有的導數(shù)為0的點、不可導點、區(qū)間的端點。計算所有以上點的函數(shù)值，進行比較，則最大的必定是最大值點、最小的必定是最小值點。對于導數(shù)為0的點，還可以通過二階導數(shù)來判斷是極小還是極大值。23求函數(shù)的極值很顯然：利用導數(shù)求函數(shù)的極值只能針對那些簡單的函數(shù)才可以那樣做，如果函數(shù)比較復雜，則無法利用求導數(shù)的方法求函數(shù)的極值。求導數(shù)可能比較困難；即使求出導數(shù)，求導數(shù)為0的點也相當?shù)睦щy。是否不需要利用函數(shù)的導數(shù)，也可以求函數(shù)的極值？？？關于不需要利用導數(shù)就可以直接求函數(shù)的極值的方法，現(xiàn)在有幾種比較好的算法，遺傳算法就是其中的一種，它不需要利用導數(shù)，只要有函數(shù)的表達式就可以求函數(shù)的極值。24我們得到的結論是：

生物一代比一代優(yōu)目的：模仿生物遺傳的方式設計一個求解函數(shù)極值的算法。例如：求y=x2的最小值任取一些值25-48-1012稱為第一代，其實就是自變量x的任意一些值。它們的函數(shù)值分別為4251664100144.25生物有染色體，根據(jù)染色體進行遺傳與變異，從而得到下一代。人為的構造這些染色體，用5位二進制表示，第一位表示正負號，0表示正、1表示負。

25-48-1012000100010110100010001101001100

遺傳（雜交）00001001101010001000110000111016-48-81626遺傳（雜交）000010011010100010001100001110變異得到第二代，產(chǎn)生變異的概率很小，一般變異的概率8%，即每一位的0或1都有8%的可能編碼1或者0第二代：00001001001010001000110000111014-48-816對應的函數(shù)值

116166464169第二代比第一代好27第二代：000010010010100010001100001110

遺傳（雜交）000000010110100010001101001100

變異第三代：00000001011010001010110100110005-410-1012就已經(jīng)得到了函數(shù)的最小值點x=0，結束。28以上就是遺傳算法求解最優(yōu)問題的簡單設計，是模仿生物的遺傳機制而設計的算法，是最基本形式的遺傳算法。遺傳算法的不同形式：（對基本遺傳做出一些改動）由于遺傳算法是模擬生物的遺傳與變異機制而設計的，而生物的遺傳與變異是通過染色體來進行，所以遺傳算法必須編碼，因此，不同的編碼機制就得到不同形式的遺傳算法，從而，不同的遺傳算法的第一個區(qū)別就是編碼不同。29第一：編碼不同得到的遺傳算法就不一樣。例如：上面這個例子是用5位編碼，其實，我們也可以采用6位編碼、也可以采用7位或100位編碼都可以。習題：采用6位編碼采用不同的編碼方法就得到不同的遺傳算法。問題：采用什么編碼好呢？這個問題到現(xiàn)在為止還沒有答案，很多對遺傳算法進行研究的人，就是對各種各樣的編碼方法進行研究，看哪種編碼更好。30遺傳算法是模擬生物的遺傳與變異機制而設計的，遺傳算法的兩個基本運算就是遺傳雜交、變異。因此不同的選擇遺傳雜交方式與不同的變異方式就得到不同的遺傳算法。第二：不同的雜交方法得到不同的遺傳算法。例如：上面例子是每個個體都參與雜交。其實，我們知道自然界中的法則是優(yōu)勝劣汰。并不是每個個體都能找到伴侶。只有那些好的，才能找到伴侶，同樣的，這里也可以這樣做。先看哪些個體是好的，哪些個體是差的，讓好的個體多雜交，把那些差的直接淘汰。

哪些個體是好的，哪些個體是差的，怎么區(qū)分呢？31

求函數(shù)的最小值？25-48-1012000100010110100010001101001100函數(shù)值分別為4251664100144因為是要求函數(shù)的最小值，所以顯然函數(shù)值越小越好，函數(shù)值越大越不好。所以最好的點是2，最差的點是12，因此，可以直接淘汰12，而讓2這個點多雜交一次，因此雜交這一步可以這樣做：

25-48-10200010001011010001000110100001032上面只是給出了遺傳算法的一種基本的形式，而不同的編碼方法與不同的雜交策略可以變形出各種各樣的遺傳算法。同樣，還有不同的變異方式也得到不同的算法。33在進行遺傳算法操作時：上面第一種方法是兩兩交叉遺傳，而第二種做法是先淘汰最差，用一個最好的去代替最差，再進行交叉遺傳，也可以刪除兩個最差，用兩個好一點的取代。

25-48-1012000100010110100010001101001100淘汰一個最差的

25-48-102000100010110100010001101000010淘汰兩個最差的

25-482200010001011010001000000100001034到底淘汰幾個最差的？？？又用哪些好的取代差的，這些是可以有不同的數(shù)目的，這些數(shù)就叫控制參數(shù)。選擇不同的控制參數(shù)（控制策略），算法就不一樣。例如不刪除最差，每個都一樣的交叉遺傳，與刪除最差，用好的代替差的，算法不一樣。還有一個控制參數(shù)就是在進行變異操作時，選多少個進行變異，有選8%的個體進行變異，也有選5%的個數(shù)進行變異。這個百分數(shù)通常稱為變異率。35可以把遺傳算法的基本形式描述為：Begin生成初始種群，選擇適當?shù)木幋a方式；通過計算群體中各個體的適應度對群體進行評價；While未達到要求的目標dobegina.選擇繁殖下一代群體的各個體

b.執(zhí)行雜交操作

c.執(zhí)行變異操作

d.對群體進行評價

endend36例1.設f(x)=-x2+2x+0.5，求max

f(x),x[-1,2]。遺傳算法的實際應用我們將通過這個簡單的求最值問題來詳細給出遺傳算法的整個過程。（1）編碼和產(chǎn)生初始群體首先需要確定編碼的策略，也就是說如何把[-1,2]

區(qū)間內(nèi)的數(shù)用計算機語言表示出來。編碼就是從表現(xiàn)型到基因型的映射，編碼時要注意以下三個原則：完備性：問題空間中所有點（潛在解）都能成為GA編碼空間中的點（染色體位串）的表現(xiàn)型；健全性：GA編碼空間中的染色體位串必須對應問題空間中的某一潛在解；非冗余性：染色體和潛在解必須一一對應．37編碼我們采用二進制形式來解決編碼問題，即將某個變量值代表的個體表示為一個{0,1}二進制串。串的長度取決于求解的精度，例如假設求解精度為保留六位小數(shù)，由于區(qū)間[-1,2]的長度為3，則必須將該區(qū)間分為3106

等分。因為221<3106<222，所以編碼所用的二進制串至少需要22位。二進制串（b21b20b19…b1b0）與[a,b]

內(nèi)實數(shù)的一一映射：二進制串十進制數(shù)[a,b]

內(nèi)實數(shù)b21b20b19…b1b038編碼轉(zhuǎn)化到[-1,2]

內(nèi)的實數(shù)為：例.二進制串a(chǎn)=<1000101110110101000111>

其對應的十進制數(shù)為：39產(chǎn)生初始群體隨機的產(chǎn)生一個初始群體。pop1={<1101011101001100011110>，%a1<1000011001010001000010>，%a2<0001100111010110000000>，%a3<0110101001101110010101>}%a4這里假設初始群體的個體數(shù)為4。轉(zhuǎn)化成[-1,2]

之間的十進制數(shù)即為：下面就需要解決每個染色體個體的適應值pop1={

1.523032,0.574022,-0.697235,0.247238}40適應函數(shù)（2）定義適應函數(shù)和適應值由于目標函數(shù)f(x)

在[-1,2]

內(nèi)的值有正有負，所以必須通過建立適應函數(shù)與目標函數(shù)的映射關系，保證映射后的適應值非負，而且目標函數(shù)的優(yōu)化方向應對應于適應值增大的方向，目的：為以后計算各個體的入選概率打下基礎。定義適應函數(shù)：為了便于計算，這里的Fmin

采用了一個特定的輸入值例：如果取Fmin=-1，則f(x)=1對應的適應值為g(x)=241適應函數(shù)和適應值上述隨機產(chǎn)生的初始群體，取Fmin=-1，則它們的目標函數(shù)值和適應值分別為：f(pop1)={

1.226437,1.318543,-1.380607,0.933350}g(pop1)={

2.226437,2.318543,0,1.933350}42選擇標準（3）確定選擇標準用適應值比例來作為入選概率。設給定的規(guī)模為n

的群體pop={a1,a2,...,an

}，個體ai

的適應值為g(ai)，則其入選概率為上述隨機產(chǎn)生的初始群體，它們的入選概率分別為：p(pop1)=g(pop1)/sum(g(pop1))={0.343675,0.357892,0,0.298433}43產(chǎn)生種群（4）產(chǎn)生種群將入選概率大的個體選入種群，淘汰概率小的個體，并用概率最大的個體補入種群，得到與原群體大小同樣的種群。newpop1={<1101011101001100011110>，%a1<1000011001010001000010>，%a2<1000011001010001000010>，%a2<0110101001101110010101>}%a4在上述隨機產(chǎn)生的初始群體中，淘汰掉a3，再加入a2，得到新的種群：44交叉（5）交叉

交叉也就是將一組染色體上對應的基因段交換得到新的染色體，然后得到新的染色體組，組成新的群體。將前面得到的newpop1

的四個個體兩兩配對，重復的不配對，進行交叉（可以在任一位進行交叉）：<1101011101001100011110>

<1101011101010001000010>

<1000011001010001000010>

<1000011001001100011110><1000011001010001000010>

<1000011001010010010101><0110101001101110010101>

<0110101001101101000010>新的群體jchpop145變異（6）變異

變異就是通過一個小概率改變?nèi)旧w位串上的某個基因。現(xiàn)把jchpop1

中第3個個體中的第9位改變，就產(chǎn)生了變異，得到了新的群體pop2

：pop2={

<110101