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

遺傳算法

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

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

旅行商或貨郎擔問題：設有n個城市，貨郎擔從其中的一個城市出發(fā)，每個城市必須訪問一次、而且只能訪問一次，最終回到開始的城市。兩個城市之間的旅費是已知的，他應該選擇什么樣的路線才能使花費達到最小？GA求解：設有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‘中間部分交換，外圍部分中重復的城市用旅程之間對應的替換。這樣，每一個都滿足可行解的條件變異操作：隨機選擇一個城市并插入到隨機位置(或隨機選擇兩個城市并互換位置)用GA求解TSP，有很多研究(編碼、遺傳操作等的形式多樣)

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