經(jīng)典算法之遺傳算法課件

遺傳算法

遺傳算法1遺傳算法簡(jiǎn)介

產(chǎn)生早在50年代，一些生物學(xué)家開(kāi)始研究運(yùn)用數(shù)字計(jì)算機(jī)模擬生物的自然遺傳與自然進(jìn)化過(guò)程；1963年，德國(guó)柏林技術(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ī)劃的思想。

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

遺傳算法簡(jiǎn)介產(chǎn)生1.遺傳算法的產(chǎn)生與發(fā)展2遺傳算法簡(jiǎn)介

產(chǎn)生60年代中期，美國(guó)Michigan大學(xué)的J.H.Holland教授提出借鑒生物自然遺傳的基本原理用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；1967年，他的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法(Genetic

Algorithms)”一詞；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，標(biāo)志遺傳算法的誕生。遺傳算法的產(chǎn)生與發(fā)展

遺傳算法簡(jiǎn)介產(chǎn)生遺傳算法的產(chǎn)生與發(fā)展3遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介發(fā)展遺傳算法的產(chǎn)生與發(fā)展4遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介發(fā)展遺傳算法的產(chǎn)生與發(fā)展5遺傳算法簡(jiǎn)介

幾個(gè)名詞概念進(jìn)化計(jì)算：遺傳算法的產(chǎn)生與發(fā)展

由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)域的研究人員分別獨(dú)立提出的，在相當(dāng)長(zhǎng)的時(shí)期里相互之間沒(méi)有正式溝通。直到90年代，才有所交流。他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，于是提出將這類方法統(tǒng)稱為“進(jìn)化計(jì)算”(EvolutionaryComputation)。遺傳算法簡(jiǎn)介幾個(gè)名詞概念遺傳算法的產(chǎn)生與發(fā)展由6遺傳算法簡(jiǎn)介

達(dá)爾文的自然選擇說(shuō)遺傳（heredity）：子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異（variation）：子代與父代，子代不同個(gè)體之間總有差異，是生命多樣性的根源；生存斗爭(zhēng)和適者生存：具有適應(yīng)性變異的個(gè)體被保留，不具適應(yīng)性變異的個(gè)體被淘汰。自然選擇過(guò)程是長(zhǎng)期的、緩慢的、連續(xù)的過(guò)程。2.生物進(jìn)化理論和遺傳學(xué)的基本知識(shí)

遺傳算法簡(jiǎn)介達(dá)爾文的自然選擇說(shuō)2.生物進(jìn)化理論和遺傳學(xué)的7遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介遺傳學(xué)基本概念與術(shù)語(yǔ)生物進(jìn)化理論和遺傳學(xué)的基8遺傳算法簡(jiǎn)介

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

1111111

1110111遺傳算法簡(jiǎn)介遺傳學(xué)基本概念與術(shù)語(yǔ)生物進(jìn)化理論和遺傳學(xué)的基9遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介遺傳學(xué)基本概念與術(shù)語(yǔ)生物進(jìn)化理論和遺傳學(xué)的基10遺傳算法簡(jiǎn)介

遺傳學(xué)基本概念與術(shù)語(yǔ)進(jìn)化（evolution）：生物在其延續(xù)生存的過(guò)程中，逐漸適應(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ì)較少，甚至逐漸滅絕;生物進(jìn)化理論和遺傳學(xué)的基本知識(shí)

遺傳算法簡(jiǎn)介遺傳學(xué)基本概念與術(shù)語(yǔ)生物進(jìn)化理論和遺傳學(xué)的基11遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介遺傳學(xué)基本概念與術(shù)語(yǔ)生物進(jìn)化理論和遺傳學(xué)的基12遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介遺傳學(xué)基本概念與術(shù)語(yǔ)生物進(jìn)化理論和遺傳學(xué)的基13遺傳算法基本概念與術(shù)語(yǔ)個(gè)體（individual）：GA所處理的基本對(duì)象、結(jié)構(gòu)。群體（population）：個(gè)體的集合。位串（bitString）：個(gè)體的表示形式。對(duì)應(yīng)于遺傳學(xué)中的染色體（Chromosome）基因（gene）：位串中的元素，表示不同的特征。對(duì)應(yīng)于生物學(xué)中的遺傳物質(zhì)單位，以

DNA序列形式把遺傳信息譯成編碼。遺傳算法基本概念與術(shù)語(yǔ)14遺傳算法基本概念與術(shù)語(yǔ)位串結(jié)構(gòu)空間（bitStringSpace）：等位基因任意組合構(gòu)成的位串集合，基因操作在位串結(jié)構(gòu)空間進(jìn)行，對(duì)應(yīng)于遺傳學(xué)中的基因型的集合。參數(shù)空間（ParametersSpace）：是位串空間在物理系統(tǒng)中的映射。對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型的集合。適應(yīng)值（fitness）：某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度，或者在環(huán)境壓力下的生存能力，取決于遺傳特性。復(fù)制、選擇（reproductionorselection）：在有限資源空間上的排他性競(jìng)爭(zhēng)。逆轉(zhuǎn)或倒位（inversion）：反轉(zhuǎn)位串上的一段基因的排列順序。對(duì)應(yīng)于染色體上的一部分，在脫離之后反轉(zhuǎn)180o再連接起來(lái)。遺傳算法基本概念與術(shù)語(yǔ)15遺傳算法簡(jiǎn)介

進(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)化過(guò)程中體現(xiàn)的智能，也是人工系統(tǒng)夢(mèng)寐以求的功能。生物進(jìn)化理論和遺傳學(xué)的基本知識(shí)

遺傳算法簡(jiǎn)介進(jìn)化論與遺傳學(xué)的融合生物進(jìn)化理論和遺傳學(xué)的基16遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介遺傳算法的基本思路3遺傳算法的思路與特點(diǎn)17遺傳算法簡(jiǎn)介

自組織、自適應(yīng)和自學(xué)習(xí)性在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過(guò)程中獲得的信息自行組織搜索。本質(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)

遺傳算法簡(jiǎn)介自組織、自適應(yīng)和自學(xué)習(xí)性遺傳算法的特點(diǎn)18遺傳算法簡(jiǎn)介

選擇

適應(yīng)度計(jì)算：計(jì)算結(jié)果非負(fù)

選擇算法：兩類基于適應(yīng)度比例的基于適應(yīng)度排序的4遺傳算法的基本操作

遺傳算法簡(jiǎn)介選擇4遺傳算法的基本操作19遺傳算法簡(jiǎn)介

選擇

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

遺傳算法簡(jiǎn)介選擇遺傳算法的基本操作20遺傳算法簡(jiǎn)介

交叉或基因重組

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

遺傳算法簡(jiǎn)介交叉或基因重組遺傳算法的基本操作21遺傳算法簡(jiǎn)介

交叉或基因重組

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

遺傳算法簡(jiǎn)介交叉或基因重組遺傳算法的基本操作22遺傳算法簡(jiǎn)介

變異

實(shí)值變異

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

遺傳算法簡(jiǎn)介變異遺傳算法的基本操作23遺傳算法簡(jiǎn)介

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

0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）遺傳算法簡(jiǎn)介簡(jiǎn)單實(shí)例遺傳算法的基本操作000110024遺傳算法簡(jiǎn)介

簡(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.152174遺傳算法簡(jiǎn)介簡(jiǎn)單實(shí)例遺傳算法的基本操作個(gè)體染色體適應(yīng)25遺傳算法簡(jiǎn)介

簡(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.000000遺傳算法簡(jiǎn)介簡(jiǎn)單實(shí)例遺傳算法的基本操作個(gè)體染色體適應(yīng)26遺傳算法簡(jiǎn)介

簡(jiǎn)單實(shí)例選擇在0～1之間產(chǎn)生一個(gè)隨機(jī)數(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淘汰！淘汰！遺傳算法簡(jiǎn)介簡(jiǎn)單實(shí)例遺傳算法的基本操作個(gè)體染色體適應(yīng)270001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011遺傳算法簡(jiǎn)介

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

00011000001110010110110000000110011101001010101010111001011010010110111001110100110000000100010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011000110000011100101101128遺傳算法簡(jiǎn)介

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

0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010010101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011遺傳算法簡(jiǎn)介簡(jiǎn)單實(shí)例遺傳算法的基本操作000110029遺傳算法簡(jiǎn)介

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

遺傳算法簡(jiǎn)介簡(jiǎn)單實(shí)例遺傳算法的基本操作30遺傳算法簡(jiǎn)介

函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域;組合優(yōu)化實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問(wèn)題非常有效;自動(dòng)控制如基于遺傳算法的模糊控制器優(yōu)化設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)等;5遺傳算法的應(yīng)用

遺傳算法簡(jiǎn)介函數(shù)優(yōu)化5遺傳算法的應(yīng)用31遺傳算法簡(jiǎn)介

機(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)用;遺傳算法的應(yīng)用

遺傳算法簡(jiǎn)介機(jī)器人智能控制遺傳算法的應(yīng)用32遺傳算法簡(jiǎn)介

人工生命基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力；遺傳程序設(shè)計(jì)

Koza發(fā)展了遺傳程序設(shè)計(jì)的慨念，他使用了以LISP語(yǔ)言所表示的編碼方法，基于對(duì)一種樹(shù)型結(jié)構(gòu)所進(jìn)行的遺傳操作自動(dòng)生成計(jì)算機(jī)程序;遺傳算法的應(yīng)用

遺傳算法簡(jiǎn)介人工生命遺傳算法的應(yīng)用332基本遺傳算法

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

2基本遺傳算法問(wèn)題的提出1簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例34基本遺傳算法

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

基本遺傳算法問(wèn)題的提出簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例35基本遺傳算法

問(wèn)題的提出當(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(wàn)(1.85)=3.85稍大。簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

基本遺傳算法問(wèn)題的提出簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例36基本遺傳算法

編碼表現(xiàn)型：x

基因型：二進(jìn)制編碼（串長(zhǎng)取決于求解精度）

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

基本遺傳算法編碼簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例37基本遺傳算法

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

基本遺傳算法產(chǎn)生初始種群簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例38基本遺傳算法

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

基本遺傳算法計(jì)算適應(yīng)度簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例39基本遺傳算法

計(jì)算適應(yīng)度（簡(jiǎn)單函數(shù)值替換）

二進(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ù)：簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

(0000000000000000000000)→-1(1111111111111111111111)→2基本遺傳算法計(jì)算適應(yīng)度（簡(jiǎn)單函數(shù)值替換）簡(jiǎn)單函數(shù)優(yōu)化的實(shí)40基本遺傳算法

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

基本遺傳算法遺傳操作簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例41基本遺傳算法

模擬結(jié)果

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

得到的最佳個(gè)體：

smax=<1111001100111011111100>;xmax=1.8506;f(xmax)=3.8503;簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例

基本遺傳算法模擬結(jié)果簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例42基本遺傳算法

模擬結(jié)果

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

世代數(shù)自變量適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503基本遺傳算法模擬結(jié)果簡(jiǎn)單函數(shù)優(yōu)化的實(shí)例世代數(shù)自變量適43基本遺傳算法

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

基本遺傳算法編碼原則2遺傳基因型44基本遺傳算法

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

基本遺傳算法多種編碼方式遺傳基因型45基本遺傳算法

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

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

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

基本遺傳算法適應(yīng)度函數(shù)的重要性3適應(yīng)度函數(shù)及其尺度變47基本遺傳算法

幾種常見(jiàn)的適應(yīng)度函數(shù)直接轉(zhuǎn)換若目標(biāo)函數(shù)為最大化問(wèn)題：Fit(f(x))=f(x)

若目標(biāo)函數(shù)為最小化問(wèn)題：Fit(f(x))=-f(x)適應(yīng)度函數(shù)及其尺度變換

基本遺傳算法幾種常見(jiàn)的適應(yīng)度函數(shù)適應(yīng)度函數(shù)及其尺度變換48基本遺傳算法

幾種常見(jiàn)的適應(yīng)度函數(shù)界限構(gòu)造法1

若目標(biāo)函數(shù)為最大化問(wèn)題：若目標(biāo)函數(shù)為最小化問(wèn)題：適應(yīng)度函數(shù)及其尺度變換

基本遺傳算法幾種常見(jiàn)的適應(yīng)度函數(shù)適應(yīng)度函數(shù)及其尺度變換49基本遺傳算法

幾種常見(jiàn)的適應(yīng)度函數(shù)界限構(gòu)造法2

若目標(biāo)函數(shù)為最大化問(wèn)題：若目標(biāo)函數(shù)為最小化問(wèn)題：

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

基本遺傳算法幾種常見(jiàn)的適應(yīng)度函數(shù)適應(yīng)度函數(shù)及其尺度變換50基本遺傳算法

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

基本遺傳算法適應(yīng)度函數(shù)的作用適應(yīng)度函數(shù)及其尺度變換51基本遺傳算法

適應(yīng)度函數(shù)的設(shè)計(jì)單值、連續(xù)、非負(fù)、最大化合理、一致性計(jì)算量小通用性強(qiáng)適應(yīng)度函數(shù)及其尺度變換

基本遺傳算法適應(yīng)度函數(shù)的設(shè)計(jì)適應(yīng)度函數(shù)及其尺度變換52基本遺傳算法

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

f’=α*f+β

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

cmult=1.0~2.0適應(yīng)度函數(shù)及其尺度變換

基本遺傳算法適應(yīng)度函數(shù)的線性變換法適應(yīng)度函數(shù)及其尺度變換53基本遺傳算法

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

f’=fk

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

k基本遺傳算法適應(yīng)度函數(shù)的冪函數(shù)變換法適應(yīng)度函數(shù)及其尺度變54基本遺傳算法

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

f’=e-af

a決定了復(fù)制的強(qiáng)制性，其值越小，復(fù)制的強(qiáng)制性就越趨向于那些具有最大適應(yīng)性的個(gè)體。適應(yīng)度函數(shù)及其尺度變換

α基本遺傳算法適應(yīng)度函數(shù)的指數(shù)變換法適應(yīng)度函數(shù)及其尺度變換55基本遺傳算法

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

基本遺傳算法幾個(gè)概念4遺傳操作——選擇56基本遺傳算法

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

基本遺傳算法幾個(gè)概念遺傳操作——選擇57基本遺傳算法

個(gè)體選擇概率的常用分配方法按比例的適應(yīng)度分配（proportionalfitnessassignment）某個(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.09基本遺傳算法個(gè)體選擇概率的常用分配方法遺傳操作——選擇58基本遺傳算法

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

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

基本遺傳算法個(gè)體選擇概率的常用分配方法遺傳操作——選擇59基本遺傳算法

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

i為個(gè)體序號(hào)，c為排序第一的個(gè)體的選擇概率。遺傳操作——選擇

基本遺傳算法個(gè)體選擇概率的常用分配方法遺傳操作——選擇60基本遺傳算法

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

遺傳操作——選擇

個(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.00基本遺傳算法常用選擇方法遺傳操作——選擇個(gè)體123461基本遺傳算法

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

遺傳操作——選擇

個(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.00設(shè)定n為需要選擇的個(gè)體數(shù)目，等距離選擇個(gè)體，選擇指針的距離為1／n。第一個(gè)指針的位置由[0，l／n]區(qū)間的均勻隨機(jī)數(shù)決定。如圖所示，需要選擇6個(gè)個(gè)體，指針間的距離為l／6＝o.167，第一個(gè)指針的隨機(jī)位置為0.1，按這種選擇方法被選中作為交配集個(gè)體為：1．2，3．4，6，8。

基本遺傳算法常用選擇方法遺傳操作——選擇個(gè)體123462基本遺傳算法

常用選擇方法局部選擇法（localselection）

(1)線形鄰集遺傳操作——選擇

在局部選擇法中，每個(gè)個(gè)體處于一個(gè)約束環(huán)境中，稱為局部鄰域(而其他選擇方法中視整個(gè)種群為個(gè)體之鄰域)，個(gè)體僅與其鄰近個(gè)體產(chǎn)生交互，該鄰域的定義由種群的分布結(jié)構(gòu)給出。鄰域可被當(dāng)作潛在的交配伙伴。首先均勻隨機(jī)地選擇一半交配種群，選擇方法可以是隨機(jī)遍歷方法也可以是截?cái)噙x擇方法，然后對(duì)每個(gè)被選個(gè)體定義其局部鄰域，在鄰域內(nèi)部選擇交配伙伴?；具z傳算法常用選擇方法遺傳操作——選擇在局部選擇法63基本遺傳算法

常用選擇方法局部選擇法（localselection）

(2)兩對(duì)角鄰集遺傳操作——選擇

基本遺傳算法常用選擇方法遺傳操作——選擇64基本遺傳算法

常用選擇方法局部選擇法（localselection）

(2)兩對(duì)角鄰集遺傳操作——選擇

基本遺傳算法常用選擇方法遺傳操作——選擇65基本遺傳算法

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

截?cái)嚅y值1％10％20％40％50％80％選擇強(qiáng)度2.661.761.20.970.80.34基本遺傳算法常用選擇方法遺傳操作——選擇截?cái)嚅y值1％66基本遺傳算法

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

競(jìng)賽規(guī)模12351030選擇強(qiáng)度00.560.851.151.532.04基本遺傳算法常用選擇方法遺傳操作——選擇競(jìng)賽規(guī)模1267基本遺傳算法

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

父?jìng)€(gè)體112

25

5父?jìng)€(gè)體2123

4

34子個(gè)體1123

4

5子個(gè)體212

4

34基本遺傳算法實(shí)值重組5遺傳操作——交叉/基因重組68基本遺傳算法

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

α是比例因子，由[-d,1+d]上均勻分布地隨機(jī)數(shù)產(chǎn)生。一般取d=0.25。子代的每個(gè)變量均產(chǎn)生一個(gè)α

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

基本遺傳算法實(shí)值重組遺傳操作——交叉/基因重組69基本遺傳算法

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

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

父?jìng)€(gè)體112255父?jìng)€(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.5基本遺傳算法實(shí)值重組遺傳操作——交叉/基因重組父?jìng)€(gè)體70基本遺傳算法

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

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

基本遺傳算法實(shí)值重組遺傳操作——交叉/基因重組71基本遺傳算法

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

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

父?jìng)€(gè)體112255父?jìng)€(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.9基本遺傳算法實(shí)值重組遺傳操作——交叉/基因重組父?jìng)€(gè)體72基本遺傳算法

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

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

基本遺傳算法實(shí)值重組遺傳操作——交叉/基因重組73基本遺傳算法

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

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

基本遺傳算法二進(jìn)制交叉遺傳操作——交叉/基因重組74基本遺傳算法

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

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

基本遺傳算法二進(jìn)制交叉遺傳操作——交叉/基因重組75基本遺傳算法

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

6遺傳操作——變異

基本遺傳算法實(shí)值變異6遺傳操作——變異764.2基本遺傳算法

運(yùn)行程序

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

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

運(yùn)行程序

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

基本遺傳算法運(yùn)行程序算法的設(shè)計(jì)與實(shí)現(xiàn)784.2基本遺傳算法

運(yùn)行程序

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

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

運(yùn)行程序

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

4.2基本遺傳算法運(yùn)行程序4.2.7算法803遺傳算法的改進(jìn)

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

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

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

遺傳算法的改進(jìn)改進(jìn)思路1.CHC算法82遺傳算法的改進(jìn)

選擇上一代種群與通過(guò)新的交叉方法產(chǎn)生的個(gè)體群混合起來(lái)，從中按一定概率選擇較優(yōu)的個(gè)體；即使交叉操作產(chǎn)生較劣個(gè)體偏多，由于原種群大多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低；可以更好地保持遺傳多樣性；排序方法，克服比例適應(yīng)度計(jì)算的尺度問(wèn)題。CHC算法

遺傳算法的改進(jìn)選擇CHC算法83遺傳算法的改進(jìn)

交叉均勻交叉的改進(jìn)：當(dāng)兩個(gè)父?jìng)€(gè)體位值相異的位數(shù)為m時(shí)，從中隨機(jī)選取m/2個(gè)位置，實(shí)行父?jìng)€(gè)體位值的交換；顯然，這樣的操作對(duì)模式具有很強(qiáng)的破壞性。確定一閾值，當(dāng)個(gè)體間距離低于該閾值時(shí)，不進(jìn)行交叉操作。進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。CHC算法

遺傳算法的改進(jìn)交叉CHC算法84遺傳算法的改進(jìn)

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

遺傳算法的改進(jìn)變異CHC算法85遺傳算法的改進(jìn)

參數(shù)分析交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性；Pc越大，新個(gè)體產(chǎn)生的速度就越快，但過(guò)大會(huì)使優(yōu)秀個(gè)