遺傳算法GeneticAlgorithm(matlabGAtool用法打印了,和實驗指導書放在一起)

遺傳算法

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

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

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

JHDBCJGCBA→

IHDBCJGFEA—旅程1‘旅程2→HGEEFIIADF

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

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