經(jīng)典算法之遺傳算法.ppt

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ī)劃的思想。,1.遺傳算法的產(chǎn)生與發(fā)展,遺傳算法簡介,產(chǎn)生 60年代中期，美國Michigan大學(xué)的J. H. Holland教授提出借鑒生物自然遺傳的基本原理用于自然 和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)； 19

2、67年，他的學(xué)生J. D. Bagley在博士論文中首次提出“遺傳算法(Genetic Algorithms)”一詞； 1975年，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，標(biāo)志遺傳算法的誕生。,遺傳算法的產(chǎn)生與發(fā)展,遺傳算法簡介,發(fā)展 70年代初，Holland提出了“模式定理”（Schema Theorem），一般認(rèn)為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)； 1985年，在美國召開了第一屆遺傳算法國際會議，并且成立了國際遺傳算法學(xué)會(ISGA，International Society of

3、Genetic Algorithms)；,遺傳算法的產(chǎn)生與發(fā)展,遺傳算法簡介,發(fā)展 1989年，Holland的學(xué)生D. J. Goldherg出版了“Genetic Algorithms in Search, Optimization, and Machine Learning”，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述； 1991年，L. Davis編輯出版了遺傳算法手冊，其中包括了遺傳算法在工程技術(shù)和社會生活中大量的應(yīng)用實(shí)例。,遺傳算法的產(chǎn)生與發(fā)展,遺傳算法簡介,幾個名詞概念 進(jìn)化計算：,遺傳算法的產(chǎn)生與發(fā)展,由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)域的研究人員分別獨(dú)立提出的，在相當(dāng)長的時

4、期里相互之間沒有正式溝通。直到90年代，才有所交流。 他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，于是提出將這類方法統(tǒng)稱為“進(jìn)化計算” ( Evolutionary Computation ) 。,遺傳算法簡介,達(dá)爾文的自然選擇說 遺傳（heredity）：子代和父代具有相 同或相似的性狀，保證物種的穩(wěn)定性； 變異（variation）：子代與父代，子代不同個體之間總有差異，是生命多樣性的根源； 生存斗爭和適者生存：具有適應(yīng)性變異的個體被保留，不具適應(yīng)性變異的個體被淘汰。 自然選擇過程是長期的、緩慢的、連續(xù)的過程。,2.生物進(jìn)化理論和遺傳學(xué)的基本知識,遺傳算法簡介,遺傳學(xué)基本概念與術(shù)語 染色體（

5、chromosome）：遺傳物質(zhì)的載體； 脫氧核糖核酸（DNA）：大分子有機(jī)聚合物，雙螺旋結(jié)構(gòu)； 遺傳因子（gene）：DNA或RNA長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；,生物進(jìn)化理論和遺傳學(xué)的基本知識,遺傳算法簡介,遺傳學(xué)基本概念與術(shù)語 基因型（genotype）：遺傳因子組合的模型； 表現(xiàn)型（phenotype）：由染色體決定性狀的外部表現(xiàn)；,生物進(jìn)化理論和遺傳學(xué)的基本知識,遺傳算法簡介,遺傳學(xué)基本概念與術(shù)語 基因座（locus）：遺傳基因在染色體中所占據(jù)的位置，同一基因座可能有的全部基因稱為等位基因（allele）； 個體（individual）：指帶有染色體特征的實(shí)體； 種群（pop

6、ulation）：個體的集合，該集合內(nèi)個體數(shù)稱為種群的大小；,生物進(jìn)化理論和遺傳學(xué)的基本知識,遺傳算法簡介,遺傳學(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ī)會就會相對較少，甚至逐漸滅絕;,生物進(jìn)化理論和遺傳學(xué)的基本知識,遺傳算法簡介,遺傳學(xué)基本概念與術(shù)語 選擇（selection）：指決定以一定的概率從種群中選擇若干個體的操作 ； 復(fù)制（reprod

7、uction）：細(xì)胞在分裂時，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因; 交叉（crossover）：在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體。又稱基因重組，俗稱“雜交”;,生物進(jìn)化理論和遺傳學(xué)的基本知識,遺傳算法簡介,遺傳學(xué)基本概念與術(shù)語 變異（mutation）：在細(xì)胞進(jìn)行復(fù)制時可能以很小的概率產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀; 編碼（coding）：表現(xiàn)型到基因型的映射； 解碼（decoding）：從基因型到表現(xiàn)型的映射。,生物進(jìn)化理論和遺傳學(xué)的基本知識,

8、遺傳算法基本概念與術(shù)語 個體（individual）：GA所處理的基本對象、結(jié)構(gòu)。 群體（population）：個體的集合。 位串（bit String）：個體的表示形式。對應(yīng)于遺傳學(xué)中的染色體（Chromosome） 基因（gene）：位串中的元素，表示不同的特征。對應(yīng)于生物學(xué)中的遺傳物質(zhì)單位，以DNA序列形式把遺傳信息譯成編碼。,遺傳算法基本概念與術(shù)語 位串結(jié)構(gòu)空間（bit String Space）：等位基因任意組合構(gòu)成的位串集合，基因操作在位串結(jié)構(gòu)空間進(jìn)行，對應(yīng)于遺傳學(xué)中的基因型的集合。 參數(shù)空間（Parameters Space）：是位串空間在物理系統(tǒng)中的映射。對應(yīng)于遺傳學(xué)中的表現(xiàn)

9、型的集合。 適應(yīng)值（fitness）：某一個體對于環(huán)境的適應(yīng)程度，或者在環(huán)境壓力下的生存能力，取決于遺傳特性。 復(fù)制、選擇（reproduction or selection）：在有限資源空間上的排他性競爭。 逆轉(zhuǎn)或倒位（inversion）：反轉(zhuǎn)位串上的一段基因的排列順序。對應(yīng)于染色體上的一部分，在脫離之后反轉(zhuǎn) 180o再連接起來。,遺傳算法簡介,進(jìn)化論與遺傳學(xué)的融合 19301947年，達(dá)爾文進(jìn)化論與遺傳學(xué)走向融合，Th. Dobzhansky1937年發(fā)表的遺傳學(xué)與物種起源是融合進(jìn)化論與遺傳學(xué)的代表作。 生物進(jìn)化與智能學(xué)的關(guān)系 生物物種作為復(fù)雜系統(tǒng)，具有奇妙的自適應(yīng)、自組織和自優(yōu)化能力，

10、這是一種生物在進(jìn)化過程中體現(xiàn)的智能，也是人工系統(tǒng)夢寐以求的功能。,生物進(jìn)化理論和遺傳學(xué)的基本知識,遺傳算法簡介,遺傳算法的基本思路,3 遺傳算法的思路與特點(diǎn),遺傳算法簡介,自組織、自適應(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ī)則,遺傳算法的特點(diǎn),遺傳算法簡介,選擇 適應(yīng)度計算： 計算結(jié)果非負(fù) 選擇算法： 兩類 基于適應(yīng)度比例的 基于適應(yīng)度排序的,4 遺傳算法的基本操作,遺傳算法簡介,選擇 選擇算法： 輪盤賭選擇（ro

11、ulette wheel selection） 隨機(jī)遍歷抽樣（stochastic universal selection） 局部選擇（local selection） 截斷選擇（truncation selection） 錦標(biāo)賽選擇（tournament selection）,遺傳算法的基本操作,遺傳算法簡介,交叉或基因重組 實(shí)值重組（real valued recombination）： 離散重組（discrete recombination） 中間重組（intermediate recombination） 線性重組（linear recombination） 擴(kuò)展線性重組（extend

12、ed linear recombination）,遺傳算法的基本操作,遺傳算法簡介,交叉或基因重組 二進(jìn)制交叉（binary valued crossover）： 單點(diǎn)交叉（single-point crossover） 多點(diǎn)交叉（multiple-point crossover） 均勻交叉（uniform crossover） 洗牌交叉（shuffle crossover） 縮小代理交叉（crossover with reduced surrogate）,遺傳算法的基本操作,遺傳算法簡介,變異 實(shí)值變異 二進(jìn)制變異,遺傳算法的基本操作,遺傳算法簡介,簡單實(shí)例 產(chǎn)生初始種群 計算適應(yīng)度,遺傳算

13、法的基本操作,0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011,（8） （5） （2） （10） （7） （12） （5） （19） （10） （14）,遺傳算法簡介,簡單實(shí)例 選擇,遺傳算法的基本操作,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,遺傳算法簡介,簡單實(shí)例 選擇,遺傳算法的基本操

14、作,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,遺傳算法簡介,簡單實(shí)例 選擇 在01之間產(chǎn)生一個 隨機(jī)數(shù)：,遺傳算法的基本操作,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.1086

15、96 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,0.070221,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 000101001

16、1,遺傳算法簡介,簡單實(shí)例 交叉,遺傳算法的基本操作,0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,100111,0100,0001,1001110100,1100000001,1010101,0001010,010,011,遺傳算法簡介,簡單實(shí)例 變異,遺傳算法的基本操作,遺傳算法簡介,簡單實(shí)例 至下一代，適應(yīng)度

17、計算選擇交叉變異，直至滿足終止條件。,遺傳算法的基本操作,遺傳算法簡介,函數(shù)優(yōu)化 是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域; 組合優(yōu)化 實(shí)踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效; 自動控制 如基于遺傳算法的模糊控制器優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識等;,5 遺傳算法的應(yīng)用,遺傳算法簡介,機(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)用;,遺傳算法的應(yīng)用,遺傳算法簡介,人工生命 基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基

18、礎(chǔ)，遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力； 遺傳程序設(shè)計 Koza發(fā)展了遺傳程序設(shè)計的慨念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作自動生成計算機(jī)程序;,遺傳算法的應(yīng)用,2 基本遺傳算法,問題的提出 一元函數(shù)求最大值：,1 簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,問題的提出 用微分法求取f(x)的最大值： 解有無窮多個：,簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,問題的提出 當(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稍大。,簡單函

19、數(shù)優(yōu)化的實(shí)例,基本遺傳算法,編碼 表現(xiàn)型：x 基因型：二進(jìn)制編碼（串長取決于求解精度） 串長與精度之間的關(guān)系： 若要求求解精度到6位小數(shù)，區(qū)間長度為2-(-1)3，即需將區(qū)間分為3/0.000001=3106等份。 所以編碼的二進(jìn)制串長應(yīng)為22位。,簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,產(chǎn)生初始種群 產(chǎn)生的方式：隨機(jī) 產(chǎn)生的結(jié)果：長度為22的二進(jìn)制串 產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50， 1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 000110010

20、1001100000011 0000011010010000000000 ,簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,計算適應(yīng)度 不同的問題有不同的適應(yīng)度計算方法 本例：直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù) 將某個體轉(zhuǎn)化為-1,2區(qū)間的實(shí)數(shù)： s= x=0.637197 計算x的函數(shù)值（適應(yīng)度）： f(x)=xsin(10 x)+2.0=2.586345,簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,計算適應(yīng)度（簡單函數(shù)值替換） 二進(jìn)制與十進(jìn)制之間的轉(zhuǎn)換： 第一步，將一個二進(jìn)制串（b21b20b0）轉(zhuǎn)化為10進(jìn)制數(shù)： 第二步，x對應(yīng)的區(qū)間-1,2內(nèi)的實(shí)數(shù)：,簡單函數(shù)優(yōu)化的實(shí)例,(000000000000000000000

21、0)-1 (1111111111111111111111)2,基本遺傳算法,遺傳操作 選擇：輪盤賭選擇法； 交叉：單點(diǎn)交叉； 變異：小概率變異,簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,模擬結(jié)果 設(shè)置的參數(shù)： 種群大小50；交叉概率0.75；變異概率0.05；最大迭代數(shù)200。 得到的最佳個體： smax=; xmax=1.8506; f(xmax)=3.8503;,簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,模擬結(jié)果 進(jìn)化的過程：,簡單函數(shù)優(yōu)化的實(shí)例,基本遺傳算法,編碼原則 完備性（completeness）：問題空間的所有解都能表示為所設(shè)計的基因型； 健全性（soundness）：任何一個基因型都對應(yīng)于一個

22、可能解； 非冗余性（non-redundancy）：問題空間和表達(dá)空間一一對應(yīng)。,2 遺傳基因型,基本遺傳算法,多種編碼方式 二進(jìn)制編碼； 浮點(diǎn)數(shù)編碼； 格雷碼編碼； 符號編碼； 復(fù)數(shù)編碼； DNA編碼等。,遺傳基因型,基本遺傳算法,二進(jìn)制編碼與浮點(diǎn)數(shù)編碼的比較 在交叉操作時，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼產(chǎn)生新個體的可能性多，而且產(chǎn)生的新個體不受父個體所構(gòu)成的超體的限制； 在變異操作時，二進(jìn)制編碼的種群穩(wěn)定性比浮點(diǎn)數(shù)編碼差。,遺傳基因型,基本遺傳算法,適應(yīng)度函數(shù)的重要性 適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解。 一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，對目標(biāo)函數(shù)值域的某種映

23、射變換稱為適應(yīng)度的尺度變換（fitness scaling）。,3 適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,幾種常見的適應(yīng)度函數(shù) 直接轉(zhuǎn)換 若目標(biāo)函數(shù)為最大化問題：Fit ( f (x) )= f (x) 若目標(biāo)函數(shù)為最小化問題：Fit ( f (x) )= - f (x),適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,幾種常見的適應(yīng)度函數(shù) 界限構(gòu)造法1 若目標(biāo)函數(shù)為最大化問題： 若目標(biāo)函數(shù)為最小化問題：,適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,幾種常見的適應(yīng)度函數(shù) 界限構(gòu)造法2 若目標(biāo)函數(shù)為最大化問題： 若目標(biāo)函數(shù)為最小化問題： c為目標(biāo)函數(shù)的保守估計值。,適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,適應(yīng)度函

24、數(shù)的作用 適應(yīng)度函數(shù)設(shè)計不當(dāng)有可能出現(xiàn)欺騙問題： （1）進(jìn)化初期，個別超常個體控制選擇過程； （2）進(jìn)化末期，個體差異太小導(dǎo)致進(jìn)化緩慢。,適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,適應(yīng)度函數(shù)的設(shè)計 單值、連續(xù)、非負(fù)、最大化 合理、一致性 計算量小 通用性強(qiáng),適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,適應(yīng)度函數(shù)的線性變換法 f=*f+ 系數(shù)的確定滿足以下條件： favg= favg fmax= cmult favg cmult =1.02.0,適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,適應(yīng)度函數(shù)的冪函數(shù)變換法 f= f k k與所求優(yōu)化相關(guān),適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,適應(yīng)度函數(shù)的指數(shù)變換法 f=

25、 e-af a決定了復(fù)制的強(qiáng)制性，其值越小，復(fù)制的強(qiáng)制性就越趨向于那些具有最大適應(yīng)性的個體。,適應(yīng)度函數(shù)及其尺度變換,基本遺傳算法,幾個概念 選擇壓力（selection pressure）:最佳個體選中的概率與平均個體選中概率的比值； 偏差（bias）：個體正規(guī)化適應(yīng)度與其期望再生概率的絕對差值； 個體擴(kuò)展（spread）：單個個體子代個數(shù)的范圍； 多樣化損失（loss of diversity）：在選擇階段未選中個體數(shù)目占種群的比例；,4 遺傳操作選擇,基本遺傳算法,幾個概念 選擇強(qiáng)度（selection intensity）:將正規(guī)高斯分布應(yīng)用于選擇方法，期望平均適應(yīng)度； 選擇方差（se

26、lection variance）：將正規(guī)高斯分布應(yīng)用于選擇方法，期望種群適應(yīng)度的方差。,遺傳操作選擇,基本遺傳算法,個體選擇概率的常用分配方法 按比例的適應(yīng)度分配（proportional fitness assignment） 某個體i，其適應(yīng)度為fi，則其被選取的概率Pi為：,遺傳操作選擇,基本遺傳算法,個體選擇概率的常用分配方法 基于排序的適應(yīng)度分配（rank-based fitness assignment） 線性排序（by Baker） 為種群大小，i為個體序號，max代表選擇壓力。,遺傳操作選擇,基本遺傳算法,個體選擇概率的常用分配方法 基于排序的適應(yīng)度分配（rank-based

27、 fitness assignment） 非線性排序（by Michalewicz） i為個體序號，c為排序第一的個體的選擇概率。,遺傳操作選擇,基本遺傳算法,常用選擇方法 輪盤賭選擇法（roulette wheel selection）,遺傳操作選擇,基本遺傳算法,常用選擇方法 隨機(jī)遍歷抽樣法（stochastic universal sampling）,遺傳操作選擇,設(shè)定n為需要選擇的個體數(shù)目，等距離選擇個體，選擇指針的距離為1n。第一個指針的位置由0，ln區(qū)間的均勻隨機(jī)數(shù)決定。如圖所示，需要選擇6個個體，指針間的距離為l6o.167，第一個指針的隨機(jī)位置為0.1，按這種選擇方法被選中作為

28、交配集個體為：12，34，6，8。,基本遺傳算法,常用選擇方法 局部選擇法（local selection） (1)線形鄰集,遺傳操作選擇,在局部選擇法中，每個個體處于一個約束環(huán)境中，稱為局部鄰域(而其他選擇方法中視整個種群為個體之鄰域)，個體僅與其鄰近個體產(chǎn)生交互，該鄰域的定義由種群的分布結(jié)構(gòu)給出。鄰域可被當(dāng)作潛在的交配伙伴。 首先均勻隨機(jī)地選擇一半交配種群，選擇方法可以是隨機(jī)遍歷方法也可以是截斷選擇方法，然后對每個被選個體定義其局部鄰域，在鄰域內(nèi)部選擇交配伙伴。,基本遺傳算法,常用選擇方法 局部選擇法（local selection） (2)兩對角鄰集,遺傳操作選擇,基本遺傳算法,常用選擇

29、方法 局部選擇法（local selection） (2)兩對角鄰集,遺傳操作選擇,基本遺傳算法,常用選擇方法 截斷選擇法（truncation selection） 個體按適應(yīng)度排列，只有優(yōu)秀個體能夠成為父個體，參數(shù)為截斷閥值（被選作父個體的百分比）。,遺傳操作選擇,基本遺傳算法,常用選擇方法 錦標(biāo)賽選擇法（tournament selection） 隨機(jī)從種群中挑選一定數(shù)目個體，其中最好的個體作為父個體，此過程重復(fù)進(jìn)行完成個體的選擇。,遺傳操作選擇,基本遺傳算法,實(shí)值重組 離散重組 子個體的每個變量可以按等概率隨機(jī)地挑選父個體。,5 遺傳操作交叉/基因重組,父個體1 12 25 5 父個體

30、2 123 4 34,子個體1 123 4 5 子個體2 12 4 34,基本遺傳算法,實(shí)值重組 中間重組 子個體父個體1（父個體2父個體1） 是比例因子，由-d,1+d上均勻分布地隨機(jī)數(shù)產(chǎn)生。 一般取d=0.25。 子代的每個變量均產(chǎn)生一個 。,遺傳操作交叉/基因重組,基本遺傳算法,實(shí)值重組 中間重組示例,遺傳操作交叉/基因重組,父個體1 12 25 5 父個體2 123 4 34,子個體1 子個體2,值樣本1 0.5 1.1 -0.1 值樣本2 0.1 0.8 0.5,120.5（12312）=67.5,67.5,251.1（425）=1.9,1.9,2.1,120.1（12312）=23

31、.1,23.1,8.2,19.5,基本遺傳算法,實(shí)值重組 中間重組,遺傳操作交叉/基因重組,基本遺傳算法,實(shí)值重組 線性重組,遺傳操作交叉/基因重組,父個體1 12 25 5 父個體2 123 4 34,子個體1 子個體2,值樣本1 0.5 值樣本2 0.1,120.5（12312）=67.5,67.5,250.5（425）=14.5,14.5,19.5,120.1（12312）=23.1,23.1,22.9,7.9,基本遺傳算法,實(shí)值重組 線性重組,遺傳操作交叉/基因重組,基本遺傳算法,二進(jìn)制交叉 單點(diǎn)交叉,遺傳操作交叉/基因重組,基本遺傳算法,二進(jìn)制交叉 多點(diǎn)交叉,遺傳操作交叉/基因重組,

32、基本遺傳算法,實(shí)值變異 一般采用： 二進(jìn)制變異,6 遺傳操作變異,4.2 基本遺傳算法,運(yùn)行程序,4.2.7 算法的設(shè)計與實(shí)現(xiàn),基本遺傳算法,運(yùn)行程序,算法的設(shè)計與實(shí)現(xiàn),4.2 基本遺傳算法,運(yùn)行程序,4.2.7 算法的設(shè)計與實(shí)現(xiàn),4.2 基本遺傳算法,運(yùn)行程序,4.2.7 算法的設(shè)計與實(shí)現(xiàn),3 遺傳算法的改進(jìn),改進(jìn)的途徑 改變遺傳算法的組成成分； 采用混合遺傳算法； 采用動態(tài)自適應(yīng)技術(shù)； 采用非標(biāo)準(zhǔn)的遺傳操作算子； 采用并行遺傳算法等。,遺傳算法的改進(jìn),改進(jìn)思路 1991年Eshelman提出的一種改進(jìn)遺傳算法； C：跨代精英選擇（Cross generational elitist sel

33、ection）策略； H：異物種重組（Heterogeneous recombination）； C：大變異（Cataclysmic mutation）。,1. CHC算法,遺傳算法的改進(jìn),選擇 上一代種群與通過新的交叉方法產(chǎn)生的個體群混合起來，從中按一定概率選擇較優(yōu)的個體； 即使交叉操作產(chǎn)生較劣個體偏多，由于原種群大多數(shù)個體殘留，不會引起個體的評價值降低； 可以更好地保持遺傳多樣性； 排序方法，克服比例適應(yīng)度計算的尺度問題。,CHC算法,遺傳算法的改進(jìn),交叉 均勻交叉的改進(jìn)：當(dāng)兩個父個體位值相異的位數(shù)為m時，從中隨機(jī)選取m/2個位置，實(shí)行父個體位值的交換； 顯然，這樣的操作對模式具有很強(qiáng)的破

34、壞性。 確定一閾值，當(dāng)個體間距離低于該閾值時，不進(jìn)行交叉操作。進(jìn)化收斂的同時，逐漸地減小該閾值。,CHC算法,遺傳算法的改進(jìn),變異 在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時期，從最優(yōu)個體中選擇一部分個體進(jìn)行初始化； 初始化：選擇一定比例（擴(kuò)散率，一般0.35）的基因座，隨機(jī)地決定它們的位值。,CHC算法,遺傳算法的改進(jìn),參數(shù)分析 交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性； Pc越大，新個體產(chǎn)生的速度就越快，但過大會使優(yōu)秀個體的結(jié)構(gòu)很快被破壞； Pc過小，搜索過程緩慢，以至停止不前； Pm過小，不易產(chǎn)生新個體結(jié)構(gòu)， Pm過大，變成純粹的隨機(jī)搜索；,2 自適應(yīng)遺傳算法,遺傳算法的改進(jìn),自適應(yīng)策略 Srinvivas等提出一種自適應(yīng)遺傳算法，Pc和Pm能夠隨適應(yīng)度自動改變： 當(dāng)種群各個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，使Pc和