有關(guān)于遺傳算法的教程課件

1、遺傳算法與模擬退火算法杭州電子科技大學(xué) 數(shù)學(xué)教研室杭州電子科技大學(xué) 沈 灝二00八年八月任務(wù)一. 讀閱讀模型3，案例39： 血管的三維重建報告日：8月22日下午1：30負(fù)責(zé)老師：陳建蘭，劉建貞任務(wù)二. 寫一篇集訓(xùn)心得（簡明扼要），內(nèi)容：本人集訓(xùn)體會（真實體會，不要寫套話）本人在集訓(xùn)中做了哪些工作另兩名隊友各自做了哪些工作本隊合作實際情況是否希望參加全國競賽。集訓(xùn)心得8月27日12：00之前發(fā)到：集訓(xùn)心得紙質(zhì)材料8月28日一早交給裘哲勇老師。暑期集訓(xùn)結(jié)束前不重新組隊。希望重新組隊同學(xué)說明如果留在原來的隊里是否仍愿意參加全國競賽。遺傳算法（genetic algorithm）遺傳算法是一種全局搜索

2、優(yōu)化算法，特點是仿生物進化過程，使遺傳算子作用于群體P(t)，得到新群體P(t+1)。遺傳算子的基本運算有：個體P(t)選擇運算交叉運算變異運算群體P(t+1)解碼解集合個體評價遺傳算法流程圖算法步驟Step1 初始化。設(shè)置進化代數(shù)計數(shù)器t=0,設(shè)置最大進化代數(shù)T，隨機生成M個個體作為初始群體P(0).Step2 個體評價。計算P(t)中各個體的適應(yīng)度。Step3 選擇運算。將選擇算子作用于群體。Step4 交叉運算。將交叉算子作用于群體。Step5 變異運算。 將變異算子作用于群體。群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體P(t+1).Step6 t=T?是則輸出整個進化過程中

3、具有最大適應(yīng)度的個體作為最優(yōu)解，否則t:=t+1,返回step2.運算過程1. 個體編碼：采用6位無符號二進制整數(shù)，如X=101110表示x=(5,6)。2. 取群體規(guī)模M=4.隨機產(chǎn)生初始群體。3.適應(yīng)度計算。適應(yīng)度大小用來評定個體優(yōu)劣程度，從而決定染色體遺傳機會大小。初始數(shù)據(jù)染色體編號 初始群體P(0) x1 x2 f(x1,x2) 011101 3 5 34 0.242 101011 5 3 34 0.24 3 011100 3 4 25 0.174 111001 7 1 50 0.354.選擇運算。按照“適者生存”原則進行選擇。如本題可采用對第i個個體，以 的概率將其選擇出來進行交叉和

4、變異運算。這樣函數(shù)值越大的染色體被選中的機會也越大。具體操作可以采用輪盤賭的方法。5.交叉運算方法：以某個概率交換兩個個體之間的部分染色體。本題采用單點交叉：染色體隨機配對后，隨機設(shè)置一個交叉點位置d（d表示交叉點設(shè)置在該基因座之后），再相互交換配對染色體之間的部分基因。交叉與變異選擇結(jié)果 配對 交叉點位置 交叉結(jié)果 變異點 變異結(jié)果011101 1-2 2 011001 4 011101111001 111101 5 111111 101011 3-4 4 101001 2 111001111001 111011 6 111000 解碼子代群體P(1) x1 x2 fi(x1,x2) fi/

5、fj011101 3 5 34 0.14111111 7 7 98 0.42 111001 7 1 50 0.21111010 7 2 53 0.23 遺傳算法與梯度法及牛頓法等比較主要差異1. 上升法只有一個初始點，由決策者給出；遺傳算法有一群初始點，隨機產(chǎn)生。2. 上升算法產(chǎn)生一個方向，根據(jù)這個方向求最佳或合適的步長，然后產(chǎn)生一個新的搜索點。遺傳算法經(jīng)過選擇、遺傳、變異產(chǎn)生下一代種群。上升算法搜索方向明確，對同一個初始點，搜索過程是確定的，迭代點的目標(biāo)值越來越好；遺傳算法是不確定的，但容易操作，可以計算一些性態(tài)比較復(fù)雜的函數(shù)。3.上升算法如果收斂到一個局部最優(yōu)點，則算法停止，并輸出該點作為

6、最優(yōu)解（上升算法不能判別是否全局最優(yōu)解）。遺傳算法最終輸出的“最優(yōu)解”由進化代數(shù)所決定，它是所有進化群體中的最優(yōu)解，遺傳算法一樣不能判別解的最優(yōu)性，不同的是，遺傳算法不會陷入局部最優(yōu)點后不動。4. 上升算法的局部搜索能力比遺傳算法強。手工模擬示例2可行域本題目標(biāo)函數(shù)與可行域邊界均為非線性，用傳統(tǒng)的上升法搜索步長的計算較困難。本例用遺傳算法時，取群體規(guī)模M=30，隨機生成30個初始可行解（染色體取為十進制浮點數(shù)）v1，v2，v30；適應(yīng)度可取為目標(biāo)函數(shù)值f(v1),f(v2),f(v30)。例如，其中v7是最好的染色體，此次進化中保留v7，令v0=v7。再將v1,v30按適應(yīng)度從大到小的順序排成

7、V1,V2,V30。計算累計概率0q1q2 q3 q4旋轉(zhuǎn)賭輪30次：由計算機在區(qū)間0，q30上產(chǎn)生隨機數(shù)，如第一個隨機數(shù)為0.0328，它介于q0和q1之間，則取v1為新種群一名成員，第二個隨機數(shù)為0.1284，介于q2和q3之間，就取v3為新種群成員,經(jīng)過30次選擇，得到大小為30的新種群（可以有相同的染色體）：交叉：取交叉概率p1=20%從區(qū)間0,1產(chǎn)生隨機數(shù)，設(shè)第一個隨機數(shù)為0.6437，大于0.2，v1”未被選中，設(shè)第二個隨機數(shù)為0.1256，小于0.2，則v2”被選中，共進行30次這樣的操作（被選中染色體個數(shù)期望值為6個），設(shè)最后選中10個染色體進行交叉操作（如果是奇數(shù)個可以隨機去

8、掉一個），隨機分成5對。采用算術(shù)交叉算子：如染色體v16”和v19”的交叉操作后產(chǎn)生兩個后代：任取0,1區(qū)間隨機數(shù)c交叉后的后代10個加上未參加交叉操作的20個染色體，得到新種群取一變異概率p2，用前面一樣的方法可選擇若干染色體進行變異。如v1被選來變異，先隨機產(chǎn)生一個方向d和隨機數(shù)M，若若上述染色體不可行，則可在區(qū)間0.M中重新隨機產(chǎn)生M1，然后再用M1代替原來的M值，等等。注意事項遺傳算法的選擇、交叉與變異概率不適當(dāng)?shù)脑?，會引起“早熟現(xiàn)象”。遺傳算法局部搜索能力較差，如果中間適當(dāng)穿插局部搜索算法（上升法，模擬退火算法等），可以提高算法質(zhì)量個體P(t)選擇運算交叉運算變異運算群體P(t+1)

9、解碼解集合個體評價局部搜索局部最優(yōu)解集合編碼變換 模擬退火算法(Simulated Annealing )原理：模仿金屬熱處理過程算法要素：1. 搜索空間，也稱狀態(tài)空間，一個狀態(tài)代表一個可行解。2.能量函數(shù)E(x)。3.狀態(tài)轉(zhuǎn)移規(guī)則：從一個狀態(tài)xold到另一個狀態(tài)xnew的轉(zhuǎn)移概率，與當(dāng)前溫度參數(shù)T有關(guān)。4.冷卻進度表T(t)經(jīng)典降溫方式快速降溫方式常用算式還有：K為略小于1的系數(shù)系統(tǒng)由狀態(tài)xold變?yōu)閤new的接受概率可按照以下Meteopolis規(guī)則確定：ABC如果搜索陷入局部最優(yōu)點A，若要使搜索脫離這個局部最優(yōu)點達(dá)到C，則必須使系統(tǒng)至少具有B點所對應(yīng)的能量。溫度T減小時接受概率也隨之減小，最后系統(tǒng)收斂于某一能量最小的狀態(tài)，該狀態(tài)可視作目標(biāo)函數(shù)的全局最小值。模擬退火算法計算步驟Step1 隨機產(chǎn)生一個初始點，計算目標(biāo)函數(shù)值。Step2 設(shè)置初始溫度：=T0.Step3 設(shè)置循環(huán)計數(shù)器初始值t：=1Step4 對當(dāng)前最優(yōu)點作一隨機變動，產(chǎn)生一新的最優(yōu)點，計算新的目標(biāo)函數(shù)值，計算能量函數(shù)值增量Step5 如果0則接受新產(chǎn)生的最優(yōu)點為當(dāng)前最優(yōu)點，否則以概率p=exp(-/)接受該點為當(dāng)前最優(yōu)點。Step6 如果t終止步數(shù)則t:=t+1轉(zhuǎn)step4.Step7 如果未達(dá)到冷