第四章遺傳算法第1頁，共37頁，2023年，2月20日，星期三教學(xué)重點(diǎn)掌握遺傳算法的二進(jìn)制編碼掌握遺傳算法的適應(yīng)度函數(shù)設(shè)計(jì)掌握遺傳算法的三個遺傳算子教學(xué)難點(diǎn)遺傳算法的三個遺傳算子第2頁，共37頁，2023年，2月20日，星期三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è)計(jì)與實(shí)現(xiàn)

4.2.8模式定理智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年第3頁，共37頁，2023年，2月20日，星期三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)用智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院2013年第4頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年產(chǎn)生早在50年代，一些生物學(xué)家開始研究運(yùn)用數(shù)字計(jì)算機(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è)計(jì)有限態(tài)自動機(jī)時提出進(jìn)化規(guī)劃的思想。1966年Fogel等出版了《基于模擬進(jìn)化的人工智能》，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想。4.1.1遺傳算法的產(chǎn)生與發(fā)展

第5頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

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

第6頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

第7頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

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

第8頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年幾個名詞概念

遺傳算法——進(jìn)化計(jì)算——計(jì)算智能——人工智能4.1.1遺傳算法的產(chǎn)生與發(fā)展

第9頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算華東理工大學(xué)自動化系2007年幾個名詞概念進(jìn)化計(jì)算：4.1.1遺傳算法的產(chǎn)生與發(fā)展

由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)域的研究人員分別獨(dú)立提出的，在相當(dāng)長的時期里相互之間沒有正式溝通。直到90年代，才有所交流。他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，于是提出將這類方法統(tǒng)稱為“進(jìn)化計(jì)算”(EvolutionaryComputation)。第10頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年幾個名詞概念計(jì)算智能：4.1.1遺傳算法的產(chǎn)生與發(fā)展

計(jì)算智能主要包括神經(jīng)計(jì)算、進(jìn)化計(jì)算和模糊計(jì)算等。它們分別從不同的角度模擬人類的智能活動，以使計(jì)算機(jī)具有智能。通常將基于符號處理的傳統(tǒng)人工智能稱為符號智能，以區(qū)別于正在興起的計(jì)算智能。符號智能的特點(diǎn)是以知識為基礎(chǔ)，偏重于邏輯推理，而計(jì)算智能則是以數(shù)據(jù)為基礎(chǔ)，偏重于數(shù)值計(jì)算。第11頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

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

第12頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

第13頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

1111111

1110111第14頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

第15頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年遺傳學(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é)的基本知識

第16頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

第17頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年遺傳學(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é)的基本知識

第18頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年進(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é)的基本知識

第19頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

第20頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年自組織、自適應(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)

第21頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年選擇

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

選擇算法：輪盤賭選擇（roulettewheelselection）4.1.4遺傳算法的基本操作

第22頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年選擇

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

第23頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年交叉或基因重組

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

第24頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年交叉或基因重組

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

第25頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年變異

實(shí)值變異

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

第26頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

0001100000010111100100000001011001110100101010101011100101101001011011110000000110011101000001010011（8）（5）（2）（10）（7）（12）（5）（19）（10）（14）第27頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年簡單實(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.152174第28頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院2013年簡單實(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.000000第29頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

2013年簡單實(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淘汰！淘汰！第30頁，共37頁，2023年，2月20日，星期三00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100114.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

00011000001110010110110000000110011101001010101010111001011010010110111001110100110000000100010100110001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011第31頁，共37頁，2023年，2月20日，星期三4.1遺傳算法簡介

智能優(yōu)化計(jì)算數(shù)學(xué)與統(tǒng)計(jì)學(xué)院

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

00011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001010010011000110000011100101101100000001100111010010101010101110010110100101101111000000011001110100000101001100011110100000010110111100001011010