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

1、現(xiàn)代智能優(yōu)化算法遺傳算法華北電力大學輸配電技術研究所劉自發(fā)2008年2月1a現(xiàn)代智能優(yōu)化算法遺傳算法華北電力大學輸配電技術研究所1a簡 介1995 畢業(yè)于東北電力學院，獲學士學位2000年畢業(yè)于東北電力學院，獲碩士學位2005年畢業(yè)于天津大學，獲博士學位2007年Univeristy of Strathclyde 博士后2a簡 介1995 畢業(yè)于東北電力學院，獲學士學位2a現(xiàn)代智能優(yōu)化算法遺傳算法禁忌算法蟻群算法粒子群算法細菌算法混沌算法TSGAACOPSOBCCOA混沌算法DE3a現(xiàn)代智能優(yōu)化算法遺禁蟻粒細混TSGAACOPSOBCCOA混遺傳算法（Genetic Algorithm, GA

2、），是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它是由美國Michigan大學的J. Holland教授于1975年首先提出的。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息，尤其適用于處理傳統(tǒng)搜索方法難于解決的復雜和非線性問題，可廣泛用于組合優(yōu)化、機器學習、自適應控制等領域，是21世界有關智能計算中的關鍵技術之一。 4a遺傳算法（Genetic Algorithm, GA），是模GA 四個基本條件1.存在由多個生物個體組成的種群2.生物個體之間存在著差異，或全體具有 多樣性3.生物能夠自我繁殖4.不同個體具有不同的環(huán)境生存能力，具有優(yōu)良基因結構的個體繁

3、殖能力強，反之則弱5aGA 四個基本條件1.存在由多個生物個體組成的種群5aGA - 特點遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實際值本身進行優(yōu)化計算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運算對象，從而可以很方便地引入和應用遺傳操作算子遺傳算法直接以目標函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法往往不只需要目標函數(shù)值，還需要目標函數(shù)的導數(shù)等其它信息。這樣對許多目標函數(shù)無法求導或很難求導的函數(shù)，遺傳算法就比較方便。6aGA - 特點遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)GA - 特點遺傳算法同時進行解空間的多點搜索。傳統(tǒng)的優(yōu)化算法往往

4、從解空間的一個初始點開始搜索，這樣容易陷入局部極值點。遺傳算法進行群體搜索，而且在搜索的過程中引入遺傳運算，使群體又可以不斷進化。這些是遺傳算法所特有的一種隱含并行性。遺傳算法使用概率搜索技術 。遺傳算法屬于一種自適應概率搜索技術，其選擇、交叉、變異等運算都是以一種概率的方式來進行的，從而增加了其搜索過程的靈活性。實踐和理論都已證明了在一定條件下遺傳算法總是以概率1收斂于問題的最優(yōu)解。7aGA - 特點遺傳算法同時進行解空間的多點搜索。傳統(tǒng)的優(yōu)達爾文1858年用自然選擇來解釋物種起源和生物的進化，其自然選擇學說包括以下三個方面1 遺傳 種瓜得瓜，種豆得豆。生物有了這個特征，物種才能穩(wěn)定存在；2

5、 變異 一母生九子，九子各不同。變異的選擇和積累是生物多樣性的根源；3 適者生存 具有適應性變異的個體被保留下來，通過一代代生存環(huán)境的選擇作用，物種一代代進化，演變?yōu)樾碌奈锓N8a達爾文1858年用自然選擇來解釋物種起源和生物的進化，其自然GA的基礎術語染色體（Chromosome） 生物細胞中含有的一種微小的絲狀化合物。是遺傳物質(zhì)的主要載體，由多個遺傳基因組成DNA & RNA in the chromosome基因 （gene）也稱遺傳因子，DNA 或RNA長鏈中占有一定位置的基本單位。生物的基因數(shù)量根據(jù)物種不同多少不一，從幾個（病毒）到幾萬個（動物）。9aGA的基礎術語染色體（Chromo

6、some） 生物細胞中含有GA的基礎術語基因座 （locus）染色體中基因的位置表現(xiàn)型 （phenotype）由染色體決定性狀的外部表現(xiàn)基因型 （genetype）與表現(xiàn)型密切相關的基因組成個體（individual）指染色體帶有特征的實體種群（population）一定數(shù)量個體的集合10aGA的基礎術語基因座 （locus）染色體中基因的位置10aGA的基礎術語適應度（fitness）個體對環(huán)境的適應程度進化（evolution）生物逐漸適應其生存環(huán)境，使得其品質(zhì)不斷提高選擇（selection）指決定以一定概率從種群中選擇若干個體的操作。一般而言，選擇的過程是一種基于適應度的優(yōu)勝劣汰的過程

7、復制（reproduction）細胞分裂時，遺傳物質(zhì)DNA通過復制轉(zhuǎn)移到新的細胞中，新的細胞就繼承了舊細胞的基因11aGA的基礎術語適應度（fitness）個體對環(huán)境的適應程度1GA的基礎術語交叉（crossover）兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體變異（mutation）在細胞復制時，基因的某個位發(fā)生某種突變，產(chǎn)生新的染色體編碼（coding）DNA中遺傳信息按一定的方式排列，也可看作從表現(xiàn)型到遺傳型的映射解碼（decoding）從遺傳型到表現(xiàn)型的映射12aGA的基礎術語交叉（crossover）兩個染色體的某一相同GA的三個基本算子復制選擇(

8、Reproduction / Selection) 依據(jù)每一物種的適應程度來決定其在下一代中應被復制或淘汰個數(shù)的多少輪盤式選擇競爭式選擇13aGA的三個基本算子復制選擇(Reproduction / GA 三個基本算子交叉 交叉式一種提供個體間彼此交換信息的機制，交叉過程主要是母代中較優(yōu)良的染色體作某些基因的交換，預期產(chǎn)生更優(yōu)良的后代。一般常見的交叉方式有：（1）單點交叉(One-point crossover)（2）雙點交叉(Tail-tail crossover) （3）均勻交叉14aGA 三個基本算子交叉 交叉式一種提供個體間彼此交換GA 三個基本算子變異 通過突變的方式，使得解可以跳脫

9、單純的交叉產(chǎn)生的區(qū)域，進而產(chǎn)生新的染色體，變異的過程主要以隨機的方式，將染色體的基因位由0變成1或由1變成0，主要的變異方式有：（1）等位基因突變(Simple Mutation)（2）均勻突變(Uniform Mutation)（3）非均勻突變(Non-Uniform Mutation)15aGA 三個基本算子變異 通過突變的方式，使得解可以跳脫GA的基本流程根據(jù)問題編碼，并初始化種群計算群體適應度選擇操作交叉操作變異操作滿足收斂條件否N輸出計算結果Y16aGA的基本流程根據(jù)問題編碼，并初始化種群計算群體適應度選擇操算 例 說 明編碼求解問題 max f(x) = x2 0,31 x取正整數(shù)

10、第一步：編碼 采用二進制形式我們把變量x編碼為5位長的二進制無符號整數(shù)表示形式 0 00000 31 11111 7 00111 12 0110017a算 例 說 明編碼求解問題 max f(x) =算 例 說 明種群生成第二步 初始種群的生成 由于遺傳算法的群體型操作需要，所以為遺傳操作準備了一個由若干初始解組成的初始群體。 這里我們?nèi)∪后w大小為4，即群體由4個個體組成，每個個體通過隨機初始化產(chǎn)生 初始群體也稱為進化的初始代，即第一代 （first generation），初始化后，群體為 01101 11000 01000 10011 18a算 例 說 明種群生成第二步 初始種群的生成18

11、算 例 說 明適應度評價遺傳算法用評價函數(shù)（適應度函數(shù)值）來評估個體（解）的優(yōu)劣，并作為以后遺傳操作的依據(jù)。這里 我們根據(jù) f(x) = x2 在評價個體適應度值大小時，首先要解碼，即把基因型個體變成表現(xiàn)型個體（即搜索空間的解） 這里就是二進制到十進制的轉(zhuǎn)換 基因型 01101 11000 01000 10011 表現(xiàn)型 x 13 24 8 19 f(x) = x2 169 576 64 361 （適應值）19a算 例 說 明適應度評價遺傳算法用評價函數(shù)（適應度函算 例 說 明選擇選擇概率 適應度總和1170，平均值293運用輪盤賭選擇結果 1 2 0 1計算結果為 0.14 0.49 0.0

12、6 0.3120a算 例 說 明選擇選擇概率 計算結果為 20a算 例 說 明選擇初始族群適應值E(i)複製個數(shù)011101960.180.711110005760.522.072100012890.261.04100111490.040.180初始族群01110110001000100111選擇后0111011000100011100021a算 例 說 明選擇初始族群適應值E(i)複製個數(shù)01算 例 說 明交叉單點交叉為例兩個染色體 10111001 11001100假設交叉點在位置4 1011|1001 1100|1100 1011 1100 1100 100122a算 例 說 明交叉單點

13、交叉為例22a算 例 說 明交叉01110110001100010001選擇后的結果配對情況 1 和 2 配對 3 和4 配對 01110 11000 11000 10001交叉點選擇 第一對 位置3，第二對 位置1交叉前 01|110 1100|0 11|000 1000|1交叉后 01 000 1100 1 11 110 1000 023a算 例 說 明交叉01110110001100010算 例 說 明交叉交配池配對交叉點交叉后xf(x)011102301000864110001311110309001100041110012562510001311000016256f=1845 平均適

14、應度值f=46124a算 例 說 明交叉交配池配對交叉點交叉后xf(x)0算 例 說 明變異變異基因數(shù)的決定基因總數(shù)變異概率 = (45)0.1=2 有兩個基因?qū)⒈煌蛔冸S機選取染色體進行變異隨機選取要變異染色體的基因位變異目的在避免陷入局部最優(yōu)解25a算 例 說 明變異變異基因數(shù)的決定25a算 例 說 明變異01000 11001 11110 10000假設變異基因發(fā)生在 第一個染色體的第3位和第四個染色體的第二位上變異就是把二進制的0 變成1 把1 變成0變異前 01000 11001 11110 10000變異后 01100 11001 11110 1001026a算 例 說 明變異010

15、00 11001 算 例 說 明變異變異池是否有變異變異點變異后ff(x)01000是3011001010011001否3111103090011110否1110012562510000是11001018324f=1949 平均適應度值f=48727a算 例 說 明變異變異池是否有變異變異點變異后ff算 例 說 明進化過程進化代數(shù)染色體xf(x)f平均值最佳值101101 11000 01000 1001113 24 8 19169 576 64 361117029219201100 11001 11110 1001012 1330 18144 169900 324 1537384303101

16、00 11001 11110 1101022 2330 24484 529900 576248962230410101 11101 11111 00010 2931 2 841961 422475623128a算 例 說 明進化過程進化代數(shù)染色體xf(x)f平算 例 說 明終止準則一般而言，遺傳算法終止條件有以下幾種：（1）達到最大的進化代數(shù)；（2）所求的解達到可接受的范圍；（3）連續(xù)幾代最佳解無變化或變化非常微小；（4）達到最大的運算時間。29a算 例 說 明終止準則一般而言，遺傳算法終止條件有以遺傳算法-參數(shù)配置種群數(shù)量 視具體問題和解空間的維數(shù) 問題越復雜，維數(shù)越高，種群數(shù)量要求越大遺傳

17、運算的終止進化代數(shù) 根據(jù)問題的復雜程度，一般取為100500交叉率 一般選取范圍在 0.40.99之間 變異率 一般選取范圍在 0.0010.1之間現(xiàn)代一般采用自適應變化的交叉率和變異率30a遺傳算法-參數(shù)配置種群數(shù)量30a遺傳算法應用遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面列舉一些遺傳算法的主要應用領域。31a遺傳算法應用遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框遺傳算法應用組合優(yōu)化：遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實踐證明，遺傳算法對于組合優(yōu)化問題中的NP完全問題非常有效。32a

18、遺傳算法應用組合優(yōu)化：遺傳算法是尋求組合優(yōu)化問題滿意解的最遺傳算法應用生產(chǎn)調(diào)度問題：生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解也會因簡化得太多而使求解結果與實際相差太遠。現(xiàn)在遺傳算法已經(jīng)成為解決復雜調(diào)度問題的有效工具。33a遺傳算法應用生產(chǎn)調(diào)度問題：生產(chǎn)調(diào)度問題在很多情況下所建立起遺傳算法應用自動控制：遺傳算法已經(jīng)在自動控制領域中得到了很好的應用，例如基于遺傳算法的模糊控制器的優(yōu)化設計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進行人工神經(jīng)網(wǎng)絡的結構優(yōu)化設計和權值學習等。34a遺傳算法應用自動控制：遺傳算法已經(jīng)在自動控制領域中得到了很遺傳算法應用機器人學：機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應系統(tǒng)的研究，所以機器人學自然成為遺傳算法的一個重要應用領域。機器學習：基于遺傳算法的機器學