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

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

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

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

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

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

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

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

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

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

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

6.2基本遺傳算法6.2.2編碼編碼方式二進(jìn)制編碼：

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

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

f’=α

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

cmult

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

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

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

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

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

模式理論模式定理（復(fù)制對(duì)模式的影響）在給定時(shí)間步t,一個(gè)特定模式H有

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

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

模式理論模式定理（復(fù)制對(duì)模式的影響）當(dāng)采用非重疊的n

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

表示模式H

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

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

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

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