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

簡(jiǎn)介1995畢業(yè)于東北電力學(xué)院，獲學(xué)士學(xué)位年畢業(yè)于東北電力學(xué)院，獲碩士學(xué)位年畢業(yè)于天津大學(xué)，獲博士學(xué)位年UniveristyofStrathclyde博士后現(xiàn)代智能優(yōu)化算法遺傳算法第1頁當(dāng)代智能優(yōu)化算法遺傳算法禁忌算法蟻群算法粒子群算法細(xì)菌算法混沌算法TSGAACOPSOBCCOA混沌算法DE現(xiàn)代智能優(yōu)化算法遺傳算法第2頁遺傳算法（GeneticAlgorithm,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ì)算中關(guān)鍵技術(shù)之一。

現(xiàn)代智能優(yōu)化算法遺傳算法第3頁GA四個(gè)基本條件1.存在由多個(gè)生物個(gè)體組成種群2.生物個(gè)體之間存在著差異，或全體含有

多樣性3.生物能夠自我繁殖4.不一樣個(gè)體含有不一樣環(huán)境生存能力，含有優(yōu)良基因結(jié)構(gòu)個(gè)體繁殖能力強(qiáng)，反之則弱現(xiàn)代智能優(yōu)化算法遺傳算法第4頁GA--特點(diǎn)遺傳算法以決議變量編碼作為運(yùn)算對(duì)象。傳統(tǒng)優(yōu)化算法往往直接利用決議變量實(shí)際值本身進(jìn)行優(yōu)化計(jì)算，但遺傳算法不是直接以決議變量值，而是以決議變量某種形式編碼為運(yùn)算對(duì)象，從而能夠很方便地引入和應(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ù)，遺傳算法就比較方便?，F(xiàn)代智能優(yōu)化算法遺傳算法第5頁GA--特點(diǎn)遺傳算法同時(shí)進(jìn)行解空間多點(diǎn)搜索。傳統(tǒng)優(yōu)化算法往往從解空間一個(gè)初始點(diǎn)開始搜索，這么輕易陷入局部極值點(diǎn)。遺傳算法進(jìn)行群體搜索，而且在搜索過程中引入遺傳運(yùn)算，使群體又能夠不停進(jìn)化。這些是遺傳算法所特有一個(gè)隱含并行性。遺傳算法使用概率搜索技術(shù)。遺傳算法屬于一個(gè)自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一個(gè)概率方式來進(jìn)行，從而增加了其搜索過程靈活性。實(shí)踐和理論都已證實(shí)了在一定條件下遺傳算法總是以概率1收斂于問題最優(yōu)解。現(xiàn)代智能優(yōu)化算法遺傳算法第6頁達(dá)爾文1858年用自然選擇來解釋物種起源和生物進(jìn)化，其自然選擇學(xué)說包含以下三個(gè)方面1遺傳種瓜得瓜，種豆得豆。生物有了這個(gè)特征，物種才能穩(wěn)定存在；2變異一母生九子，九子各不一樣。變異選擇和積累是生物多樣性根源；3適者生存含有適應(yīng)性變異個(gè)體被保留下來，經(jīng)過一代代生存環(huán)境選擇作用，物種一代代進(jìn)化，演變?yōu)樾挛锓N現(xiàn)代智能優(yōu)化算法遺傳算法第7頁GA基礎(chǔ)術(shù)語染色體（Chromosome）生物細(xì)胞中含有一個(gè)微小絲狀化合物。是遺傳物質(zhì)主要載體，由多個(gè)遺傳基因組成DNA&RNAinthechromosome基因（gene）也稱遺傳因子，DNA或RNA長(zhǎng)鏈中占有一定位置基本單位。生物基因數(shù)量依據(jù)物種不一樣多少不一，從幾個(gè)（病毒）到幾萬個(gè)（動(dòng)物）。現(xiàn)代智能優(yōu)化算法遺傳算法第8頁GA基礎(chǔ)術(shù)語基因座（locus）染色體中基因位置表現(xiàn)型（phenotype）由染色體決定性狀外部表現(xiàn)基因型（genetype）與表現(xiàn)型親密相關(guān)基因組成個(gè)體（individual）指染色體帶有特征實(shí)體種群（population）一定數(shù)量個(gè)體集合現(xiàn)代智能優(yōu)化算法遺傳算法第9頁GA基礎(chǔ)術(shù)語適應(yīng)度（fitness）個(gè)體對(duì)環(huán)境適應(yīng)程度進(jìn)化（evolution）生物逐步適應(yīng)其生存環(huán)境，使得其品質(zhì)不停提升選擇（selection）指決定以一定概率從種群中選擇若干個(gè)體操作。普通而言，選擇過程是一個(gè)基于適應(yīng)度優(yōu)勝劣汰過程復(fù)制（reproduction）細(xì)胞分裂時(shí)，遺傳物質(zhì)DNA經(jīng)過復(fù)制轉(zhuǎn)移到新細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞基因現(xiàn)代智能優(yōu)化算法遺傳算法第10頁GA基礎(chǔ)術(shù)語交叉（crossover）兩個(gè)染色體某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新染色體變異（mutation）在細(xì)胞復(fù)制時(shí)，基因某個(gè)位發(fā)生某種突變，產(chǎn)生新染色體編碼（coding）DNA中遺傳信息按一定方式排列，也可看作從表現(xiàn)型到遺傳型映射解碼（decoding）從遺傳型到表現(xiàn)型映射現(xiàn)代智能優(yōu)化算法遺傳算法第11頁GA三個(gè)基本算子復(fù)制／選擇(Reproduction/Selection)

依據(jù)每一物種適應(yīng)程度來決定其在下一代中應(yīng)被復(fù)制或淘汰個(gè)數(shù)多少輪盤式選擇競(jìng)爭(zhēng)式選擇現(xiàn)代智能優(yōu)化算法遺傳算法第12頁GA三個(gè)基本算子—交叉

交叉式一個(gè)提供個(gè)體間彼此交換信息機(jī)制，交叉過程主要是母代中較優(yōu)良染色體作一些基因交換，預(yù)期產(chǎn)生更優(yōu)良后代。普通常見交叉方式有：

（1）單點(diǎn)交叉(One-pointcrossover)

（2）雙點(diǎn)交叉(Tail-tailcrossover)

（3）均勻交叉現(xiàn)代智能優(yōu)化算法遺傳算法第13頁GA三個(gè)基本算子—變異

經(jīng)過突變方式，使得解能夠跳脫單純交叉產(chǎn)生區(qū)域，進(jìn)而產(chǎn)生新染色體，變異過程主要以隨機(jī)方式，將染色體基因位由0變成1或由1變成0，主要變異方式有：（1）等位基因突變(SimpleMutation)（2）均勻突變(UniformMutation)（3）非均勻突變(Non-UniformMutation)現(xiàn)代智能優(yōu)化算法遺傳算法第14頁GA基本流程依據(jù)問題編碼，并初始化種群計(jì)算群體適應(yīng)度選擇操作交叉操作變異操作滿足收斂條件否N輸出計(jì)算結(jié)果Y現(xiàn)代智能優(yōu)化算法遺傳算法第15頁算例說明—編碼求解問題maxf(x)=x2

[0,31]x取正整數(shù)第一步：編碼采取二進(jìn)制形式我們把變量x編碼為5位長(zhǎng)二進(jìn)制無符號(hào)整數(shù)表示形式00000031111117001111201100現(xiàn)代智能優(yōu)化算法遺傳算法第16頁算例說明—種群生成第二步初始種群生成因?yàn)檫z傳算法群體型操作需要，所認(rèn)為遺傳操作準(zhǔn)備了一個(gè)由若干初始解組成初始群體。這里我們?nèi)∪后w大小為4，即群體由4個(gè)個(gè)體組成，每個(gè)個(gè)體經(jīng)過隨機(jī)初始化產(chǎn)生初始群體也稱為進(jìn)化初始代，即第一代（firstgeneration），初始化后，群體為

01101110000100010011

現(xiàn)代智能優(yōu)化算法遺傳算法第17頁算例說明—適應(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)度值大小時(shí)，首先要解碼，即把基因型個(gè)體變成表現(xiàn)型個(gè)體（即搜索空間解）這里就是二進(jìn)制到十進(jìn)制轉(zhuǎn)換基因型01101110000100010011表現(xiàn)型x

1324819f(x)=x2169

57664361

（適應(yīng)值）現(xiàn)代智能優(yōu)化算法遺傳算法第18頁算例說明—選擇選擇概率

適應(yīng)度總和1170，平均值293利用輪盤賭選擇結(jié)果1201計(jì)算結(jié)果為0.140.490.060.31現(xiàn)代智能優(yōu)化算法遺傳算法第19頁算例說明—選擇初始族群適應(yīng)值E(i)複製個(gè)數(shù)011101960.180.711110005760.522.072100012890.261.04100111490.040.180初始族群01110110001000100111選擇后01110110001000111000現(xiàn)代智能優(yōu)化算法遺傳算法第20頁算例說明—交叉單點(diǎn)交叉為例兩個(gè)染色體1011100111001100假設(shè)交叉點(diǎn)在位置41011|10011100|11001011110011001001現(xiàn)代智能優(yōu)化算法遺傳算法第21頁算例說明—交叉01110110001100010001選擇后結(jié)果配對(duì)情況1和2配對(duì)3和4配對(duì)

01110110001100010001交叉點(diǎn)選擇第一對(duì)位置3，第二對(duì)位置1交叉前

01|110

1100|0

11|000

1000|1交叉后

01000110011111010000現(xiàn)代智能優(yōu)化算法遺傳算法第22頁算例說明—交叉交配池配對(duì)交叉點(diǎn)交叉后xf(x)011102301000864110001311110309001100041110012562510001311000016256

f=1845平均適應(yīng)度值f=461現(xiàn)代智能優(yōu)化算法遺傳算法第23頁算例說明—變異變異基因數(shù)決定基因總數(shù)×變異概率=(4×5)×0.1=2

有兩個(gè)基因?qū)⒈煌蛔冸S機(jī)選取染色體進(jìn)行變異隨機(jī)選取要變異染色體基因位變異目標(biāo)在防止陷入局部最優(yōu)解現(xiàn)代智能優(yōu)化算法遺傳算法第24頁算例說明—變異01000110011111010000假設(shè)變異基因發(fā)生在第一個(gè)染色體第3位和第四個(gè)染色體第二位上變異就是把二進(jìn)制0變成1把1變成0變異前01000110011111010000變異后01100110011111010010現(xiàn)代智能優(yōu)化算法遺傳算法第25頁算例說明—變異變異池是否有變異變異點(diǎn)變異后

ff(x)01000是3011001010011001否3111103090011110否1110012562510000是11001018324

f=1949

平均適應(yīng)度值f=487現(xiàn)代智能優(yōu)化算法遺傳算法第26頁算例說明—進(jìn)化過程進(jìn)化代數(shù)染色體xf(x)

f平均值最正確值1011011100001000100111324819169576

6436111702921920110011001111101001012133018144169900324

15373843031010011001111101101022233024484529900576248962230410101111011111100010

293128419614224756231現(xiàn)代智能優(yōu)化算法遺傳算法第27頁算例說明—終止準(zhǔn)則普通而言，遺傳算法終止條件有以下幾個(gè)：

（1）到達(dá)最大進(jìn)化代數(shù)；

（2）所求解到達(dá)可接收范圍；

（3）連續(xù)幾代最正確解無改變或改變非常微?。?/p>

（4）到達(dá)最大運(yùn)算時(shí)間?，F(xiàn)代智能優(yōu)化算法遺傳算法第28頁遺傳算法--參數(shù)配置種群數(shù)量視詳細(xì)問題和解空間維數(shù)問題越復(fù)雜，維數(shù)越高，種群數(shù)量要求越大遺傳運(yùn)算終止進(jìn)化代數(shù)依據(jù)問題復(fù)雜程度，普通取為100~500交叉率普通選取范圍在0.4~0.99之間變異率普通選取范圍在0.001~0.1之間當(dāng)代普通采取自適應(yīng)改變交叉率和變異率現(xiàn)代智能優(yōu)化算法遺傳算法第29頁遺傳算法—應(yīng)用遺傳算法提供了一個(gè)求解復(fù)雜系統(tǒng)優(yōu)化問題通用框架，它不依賴于問題詳細(xì)領(lǐng)域，對(duì)問題種類有很強(qiáng)魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面列舉一些遺傳算法主要應(yīng)用領(lǐng)域。現(xiàn)代智能優(yōu)化算法遺傳算法第30頁遺傳算法—應(yīng)用組合優(yōu)化：遺傳算法是尋求組合優(yōu)化問題滿意解最正確工具之一，實(shí)踐證實(shí)，遺傳算法對(duì)于組合優(yōu)化問題中NP完全問題非常有效。現(xiàn)代智能優(yōu)化算法遺傳算法第31頁遺傳算法—應(yīng)用生產(chǎn)調(diào)度問題：生產(chǎn)調(diào)度問題在很多情況下所建立起來數(shù)學(xué)模型難以準(zhǔn)確求解，即使經(jīng)過一些簡(jiǎn)化之后能夠進(jìn)行求解也會(huì)因簡(jiǎn)化得太多而使求解結(jié)果與實(shí)際相差太遠(yuǎn)?，F(xiàn)在遺傳算法已經(jīng)成為處理復(fù)雜調(diào)度問題有效工具。現(xiàn)代智能優(yōu)化算法遺傳算法第32頁遺傳算法—應(yīng)用自動(dòng)控制：遺傳算法已經(jīng)在自動(dòng)控制領(lǐng)域中得到了很好應(yīng)用，比如基于遺傳算法含糊控制器優(yōu)化設(shè)計(jì)、基于遺傳算法參數(shù)辨識(shí)、基于遺傳算法含糊控制規(guī)則學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)