遺傳算法綜述及簡單應(yīng)用實(shí)例的Matlab程序課件

遺傳算法綜述及簡單應(yīng)用實(shí)例及Matlab程序

1遺傳算法綜述及簡單應(yīng)用實(shí)例14.1遺傳算法簡介

4.1.1遺傳算法的產(chǎn)生與發(fā)展

4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

4.1.3遺傳算法的思路與特點(diǎn)

4.1.4遺傳算法的基本操作

4.1.5遺傳算法的應(yīng)用4.2基本遺傳算法

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

4.2.2遺傳基因型

4.2.3適應(yīng)度函數(shù)及其尺度變換

4.2.4遺傳操作——選擇

4.2.5遺傳操作——交叉/基因重組

4.2.6遺傳操作——變異

4.2.7算法的設(shè)計與實(shí)現(xiàn)

4.2.8模式定理?24.1遺傳算法簡介?24.1遺傳算法簡介

產(chǎn)生早在50年代，一些生物學(xué)家開始研究運(yùn)用數(shù)字計算機(jī)模擬生物的自然遺傳與自然進(jìn)化過程；1963年，德國柏林技術(shù)大學(xué)的I.Rechenberg和H.P.Schwefel，做風(fēng)洞實(shí)驗(yàn)時，產(chǎn)生了進(jìn)化策略的初步思想；60年代，L.J.Fogel在設(shè)計有限態(tài)自動機(jī)時提出進(jìn)化規(guī)劃的思想。1966年Fogel等出版了《基于模擬進(jìn)化的人工智能》，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想。4.1.1遺傳算法的產(chǎn)生與發(fā)展

34.1遺傳算法簡介產(chǎn)生4.1.1遺傳算法4.1遺傳算法簡介

產(chǎn)生60年代中期，美國Michigan大學(xué)的J.H.Holland教授提出借鑒生物自然遺傳的基本原理用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；1967年，他的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法(GeneticAlgorithms)”一詞；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，標(biāo)志遺傳算法的誕生。4.1.1遺傳算法的產(chǎn)生與發(fā)展

44.1遺傳算法簡介產(chǎn)生4.1.1遺傳算法4.1遺傳算法簡介

發(fā)展70年代初，Holland提出了“模式定理”（SchemaTheorem），一般認(rèn)為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；1985年，在美國召開了第一屆遺傳算法國際會議，并且成立了國際遺傳算法學(xué)會(ISGA，InternationalSocietyofGeneticAlgorithms)；4.1.1遺傳算法的產(chǎn)生與發(fā)展

54.1遺傳算法簡介發(fā)展4.1.1遺傳算法4.1遺傳算法簡介

發(fā)展1988年，Holland的學(xué)生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述；1991年，L.Davis編輯出版了《Handbookofgeneticalgorithms》，其中包括了遺傳算法在工程技術(shù)和社會生活中大量的應(yīng)用實(shí)例。4.1.1遺傳算法的產(chǎn)生與發(fā)展

64.1遺傳算法簡介發(fā)展4.1.1遺傳算法4.1遺傳算法簡介

達(dá)爾文的自然選擇說遺傳（heredity）：子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異（variation）：子代與父代，子代不同個體之間總有差異，是生命多樣性的根源；生存斗爭和適者生存：具有適應(yīng)性變異的個體被保留，不具適應(yīng)性變異的個體被淘汰。

自然選擇過程是長期的、緩慢的、連續(xù)的過程。4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

74.1遺傳算法簡介達(dá)爾文的自然選擇說4.1.4.1遺傳算法簡介

遺傳學(xué)(Genetics)基本概念與術(shù)語染色體（chromosome）：遺傳物質(zhì)的載體；脫氧核糖核酸（DNA）：大分子有機(jī)聚合物，雙螺旋結(jié)構(gòu)；遺傳因子（gene）：DNA或RNA長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

84.1遺傳算法簡介遺傳學(xué)(Genetics)基本概念4.1遺傳算法簡介

遺傳學(xué)基本概念與術(shù)語基因型（genotype）：遺傳因子組合的模型；表現(xiàn)型（phenotype）：由染色體決定性狀的外部表現(xiàn)；4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

1111111

111011194.1遺傳算法簡介遺傳學(xué)基本概念與術(shù)語4.14.1遺傳算法簡介

遺傳學(xué)基本概念與術(shù)語基因座（locus）：遺傳基因在染色體中所占據(jù)的位置，同一基因座可能有的全部基因稱為等位基因（allele）；個體（individual）：指染色體帶有特征的實(shí)體；種群（population）：個體的集合，該集合內(nèi)個體數(shù)稱為種群的大??；4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

104.1遺傳算法簡介遺傳學(xué)基本概念與術(shù)語4.14.1遺傳算法簡介

遺傳學(xué)基本概念與術(shù)語進(jìn)化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化；適應(yīng)度（fitness）：度量某個物種對于生存環(huán)境的適應(yīng)程度。對生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會，而對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會就會相對較少，甚至逐漸滅絕;4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

114.1遺傳算法簡介遺傳學(xué)基本概念與術(shù)語4.14.1遺傳算法簡介

遺傳學(xué)基本概念與術(shù)語選擇（selection）：指決定以一定的概率從種群中選擇若干個體的操作；復(fù)制（reproduction）：細(xì)胞在分裂時，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因;交叉（crossover）：在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體。又稱基因重組，俗稱“雜交”;4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

124.1遺傳算法簡介遺傳學(xué)基本概念與術(shù)語4.14.1遺傳算法簡介

遺傳學(xué)基本概念與術(shù)語變異（mutation）：在細(xì)胞進(jìn)行復(fù)制時可能以很小的概率產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀;編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

134.1遺傳算法簡介遺傳學(xué)基本概念與術(shù)語4.14.1遺傳算法簡介

進(jìn)化論與遺傳學(xué)的融合1930～1947年，達(dá)爾文進(jìn)化論與遺傳學(xué)走向融合，Th.Dobzhansky1937年發(fā)表的《遺傳學(xué)與物種起源》是融合進(jìn)化論與遺傳學(xué)的代表作。生物進(jìn)化與智能學(xué)的關(guān)系生物物種作為復(fù)雜系統(tǒng)，具有奇妙的自適應(yīng)、自組織和自優(yōu)化能力，這是一種生物在進(jìn)化過程中體現(xiàn)的智能，也是人工系統(tǒng)夢寐以求的功能。4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

144.1遺傳算法簡介進(jìn)化論與遺傳學(xué)的融合4.14.1遺傳算法簡介

遺傳算法的基本思路4.1.3遺傳算法的思路與特點(diǎn)

154.1遺傳算法簡介遺傳算法的基本思路4.1.4.1遺傳算法簡介

自組織、自適應(yīng)和自學(xué)習(xí)性在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。本質(zhì)并行性內(nèi)在并行性與內(nèi)含并行性不需求導(dǎo)只需目標(biāo)函數(shù)和適應(yīng)度函數(shù)概率轉(zhuǎn)換規(guī)則強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則4.1.3遺傳算法的思路與特點(diǎn)

164.1遺傳算法簡介自組織、自適應(yīng)和自學(xué)習(xí)性44.1遺傳算法簡介

簡單實(shí)例產(chǎn)生初始種群計算適應(yīng)度4.1.4遺傳算法的基本操作

0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）174.1遺傳算法簡介簡單實(shí)例4.1.4遺傳4.1遺傳算法簡介

簡單實(shí)例選擇4.1.4遺傳算法的基本操作

個體染色體適應(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.152174184.1遺傳算法簡介簡單實(shí)例4.1.4遺傳4.1遺傳算法簡介

簡單實(shí)例選擇4.1.4遺傳算法的基本操作

個體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000194.1遺傳算法簡介簡單實(shí)例4.1.4遺傳4.1遺傳算法簡介

簡單實(shí)例選擇在0～1之間產(chǎn)生一個隨機(jī)數(shù)：4.1.4遺傳算法的基本操作

個體染色體適應(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淘汰！淘汰！204.1遺傳算法簡介簡單實(shí)例4.1.4遺傳00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100114.1遺傳算法簡介

簡單實(shí)例交叉4.1.4遺傳算法的基本操作

000110000011100101101100000001100111010010101010101110010110100101101110011101001100000001000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100112100011000001110010110114.1遺傳算法簡介

簡單實(shí)例變異4.1.4遺傳算法的基本操作

0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010010101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011224.1遺傳算法簡介簡單實(shí)例4.1.4遺傳4.1遺傳算法簡介

簡單實(shí)例至下一代，適應(yīng)度計算→選擇→交叉→變異，直至滿足終止條件。4.1.4遺傳算法的基本操作

234.1遺傳算法簡介簡單實(shí)例4.1.4遺傳4.1遺傳算法簡介

選擇1.適應(yīng)度計算：按比例的適應(yīng)度函數(shù)（proportionalfitnessassignment）基于排序的適應(yīng)度計算（Rank-basedfitnessassignment）

4.1.4遺傳算法的基本操作

244.1遺傳算法簡介選擇4.1.4遺傳算法4.1遺傳算法簡介

選擇2.選擇算法：輪盤賭選擇（roulettewheelselection）隨機(jī)遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截斷選擇（truncationselection）錦標(biāo)賽選擇（tournamentselection）4.1.4遺傳算法的基本操作

254.1遺傳算法簡介選擇4.1.4遺傳算法4.1遺傳算法簡介

交叉或基因重組

實(shí)值重組（realvaluedrecombination）：離散重組（discreterecombination）中間重組（intermediaterecombination）線性重組（linearrecombination）擴(kuò)展線性重組（extendedlinearrecombination）4.1.4遺傳算法的基本操作

264.1遺傳算法簡介交叉或基因重組4.1.44.1遺傳算法簡介

交叉或基因重組

二進(jìn)制交叉（binaryvaluedcrossover）：單點(diǎn)交叉（single-pointcrossover）多點(diǎn)交叉（multiple-pointcrossover）均勻交叉（uniformcrossover）洗牌交叉（shufflecrossover）縮小代理交叉（crossoverwithreducedsurrogate）4.1.4遺傳算法的基本操作

274.1遺傳算法簡介交叉或基因重組4.1.44.1遺傳算法簡介

變異

實(shí)值變異

二進(jìn)制變異4.1.4遺傳算法的基本操作

284.1遺傳算法簡介變異4.1.4遺傳算法4.1遺傳算法簡介

函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域;組合優(yōu)化實(shí)踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效;自動控制如基于遺傳算法的模糊控制器優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)等;4.1.5遺傳算法的應(yīng)用

294.1遺傳算法簡介函數(shù)優(yōu)化4.1.5遺傳4.1遺傳算法簡介

機(jī)器人智能控制遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動軌跡規(guī)劃、機(jī)器人逆運(yùn)動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動協(xié)調(diào)等;組合圖像處理和模式識別目前已在圖像恢復(fù)、圖像邊緣持征提取、幾何形狀識別等方面得到了應(yīng)用;4.1.5遺傳算法的應(yīng)用

304.1遺傳算法簡介機(jī)器人智能控制4.1.54.1遺傳算法簡介

人工生命基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力；遺傳程序設(shè)計Koza發(fā)展了遺傳程序設(shè)計的慨念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作自動生成計算機(jī)程序。4.1.5遺傳算法的應(yīng)用

314.1遺傳算法簡介人工生命4.1.5遺傳4.1遺傳算法簡介

4.1.1遺傳算法的產(chǎn)生與發(fā)展

4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識

4.1.3遺傳算法的思路與特點(diǎn)

4.1.4遺傳算法的基本操作

4.1.5遺傳算法的應(yīng)用4.2基本遺傳算法

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

4.2.2遺傳基因型

4.2.3適應(yīng)度函數(shù)及其尺度變換

4.2.4遺傳操作——選擇

4.2.5遺傳操作——交叉/基因重組

4.2.6遺傳操作——變異

4.2.7算法的設(shè)計與實(shí)現(xiàn)

4.2.8模式定理?324.1遺傳算法簡介?324.2基本遺傳算法

問題的提出一元函數(shù)求最大值：4.2.1簡單函數(shù)優(yōu)化的實(shí)例

334.2基本遺傳算法問題的提出4.2.1簡4.2基本遺傳算法

問題的提出用微分法求取f(x)的最大值：解有無窮多個：4.2.1簡單函數(shù)優(yōu)化的實(shí)例

344.2基本遺傳算法問題的提出4.2.1簡4.2基本遺傳算法

問題的提出當(dāng)i為奇數(shù)時xi對應(yīng)局部極大值點(diǎn)，i為偶數(shù)時xi對應(yīng)局部極小值。x19即為區(qū)間[-1,2]內(nèi)的最大值點(diǎn)：此時，函數(shù)最大值f(x19)比f(1.85)=3.85稍大。4.2.1簡單函數(shù)優(yōu)化的實(shí)例

354.2基本遺傳算法問題的提出4.2.1簡4.2基本遺傳算法

編碼表現(xiàn)型：x基因型：二進(jìn)制編碼（串長取決于求解精度）

串長與精度之間的關(guān)系：若要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)＝3，即需將區(qū)間分為3/0.000001=3×106等份。所以編碼的二進(jìn)制串長應(yīng)為22位。4.2.1簡單函數(shù)優(yōu)化的實(shí)例

364.2基本遺傳算法編碼4.2.1簡單函數(shù)4.2基本遺傳算法

產(chǎn)生初始種群產(chǎn)生的方式：隨機(jī)產(chǎn)生的結(jié)果：長度為22的二進(jìn)制串產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……4.2.1簡單函數(shù)優(yōu)化的實(shí)例

374.2基本遺傳算法產(chǎn)生初始種群4.2.14.2基本遺傳算法

計算適應(yīng)度不同的問題有不同的適應(yīng)度計算方法本例：直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù)①將某個體轉(zhuǎn)化為[-1,2]區(qū)間的實(shí)數(shù)：

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

f(x)=xsin(10πx)+2.0=2.5863454.2.1簡單函數(shù)優(yōu)化的實(shí)例

384.2基本遺傳算法計算適應(yīng)度4.2.1簡4.2基本遺傳算法

計算適應(yīng)度

二進(jìn)制與十進(jìn)制之間的轉(zhuǎn)換：第一步，將一個二進(jìn)制串（b21b20…b0）轉(zhuǎn)化為10進(jìn)制數(shù)：第二步，x’對應(yīng)的區(qū)間[-1,2]內(nèi)的實(shí)數(shù)：4.2.1簡單函數(shù)優(yōu)化的實(shí)例

(0000000000000000000000)→-1(1111111111111111111111)→2394.2基本遺傳算法計算適應(yīng)度4.2.1簡4.2基本遺傳算法

遺傳操作選擇：輪盤賭選擇法；交叉：單點(diǎn)交叉；變異：小概率變異4.2.1簡單函數(shù)優(yōu)化的實(shí)例

404.2基本遺傳算法遺傳操作4.2.1簡單4.2基本遺傳算法

模擬結(jié)果

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

得到的最佳個體：smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;4.2.1簡單函數(shù)優(yōu)化的實(shí)例

414.2基本遺傳算法模擬結(jié)果4.2.1簡單4.2基本遺傳算法

模擬結(jié)果

進(jìn)化的過程：4.2.1簡單函數(shù)優(yōu)化的實(shí)例

世代數(shù)自變量適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503424.2基本遺傳算法模擬結(jié)果4.2.1簡單4.2基本遺傳算法

編碼原則完備性（completeness）：問題空間的所有解都能表示為所設(shè)計的基因型；健全性（soundness）：任何一個基因型都對應(yīng)于一個可能解；非冗余性（non-redundancy）：問題空間和表達(dá)空間一一對應(yīng)。4.2.2遺傳基因型

434.2基本遺傳算法編碼原則4.2.2遺傳4.2基本遺傳算法

多種編碼方式二進(jìn)制編碼；浮點(diǎn)數(shù)編碼；格雷碼編碼；符號編碼；復(fù)數(shù)編碼；DNA編碼等。4.2.2遺傳基因型

444.2基本遺傳算法多種編碼方式4.2.24.2基本遺傳算法

二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較在交叉操作時，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼產(chǎn)生新個體的可能性多，而且產(chǎn)生的新個體不受父個體所構(gòu)成的超體的限制；在變異操作時，二進(jìn)制編碼的種群穩(wěn)定性比浮點(diǎn)數(shù)編碼差。4.2.2遺傳基因型

454.2基本遺傳算法二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較4.2基本遺傳算法

適應(yīng)度函數(shù)的重要性適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，對目標(biāo)函數(shù)值域的某種映射變換稱為適應(yīng)度的尺度變換（fitnessscaling）。4.2.3適應(yīng)度函數(shù)及其尺度變換

464.2基本遺傳算法適應(yīng)度函數(shù)的重要性4.2.4.2基本遺傳算法

適應(yīng)度函數(shù)的設(shè)計單值、連續(xù)、非負(fù)、最大化合理、一致性（能夠反映解的優(yōu)劣）計算量小通用性強(qiáng)4.2.3適應(yīng)度函數(shù)及其尺度變換

474.2基本遺傳算法適應(yīng)度函數(shù)的設(shè)計4.2.34.2基本遺傳算法

幾種常見的適應(yīng)度函數(shù)直接轉(zhuǎn)換若目標(biāo)函數(shù)為最大化問題：Fit(f(x))=f(x)若目標(biāo)函數(shù)為最小化問題：Fit(f(x))=-f(x)4.2.3適應(yīng)度函數(shù)及其尺度變換

484.2基本遺傳算法幾種常見的適應(yīng)度函數(shù)4.24.2基本遺傳算法

幾種常見的適應(yīng)度函數(shù)界限構(gòu)造法1若目標(biāo)函數(shù)為最大化問題：若目標(biāo)函數(shù)為最小化問題：4.2.3適應(yīng)度函數(shù)及其尺度變換

494.2基本遺傳算法幾種常見的適應(yīng)度函數(shù)4.24.2基本遺傳算法

幾種常見的適應(yīng)度函數(shù)界限構(gòu)造法2若目標(biāo)函數(shù)為最大化問題：若目標(biāo)函數(shù)為最小化問題：

c為目標(biāo)函數(shù)的保守估計值。4.2.3適應(yīng)度函數(shù)及其尺度變換

504.2基本遺傳算法幾種常見的適應(yīng)度函數(shù)4.24.2基本遺傳算法

適應(yīng)度函數(shù)的作用適應(yīng)度函數(shù)設(shè)計不當(dāng)有可能出現(xiàn)欺騙問題：（1）進(jìn)化初期，個別超常個體控制選擇過程；（2）進(jìn)化末期，個體差異太小導(dǎo)致陷入局部極值。4.2.3適應(yīng)度函數(shù)及其尺度變換

514.2基本遺傳算法適應(yīng)度函數(shù)的作用4.2.34.2基本遺傳算法

適應(yīng)度函數(shù)的線性變換法

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

cmult=1.0~2.0，α和β取適當(dāng)值，以保證適應(yīng)度值非負(fù)。4.2.3適應(yīng)度函數(shù)及其尺度變換

524.2基本遺傳算法適應(yīng)度函數(shù)的線性變換法4.4.2基本遺傳算法

適應(yīng)度函數(shù)的冪函數(shù)變換法

f’=fk

k與所求優(yōu)化問題相關(guān)4.2.3適應(yīng)度函數(shù)及其尺度變換

k534.2基本遺傳算法適應(yīng)度函數(shù)的冪函數(shù)變換法44.2基本遺傳算法

適應(yīng)度函數(shù)的指數(shù)變換法

f’=e-af

a決定了復(fù)制的強(qiáng)制性。a越大，大適應(yīng)度的個體被復(fù)制的強(qiáng)制性就越弱。4.2.3適應(yīng)度函數(shù)及其尺度變換

α544.2基本遺傳算法適應(yīng)度函數(shù)的指數(shù)變換法4.4.2基本遺傳算法

幾個概念選擇壓力（selectionpressure）:最佳個體選中的概率與平均個體選中概率的比值；偏差（bias）：個體正規(guī)化適應(yīng)度與其期望再生概率的絕對差值；個體擴(kuò)展（spread）：單個個體子代個數(shù)的范圍；多樣化損失（lossofdiversity）：在選擇階段未選中個體數(shù)目占種群的比例；4.2.4遺傳操作——選擇

554.2基本遺傳算法幾個概念4.2.4遺傳4.2基本遺傳算法

幾個概念選擇強(qiáng)度（selectionintensity）:將正規(guī)高斯分布應(yīng)用于選擇方法，期望平均適應(yīng)度；選擇方差（selectionvariance）：將正規(guī)高斯分布應(yīng)用于選擇方法，期望種群適應(yīng)度的方差。4.2.4遺傳操作——選擇

564.2基本遺傳算法幾個概念4.2.4遺傳4.2基本遺傳算法

個體選擇概率的常用分配方法按比例的適應(yīng)度分配（proportionalfitnessassignment）某個體i，其適應(yīng)度為fi，則其被選取的概率Pi為：如果尺度變換不合適，可能造成早熟。4.2.4遺傳操作——選擇

個體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.09574.2基本遺傳算法個體選擇概率的常用分配方法4.2基本遺傳算法

個體選擇概率的常用分配方法基于排序的適應(yīng)度分配（rank-basedfitnessassignment）線性排序（byBaker）

μ為種群大小，i為個體序號，ηmax代表選擇壓力。4.2.4遺傳操作——選擇

584.2基本遺傳算法個體選擇概率的常用分配方法4.2基本遺傳算法

個體選擇概率的常用分配方法基于排序的適應(yīng)度分配（rank-basedfitnessassignment）非線性排序（byMichalewicz）i為個體序號，c為排序第一的個體的選擇概率。4.2.4遺傳操作——選擇

594.2基本遺傳算法個體選擇概率的常用分配方法4.2基本遺傳算法

常用選擇方法輪盤賭選擇法（roulettewheelselection）

4.2.4遺傳操作——選擇

個體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累計概率0.180.340.490.620.730.820.890.950.981.001.00604.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

常用選擇方法隨機(jī)遍歷抽樣法（stochasticuniversalsampling）

4.2.4遺傳操作——選擇

個體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累計概率0.180.340.490.620.730.820.890.950.981.001.00614.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

常用選擇方法局部選擇法（localselection）(1)線形鄰集4.2.4遺傳操作——選擇

624.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

常用選擇方法局部選擇法（localselection）(2)兩對角鄰集4.2.4遺傳操作——選擇

634.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

常用選擇方法局部選擇法（localselection）(2)兩對角鄰集4.2.4遺傳操作——選擇

644.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

常用選擇方法截斷選擇法（truncationselection）個體按適應(yīng)度排列，只有優(yōu)秀個體能夠成為父個體，參數(shù)為截斷閾值（被選作父個體的百分比）。4.2.4遺傳操作——選擇

截斷閾值1％10％20％40％50％80％選擇強(qiáng)度2.661.761.20.970.80.34654.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

常用選擇方法錦標(biāo)賽選擇法（tournamentselection）隨機(jī)從種群中挑選一定數(shù)目個體（競賽規(guī)模），其中最好的個體作為父個體，此過程重復(fù)進(jìn)行完成個體的選擇。4.2.4遺傳操作——選擇

競賽規(guī)模12351030選擇強(qiáng)度00.560.851.151.532.04664.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

常用選擇方法早熟現(xiàn)象——適應(yīng)度高的個體迅速繁殖，使搜索過程過早結(jié)束；種群中個體的適應(yīng)度接近，導(dǎo)致進(jìn)化過程陷入局部最優(yōu)點(diǎn)；基本遺傳算法達(dá)到收斂的代數(shù)與選擇強(qiáng)度成反比，較高的選擇強(qiáng)度是很好的選擇方法，但太高會導(dǎo)致收斂過快。4.2.4遺傳操作——選擇

674.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

實(shí)值重組離散重組子個體的每個變量可以按等概率隨機(jī)地挑選父個體。4.2.5遺傳操作——交叉/基因重組

父個體112

25

5父個體2123

4

34子個體1123

4

5子個體212

4

34684.2基本遺傳算法實(shí)值重組4.2.5遺傳4.2基本遺傳算法

實(shí)值重組中間重組子個體＝父個體1＋α×（父個體2－父個體1）

α是比例因子，由[-d,1+d]上均勻分布地隨機(jī)數(shù)產(chǎn)生。

d=0時為中間重組，一般取d=0.25。子代的每個變量均產(chǎn)生一個α。4.2.5遺傳操作——交叉/基因重組

694.2基本遺傳算法實(shí)值重組4.2.5遺傳4.2基本遺傳算法

實(shí)值重組中間重組

4.2.5遺傳操作——交叉/基因重組

父個體112255父個體2123434子個體1子個體2α值樣本10.51.1-0.1α值樣本20.10.80.512＋0.5×（123－12）=67.567.525＋1.1×（4－25）=1.91.92.112＋0.1×（123－12）=23.123.18.219.5704.2基本遺傳算法實(shí)值重組4.2.5遺傳4.2基本遺傳算法

實(shí)值重組中間重組

4.2.5遺傳操作——交叉/基因重組

714.2基本遺傳算法實(shí)值重組4.2.5遺傳4.2基本遺傳算法

實(shí)值重組線性重組

4.2.5遺傳操作——交叉/基因重組

父個體112255父個體2123434子個體1子個體2α值樣本10.5α值樣本20.112＋0.5×（123－12）=67.567.525＋0.5×（4－25）=14.514.519.512＋0.1×（123－12）=23.123.122.97.9724.2基本遺傳算法實(shí)值重組4.2.5遺傳4.2基本遺傳算法

實(shí)值重組線性重組

4.2.5遺傳操作——交叉/基因重組

734.2基本遺傳算法實(shí)值重組4.2.5遺傳4.2基本遺傳算法

二進(jìn)制交叉單點(diǎn)交叉

4.2.5遺傳操作——交叉/基因重組

744.2基本遺傳算法二進(jìn)制交叉4.2.5遺4.2基本遺傳算法

二進(jìn)制交叉多點(diǎn)交叉

4.2.5遺傳操作——交叉/基因重組

754.2基本遺傳算法二進(jìn)制交叉4.2.5遺4.2基本遺傳算法

二進(jìn)制交叉均勻交叉

4.2.5遺傳操作——交叉/基因重組

父個體101110011010

父個體210101100101子個體11

11

011

11

1

1

1子個體20

01

100

00

0

0

0

樣本101100011010樣本2100111001011表示由父個體1提供變量值；0表示由父個體2提供變量值。764.2基本遺傳算法二進(jìn)制交叉4.2.5遺4.2基本遺傳算法

實(shí)值變異一般采用：二進(jìn)制變異

4.2.6遺傳操作——變異

774.2基本遺傳算法實(shí)值變異4.2.6遺傳4.2基本遺傳算法

主程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%用遺傳算法進(jìn)行簡單函數(shù)的優(yōu)化clearbn=22;%個體串長度inn=50;%初始種群大小gnmax=200;%最大代數(shù)pc=0.75;%交叉概率pm=0.05;%變異概率Continue…784.2基本遺傳算法主程序4.2.7算法的4.2基本遺傳算法

主程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%產(chǎn)生初始種群s=round(rand(inn,bn));%計算適應(yīng)度,返回適應(yīng)度f和累積概率p[f,p]=objf(s);Continue…794.2基本遺傳算法主程序4.2.7算法的4.2基本遺傳算法

主程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

gn=1;whilegn<gnmax+1forj=1:2:inn%選擇操作seln=sel(s,p);%交叉操作scro=cro(s,seln,pc);scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);%變異操作smnew(j,:)=mut(scnew(j,:),pm);smnew(j+1,:)=mut(scnew(j+1,:),pm);endContinue…804.2基本遺傳算法主程序4.2.7算法的4.2基本遺傳算法

主程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

s=smnew;%產(chǎn)生了新的種群%計算新種群的適應(yīng)度[f,p]=objf(s);

%記錄當(dāng)前代最好和平均的適應(yīng)度[fmax,nmax]=max(f);fmean=mean(f);ymax(gn)=fmax;ymean(gn)=fmean;Continue…814.2基本遺傳算法主程序4.2.7算法的4.2基本遺傳算法

主程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%記錄當(dāng)前代的最佳個體x=n2to10(s(nmax,:));xx=-1.0+x*3/(power(2,bn)-1);xmax(gn)=xx;

gn=gn+1endgn=gn-1;Continue…824.2基本遺傳算法主程序4.2.7算法的4.2基本遺傳算法

主程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%繪制曲線subplot(2,1,1);plot(1:gn,[ymax;ymean]);title('歷代適應(yīng)度變化','fonts',10);legend('最大適應(yīng)度','平均適應(yīng)度');string1=['最終適應(yīng)度',num2str(ymax(gn))];gtext(string1);subplot(2,1,2);plot(1:gn,xmax,'r-');legend('自變量');string2=['最終自變量',num2str(xmax(gn))];gtext(string2);End834.2基本遺傳算法主程序4.2.7算法的4.2基本遺傳算法

計算適應(yīng)度和累計概率函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%計算適應(yīng)度函數(shù)function[f,p]=objf(s);[innbn]=size(s);%讀取種群大小,有inn個個體,個體長度為bnContinue…844.2基本遺傳算法計算適應(yīng)度和累計概率函數(shù)44.2基本遺傳算法

計算適應(yīng)度和累計概率函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

fori=1:innx=n2to10(s(i,:));%將二進(jìn)制轉(zhuǎn)換為十進(jìn)制xx=-1.0+x*3/(power(2,bn)-1);%轉(zhuǎn)化為[-1,2]區(qū)間的實(shí)數(shù)f(i)=ft(xx);%計算函數(shù)值，即適應(yīng)度endf=f';Continue…854.2基本遺傳算法計算適應(yīng)度和累計概率函數(shù)44.2基本遺傳算法

計算適應(yīng)度和累計概率函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%計算選擇概率fsum=0;fori=1:innfsum=fsum+f(i)*f(i);endfori=1:innps(i)=f(i)*f(i)/fsum;endContinue…864.2基本遺傳算法計算適應(yīng)度和累計概率函數(shù)44.2基本遺傳算法

計算適應(yīng)度和累計概率函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%計算累積概率p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p';Backtomain.m874.2基本遺傳算法計算適應(yīng)度和累計概率函數(shù)44.2基本遺傳算法

計算目標(biāo)函數(shù)值函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%目標(biāo)函數(shù)functiony=ft(x);y=x.*sin(10*pi*x)+2;Backtoobjf.m884.2基本遺傳算法計算目標(biāo)函數(shù)值函數(shù)4.2.4.2基本遺傳算法

選擇操作函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%“選擇”操作functionseln=sel(s,p);inn=size(p,1);%從種群中選擇兩個個體fori=1:2r=rand;%產(chǎn)生一個隨機(jī)數(shù)prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;%選中個體的序號endBacktomain.m894.2基本遺傳算法選擇操作函數(shù)4.2.74.2基本遺傳算法

交叉操作函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%“交叉”操作functionscro=cro(s,seln,pc);[innbn]=size(s);Continue…904.2基本遺傳算法交叉操作函數(shù)4.2.74.2基本遺傳算法

交叉操作函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

ifrand<pcchb=ceil(rand*(bn-1));%在[1,bn-1]范圍內(nèi)隨機(jī)產(chǎn)生一個交叉位scro(1,:)=[s(seln(1),1:chb)s(seln(2),chb+1:bn)];scro(2,:)=[s(seln(2),1:chb)s(seln(1),chb+1:bn)];elsescro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);endBacktomain.m914.2基本遺傳算法交叉操作函數(shù)4.2.74.2基本遺傳算法

變異操作函數(shù)

4.2.7算法的設(shè)計與實(shí)現(xiàn)

%“變異”操作functionsnnew=mut(snew,pm);bn=size(snew,2);snnew=snew;ifrand<pmchb=ceil(rand*bn);%在[1,bn]范圍內(nèi)隨機(jī)產(chǎn)生一個變異位snnew(chb)=abs(snew(chb)-1);endBacktomain.m924.2基本遺傳算法變異操作函數(shù)4.2.74.2基本遺傳算法

運(yùn)行程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

934.2基本遺傳算法運(yùn)行程序4.2.7算法4.2基本遺傳算法

運(yùn)行程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

944.2基本遺傳算法運(yùn)行程序4.2.7算法4.2基本遺傳算法

運(yùn)行程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

954.2基本遺傳算法運(yùn)行程序4.2.7算法4.2基本遺傳算法

運(yùn)行程序

4.2.7算法的設(shè)計與實(shí)現(xiàn)

964.2基本遺傳算法運(yùn)行程序4.2.7算法4.2基本遺傳算法

模式將種群中的個體即基因串中的相似樣板稱為模式。在二進(jìn)制編碼的串中，模式是基于三個字符集（0，1，*）的字符串，符號*代表任意字符，即0或1。如模式*1*描述了一個四個元的子集{010，011，110，111}。4.2.8模式定理

974.2基本遺傳算法模式4.2.8模式定理4.2基本遺傳算法

模式階和定義距模式H中確定位置的個數(shù)稱為模式H的模式階，記作O(H)，如O(011*1*)=4。模式階用來反映不同模式間確定性的差異，模式階越高，模式的確定性就越高，所匹配的樣本個數(shù)就越少。4.2.8模式定理

984.2基本遺傳算法模式階和定義距4.2.84.2基本遺傳算法

模式階和定義距模式H中第一個確定位置和最后一個確定位置之間的距離稱為模式的定義距，記作δ(H)，如

δ(011*1**)=4。階數(shù)相同的模式會有不同的性質(zhì)，定義距就反映了這種性質(zhì)的差異。4.2.8模式定理

994.2基本遺傳算法模式階和定義距4.2.84.2基本遺傳算法

模式定理（schematheorem）在給定時間步t,一個特定模式H有m個代表串包含在種群A(t)中，記為m=m(H,t)，在再生階段，每個串根據(jù)它的適應(yīng)值進(jìn)行復(fù)制，一個串Ai的再生概率為4.2.8模式定理

1004.2基本遺傳算法模式定理（schematheor4.2基本遺傳算法

模式定理（schematheorem）當(dāng)采用非重疊的n個串的種群替代種群A(t)，可以得到：其中f(H)是在時間t，模式H的串的平均適應(yīng)度；

而整個種群的平均適應(yīng)度為4.2.8模式定理

1014.2基本遺傳算法模式定理（schematheor4.2基本遺傳算法

4.2.8模式定理

模式定理（schematheorem）假設(shè)從t=0開始，某一特定模式適應(yīng)度值保持在種群平均適應(yīng)度以上一個cf（c為一常數(shù)），則模式的選擇生長方程為在種群平均值以上（以下）的模式將按指數(shù)增長（衰減）的方式復(fù)制。1024.2基本遺傳算法4.2.8模式定理模4.2基本遺傳算法

模式定理（schematheorem）考慮交叉操作，模式H被破壞的概率為δ(H)/(l-1)，模式H生存概率為1-δ(H)/(l-1)，若交叉操作發(fā)生的概率為pc，因此對于模式H的生存概率計算為：

同時考慮選擇、交叉操作對模式的影響，可得：4.2.8模式定理

H1=*1****0H2=***10*01034.2基本遺傳算法模式定理（schematheor4.2基本遺傳算法

模式定理（schematheorem）考慮變異操作，單個等位基因存活的概率為1-pm，當(dāng)模式H中O(H)個確定位都存活時，模式H才被保留，存活概率為：

同時考慮選擇、交叉和變異操作對模式的影響，可得：4.2.8模式定理

H1=*1****0H2=***10*01044.2基本遺傳算法模式定理（schematheor4.2基本遺傳算法

模式定理（schematheorem）

模式定理：在遺傳算子選擇、交叉、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式被定義為積木塊。4.2.8模式定理

1054.2基本遺傳算法模式定理（schematheor4.2基本遺傳算法

積木塊假設(shè)（buildingblockhypothesis）遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作作用下相互結(jié)合，最終接近全局最優(yōu)解。4.2.8模式定理

1064.2基本遺傳算法積木塊假設(shè)（buildingbl4.3遺傳算法的改進(jìn)

4.3.1CHC算法

4.3.2自適應(yīng)遺傳算法

4.3.3基于小生境技術(shù)的遺傳算法4.4遺傳算法的應(yīng)用

4.4.1解決帶約束的函數(shù)優(yōu)化問題

4.4.2解決多目標(biāo)優(yōu)化問題

4.4.3解決組合優(yōu)化問題

4.4.4遺傳算法在過程建模中的應(yīng)用

4.4.5遺傳算法在模式識別中的應(yīng)用?1074.3遺傳算法的改進(jìn)?1074.3遺傳算法的改進(jìn)

改進(jìn)的途徑改變遺傳算法的組成成分；采用混合遺傳算法；采用動態(tài)自適應(yīng)技術(shù)；采用非標(biāo)準(zhǔn)的遺傳操作算子；采用并行遺傳算法等。

1084.3遺傳算法的改進(jìn)改進(jìn)的途徑1084.3遺傳算法的改進(jìn)

改進(jìn)思路1991年Eshelman提出的一種改進(jìn)遺傳算法；C：跨世代精英選擇（Crossgenerationalelitistselection）策略；H：異物種重組（Heterogeneousrecombination）；C：大變異（Cataclysmicmutation）。4.3.1CHC算法

1094.3遺傳算法的改進(jìn)改進(jìn)思路4.3.1C4.3遺傳算法的改進(jìn)

選擇（C：跨世代精英選擇）上一代種群與通過新的交叉方法產(chǎn)生的個體群混合起來，從中按一定概率選擇較優(yōu)的個體；即使當(dāng)交叉操作產(chǎn)生較劣個體偏多時，由于原種群大多數(shù)個體殘留，不會引起個體的評價值降低；可以更好地保持遺傳多樣性；排序方法，克服比例適應(yīng)度計算的尺度問題。4.3.1CHC算法

1104.3遺傳算法的改進(jìn)選擇（C：跨世代精英選擇）4.3遺傳算法的改進(jìn)

交叉（H：異物種重組）均勻交叉的改進(jìn)：當(dāng)兩個父個體位值相異的位數(shù)為m時，從中隨機(jī)選取m/2個位置，實(shí)行父個體位值的交換；確定一閾值，當(dāng)個體間距離低于該閾值時，不進(jìn)行交叉操作。進(jìn)化收斂的同時，逐漸地減小該閾值。4.3.1CHC算法

1114.3遺傳算法的改進(jìn)交叉（H：異物種重組）4.3遺傳算法的改進(jìn)

變異（C：大變異）在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時期，從最優(yōu)個體中選擇一部分個體進(jìn)行初始化；初始化：選擇一定比例（擴(kuò)散率，一般0.35）的基因座，隨機(jī)地決定它們的位值。4.3.1CHC算法

1124.3遺傳算法的改進(jìn)變異（C：大變異）4.4.3遺傳算法的改進(jìn)

參數(shù)分析交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性；Pc越大，新個體產(chǎn)生的速度就越快，但過大會使優(yōu)秀個體的結(jié)構(gòu)很快被破壞；Pc過小，搜索過程緩慢，以至停止不前；Pm過小，不易產(chǎn)生新個體結(jié)構(gòu)，Pm過大，變成純粹的隨機(jī)搜索；4.3.2自適應(yīng)遺傳算法

1134.3遺傳算法的改進(jìn)參數(shù)分析4.3.2自4.3遺傳算法的改進(jìn)

自適應(yīng)策略使Pc和Pm能夠隨適應(yīng)度自動改變：當(dāng)種群各個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，使Pc和Pm增加；而當(dāng)群體適應(yīng)度比較分散時，使Pc和Pm減少；對于適應(yīng)度較高的個體，對應(yīng)于較低的Pc和Pm；而較低適應(yīng)度的個體，對應(yīng)于較高的Pc和Pm。在保持群體多樣性的同時，保證遺傳算法收斂性。4.3.2自適應(yīng)遺傳算法

1144.3遺傳算法的改進(jìn)自適應(yīng)策略4.3.24.3遺傳算法的改進(jìn)

自適應(yīng)方法fmax——群體中最大的適應(yīng)度值；favg——每代群體的平均適應(yīng)度值；f’——要交叉的兩個個體中較大的適應(yīng)度值；f——要交叉或變異的個體適應(yīng)度值；4.3.2自適應(yīng)遺傳算法

k1、k2、k3、k4取(0,1)的值1154.3遺傳算法的改進(jìn)自適應(yīng)方法4.3.24.3遺傳算法的改進(jìn)

自適應(yīng)方法進(jìn)一步改進(jìn)適用于進(jìn)化后期，不適于進(jìn)化前期，因?yàn)榍捌诘膬?yōu)秀個體有可能是局部最優(yōu)點(diǎn)；使最大適應(yīng)度個體的交叉概率和變異概率由0提高到Pc2和Pm2；采用精英選擇策略，將優(yōu)良個體直接復(fù)制到下一代。4.3.2自適應(yīng)遺傳算法

1164.3遺傳算法的改進(jìn)自適應(yīng)方法進(jìn)一步改進(jìn)4.4.3遺傳算法的改進(jìn)

自適應(yīng)方法進(jìn)一步改進(jìn)4.3.2自適應(yīng)遺傳算法

1174.3遺傳算法的改進(jìn)自適應(yīng)方法進(jìn)一步改進(jìn)4.4.3遺傳算法的改進(jìn)

小生境概念小生境（niche）：生物學(xué)中，特定環(huán)境中的一種組織功能；在SGA中，容易“近親繁殖”；NGA（NicheGenericAlgorithm），將每一代個體劃分為若干類，每類選出優(yōu)秀個體組成一個種群；優(yōu)勢：保持解的多樣性，提高全局搜索能力，適合復(fù)雜多峰函數(shù)的優(yōu)化。4.3.3基于小生境技術(shù)的遺傳算法

1184.3遺傳算法的改進(jìn)小生境概念4.3.34.3遺傳算法的改進(jìn)

選擇策略預(yù)選擇機(jī)制、排擠機(jī)制、分享機(jī)制；預(yù)選擇（preselection,1970）機(jī)制當(dāng)子個體的適應(yīng)度超過其父個體適應(yīng)度時，子個體才可以替代父個體，否則父個體仍保留；有效維持種群多樣性，造就小生境進(jìn)化環(huán)境。4.3.3基于小生境技術(shù)的遺傳算法

1194.3遺傳算法的改進(jìn)選擇策略4.3.3基4.3遺傳算法的改進(jìn)

排擠（crowding,1975）機(jī)制設(shè)置排擠因子CF（CF=2或3），隨機(jī)選取1/CF個個體組成排擠成員，排擠與其相似（用距離來度量）的個體；個體之間的相似性可用個體編碼串之間的海明距離來度量。4.3.3基于小生境技術(shù)的遺傳算法

1204.3遺傳算法的改進(jìn)排擠（crowding,19754.3遺傳算法的改進(jìn)

共享（sharing,1987）機(jī)制通過個體之間的相似性程度的共享函數(shù)來調(diào)整各個體的適應(yīng)度；共享函數(shù)的目的：將搜索空間的多個峰值在地理上區(qū)分開來，每一個峰值處接受一定比例數(shù)目的個體，比例數(shù)目與峰值高度有關(guān)；4.3.3基于小生境技術(shù)的遺傳算法

1214.3遺傳算法的改進(jìn)共享（sharing,1987）4.3遺傳算法的改進(jìn)

共享（sharing,1987）機(jī)制共享函數(shù)的值越大，表明個體之間越相似，記為S(dij)，dij為兩個個體i和j之間的距離；

σshare是niche的半徑，由使用者給定。4.3.3基于小生境技術(shù)的遺傳算法

1224.3遺傳算法的改進(jìn)共享（sharing,1987）4.3遺傳算法的改進(jìn)

共享（sharing,1987）機(jī)制共享法將個體的適應(yīng)度降低，即適應(yīng)度值fi除以一個niche計數(shù)mi：在距離為σshare的范圍內(nèi)的個體彼此削減適應(yīng)度，這些個體將收斂在一個niche內(nèi)，避免了整個種群的收斂。4.3.3基于小生境技術(shù)的遺傳算法

1234.3遺傳算法的改進(jìn)共享（sharing,1987）4.3遺傳算法的改進(jìn)

4.3.1CHC算法

4.3.2自適應(yīng)遺傳算法

4.3.3基于小生境技術(shù)的遺傳算法4.4遺傳算法的應(yīng)用

4.4.1解決帶約束的函數(shù)優(yōu)化問題

4.4.2解決多目標(biāo)優(yōu)化問題

4.4.3解決組合優(yōu)化問題

4.4.4遺傳算法在過程建模中的應(yīng)用

4.4.5遺傳算法在模式識別中的應(yīng)用?1244.3遺傳算法的改進(jìn)?1244.4遺傳算法的應(yīng)用

約束最優(yōu)化問題（ConstrainedOptimizationProblems）的表述

4.4.1解決帶約束的函數(shù)優(yōu)化問題

1254.4遺傳算法的應(yīng)用約束最優(yōu)化問題（Constrai4.4遺傳算法的應(yīng)用

4.4.1解決帶約束的函數(shù)優(yōu)化問題

測試函數(shù)（Benchmark問題）

其全局最優(yōu)解和最優(yōu)值為1264.4遺傳算法的應(yīng)用4.4.1解決帶約