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

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

2、SO,BC,COA,,混沌算法,DE,,遺傳算法（Genetic Algorithm, GA），是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。它是由美國Michigan大學的J. Holland教授于1975年首先提出的。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴于梯度信息，尤其適用于處理傳統(tǒng)搜索方法難于解決的復雜和非線性問題，可廣泛用于組合優(yōu)化、機器學習、自適應控制等領域，是21世界有關智能計算

3、中的關鍵技術之一。,GA 四個基本條件,1.存在由多個生物個體組成的種群2.生物個體之間存在著差異，或全體具有 多樣性3.生物能夠自我繁殖4.不同個體具有不同的環(huán)境生存能力，具有優(yōu)良基因結構的個體繁殖能力強，反之則弱,GA -- 特點,遺傳算法以決策變量的編碼作為運算對象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實際值本身進行優(yōu)化計算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運算對象，從而可

4、以很方便地引入和應用遺傳操作算子遺傳算法直接以目標函數(shù)值作為搜索信息。傳統(tǒng)的優(yōu)化算法往往不只需要目標函數(shù)值，還需要目標函數(shù)的導數(shù)等其它信息。這樣對許多目標函數(shù)無法求導或很難求導的函數(shù)，遺傳算法就比較方便。,GA -- 特點,遺傳算法同時進行解空間的多點搜索。傳統(tǒng)的優(yōu)化算法往往從解空間的一個初始點開始搜索，這樣容易陷入局部極值點。遺傳算法進行群體搜索，而且在搜索的過程中引入遺傳運算，使群體又可以不斷進化。這些是遺傳算法所特有的一種隱含

5、并行性。遺傳算法使用概率搜索技術 。遺傳算法屬于一種自適應概率搜索技術，其選擇、交叉、變異等運算都是以一種概率的方式來進行的，從而增加了其搜索過程的靈活性。實踐和理論都已證明了在一定條件下遺傳算法總是以概率1收斂于問題的最優(yōu)解。,達爾文1858年用自然選擇來解釋物種起源和生物的進化，其自然選擇學說包括以下三個方面,1 遺傳 種瓜得瓜，種豆得豆。生物有了這個特征，物種才能穩(wěn)定存在；2 變異 一母生九子，九子各不同。變異

6、的選擇和積累是生物多樣性的根源；3 適者生存 具有適應性變異的個體被保留下來，通過一代代生存環(huán)境的選擇作用，物種一代代進化，演變?yōu)樾碌奈锓N,GA的基礎術語,染色體（Chromosome） 生物細胞中含有的一種微小的絲狀化合物。是遺傳物質(zhì)的主要載體，由多個遺傳基因組成DNA & RNA in the chromosome基因 （gene）也稱遺傳因子，DNA 或RNA長鏈中占有一定位置的基本單位。生物的基因數(shù)量根據(jù)

7、物種不同多少不一，從幾個（病毒）到幾萬個（動物）。,GA的基礎術語,基因座 （locus）染色體中基因的位置表現(xiàn)型 （phenotype）由染色體決定性狀的外部表現(xiàn)基因型 （genetype）與表現(xiàn)型密切相關的基因組成個體（individual）指染色體帶有特征的實體種群（population）一定數(shù)量個體的集合,GA的基礎術語,適應度（fitness）個體對環(huán)境的適應程度進化（evolution）生物逐漸適應其生存環(huán)境，使

8、得其品質(zhì)不斷提高選擇（selection）指決定以一定概率從種群中選擇若干個體的操作。一般而言，選擇的過程是一種基于適應度的優(yōu)勝劣汰的過程復制（reproduction）細胞分裂時，遺傳物質(zhì)DNA通過復制轉移到新的細胞中，新的細胞就繼承了舊細胞的基因,GA的基礎術語,交叉（crossover）兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個新的染色體變異（mutation）在細胞復制時，基因的某個位發(fā)生某種突

9、變，產(chǎn)生新的染色體編碼（coding）DNA中遺傳信息按一定的方式排列，也可看作從表現(xiàn)型到遺傳型的映射解碼（decoding）從遺傳型到表現(xiàn)型的映射,GA的三個基本算子,復制／選擇(Reproduction / Selection) 依據(jù)每一物種的適應程度來決定其在下一代中應被復制或淘汰個數(shù)的多少輪盤式選擇競爭式選擇,GA 三個基本算子—交叉,交叉式一種提供個體間彼此交換信息的機制，交叉過程主要是母代中較優(yōu)良的染色體作某些基因

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

11、均勻突變(Uniform Mutation)（3）非均勻突變(Non-Uniform Mutation),GA的基本流程,根據(jù)問題編碼，并初始化種群,計算群體適應度,選擇操作,交叉操作,變異操作,滿足收斂條件否,,,,,,,N,輸出計算結果,,,Y,算 例 說 明—編碼,求解問題 max f(x) = x2 [0,31] x取正整數(shù)第一步：編碼 采用二進制形式我們把變量x編碼為5位長的二進制無符號整數(shù)表示形式

12、 0 00000 31 11111 7 00111 12 01100,算 例 說 明—種群生成,第二步 初始種群的生成 由于遺傳算法的群體型操作需要，所以為遺傳操作準備了一個由若干初始解組成的初始群體。 這里

13、我們?nèi)∪后w大小為4，即群體由4個個體組成，每個個體通過隨機初始化產(chǎn)生 初始群體也稱為進化的初始代，即第一代 （first generation），初始化后，群體為 01101 11000 01000 10011,算 例 說 明—適應度評價,遺傳算法用評價函數(shù)（適應度函數(shù)值）來評估個體（解）的優(yōu)劣，并作為以后遺傳操作的依據(jù)。這里 我們根據(jù) f(x) = x2 在評價個體適應度值大

14、小時，首先要解碼，即把基因型個體變成表現(xiàn)型個體（即搜索空間的解） 這里就是二進制到十進制的轉換 基因型 01101 11000 01000 10011 表現(xiàn)型 x 13 24 8 19 f(x) = x2 169 576 64

15、361 （適應值）,算 例 說 明—選擇,選擇概率 適應度總和1170，平均值293運用輪盤賭選擇結果 1 2 0 1,,計算結果為 0.14 0.49 0.06 0.31,算 例 說 明—選擇,算 例 說 明—交叉,單點交叉為例兩個染色體 10111001 11001100假設交叉點在位置4 1011|1001 110

16、0|1100 1011 1100 1100 1001,算 例 說 明—交叉,選擇后的結果,配對情況 1 和 2 配對 3 和4 配對 01110 11000 11000 10001交叉點選擇 第一對 位置3，第二對 位置1交叉前 01|110 1100|0 11|000 1000|1交叉后 01 000

17、 1100 1 11 110 1000 0,算 例 說 明—交叉,?f=1845 平均適應度值f=461,算 例 說 明—變異,變異基因數(shù)的決定基因總數(shù)×變異概率 = (4×5)×0.1=2 有兩個基因?qū)⒈煌蛔冸S機選取染色體進行變異隨機選取要變異染色體的基因位變異目的在避免陷入局部最優(yōu)解,算 例 說 明—變異,01000

18、 11001 11110 10000假設變異基因發(fā)生在 第一個染色體的第3位和第四個染色體的第二位上變異就是把二進制的0 變成1 把1 變成0變異前 01000 11001 11110 10000變異后 01100 11001 11110 10010,算 例 說 明—變異,?f=1949 平均適應度值f=487,算 例

19、說 明—進化過程,算 例 說 明—終止準則,一般而言，遺傳算法終止條件有以下幾種：（1）達到最大的進化代數(shù)；（2）所求的解達到可接受的范圍；（3）連續(xù)幾代最佳解無變化或變化非常微?。唬?）達到最大的運算時間。,遺傳算法--參數(shù)配置,種群數(shù)量 視具體問題和解空間的維數(shù) 問題越復雜，維數(shù)越高，種群數(shù)量要求越大遺傳運算的終止進化代數(shù) 根據(jù)問題的復雜程度，一般取為100~500交叉率

20、 一般選取范圍在 0.4~0.99之間 變異率 一般選取范圍在 0.001~0.1之間現(xiàn)代一般采用自適應變化的交叉率和變異率,遺傳算法—應用,遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科。下面列舉一些遺傳算法的主要應用領域。,遺傳算法—應用,組合優(yōu)化：遺傳算法是尋求組合優(yōu)化問題滿意解的最佳工具之一，實踐證明，遺傳算法對

21、于組合優(yōu)化問題中的NP完全問題非常有效。,遺傳算法—應用,生產(chǎn)調(diào)度問題：生產(chǎn)調(diào)度問題在很多情況下所建立起來的數(shù)學模型難以精確求解，即使經(jīng)過一些簡化之后可以進行求解也會因簡化得太多而使求解結果與實際相差太遠?，F(xiàn)在遺傳算法已經(jīng)成為解決復雜調(diào)度問題的有效工具。,遺傳算法—應用,自動控制：遺傳算法已經(jīng)在自動控制領域中得到了很好的應用，例如基于遺傳算法的模糊控制器的優(yōu)化設計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學習、利用遺傳算法進

22、行人工神經(jīng)網(wǎng)絡的結構優(yōu)化設計和權值學習等。,遺傳算法—應用,機器人學：機器人是一類復雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于對人工自適應系統(tǒng)的研究，所以機器人學自然成為遺傳算法的一個重要應用領域。機器學習：基于遺傳算法的機器學習，在很多領域中都得到了應用。例如基于遺傳算法的機器學習可用來調(diào)整人工神經(jīng)網(wǎng)絡的連接權，也可以用于人工神經(jīng)網(wǎng)絡的網(wǎng)絡結構優(yōu)化設計。,遺傳算法—應用,圖象處理：圖像處理是計算機視覺中的一個重要研究領域。

23、在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求，遺傳算法在這些圖像處理中的優(yōu)化計算方面得到了很好的應用。,遺傳算法—應用,人工生命：人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學習能力是人工生命的兩大重要特征。人工生命與遺傳算法有著密切的關系，基于遺傳算法的進化模型是研究人工生命