現(xiàn)代智能優(yōu)化算法遺傳算法課件

《現(xiàn)代智能優(yōu)化算法遺傳算法課件》由會員分享，可在線閱讀，更多相關(guān)《現(xiàn)代智能優(yōu)化算法遺傳算法課件（40頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,a,*,現(xiàn)代智能優(yōu)化算法遺傳算法,華北電力大學(xué)輸配電技術(shù)研究所,劉自發(fā),2008年2月,1,a,現(xiàn)代智能優(yōu)化算法遺傳算法華北電力大學(xué)輸配電技術(shù)研究所1a,簡 介,1995 畢業(yè)于東北電力學(xué)院，獲學(xué)士學(xué)位,2000年畢業(yè)于東北電力學(xué)院，獲碩士學(xué)位,2005年畢業(yè)于天津大學(xué)，獲博士學(xué)位,2007年Univeristy of Strathclyde 博士后,2,a,簡 介1995 畢業(yè)于東北電力學(xué)院，獲學(xué)士學(xué)位2a,現(xiàn)代智能優(yōu)化算法,遺,傳,算,法,禁,忌,算,法,蟻,群,算,法,粒,子,群,算,法,細(xì),菌,算,法,

2、混,沌,算,法,TS,GA,ACO,PSO,BC,COA,混,沌,算,法,DE,3,a,現(xiàn)代智能優(yōu)化算法遺禁蟻粒細(xì)混TSGAACOPSOBCCOA混,遺傳算法（Genetic Algorithm,GA），是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型。它是由美國Michigan大學(xué)的J.Holland教授于1975年首先提出的。,其主要特點(diǎn)是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息，尤其適用于處理傳統(tǒng)搜索方法難于解決的復(fù)雜和非線性問題，可廣泛用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制等領(lǐng)域，是21世界有關(guān)智能計算中的關(guān)鍵技術(shù)之一。,4,a,遺傳算法（Genetic Alg

3、orithm,GA），是模,GA 四個基本條件,1.,存在由多個生物個體組成的種群,2.,生物個體之間存在著差異，或全體具有,多樣性,3.,生物能夠自我繁殖,4.,不同個體具有不同的環(huán)境生存能力，具有優(yōu)良基因結(jié)構(gòu)的個體繁殖能力強(qiáng)，反之則弱,5,a,GA 四個基本條件1.存在由多個生物個體組成的種群5a,GA -特點(diǎn),遺傳算法以決策變量的編碼作為運(yùn)算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身進(jìn)行優(yōu)化計算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運(yùn)算對象，從而可以很方便地引入和應(yīng)用遺傳操作算子,遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法往往不只需要目標(biāo)

4、函數(shù)值，還需要目標(biāo)函數(shù)的導(dǎo)數(shù)等其它信息。這樣對許多目標(biāo)函數(shù)無法求導(dǎo)或很難求導(dǎo)的函數(shù)，遺傳算法就比較方便。,6,a,GA -特點(diǎn)遺傳算法以決策變量的編碼作為運(yùn)算對象。傳統(tǒng),GA -特點(diǎn),遺傳算法同時進(jìn)行解空間的多點(diǎn)搜索。傳統(tǒng)的優(yōu)化算法往往從解空間的一個初始點(diǎn)開始搜索，這樣容易陷入局部極值點(diǎn)。遺傳算法進(jìn)行群體搜索，而且在搜索的過程中引入遺傳運(yùn)算，使群體又可以不斷進(jìn)化。這些是遺傳算法所特有的一種隱含并行性。,遺傳算法使用概率搜索技術(shù)。遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。實(shí)踐和理論都已證明了在一定條件下遺傳算法總是以概

5、率1收斂于問題的最優(yōu)解。,7,a,GA -特點(diǎn)遺傳算法同時進(jìn)行解空間的多點(diǎn)搜索。傳統(tǒng)的優(yōu),達(dá)爾文1858年用自然選擇來解釋物種起源和生物的進(jìn)化，其自然選擇學(xué)說包括以下三個方面,1 遺傳 種瓜得瓜，種豆得豆。生物有了這個特征，物種才能穩(wěn)定存在；,2 變異 一母生九子，九子各不同。變異的選擇和積累是生物多樣性的根源；,3 適者生存 具有適應(yīng)性變異的個體被保留下來，通過一代代生存環(huán)境的選擇作用，物種一代代進(jìn)化，演變?yōu)樾碌奈锓N,8,a,達(dá)爾文1858年用自然選擇來解釋物種起源和生物的進(jìn)化，其自然,GA的基礎(chǔ)術(shù)語,染色體（Chromosome）生物細(xì)胞中含有的一種微小的絲狀化合物。是遺傳物質(zhì)的主要載體，

6、由多個遺傳基因組成,DNA&RNA in the chromosome,基因 （gene）也稱遺傳因子，DNA 或RNA長鏈中占有一定位置的基本單位。生物的基因數(shù)量根據(jù)物種不同多少不一，從幾個（病毒）到幾萬個（動物）。,9,a,GA的基礎(chǔ)術(shù)語染色體（Chromosome）生物細(xì)胞中含有,GA的基礎(chǔ)術(shù)語,基因座（locus）染色體中基因的位置,表現(xiàn)型（phenotype）由染色體決定性狀的外部表現(xiàn),基因型 （genetype）與表現(xiàn)型密切相關(guān)的基因組成,個體（individual）指染色體帶有特征的實(shí)體,種群（population）一定數(shù)量個體的集合,10,a,GA的基礎(chǔ)術(shù)語基因座（locus）

7、染色體中基因的位置10a,GA的基礎(chǔ)術(shù)語,適應(yīng)度（fitness）個體對環(huán)境的適應(yīng)程度,進(jìn)化（evolution）生物逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷提高,選擇（selection）指決定以一定概率從種群中選擇若干個體的操作。一般而言，選擇的過程是一種基于適應(yīng)度的優(yōu)勝劣汰的過程,復(fù)制（reproduction）細(xì)胞分裂時，遺傳物質(zhì)DNA通過復(fù)制轉(zhuǎn)移到新的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因,11,a,GA的基礎(chǔ)術(shù)語適應(yīng)度（fitness）個體對環(huán)境的適應(yīng)程度1,GA的基礎(chǔ)術(shù)語,交叉（crossover）兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體,變異（m

8、utation）在細(xì)胞復(fù)制時，基因的某個位發(fā)生某種突變，產(chǎn)生新的染色體,編碼（coding）DNA中遺傳信息按一定的方式排列，也可看作從表現(xiàn)型到遺傳型的映射,解碼（decoding）從遺傳型到表現(xiàn)型的映射,12,a,GA的基礎(chǔ)術(shù)語交叉（crossover）兩個染色體的某一相同,GA的三個基本算子,復(fù)制,選擇,(Reproduction/Selection),依據(jù)每一物種的適應(yīng)程度來決定其在下一代中應(yīng)被復(fù)制或淘汰個數(shù)的多少,輪盤式選擇,競爭式選擇,13,a,GA的三個基本算子復(fù)制選擇(Reproduction/,GA 三個基本算子交叉,交叉式一種提供個體間彼此交換信息的機(jī)制，交叉過程主要是母代中

9、較優(yōu)良的染色體作某些基因的交換，預(yù)期產(chǎn)生更優(yōu)良的后代。一般常見的交叉方式有：,（,1,）,單點(diǎn)交叉,(One-point crossover,),（,2,）,雙點(diǎn)交叉,(Tail-tail crossover,),（,3,）均勻交叉,14,a,GA 三個基本算子交叉 交叉式一種提供個體間彼此交換,GA 三個基本算子變異,通過突變的方式，使得解可以跳脫單純的交叉產(chǎn)生的區(qū)域，進(jìn)而產(chǎn)生新的染色體，變異的過程主要以隨機(jī)的方式，將染色體的基因位由0變成1或由1變成0，主要的變異方式有：,（,1,）等位基因突變,(Simple Mutation),（,2,）均勻突變,(Uniform Mutation),

10、（,3,）非均勻突變,(Non-Uniform Mutation),15,a,GA 三個基本算子變異 通過突變的方式，使得解可以跳脫,GA的基本流程,根據(jù)問題編碼，并初始化種群,計算群體適應(yīng)度,選擇操作,交叉操作,變異操作,滿足收斂條件否,N,輸出計算結(jié)果,Y,16,a,GA的基本流程根據(jù)問題編碼，并初始化種群計算群體適應(yīng)度選擇操,算 例 說 明編碼,求解問題,max f(x)=x,2,0,31,x取正整數(shù),第一步：編碼 采用二進(jìn)制形式,我們把變量x編碼為5位長的二進(jìn)制無符號整數(shù)表示形式,0 00000,31 11111,7 00111,12 01100,17,a,算 例 說 明編碼求解問題

11、max f(x)=,算 例 說 明種群生成,第二步 初始種群的生成,由于遺傳算法的群體型操作需要，所以為遺傳操作準(zhǔn)備了一個由若干初始解組成的初始群體。,這里我們?nèi)∪后w大小為4，即群體由4個個體組成，每個個體通過隨機(jī)初始化產(chǎn)生,初始群體也稱為進(jìn)化的初始代，即第一代,（first generation），初始化后，群體為,01101 11000 01000 10011,18,a,算 例 說 明種群生成第二步 初始種群的生成18,算 例 說 明適應(yīng)度評價,遺傳算法用評價函數(shù)（適應(yīng)度函數(shù)值）來評估個體（解）的優(yōu)劣，并作為以后遺傳操作的依據(jù)。這里 我們根據(jù),f(x)=x,2,在評價個體適應(yīng)度值大小時，首

12、先要解碼，即把基因型個體變成表現(xiàn)型個體（即搜索空間的解）,這里就是二進(jìn)制到十進(jìn)制的轉(zhuǎn)換,基因型 01101 11000 01000 10011,表現(xiàn)型,x,13 24 8 19,f(x)=x,2,169,576 64 361,（適應(yīng)值）,19,a,算 例 說 明適應(yīng)度評價遺傳算法用評價函數(shù)（適應(yīng)度函,算 例 說 明選擇,選擇概率,適應(yīng)度總和1170，平均值293,運(yùn)用輪盤賭選擇結(jié)果,1 2 0 1,計算結(jié)果為,0.14 0.49 0.06 0.31,20,a,算 例 說 明選擇選擇概率 計算結(jié)果為 20a,算 例 說 明選擇,初始族群,適應(yīng)值,E(i),複製個數(shù),01110,196,0.18,

13、0.71,1,11000,576,0.52,2.07,2,10001,289,0.26,1.04,1,00111,49,0.04,0.18,0,初始族群,01110,11000,10001,00111,選擇后,01110,11000,10001,11000,21,a,算 例 說 明選擇初始族群適應(yīng)值E(i)複製個數(shù)01,算 例 說 明交叉,單點(diǎn)交叉為例,兩個染色體 10111001 11001100,假設(shè)交叉點(diǎn)在位置4,1011,|,1001,1100,|,1100,1011 1100,1100 1001,22,a,算 例 說 明交叉單點(diǎn)交叉為例22a,算 例 說 明交叉,01110,1100

14、0,11000,10001,選擇后的結(jié)果,配對情況 1 和 2 配對 3 和4 配對,01110 11000 11000 10001,交叉點(diǎn)選擇 第一對 位置3，第二對 位置1,交叉前,0,1,|,110,1100,|,0,11,|,000,1000,|,1,交叉后,01 000 1100 1,11 110 1000 0,23,a,算 例 說 明交叉01110110001100010,算 例 說 明交叉,交配池,配對,交叉點(diǎn),交叉后,x,f(x),01110,2,3,01000,8,64,11000,1,3,11110,30,900,11000,4,1,11001,25,625,10001,3

15、,1,10000,16,256,f=1845 平均適應(yīng)度值f=461,24,a,算 例 說 明交叉交配池配對交叉點(diǎn)交叉后xf(x)0,算 例 說 明變異,變異,基因數(shù)的決定,基因總數(shù)變異概率=(,45)0.1=2,有兩個基因?qū)⒈煌蛔?隨機(jī)選取染色體進(jìn)行變異,隨機(jī)選取要變異染色體的基因位,變異目的在避免陷入局部最優(yōu)解,25,a,算 例 說 明變異變異基因數(shù)的決定25a,算 例 說 明變異,01000 11001 11110 10000,假設(shè)變異基因發(fā)生在 第一個染色體的第3位,和第四個染色體的第二位上,變異就是把二進(jìn)制的0 變成1 把1 變成0,變異前 01,0,00 11001 11110 1

16、00,0,0,變異后 01,1,00 11001 11110 100,1,0,26,a,算 例 說 明變異01000 11001,算 例 說 明變異,變異池,是否有變異,變異點(diǎn),變異后,f,f(x),01000,是,3,01,1,00,10,100,11001,否,3,11110,30,900,11110,否,1,11001,25,625,10000,是,1,100,1,0,18,324,f=1949 平均適應(yīng)度值f=487,27,a,算 例 說 明變異變異池是否有變異變異點(diǎn)變異后ff,算 例 說 明進(jìn)化過程,進(jìn)化代數(shù),染色體,x,f(x),f,平均值,最佳值,1,01101 11000 01000 10011,13 24 8 19,169 576,64 361,1170,292,19,2,01100 11001 11110 10010,12 13,30 18,144 169,900 324,1537,384,30,3,10100 11001 11110 11010,22 23,30 24,484 529,900 576,2489,622,30,4,10101 11101 11111