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

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

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

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

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

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è)計(jì)與實(shí)現(xiàn)

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

產(chǎn)生早在50年代，一些生物學(xué)家開始研究運(yùn)用數(shù)字計(jì)算機(jī)模擬生物的自然遺傳與自然進(jìn)化過程；1963年，德國柏林技術(shù)大學(xué)的I.Rechenberg和H.P.Schwefel，做風(fēng)洞實(shí)驗(yàn)時(shí)，產(chǎn)生了進(jìn)化策略的初步思想；60年代，L.J.Fogel在設(shè)計(jì)有限態(tài)自動(dòng)機(jī)時(shí)提出進(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年，在美國召開了第一屆遺傳算法國際會(huì)議，并且成立了國際遺傳算法學(xué)會(huì)(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”，對(duì)遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述；1991年，L.Davis編輯出版了《Handbookofgeneticalgorithms》，其中包括了遺傳算法在工程技術(shù)和社會(huì)生活中大量的應(yīng)用實(shí)例。4.1.1遺傳算法的產(chǎn)生與發(fā)展

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

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

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

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é)的基本知識(shí)

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

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

1111111

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

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

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）：度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕;4.1.2生物進(jìn)化理論和遺傳學(xué)的基本知識(shí)

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

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

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

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

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é)的基本知識(shí)

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)生初始種群計(jì)算適應(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遺傳算法的基本操作

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

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

個(gè)體染色體適應(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)生一個(gè)隨機(jī)數(shù)：4.1.4遺傳算法的基本操作

個(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淘汰！淘汰！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)度計(jì)算→選擇→交叉→變異，直至滿足終止條件。4.1.4遺傳算法的基本操作

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

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

4.1.4遺傳算法的基本操作

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

選擇2.選擇算法：輪盤賭選擇（roulettewheelselection）隨機(jī)遍歷抽樣（stochasticuniversalselection）局部選擇（localselection）截?cái)噙x擇（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í)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問題非常有效;自動(dòng)控制如基于遺傳算法的模糊控制器優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)等;4.1.5遺傳算法的應(yīng)用

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

機(jī)器人智能控制遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動(dòng)協(xié)調(diào)等;組合圖像處理和模式識(shí)別目前已在圖像恢復(fù)、圖像邊緣持征提取、幾何形狀識(shí)別等方面得到了應(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è)計(jì)Koza發(fā)展了遺傳程序設(shè)計(jì)的慨念，他使用了以LISP語言所表示的編碼方法，基于對(duì)一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作自動(dòng)生成計(jì)算機(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é)的基本知識(shí)

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è)計(jì)與實(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)的最大值：解有無窮多個(gè)：4.2.1簡單函數(shù)優(yōu)化的實(shí)例

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

問題的提出當(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í)，函數(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基本遺傳算法

計(jì)算適應(yīng)度不同的問題有不同的適應(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.5863454.2.1簡單函數(shù)優(yōu)化的實(shí)例

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

計(jì)算適應(yīng)度

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

(0000000000000000000000)→-1(1111111111111111111111)→2394.2基本遺傳算法計(jì)算適應(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。

得到的最佳個(gè)體：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è)計(jì)的基因型；健全性（soundness）：任何一個(gè)基因型都對(duì)應(yīng)于一個(gè)可能解；非冗余性（non-redundancy）：問題空間和表達(dá)空間一一對(duì)應(yīng)。4.2.2遺傳基因型

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

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

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

二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較在交叉操作時(shí)，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼產(chǎn)生新個(gè)體的可能性多，而且產(chǎn)生的新個(gè)體不受父個(gè)體所構(gòu)成的超體的限制；在變異操作時(shí)，二進(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ù)變換而成的，對(duì)目標(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è)計(jì)單值、連續(xù)、非負(fù)、最大化合理、一致性（能夠反映解的優(yōu)劣）計(jì)算量小通用性強(qiáng)4.2.3適應(yīng)度函數(shù)及其尺度變換

474.2基本遺傳算法適應(yīng)度函數(shù)的設(shè)計(jì)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ù)的保守估計(jì)值。4.2.3適應(yīng)度函數(shù)及其尺度變換

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

適應(yīng)度函數(shù)的作用適應(yīng)度函數(shù)設(shè)計(jì)不當(dāng)有可能出現(xiàn)欺騙問題：（1）進(jìn)化初期，個(gè)別超常個(gè)體控制選擇過程；（2）進(jìn)化末期，個(gè)體差異太小導(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)度的個(gè)體被復(fù)制的強(qiáng)制性就越弱。4.2.3適應(yīng)度函數(shù)及其尺度變換

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

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

554.2基本遺傳算法幾個(gè)概念4.2.4遺傳4.2基本遺傳算法

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

564.2基本遺傳算法幾個(gè)概念4.2.4遺傳4.2基本遺傳算法

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

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

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

μ為種群大小，i為個(gè)體序號(hào)，ηmax代表選擇壓力。4.2.4遺傳操作——選擇

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

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

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

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

4.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.00604.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

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

4.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.00614.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

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

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

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

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

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

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

常用選擇方法截?cái)噙x擇法（truncationselection）個(gè)體按適應(yīng)度排列，只有優(yōu)秀個(gè)體能夠成為父個(gè)體，參數(shù)為截?cái)嚅撝担ū贿x作父個(gè)體的百分比）。4.2.4遺傳操作——選擇

截?cái)嚅撝?％10％20％40％50％80％選擇強(qiáng)度2.661.761.20.970.80.34654.2基本遺傳算法常用選擇方法4.2.44.2基本遺傳算法

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

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

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

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

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

父個(gè)體112

25

5父個(gè)體2123

4

34子個(gè)體1123

4

5子個(gè)體212

4

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

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

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

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

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

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

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

父個(gè)體112255父個(gè)體2123434子個(gè)體1子個(gè)體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遺傳操作——交叉/基因重組

父個(gè)體112255父個(gè)體2123434子個(gè)體1子個(gè)體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遺傳操作——交叉/基因重組

父個(gè)體101110011010

父個(gè)體210101100101子個(gè)體11

11

011

11

1

1

1子個(gè)體20

01

100

00

0

0

0

樣本101100011010樣本2100111001011表示由父個(gè)體1提供變量值；0表示由父個(gè)體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è)計(jì)與實(shí)現(xiàn)

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

主程序

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

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

主程序

4.2.7算法的設(shè)計(jì)與實(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è)計(jì)與實(shí)現(xiàn)

s=smnew;%產(chǎn)生了新的種群%計(jì)算新種群的適應(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è)計(jì)與實(shí)現(xiàn)

%記錄當(dāng)前代的最佳個(gè)體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è)計(jì)與實(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基本遺傳算法

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

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

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

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

4.2.7算法的設(shè)計(jì)與實(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);%計(jì)算函數(shù)值，即適應(yīng)度endf=f';Continue…854.2基本遺傳算法計(jì)算適應(yīng)度和累計(jì)概率函數(shù)44.2基本遺傳算法

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

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

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

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

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

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

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

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

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

選擇操作函數(shù)

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

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

交叉操作函數(shù)

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

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

交叉操作函數(shù)

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

ifrand<pcchb=ceil(rand*(bn-1));%在[1,bn-1]范圍內(nèi)隨機(jī)產(chǎn)生一個(gè)交叉位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è)計(jì)與實(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)生一個(gè)變異位snnew(chb)=abs(snew(chb)-1);endBacktomain.m924.2基本遺傳算法變異操作函數(shù)4.2.74.2基本遺傳算法

運(yùn)行程序

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

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

運(yùn)行程序

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

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

運(yùn)行程序

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

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

運(yùn)行程序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.8模式定理

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

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

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

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

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

同時(shí)考慮選擇、交叉和變異操作對(duì)模式的影響，可得：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遺傳算法在模式識(shí)別中的應(yīng)用?1074.3遺傳算法的改進(jìn)?1074.3遺傳算法的改進(jìn)

改進(jìn)的途徑改變遺傳算法的組成成分；采用混合遺傳算法；采用動(dòng)態(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)生的個(gè)體群混合起來，從中按一定概率選擇較優(yōu)的個(gè)體；即使當(dāng)交叉操作產(chǎn)生較劣個(gè)體偏多時(shí)，由于原種群大多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低；可以更好地保持遺傳多樣性；排序方法，克服比例適應(yīng)度計(jì)算的尺度問題。4.3.1CHC算法

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

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

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

變異（C：大變異）在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時(shí)期，從最優(yōu)個(gè)體中選擇一部分個(gè)體進(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越大，新個(gè)體產(chǎn)生的速度就越快，但過大會(huì)使優(yōu)秀個(gè)體的結(jié)構(gòu)很快被破壞；Pc過小，搜索過程緩慢，以至停止不前；Pm過小，不易產(chǎn)生新個(gè)體結(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)改變：當(dāng)種群各個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使Pc和Pm增加；而當(dāng)群體適應(yīng)度比較分散時(shí)，使Pc和Pm減少；對(duì)于適應(yīng)度較高的個(gè)體，對(duì)應(yīng)于較低的Pc和Pm；而較低適應(yīng)度的個(gè)體，對(duì)應(yīng)于較高的Pc和Pm。在保持群體多樣性的同時(shí)，保證遺傳算法收斂性。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’——要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值；f——要交叉或變異的個(gè)體適應(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)秀個(gè)體有可能是局部最優(yōu)點(diǎn)；使最大適應(yīng)度個(gè)體的交叉概率和變異概率由0提高到Pc2和Pm2；采用精英選擇策略，將優(yōu)良個(gè)體直接復(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），將每一代個(gè)體劃分為若干類，每類選出優(yōu)秀個(gè)體組成一個(gè)種群；優(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)子個(gè)體的適應(yīng)度超過其父個(gè)體適應(yīng)度時(shí)，子個(gè)體才可以替代父個(gè)體，否則父個(gè)體仍保留；有效維持種群多樣性，造就小生境進(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個(gè)個(gè)體組成排擠成員，排擠與其相似（用距離來度量）的個(gè)體；個(gè)體之間的相似性可用個(gè)體編碼串之間的海明距離來度量。4.3.3基于小生境技術(shù)的遺傳算法

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

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

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

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

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

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

共享（sharing,1987）機(jī)制共享法將個(gè)體的適應(yīng)度降低，即適應(yīng)度值fi除以一個(gè)niche計(jì)數(shù)mi：在距離為σshare的范圍內(nèi)的個(gè)體彼此削減適應(yīng)度，這些個(gè)體將收斂在一個(gè)niche內(nèi)，避免了整個(gè)種群的收斂。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遺傳算法在模式識(shí)別中的應(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解決帶約