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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、361 （適應(yīng)值）,算 例 說 明—選擇,選擇概率 適應(yīng)度總和1170，平均值293運(yùn)用輪盤賭選擇結(jié)果 1 2 0 1,,計(jì)算結(jié)果為 0.14 0.49 0.06 0.31,算 例 說 明—選擇,算 例 說 明—交叉,單點(diǎn)交叉為例兩個(gè)染色體 10111001 11001100假設(shè)交叉點(diǎn)在位置4 1011|1001 110

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

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

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

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

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

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

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

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