智能控制基礎(chǔ)：6遺傳算法

遺傳算法第四章遺傳算法 遺傳算法簡介4.14.10 基本遺傳算法4.2 遺傳算法的數(shù)學理論基礎(chǔ)4.3 遺傳算法的應用4.46.1遺傳算法簡介6.1.1遺傳算法的產(chǎn)生與發(fā)展產(chǎn)生1967年，Holland的學生J.D.Bagley在博士論文中首次提出“遺傳算法(Genetic

Algorithms)”一詞；1968年，Holland提出了“模式定理（SchemaTheorem）”，一般認為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，標志遺傳算法的誕生；6.1遺傳算法簡介6.1.1遺傳算法的產(chǎn)生與發(fā)展發(fā)展1985年，在美國召開了第一屆遺傳算法國際會議，并且成立了國際遺傳算法學會(ISGA，InternationalSocietyofGeneticAlgorithms)；1989年，Holland的學生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，對遺傳算法及其應用作了全面而系統(tǒng)的論述；1992年，Michalewicz出版了很有影響力的著作《Geneticalgorithms+DataStructures=EvolutionPrograms》；1997年，《IEEETransactionsonEvolutionaryComputation》創(chuàng)刊，做為具有系統(tǒng)優(yōu)化、適應和學習的高性能計算和建模方法，遺傳算法研究逐漸成熟。6.1遺傳算法簡介6.1.2

生物遺傳學的基本知識遺傳（heredity）：親體系把生物信息交給子代，子代按照所得信息而發(fā)育、分化，因而子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異（variation）：子代與父代，子代不同個體之間總有差異，是生命多樣性的根源；選擇是指具有精選的能力，它決定生物進化的方向。遺傳因子（gene）：DNA或RNA長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱為基因；種瓜得瓜，種豆得豆適者生存，優(yōu)勝劣汰6.1遺傳算法簡介6.1.3遺傳算法的思路與特點遺傳算法的思路6.1遺傳算法簡介6.1.3遺傳算法的思路與特點遺傳算法的特點是對參數(shù)的編碼進行操作，而非對參數(shù)本身。特別是對一些無數(shù)值概念或者很難有數(shù)值概念而只有代碼概念的優(yōu)化問題，編碼處理方式更顯示出獨特的優(yōu)越性；是從許多點開始并行操作，而非局限于一點；通過目標函數(shù)來計算適應度，從而對問題依賴小；尋優(yōu)規(guī)則是由概率決定的，而非確定性的；6.1遺傳算法簡介6.1.3遺傳算法的思路與特點遺傳算法的特點是在解空間進行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機搜索；對尋優(yōu)的函數(shù)基本無限制；具有并行計算的特點，因而可通過大規(guī)模并行計算來提高計算速度；更適合大規(guī)模復雜問題的優(yōu)化；計算簡單，功能強。6.1遺傳算法簡介6.1.4遺傳算法的基本操作選擇交叉或基因重組變異選擇是用來確定重組或交叉?zhèn)€體，以及被選個體將產(chǎn)生多少個子代個體。基因重組是結(jié)合來自父代交配種群中的信息產(chǎn)生新的個體。交叉之后子代經(jīng)歷的變異，實際上是子代基因按小概率擾動產(chǎn)生的變化6.1遺傳算法簡介6.1.4遺傳算法的基本操作簡單實例產(chǎn)生初始種群計算適應度0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）6.1遺傳算法簡介6.1.4遺傳算法的基本操作簡單實例選擇個體染色體適應度選擇概率累積概率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.1521746.1遺傳算法簡介6.1.4遺傳算法的基本操作簡單實例選擇個體染色體適應度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000006.1遺傳算法簡介6.1.4遺傳算法的基本操作簡單實例選擇個體染色體適應度選擇概率累積概率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淘汰！淘汰！選擇在0～1之間產(chǎn)生一個隨機數(shù)：6.1遺傳算法簡介6.1.4遺傳算法的基本操作簡單實例交叉0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000110000011100101101100000001100111010010101010101110010110100101101110011101001100000001000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100116.1遺傳算法簡介6.1.4遺傳算法的基本操作簡單實例變異00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001010010011000110000011100101101100000001100111010010101010101110010110100101101111000000011001110100000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100116.1.4遺傳算法的基本操作簡單實例至下一代，適應度計算→選擇→交叉→變異，直至滿足終止條件6.1遺傳算法簡介6.2基本遺傳算法6.2.1簡單函數(shù)優(yōu)化實例問題的提出一元函數(shù)求最大值：6.2基本遺傳算法6.2.1簡單函數(shù)優(yōu)化實例問題的提出用微分法求取f(x)的最大值：解有無窮多個：6.2基本遺傳算法6.2.1簡單函數(shù)優(yōu)化實例問題的提出當i為奇數(shù)時xi對應局部極大值點，i為偶數(shù)時xi對應局部極小值。x19即為區(qū)間[-1,2]內(nèi)的最大值點：函數(shù)最大值f(x19)比f(1.85)=3.85稍大6.2基本遺傳算法6.2.1簡單函數(shù)優(yōu)化實例編碼表現(xiàn)型：x

作為實數(shù)，可以視為遺傳算法的表現(xiàn)型形式基因型：二進制編碼（串長取決于求解精度）串長與精度之間的關(guān)系：若要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。所以編碼的二進制串長應為22位。6.2基本遺傳算法6.2.1簡單函數(shù)優(yōu)化實例產(chǎn)生隨機種群產(chǎn)生的方式：隨機產(chǎn)生的結(jié)果：長度為22的二進制串產(chǎn)生的數(shù)量：種群的大小（規(guī)模）指種群中個體數(shù)目，如30，50…11110100111000010110001100110011101010101110……6.2.1簡單函數(shù)優(yōu)化實例計算適應度6.2基本遺傳算法不同的問題有不同的適應度計算方法本例：直接用目標函數(shù)作為適應度函數(shù)①將某個體轉(zhuǎn)化為[-1,2]區(qū)間的實數(shù)：

s=<1000101110110101000111>→x=0.637197②計算x的函數(shù)值（適應度）：

f(x)=xsin(10πx)+2.0=2.5863456.2.1簡單函數(shù)優(yōu)化實例計算適應度第一步，將一個二進制串（b21b20…b0）轉(zhuǎn)化為10進制數(shù)：

第二步，x’對應的區(qū)間[-1,2]內(nèi)的實數(shù)：6.2基本遺傳算法二進制與十進制之間的轉(zhuǎn)換：(0000000000000000000000)→-1(1111111111111111111111)→26.2基本遺傳算法6.2.1簡單函數(shù)優(yōu)化實例遺傳操作選擇：輪盤賭選擇法；交叉：單點交叉；變異：小概率變異模擬結(jié)果

設(shè)置的參數(shù)：種群大小50；交叉概率0.75；變異概率0.05；最大迭代數(shù)200。得到的最佳個體：

smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;6.2基本遺傳算法6.2.1簡單函數(shù)優(yōu)化實例模擬結(jié)果進化的過程世代數(shù)自變量適應度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.85036.2基本遺傳算法6.2.2編碼編碼方式二進制編碼：

優(yōu)點在于編碼、解碼操作簡單，交叉、變異等遺傳操作便于實現(xiàn)，而且便于利用模式定理進行理論分析等。

6.2基本遺傳算法6.2.2編碼編碼方式二進制編碼：

缺點在于不便于反映所求問題的特定知識，對于一些連續(xù)函數(shù)的優(yōu)化問題等由于遺傳算法的隨機特性而使其局部搜索能力較差，對于一些高維、高精度的連續(xù)函數(shù)優(yōu)化問題，二進制編碼存在著連續(xù)函數(shù)離散化的映射誤差，個體編碼串較短時，可能達不到精度要求，而個體編碼串的長度較長時，雖然能提高精度，但會使算法的搜索空間急劇擴大，會造成遺傳算法的性能降低。6.2基本遺傳算法6.2.2編碼編碼方式浮點數(shù)編碼：指個體的每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示，個體的編碼長度等于決策變量的個數(shù)。優(yōu)點：適合于在遺傳算法中表示范圍較大的數(shù)適合于精度要求較高的遺傳算法便于較大空間的遺傳搜索改善了遺傳算法的計算復雜性，提高了運算效率便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用便于設(shè)計針對問題的專門知識的知識型遺傳算子便于處理復雜的決策變量約束條件6.2基本遺傳算法6.2.3種群設(shè)定種群規(guī)模種群規(guī)模的確定受遺傳操作中選擇操作的影響很大，種群規(guī)模越大，種群中個體的多樣性越高，算法陷入局解的危險就越小。從種群多樣性出發(fā)，種群規(guī)模應比較大。種群規(guī)模太大會帶來若干弊?。?、從計算效率著眼，種群越大，其適應度評估次數(shù)增加，計算量也增加，從而影響算法效能；2、種群中個體生存下來的概率大多采用和適應度成比例的方法。種群中個體非常多時，少量適應度很高的個體會被選擇而生存下來，但大多數(shù)個體卻被淘汰，這會影響配對庫的形成，從而影響交叉操作。6.2基本遺傳算法6.2.3種群設(shè)定種群規(guī)模規(guī)模太小會使遺傳算法的搜索空間分布范圍有限，因而搜索有可能停止在未成熟階段，引起未成熟收斂現(xiàn)象。要避免未成熟收斂現(xiàn)象，必須保持種群的多樣性，即種群規(guī)模不能太小。6.2基本遺傳算法6.2.4適應度函數(shù)及其尺度變換適應度函數(shù)的重要性適應度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應度函數(shù)是由目標函數(shù)變換而成的，對目標函數(shù)值域的某種映射變換稱為適應度的尺度變換（fitnessscaling）。6.2基本遺傳算法6.2.4適應度函數(shù)及其尺度變換幾種常見的適應度函數(shù)直接轉(zhuǎn)換若目標函數(shù)為最大化問題：Fit(f(x))=f(x)

若目標函數(shù)為最小化問題：Fit(f(x))=-f(x)存在兩個問題：1、可能不滿足常用的輪盤賭選擇中概率非負的要求；2、某些待求解的函數(shù)在函數(shù)值分布上相差很大，由此得到的平均適應度可能不利于體現(xiàn)種群的平均性能，影響算法的性能。6.2基本遺傳算法6.2.3適應度函數(shù)及其尺度變換幾種常見的適應度函數(shù)界限構(gòu)造法若目標函數(shù)為最大化問題：若目標函數(shù)為最小化問題：6.2基本遺傳算法6.2.3適應度函數(shù)及其尺度變換適應度函數(shù)的作用適應度函數(shù)設(shè)計不當有可能出現(xiàn)欺騙問題：（1）進化初期，個別超常個體控制選擇過程，影響算法全局優(yōu)化特性；（2）進化末期，個體差異太小導致進化緩慢，可能獲得某個局部最優(yōu)解。6.2基本遺傳算法6.2.3適應度函數(shù)及其尺度變換適應度函數(shù)的線性變換法

f’=α

*f+β系數(shù)的確定滿足以下條件：①f’avg=favg②f’max=cmultf’avg

cmult

=1.0~2.06.2基本遺傳算法6.2.4遺傳操作——選擇個體選擇概率的常用分配方法按比例的適應度分配某個體i，其適應度為fi，則其被選取的概率Pi為：個體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.096.2基本遺傳算法6.2.4遺傳操作——選擇個體選擇概率的常用分配方法基于排序的適應度分配適應值僅僅取決于個體在種群中的序位，而不是實際的目標值。排序方法克服了比例適應度計算的尺度問題，當選擇壓力太小的情況下，以及選擇導致搜索帶迅速變窄而產(chǎn)生的過早收斂。6.2基本遺傳算法6.2.4遺傳操作——選擇常用選擇方法輪盤賭選擇法個體1234567891011適應度2.01.81.61.41.21.00.80.60.40.20.1選擇概率0.180.160.150.130.110.090.070.060.030.020.0累計概率0.180.340.490.620.730.820.890.950.981.001.000.810.320.966.2基本遺傳算法6.2.4遺傳操作——選擇常用選擇方法最佳個體保存法（elitistmodel）該方法的思想是把群體中適應度最高的個體不進行配對交叉而直接復制到下一代中。優(yōu)點：某進化過程中某一代的最優(yōu)解可不被交叉和變異操作所破壞缺點：局部最優(yōu)個體的遺傳基因會急速增加而使進化有可能限于局部解，也就是全局搜索能力差，更適合單峰性質(zhì)的搜索空間搜索，而不是多峰性質(zhì)的空間搜索，一般與其他選擇方法配合使用6.2.4遺傳操作——選擇常用選擇方法截斷選擇法錦標賽選擇法6.2基本遺傳算法個體按適應度排列，只有優(yōu)秀個體能夠成為父個體，參數(shù)為截斷閥值（被選作父個體的百分比）。隨機從種群中挑選一定數(shù)目個體，其中最好的個體作為父個體，此過程重復進行完成個體的選擇。6.2基本遺傳算法6.2.4遺傳操作——交叉/基因重組單點交叉多點交叉偶數(shù)點交叉6.2基本遺傳算法6.2.4遺傳操作——交叉/基因重組二進制交叉均勻交叉6.2基本遺傳算法6.2.4遺傳操作——變異二進制變異對種群中基因鏈碼隨機挑選c個基因位置并對其對應的基因值以變異概率取反。6.3遺傳算法的理論基礎(chǔ)6.3.1

模式理論模式在二進制編碼的串中，模式是基于三個字符集（0，1，*）的字符串，符號*代表任意字符，即0或1。如模式*1*描述了一個四個元的子集{010，011，110，111}。將種群中的個體即基因串中的相似樣板稱為模式，模式表示基因串中某些特征位相同的結(jié)構(gòu)，因此模式可以解釋為相同的構(gòu)形6.3遺傳算法的理論基礎(chǔ)6.3.1

模式理論模式模式階模式H中確定性位置的個數(shù)稱為模式H的模式階，記作O(H)，如O(011*1*)=4。

模式階用來反映不同模式間確定性的差異，模式階越高，模式的確定性就越高，所匹配的樣本個數(shù)就越少。6.3遺傳算法的理論基礎(chǔ)6.3.1

模式理論定義距模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式的定義距，記作δ(H)，如δ(011*1**)=4。階數(shù)相同的模式會有不同的性質(zhì)，定義距就反映了這種性質(zhì)的差異。6.3遺傳算法的理論基礎(chǔ)6.3.1

模式理論模式定理（復制對模式的影響）在給定時間步t,一個特定模式H有

m個代表串包含在種群A(t)中，記為m=m(H,t)，每個串根據(jù)它的適應值進行選擇和復制，一個串Ai

選擇概率為6.3遺傳算法的理論基礎(chǔ)6.3.1

模式理論模式定理（復制對模式的影響）當采用非重疊的n

個串的種群替代種群A(t)，可以得到：其中f(H)是在時間t

表示模式H

的串的平均適應度。這表明，一個特定的模式按照其平均適應度值與種群的平均適應度值之間的比率生長。一個代表串被選擇復制的數(shù)量6.3遺傳算法的理論基礎(chǔ)6.3.1模式理論模式定理（復制對模式的影響）假設(shè)從t=0開始，某一特定模式適應度值保持在種群平均適應度以上一個cf（c為一常數(shù)），則模式的選擇生長方程為上式表明，在種群平均值以上(以下)的模式將按指數(shù)增長(衰減)的方式被復制。在一定程度上這種復制算子在種群中并行地采樣，許多不同的模式按照相同的規(guī)則增長或衰減。僅靠復制過程無助于檢測搜索空間中新的區(qū)域，因而需要采取交叉操作6.3遺傳算法的理論基礎(chǔ)6.3.1模式理論模式定理（交叉對模式的影響）考慮交叉操作，模式H

被破壞的概率為δ(H)/(l-1)，模式H

生存概率為1-δ(H)/(l-1)，若交叉操作發(fā)生的概率為pc，因此對于模式H

的生存概率計算為：同時考慮選擇、交叉操作對模式的影響，可得子代模式的估計：A=0111000H1=*1****0H2=***10**該式表明，模式增長或衰減依賴于兩個因素．一個因素是模式的適應值是在平均適應值之上還是在平均適應值之下，另一個因素是模式具有相對長還是相對短的定義距。那些既在種群平均適應度值之上同時又