遺傳算法GeneticAlgorithm(matlabGAtool用法打印了,和實(shí)驗(yàn)指導(dǎo)書放在一起)

1、遺傳算法GA (Genetic Algorithm)遺傳算法 John Holland 美國(guó)密歇根大學(xué)教授于1970s提出 基本思想：模擬生物群體的進(jìn)化(自然選擇natural selection、適者生存survival of the fittest) 和優(yōu)化問題的基本聯(lián)系：生物進(jìn)化和遺傳算法的對(duì)應(yīng)關(guān)系生物學(xué)中的概念生物學(xué)中的概念遺傳算法遺傳算法適者生存適者生存在算法停止時(shí)，最優(yōu)目標(biāo)函數(shù)值的解在算法停止時(shí)，最優(yōu)目標(biāo)函數(shù)值的解有最大的可能性保留下來(lái)有最大的可能性保留下來(lái)個(gè)體個(gè)體individual解解染色體染色體chromosome解的編碼（字符串、向量等）解的編碼（字符串、向量等）基因基因g

2、ene編碼位或分量編碼位或分量適應(yīng)性適應(yīng)性fitness適應(yīng)度函數(shù)的值適應(yīng)度函數(shù)的值群體群體population(種群種群) 選定的一組解選定的一組解(其中解的個(gè)數(shù)為群體的規(guī)模其中解的個(gè)數(shù)為群體的規(guī)模)(自然自然)選擇選擇根據(jù)適應(yīng)度函數(shù)選取的一組解根據(jù)適應(yīng)度函數(shù)選取的一組解交配交配crossover通過交配操作產(chǎn)生的一組新解的過程通過交配操作產(chǎn)生的一組新解的過程變異變異mutation編碼的某一位或分量發(fā)生變化的過程編碼的某一位或分量發(fā)生變化的過程最后三個(gè)在遺傳算法中稱為最后三個(gè)在遺傳算法中稱為遺傳操作遺傳操作求解優(yōu)化問題 最大化 目標(biāo)函數(shù) 也可以有約束。 可行解。遺傳算法的基本步驟選擇一個(gè)

3、問題的解的編碼編碼方案產(chǎn)生一個(gè)有N個(gè)染色體的初始群體初始群體對(duì)群體中的每一個(gè)染色體計(jì)算其適應(yīng)度計(jì)算其適應(yīng)度(目標(biāo)函數(shù)值目標(biāo)函數(shù)值)在當(dāng)代群體上重復(fù)如下步驟，直至停止條件滿足。 選擇選擇：根據(jù)染色體的適應(yīng)度，按一個(gè)規(guī)則從當(dāng)前群體中選擇一些個(gè)體組成一個(gè)新群體(配對(duì)庫(kù))在該群體上，通過交配操作交配操作產(chǎn)生后代。在該群體上，通過變異操作變異操作產(chǎn)生后代。這時(shí)已得到下一代群體。計(jì)算新一代群體中各個(gè)染色體的適應(yīng)度。簡(jiǎn)單遺傳算法選擇問題的解的編碼為二進(jìn)制編碼二進(jìn)制編碼隨機(jī)隨機(jī)產(chǎn)生一個(gè)有N個(gè)染色體的初始群體，迭代時(shí)迭代時(shí)N不改變不改變對(duì)群體中的每一個(gè)染色體計(jì)算其適應(yīng)度 / 目標(biāo)函數(shù)值在當(dāng)代群體上重復(fù)如下步驟，

4、直至停止條件滿足。 比例比例選擇：從當(dāng)代群體中選擇一些個(gè)體組成新群體， 每個(gè)個(gè)體被選中的概率與其適應(yīng)度成比例。比例選擇比例選擇也叫輪盤賭，一個(gè)個(gè)體可能被選中多次。也叫輪盤賭，一個(gè)個(gè)體可能被選中多次。在該群體上，通過交配操作產(chǎn)生后代。/ 一對(duì)染色體一對(duì)染色體,單點(diǎn)交叉單點(diǎn)交叉(pc經(jīng)常經(jīng)常=0.6-1.0)在該群體上，通過變異操作產(chǎn)生后代。/ 每個(gè)編碼位每個(gè)編碼位是等概率變異的，小概率變異是等概率變異的，小概率變異(pm經(jīng)常經(jīng)常=0.01 - 0.1)這時(shí)已得到全新的群體。計(jì)算在新群體中各個(gè)染色體的適應(yīng)度。例子 max f(x)=x2, 0 x 31, x為整數(shù)。（迭代1步）例子：TSP TSP

5、(Traveling Salesman Problem) 旅行商或貨郎擔(dān)問題： 設(shè)有n個(gè)城市，貨郎擔(dān)從其中的一個(gè)城市出發(fā)，每個(gè)城市必須訪問一次、而且只能訪問一次，最終回到開始的城市。兩個(gè)城市之間的旅費(fèi)是已知的，他應(yīng)該選擇什么樣的路線才能使花費(fèi)達(dá)到最??？GA求解：設(shè)有10個(gè)城市：A,B,C,D,E,F,G,H,I,J 解的編碼：城市的一個(gè)排列（二進(jìn)制位串不行） 初始種群：隨機(jī)生成排列 交叉操作：原來(lái)的也不適用（解會(huì)變的不可行，可行解要求排列中每個(gè)城市都出現(xiàn)且只出現(xiàn)一次）。兩個(gè)旅程： J H D E F I G C B A 旅程1 H G E B C J I A D F 旅程2部分匹配交叉部分匹配

6、交叉(PMX)：取兩個(gè)截點(diǎn)：如DE間，IG間： 旅程1 J H D B C J G C B A I H D B C J G F E A 旅程1 旅程2 H G E E F I I A D F H G B E F I J A D C 旅程2中間部分交換，外圍部分中重復(fù)的城市用旅程之間對(duì)應(yīng)的替換中間部分交換，外圍部分中重復(fù)的城市用旅程之間對(duì)應(yīng)的替換。這樣，每一個(gè)都滿足可行解的條件 變異操作：隨機(jī)選擇一個(gè)城市并插入到隨機(jī)位置(或隨機(jī)選擇兩個(gè)城市并互換位置) 用GA求解TSP，有很多研究 (編碼、遺傳操作等的形式多樣) 參看：米凱利維茨 寫的 演化程序。還可網(wǎng)上搜)。GA的特點(diǎn)的特點(diǎn) 與以前講過的算法

7、比較與以前講過的算法比較 多個(gè)解多個(gè)解 vs 一個(gè)解；一個(gè)解； 隨機(jī)性隨機(jī)性 vs 確定性。確定性。 不用求導(dǎo)數(shù)。不用求導(dǎo)數(shù)。 在編碼在編碼(而不是可行點(diǎn)而不是可行點(diǎn))上進(jìn)行操作。上進(jìn)行操作。(有實(shí)數(shù)編碼的有實(shí)數(shù)編碼的GA) 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 它是一個(gè)全局優(yōu)化算法它是一個(gè)全局優(yōu)化算法 萬(wàn)能算法萬(wàn)能算法 缺點(diǎn)：缺點(diǎn)： 需要設(shè)計(jì)需要設(shè)計(jì)(針對(duì)具體問題、設(shè)計(jì)具體的編碼和遺傳操作針對(duì)具體問題、設(shè)計(jì)具體的編碼和遺傳操作) 可能會(huì)收斂速度慢：但它本質(zhì)上是并行的，并行計(jì)算可能會(huì)收斂速度慢：但它本質(zhì)上是并行的，并行計(jì)算時(shí)效率很高。時(shí)效率很高。 Matlab中有遺傳算法工具箱 (ga 和 gatool)1. ：13、14周停課 做實(shí)驗(yàn)：14周周一下午、工程實(shí)訓(xùn)樓 實(shí)驗(yàn)內(nèi)容：見實(shí)驗(yàn)指導(dǎo)書請(qǐng)課代表通知自己班的同學(xué)，請(qǐng)課代表通知自己班的同學(xué)，并互相轉(zhuǎn)告。（并互相轉(zhuǎn)告。（15分）分）2. 交作業(yè)，15周講作業(yè)的問題。16周隨堂考。3. 公郵 : ，密碼: 123qwe以后的安排以后的安排人有了知識(shí)，就會(huì)具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中