遺傳算法及應(yīng)用課件

1、遺傳算法介紹及應(yīng)用引子：智能優(yōu)化算法 智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強、且適合于并行處理的算法。這種算法一般具有嚴密的理論依據(jù)，而不是單純憑借專家經(jīng)驗，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。 常用的智能優(yōu)化算法 （1）遺傳算法 （Genetic Algorithm， 簡稱GA） （2）模擬退火算法（Simulated Annealing， 簡稱SA） （3）禁忌搜索算法（Tabu Search， 簡稱TS） 智能優(yōu)化算法的特點它們的共同特點：都是從任一解出發(fā)，按照某種機制，以一定的概率在整個求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴展到整個問題空

2、間，因而具有全局優(yōu)化性能。遺傳算法起源 遺傳算法是由美國的J. Holland教授于1975年在他的專著自然界和人工系統(tǒng)的適應(yīng)性中首先提出的，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法 。 一、基本遺傳算法概念 基本遺傳算法（Simple Genetic Algorithms，簡稱SGA，又稱簡單遺傳算法或標準遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。 基本遺傳算法的組成 （1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運行參數(shù)函數(shù)優(yōu)化示例 求下列一元函數(shù)的最大

3、值：x-1,2 ，求解結(jié)果精確到6位小數(shù)。SGA對于本例的編碼 由于區(qū)間長度為3，求解結(jié)果精確到6位小數(shù)，因此可將自變量定義區(qū)間劃分為3106等份。又因為221 3106 222 ，所以本例的二進制編碼長度至少需要22位，本例的編碼過程實質(zhì)上是將區(qū)間-1，2內(nèi)對應(yīng)的實數(shù)值轉(zhuǎn)化為一個二進制串（b21b20b0）。幾個術(shù)語 1000101110110101000111 表現(xiàn)型：0.637197 編碼解碼個體（染色體）基因 適應(yīng)度函數(shù) 遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設(shè)計應(yīng)結(jié)合求

4、解問題本身的要求而定。 選擇算子 遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。SGA中選擇算子采用輪盤賭選擇方法。 輪盤賭選擇方法的實現(xiàn)步驟（1） 計算群體中所有個體的適應(yīng)度函數(shù)值（需要解碼）；（2） 利用比例選擇算子的公式，計算每個個體被選中遺傳到下一代群體的概率；（3） 采用模擬賭盤操作（即生成0到1之間的隨機數(shù)與每個個體遺傳到下一代群體的概率進行匹配）來確定各個個體是否遺傳到下一代群體中。輪盤賭圖例：交叉算子 所謂

5、交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。 SGA中交叉算子采用單點交叉算子。 單點交叉運算 交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點多點交叉運算基本位變異算子 基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作的某一基因座上的原有基因值為0，則變異操作將其變?yōu)?；反之，若原有基因值為1，則變異操作將其變?yōu)? 。 基本位變異算子的執(zhí)行過程 變異前：000001110000000010000變異后：000001110001000010000變異點SGA的框圖 產(chǎn)生初始群體是否滿足停止準則是輸出結(jié)果并結(jié)束計算個體適應(yīng)度值比例選擇運算單點交叉運算基本位變異運算否產(chǎn)生新一代群體遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化 （2）函數(shù)優(yōu)化 （3）自動控制 （4）生產(chǎn)調(diào)度 （5）圖像處理 （6）機