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

遺傳算法

GA(GeneticAlgorithm)遺傳算法JohnHolland美國(guó)密歇根大學(xué)教授于1970s提出基本思想：模擬生物群體的進(jìn)化(自然選擇naturalselection、適者生存survivalofthefittest)和優(yōu)化問(wèn)題的基本聯(lián)系：生物進(jìn)化和遺傳算法的對(duì)應(yīng)關(guān)系生物學(xué)中的概念遺傳算法適者生存在算法停止時(shí)，最優(yōu)目標(biāo)函數(shù)值的解有最大的可能性保留下來(lái)個(gè)體individual解染色體chromosome解的編碼（字符串、向量等）基因gene編碼位或分量適應(yīng)性fitness適應(yīng)度函數(shù)的值群體population(種群)選定的一組解(其中解的個(gè)數(shù)為群體的規(guī)模)(自然)選擇根據(jù)適應(yīng)度函數(shù)選取的一組解交配crossover通過(guò)交配操作產(chǎn)生的一組新解的過(guò)程變異mutation編碼的某一位或分量發(fā)生變化的過(guò)程最后三個(gè)在遺傳算法中稱為遺傳操作求解優(yōu)化問(wèn)題最大化目標(biāo)函數(shù)也可以有約束?？尚薪?。遺傳算法的基本步驟選擇一個(gè)問(wèn)題的解的編碼方案產(chǎn)生一個(gè)有N個(gè)染色體的初始群體對(duì)群體中的每一個(gè)染色體計(jì)算其適應(yīng)度(目標(biāo)函數(shù)值)在當(dāng)代群體上重復(fù)如下步驟，直至停止條件滿足。選擇：根據(jù)染色體的適應(yīng)度，按一個(gè)規(guī)則從當(dāng)前群體中選擇一些個(gè)體組成一個(gè)新群體(配對(duì)庫(kù))在該群體上，通過(guò)交配操作產(chǎn)生后代。在該群體上，通過(guò)變異操作產(chǎn)生后代。這時(shí)已得到下一代群體。計(jì)算新一代群體中各個(gè)染色體的適應(yīng)度。簡(jiǎn)單遺傳算法選擇問(wèn)題的解的編碼為二進(jìn)制編碼隨機(jī)產(chǎn)生一個(gè)有N個(gè)染色體的初始群體，迭代時(shí)N不改變對(duì)群體中的每一個(gè)染色體計(jì)算其適應(yīng)度//目標(biāo)函數(shù)值在當(dāng)代群體上重復(fù)如下步驟，直至停止條件滿足。比例選擇：從當(dāng)代群體中選擇一些個(gè)體組成新群體，每個(gè)個(gè)體被選中的概率與其適應(yīng)度成比例。比例選擇也叫輪盤賭，一個(gè)個(gè)體可能被選中多次。在該群體上，通過(guò)交配操作產(chǎn)生后代。//一對(duì)染色體,單點(diǎn)交叉(pc經(jīng)常=0.6-1.0)在該群體上，通過(guò)變異操作產(chǎn)生后代。//

每個(gè)編碼位是等概率變異的，小概率變異(pm經(jīng)常=0.01-0.1)這時(shí)已得到全新的群體。計(jì)算在新群體中各個(gè)染色體的適應(yīng)度。例子maxf(x)=x2,0≤x≤31,x為整數(shù)。（迭代1步）例子：TSPTSP(TravelingSalesmanProblem)

旅行商或貨郎擔(dān)問(wèn)題：設(shè)有n個(gè)城市，貨郎擔(dān)從其中的一個(gè)城市出發(fā)，每個(gè)城市必須訪問(wèn)一次、而且只能訪問(wèn)一次，最終回到開始的城市。兩個(gè)城市之間的旅費(fèi)是已知的，他應(yīng)該選擇什么樣的路線才能使花費(fèi)達(dá)到最?。縂A求解：設(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è)旅程：JHDEFIGCBA—旅程1HGEBCJIADF—旅程2部分匹配交叉(PMX)：取兩個(gè)截點(diǎn)：如DE間，IG間：旅程1→

JHDBCJGCBA→

IHDBCJGFEA—旅程1‘旅程2→HGEEFIIADF

→HGBEFIJADC—旅程2‘中間部分交換，外圍部分中重復(fù)的城市用旅程之間對(duì)應(yīng)的替換。這樣，每一個(gè)都滿足可行解的條件變異操作：隨機(jī)選擇一個(gè)城市并插入到隨機(jī)位置(或隨機(jī)選擇兩個(gè)城市并互換位置)用GA求解TSP，有很多研究(編碼、遺傳操作等的形式多樣)

參看：米凱利維茨寫的《演化程序》。還可網(wǎng)上搜)。GA的特點(diǎn)與以前講過(guò)的算法比較多個(gè)解vs一個(gè)解；隨機(jī)性vs確定性。不用求導(dǎo)數(shù)。在編碼(而不是可行點(diǎn))上進(jìn)行操作。(有實(shí)數(shù)編碼的GA)優(yōu)點(diǎn)：它是一個(gè)全局優(yōu)化算法萬(wàn)能算法缺點(diǎn)：需要設(shè)計(jì)(針對(duì)具體問(wèn)題、設(shè)計(jì)具體的編碼和遺傳操作)可能會(huì)收斂速度慢：但它本質(zhì)上是并行的，并行計(jì)算時(shí)效率很高。Matlab中有遺傳算法工具箱(ga和gatool)1.：13、14周停課做實(shí)驗(yàn)：14周周一下午、工程實(shí)訓(xùn)樓實(shí)驗(yàn)內(nèi)容：見實(shí)驗(yàn)指導(dǎo)書