經典算法之遺傳算法.ppt

1、遺傳算法,遺傳算法簡介,產生 早在50年代，一些生物學家開始研究運用數字計算機模擬生物的自然遺傳與自然進化過程； 1963年，德國柏林技術大學的I. Rechenberg和H. P. Schwefel，做風洞實驗時，產生了進化策略的初步思想； 60年代， L. J. Fogel在設計有限態(tài)自動機時提出進化規(guī)劃的思想。1966年Fogel等出版了基于模擬進化的人工智能，系統(tǒng)闡述了進化規(guī)劃的思想。,1.遺傳算法的產生與發(fā)展,遺傳算法簡介,產生 60年代中期，美國Michigan大學的J. H. Holland教授提出借鑒生物自然遺傳的基本原理用于自然 和人工系統(tǒng)的自適應行為研究和串編碼技術； 19

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

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

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

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

6、ulation）：個體的集合，該集合內個體數稱為種群的大??；,生物進化理論和遺傳學的基本知識,遺傳算法簡介,遺傳學基本概念與術語 進化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應其生存環(huán)境，使得其品質不斷得到改良，這種生命現象稱為進化； 適應度（fitness）：度量某個物種對于生存環(huán)境的適應程度。對生存環(huán)境適應程度較高的物種將獲得更多的繁殖機會，而對生存環(huán)境適應程度較低的物種，其繁殖機會就會相對較少，甚至逐漸滅絕;,生物進化理論和遺傳學的基本知識,遺傳算法簡介,遺傳學基本概念與術語 選擇（selection）：指決定以一定的概率從種群中選擇若干個體的操作 ； 復制（reprod

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

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

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

10、這是一種生物在進化過程中體現的智能，也是人工系統(tǒng)夢寐以求的功能。,生物進化理論和遺傳學的基本知識,遺傳算法簡介,遺傳算法的基本思路,3 遺傳算法的思路與特點,遺傳算法簡介,自組織、自適應和自學習性 在編碼方案、適應度函數及遺傳算子確定后，算法將利用進化過程中獲得的信息自行組織搜索。 本質并行性 內在并行性與內含并行性 不需求導 只需目標函數和適應度函數 概率轉換規(guī)則 強調概率轉換規(guī)則，而不是確定的轉換規(guī)則,遺傳算法的特點,遺傳算法簡介,選擇 適應度計算： 計算結果非負 選擇算法： 兩類 基于適應度比例的 基于適應度排序的,4 遺傳算法的基本操作,遺傳算法簡介,選擇 選擇算法： 輪盤賭選擇（ro

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

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

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

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,遺傳算法簡介,簡單實例 選擇 在01之間產生一個 隨機數：,遺傳算法的基本操作,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,遺傳算法簡介,簡單實例 交叉,遺傳算法的基本操作,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,遺傳算法簡介,簡單實例 變異,遺傳算法的基本操作,遺傳算法簡介,簡單實例 至下一代，適應度

17、計算選擇交叉變異，直至滿足終止條件。,遺傳算法的基本操作,遺傳算法簡介,函數優(yōu)化 是遺傳算法的經典應用領域; 組合優(yōu)化 實踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效; 自動控制 如基于遺傳算法的模糊控制器優(yōu)化設計、基于遺傳算法的參數辨識等;,5 遺傳算法的應用,遺傳算法簡介,機器人智能控制 遺傳算法已經在移動機器人路徑規(guī)劃、關節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學求解、細胞機器人的結構優(yōu)化和行動協(xié)調等; 組合圖像處理和模式識別 目前已在圖像恢復、圖像邊緣持征提取、幾何形狀識別等方面得到了應用;,遺傳算法的應用,遺傳算法簡介,人工生命 基于遺傳算法的進化模型是研究人工生命現象的重要理論基

18、礎，遺傳算法已在其進化模型、學習模型、行為模型等方面顯示了初步的應用能力； 遺傳程序設計 Koza發(fā)展了遺傳程序設計的慨念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結構所進行的遺傳操作自動生成計算機程序;,遺傳算法的應用,2 基本遺傳算法,問題的提出 一元函數求最大值：,1 簡單函數優(yōu)化的實例,基本遺傳算法,問題的提出 用微分法求取f(x)的最大值： 解有無窮多個：,簡單函數優(yōu)化的實例,基本遺傳算法,問題的提出 當i為奇數時xi對應局部極大值點，i為偶數時xi對應局部極小值。x19即為區(qū)間-1,2內的最大值點： 此時，函數最大值f(x19)比f(1.85)=3.85稍大。,簡單函

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

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

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

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

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

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

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

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

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

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

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

30、2 123 4 34,子個體1 123 4 5 子個體2 12 4 34,基本遺傳算法,實值重組 中間重組 子個體父個體1（父個體2父個體1） 是比例因子，由-d,1+d上均勻分布地隨機數產生。 一般取d=0.25。 子代的每個變量均產生一個 。,遺傳操作交叉/基因重組,基本遺傳算法,實值重組 中間重組示例,遺傳操作交叉/基因重組,父個體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,基本遺傳算法,實值重組 中間重組,遺傳操作交叉/基因重組,基本遺傳算法,實值重組 線性重組,遺傳操作交叉/基因重組,父個體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,基本遺傳算法,實值重組 線性重組,遺傳操作交叉/基因重組,基本遺傳算法,二進制交叉 單點交叉,遺傳操作交叉/基因重組,基本遺傳算法,二進制交叉 多點交叉,遺傳操作交叉/基因重組,

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

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

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