進(jìn)化計(jì)算及其應(yīng)用ContentPart1

進(jìn)化算法初步介紹Part2

遺傳算法基本理論P(yáng)art3

進(jìn)化策略基本理論P(yáng)art4

進(jìn)化規(guī)劃基本理論P(yáng)art5

遺傳算法應(yīng)用實(shí)例Part1

進(jìn)化算法初步介紹產(chǎn)生背景主要特點(diǎn)理論基礎(chǔ)基本結(jié)構(gòu)分類說明Part1.1產(chǎn)生背景對自身的大腦信息處理機(jī)制進(jìn)行模擬----人工神經(jīng)網(wǎng)絡(luò)理論對自身模糊性的思維方式進(jìn)行類比----模糊系統(tǒng)對自然界中動植物的免疫機(jī)理進(jìn)行模擬----免疫系統(tǒng)對自身進(jìn)化這一更為宏觀的過程學(xué)習(xí)----進(jìn)化算法(EvolutionaryComputation,EC)Part1.1產(chǎn)生背景進(jìn)化算法是一種模擬生物進(jìn)化過程與機(jī)制求解問題的自組織、自適應(yīng)人工智能技術(shù)。優(yōu)勝劣汰，適者生存進(jìn)化規(guī)則繁殖、變異、競爭、選擇指導(dǎo)思想進(jìn)化算法是建立在模擬生物進(jìn)化過程的基礎(chǔ)上而產(chǎn)生的一種隨機(jī)搜索優(yōu)化技術(shù)Part1.2主要特點(diǎn)在算法中主要表現(xiàn)為全局搜索方式，體現(xiàn)在下面幾個方面有指導(dǎo)搜索：依據(jù)是每個個體的適應(yīng)度值自適應(yīng)搜索：通過進(jìn)化操作改進(jìn)群體性能漸進(jìn)式尋優(yōu)：每代進(jìn)化的結(jié)果都優(yōu)異于上一代并行式搜索：對每一代群體所有個體同時進(jìn)行黑箱式結(jié)構(gòu)：只要研究輸入和輸出而不需考慮過程全局最優(yōu)解：在整個搜索區(qū)域的各個部分同時進(jìn)行內(nèi)在學(xué)習(xí)型：學(xué)習(xí)是一種有保留的行為穩(wěn)健性強(qiáng)：不同的條件和環(huán)境下算法適用和有效性Part1.3理論基礎(chǔ)進(jìn)化計(jì)算是模擬生物進(jìn)化理論而形成的一種全局優(yōu)化自適應(yīng)概率搜索的算法理論。具有深厚的生物學(xué)理論基礎(chǔ)：遺傳：父代利用遺傳基因?qū)⒆陨淼幕蛐畔⒔桓督o下一代（子代），屬性特征相同或相近變異：子代和父代，以及子代各個體之間存在著一定的差異，在進(jìn)化過程中是隨機(jī)發(fā)生的生存斗爭和適者生存：適應(yīng)性變異較強(qiáng)的個體被保留下來，而適應(yīng)性變異較弱的個體則被淘汰Part1.4基本結(jié)構(gòu)進(jìn)化計(jì)算作為一門新興學(xué)科，其理論框架結(jié)構(gòu)如下：Part1.4算法框架ProcedureEvolutionProgramBegin:

初始化各個進(jìn)化參數(shù)，并設(shè)置進(jìn)化代數(shù)n=0；生成初始群體P(0)；對初始群體進(jìn)行評價（適應(yīng)度計(jì)算）；

while(不滿足終止條件)do n++;

利用選擇操作從P(n-1)代中選出P(n)代群體； 對P(n)代群體執(zhí)行進(jìn)化操作； 對執(zhí)行完進(jìn)化操作后的群體進(jìn)行評價（適應(yīng)度計(jì)算）；

endEndPart1.5分類說明從進(jìn)化的過程性質(zhì)來進(jìn)行區(qū)分，與進(jìn)化算法相關(guān)的算法可細(xì)分為：遺傳算法：最具代表性也是最基本的進(jìn)化策略：側(cè)重于數(shù)值分析進(jìn)化規(guī)劃：介于數(shù)值分析與人工智能之間遺傳規(guī)劃：偏向以程式表現(xiàn)人工智能行為進(jìn)化動力學(xué)：偏向進(jìn)化的自組織和系統(tǒng)動力學(xué)特性分類系統(tǒng)：適應(yīng)動態(tài)環(huán)境學(xué)習(xí)動態(tài)模擬系統(tǒng)：用以觀察復(fù)雜系統(tǒng)交互元胞自動機(jī)：研究人工生命蟻群系統(tǒng)：模擬螞蟻群體行為Part2遺傳算法基本理論產(chǎn)生背景基本思想基本結(jié)構(gòu)遺傳算子數(shù)學(xué)基礎(chǔ)遺傳規(guī)劃Part2.1產(chǎn)生背景起源于對生物系統(tǒng)進(jìn)行的計(jì)算機(jī)模擬研究，模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程中形成的一種自適應(yīng)優(yōu)化概率搜索算法?；具z傳算法只使用選擇算子、交叉算子和變異算子這三種基本的遺傳算子。Part2.2基本思想潛在解集內(nèi)選擇一組可能解集一定數(shù)目的經(jīng)過基因編碼的個體所組成產(chǎn)生初代種群優(yōu)勝劣汰、適者生存經(jīng)過解碼得到近似最優(yōu)解Part2.3基本結(jié)構(gòu)Part2.3基本結(jié)構(gòu)編碼： 染色體對應(yīng)的是數(shù)據(jù)或數(shù)組，各位置上的值則對應(yīng)為基因。染色體編碼就是用字符串來表達(dá)所需解決的問題。 編碼是進(jìn)行優(yōu)化計(jì)算算法設(shè)計(jì)的重要步驟，很大程度上取決于問題的性質(zhì)和要求，同時也決定了對隨后的遺傳算子的設(shè)計(jì)。Part2.3基本結(jié)構(gòu)編碼方式位串編碼實(shí)數(shù)編碼符號編碼參數(shù)級聯(lián)編碼多參數(shù)交叉編碼二進(jìn)制編碼格雷碼動態(tài)編碼Part2.3基本結(jié)構(gòu)位串編碼：二進(jìn)制編碼優(yōu)點(diǎn)：類似于生物染色體組成，遺傳操作比較容易實(shí)現(xiàn)理論證明，二進(jìn)制編碼所能處理的模式數(shù)目最多缺點(diǎn)存在Hamming懸崖問題算法效率和最優(yōu)解精度的矛盾問題Part2.3基本結(jié)構(gòu)實(shí)數(shù)編碼：每個基因值用一實(shí)數(shù)表示(真值編碼)優(yōu)點(diǎn)：改善遺傳算法的計(jì)算復(fù)雜性，提高算法運(yùn)行效率適合解決搜索范圍較大，區(qū)域內(nèi)較為復(fù)雜的情況便于解決對目標(biāo)函數(shù)有復(fù)雜的約束條件的問題對精度要求較高的問題有較好的解決效果Part2.3基本結(jié)構(gòu)符號編碼：基因值取一無數(shù)值含義、而只有代碼含義的符號集。最適合于解序號排列問題。優(yōu)點(diǎn)：對符號排列問題具有獨(dú)特的求解效果完全符合有意義的積木塊編碼原則Part2.3基本結(jié)構(gòu)初始群體的產(chǎn)生： 在基本遺傳算法中，通常采用隨機(jī)方法來產(chǎn)生初始群體的。個體數(shù)目是預(yù)先定義好的，并且在進(jìn)化的整個過程中固定不變。同時需要滿足約束條件的要求。新個體也必須符合約束條件，否則就被淘汰。Part2.3基本結(jié)構(gòu)適應(yīng)度計(jì)算： 用來衡量字符串性能好壞，同時也決定了該個體被遺傳到下一代群體中的概率大小。通?？梢灾苯訉⒋蟮哪繕?biāo)函數(shù)f(x)定義為遺傳算法的適應(yīng)度函數(shù)。但是它可能出現(xiàn)負(fù)數(shù)，因此需要做個適當(dāng)?shù)淖儞Q稱為標(biāo)準(zhǔn)適應(yīng)度函數(shù)，使得該適應(yīng)度符合進(jìn)化計(jì)算中的某些選擇策略。因此需要滿足以下幾個條件：Part2.3基本結(jié)構(gòu)單值、非負(fù)能夠正確反映問題解領(lǐng)域內(nèi)的解空間分布情況計(jì)算量小要能夠滿足某一具體問題下的不同情況，即具有較強(qiáng)的通用性適應(yīng)度函數(shù)的尺度變換線性變換冪函數(shù)變換指數(shù)尺度變換Part2.3基本結(jié)構(gòu)進(jìn)化操作： 用于遺傳算法中模擬個體遺傳與新個體生成的過程。進(jìn)化操作通常運(yùn)用了幾種基本的進(jìn)化算子，其中選擇算子模擬了生物遺傳的過程，而交叉和變異算子則模擬了新個體生成的過程。Part2.3基本結(jié)構(gòu)終止操作：閾值終止：為所需解定義一個閾值或閾值函數(shù)，當(dāng)某代所得到的最優(yōu)解個體已經(jīng)達(dá)到了此閾值，則終止進(jìn)化過程，并輸出最優(yōu)個體。最大進(jìn)化代數(shù)終止：沒有定義解閾值來對進(jìn)化過程進(jìn)行終止，進(jìn)化完全依靠達(dá)到預(yù)先定義的最大進(jìn)化代數(shù)來終止。Part2.4遺傳算子交叉策略二進(jìn)制編碼的交叉操作實(shí)數(shù)編碼的交叉操作單點(diǎn)交叉雙點(diǎn)交叉均勻交叉離散交叉算術(shù)交叉選擇策略比例選擇最優(yōu)保存策略確定性采樣選擇排序選擇競技選擇輪盤選擇法繁殖池選擇法Boltzmann選擇法變異策略基本位變異均勻變異邊界變異非均勻變異Part2.4遺傳算子選擇算子：通常是通過選擇操作來將優(yōu)良個體進(jìn)行復(fù)制，并插入到下一代的新個體群體中去，參與下一輪的進(jìn)化過程，從而體現(xiàn)“優(yōu)勝劣汰”的進(jìn)化準(zhǔn)則。建立在對個體適應(yīng)度評價的基礎(chǔ)上。其目的是為了避免基因缺失、提高全局收斂性和計(jì)算效率。比例選擇：各個個體被選中的概率與其適應(yīng)度大小成正比。輪盤選擇、繁殖池選擇和Boltzmann選擇法Part2.4遺傳算子輪盤選擇法： 又稱為輪賭選擇法。主要依據(jù)個體被選中的概率取決于該個體的相對適應(yīng)度。式中：指個體i的相對適應(yīng)度，即個體i被選 中的概率； 指個體i的原始適應(yīng)度值； 指群體的累加適應(yīng)度。Part2.4遺傳算子輪盤選擇的詳細(xì)描述過程順序累計(jì)群體內(nèi)各個體的適應(yīng)度，得相應(yīng)的累 計(jì)值，設(shè)群體有n個個體，最后一個累計(jì)值為Sn。在[0，Sn]區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)r。依次用Si與r比較，第一個出現(xiàn)大于或等于r的Si所對應(yīng)的個體i被選為復(fù)制對象。重復(fù)第二步和第三步，直到滿足所需要的復(fù)制個體數(shù)目。Part2.4遺傳算子交叉算子：模擬生物進(jìn)化中染色體之間的交配重組過程。主要指兩個相互配對的染色體按照某種方式來相互交換二者的部分基因，從而形成新的個體。是遺傳算法中產(chǎn)生新個體最主要的方法，也是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征。首先對群體個體進(jìn)行隨機(jī)配對，然后再進(jìn)行交叉。Part2.4遺傳算子交叉算子設(shè)計(jì)的內(nèi)容交叉點(diǎn)位置的確定配對個體之間部分基因交換的方法二進(jìn)制編碼中的操作方法有單點(diǎn)交叉、雙點(diǎn)交叉和均勻交叉。實(shí)數(shù)編碼情況下的交叉操作有離散交叉、算術(shù)交叉。Part2.4遺傳算子單點(diǎn)交叉雙點(diǎn)交叉子代1：01|000子代2：11|101父代1：01|101父代2：11|000交叉點(diǎn)單點(diǎn)交叉子代1：01|000|00110子代2：11|101|10100父代1：01|101|00110父代2：11|000|10100交叉點(diǎn)1雙點(diǎn)交叉交叉點(diǎn)2Part2.4遺傳算子變異算子將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。二進(jìn)制編碼：基因值按照變異概率取反。實(shí)數(shù)編碼：用一個隨機(jī)數(shù)替換原變異位置上的基因值。常用算子：基本位變異、均勻變異、邊界變異和非均勻變異。Part2.4遺傳算子基本位變異：對個體編碼串中以變異概率Pm隨機(jī)指定的某一位或某幾位基因座上的基因值做變異運(yùn)算。只是改變個體編碼串中個別幾個基因座上的基因值，發(fā)生概率小、因此發(fā)揮作用較慢，效果不太明顯。均勻變異：分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的變異概率Pm來替換個體編碼串中各個基因座上的原有基因值。Part2.5數(shù)學(xué)基礎(chǔ)遺傳算法的機(jī)理具有全局搜索和優(yōu)化機(jī)制等屬性。模式定理和積木塊假設(shè)等奠定了遺傳算法的數(shù)學(xué)基礎(chǔ)。遺傳算法收斂性分析。Part2.6遺傳規(guī)劃遺傳算法：采用的是定長的字符串，相當(dāng)于對問題解答的結(jié)構(gòu)和大小的一種預(yù)確定。極大地限制了在人工智能、及其學(xué)習(xí)和符號處理等領(lǐng)域的應(yīng)用。遺傳規(guī)劃：計(jì)算機(jī)程序的結(jié)構(gòu)和大小都是可以變化的。采用層次化的計(jì)算機(jī)程序代替字符串表達(dá)問題，克服了遺傳算法表達(dá)方面的局限性。Part3

進(jìn)化策略基本理論產(chǎn)生背景基本算法構(gòu)成主要特點(diǎn)Part3.1產(chǎn)生背景在做風(fēng)洞實(shí)驗(yàn)時，用傳統(tǒng)的方法很難對參數(shù)變量進(jìn)行優(yōu)化，而采用生物變異的思想來優(yōu)化參數(shù)，卻得到了很好的效果。用模擬自然界生物進(jìn)化概率來解決參數(shù)優(yōu)化問題的進(jìn)化方法----進(jìn)化策略。最初目的是求解多峰值非線性函數(shù)的優(yōu)化問題，發(fā)展到基于各種不同的選擇機(jī)制的多種進(jìn)化策略，并都獲得較好的效果。Part3.2基本算法構(gòu)成個體表示方法Part3.2基本算法構(gòu)成初始群體的產(chǎn)生Part3.2基本算法構(gòu)成適應(yīng)度評價Part3.2基本算法構(gòu)成變異算子Part3.2基本算法構(gòu)成交叉算子Part3.2基本算法構(gòu)成選擇算子Part3.2主要特點(diǎn)相同點(diǎn)：進(jìn)化策略和遺傳算法都是基于生物的“優(yōu)勝劣汰、適者生存”的進(jìn)化原理，并采用了種群群體求解的尋優(yōu)方式。不同點(diǎn)：二者的表達(dá)方式不同二者的選擇操作不同所選擇的進(jìn)化操作不同Part4進(jìn)化規(guī)劃基本理論產(chǎn)生背景基本算法構(gòu)成主要特點(diǎn)三種算法的比較Part4.1產(chǎn)生背景起初，為求解預(yù)測問題而提出了一種有限狀態(tài)機(jī)進(jìn)化模型機(jī)器的狀態(tài)是基于均勻隨機(jī)分布的規(guī)律進(jìn)行變異進(jìn)化規(guī)劃的思想被拓展到實(shí)數(shù)空間，用來求解實(shí)數(shù)空間中的優(yōu)化計(jì)算問題在變異運(yùn)算中引入了正態(tài)分布的技術(shù)

進(jìn)化規(guī)劃演變成一種優(yōu)化搜索的算法，在很多實(shí)際領(lǐng)域中得到廣泛應(yīng)用Part4.2基本算法構(gòu)成個體表示方法適應(yīng)度評價Part4.2基本算法構(gòu)成變異算子與遺傳算法和進(jìn)化策略不同，它是從整體的角度來模擬生物的進(jìn)化過程的。個體的變異操作是唯一的一種最優(yōu)個體搜索方法。Part4.2基本算法構(gòu)成選擇算子Part4.3主要特點(diǎn)著眼于物種的進(jìn)化過程，不適用個體重組方面的操作算子著重于各個個體之間的競爭選擇，當(dāng)數(shù)目較大時，跟進(jìn)化策略中的類似直接以問題的可行解作為個體的表現(xiàn)形式，更便于其的應(yīng)用以n維實(shí)數(shù)空間上的優(yōu)化問題來作為主要的處理對象Part4.4三種算法的比較比較項(xiàng)目遺傳算法進(jìn)化策略進(jìn)化規(guī)劃個體表現(xiàn)形式離散值連續(xù)值連續(xù)值參數(shù)調(diào)整方法無標(biāo)準(zhǔn)偏差、協(xié)方差方差適應(yīng)度評價方法變換目標(biāo)函數(shù)值直接采用目標(biāo)函數(shù)值變換目標(biāo)函數(shù)值個體變異算子輔助搜索方法主要搜索方法唯一搜索方法個體交叉算子主要搜索方法輔助搜索方法不使用選擇算子概率選擇確定性選擇概率選擇Part5

遺傳算法應(yīng)用實(shí)例遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性