【正文】 ： 編碼和初始群體生成； 群體的評價； 個體的選擇； 交換； 突變； 167。 遺傳算法 在講解中會結(jié)合如下的貨郎擔(dān)問題 (Travelling Salesman Problem，簡記為 TSP)：設(shè)有 n個城市，城市 i和城市 j之間的距離為 d(i， j) i, j=1,...,n． TSP問題是要找遍訪每個域市恰好一次的一條回路，且其路徑總長度為最短。 167。 遺傳算法的基本機(jī)理 一 .編碼與解碼 許多應(yīng)用問題的結(jié)構(gòu)很復(fù)雜，但可以化為簡單的位串形式編碼表示。 :將問題結(jié)構(gòu)變換為位串形式編碼表示的過程； (或譯碼 ):而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程。 把位串形式編碼表示叫 染色體 ，有時也叫 個體 。 167。 遺傳算法的基本機(jī)理 ： ⑴ .二進(jìn)制編碼 假設(shè)某一參數(shù)的取值范圍是 [A,B],用長度為 l的二進(jìn)制串來表示該參數(shù)，將 [A,B]等分成 2l1個子部分，記每一等分的長度為 ?，則它能夠產(chǎn)生 2l個不同的編碼，如下： 000…… 00=0 → A 000…… 01=1 → A + ? 其中 ∶ ∶ ∶∶ 111…… 11=2l1 → B 假設(shè)某一個體的編碼是： X:xlxl1xl2… x2x1 則二進(jìn)制編碼所對應(yīng)的解碼公式為 缺點(diǎn) :長度較大 B A ?= ———— 2l 1 B – A l x=A + ———— .∑x 2l – 1 i=1 167。 遺傳算法的基本機(jī)理 ： ⑵ .浮點(diǎn)數(shù)編碼 個體的每個染色體用某一范圍內(nèi)的一個浮點(diǎn)數(shù)來表示 ,個體的編碼長度等于其變量的個數(shù)。 對于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題采用此法會有益 ⑶ .格雷碼 連續(xù)的兩個整數(shù)所對應(yīng)的編碼值之間只有一個碼位是不相同的，其余碼位都完全相同。 例如：十進(jìn)制數(shù) 7和 8的格雷碼分別為 0100和 1100。 167。 遺傳算法的基本機(jī)理 ： ⑷ .符號編碼 指個體染色體編碼串中的基因值取自一個無數(shù)值含義而只有代碼含義的符號集。符號集可以是字母表，如： {A、 B、 C、 D… }；數(shù)字序號表 { 4… }或代碼表 {x x x3… },等等。 舉例：對于銷售員旅行問題，按一條回路中城市的次序進(jìn)行編碼。從城市 w1開始，依次經(jīng)過城市 w2 ， …… ， wn，最后回到城市 w1，我們就有如下編碼表示： w1 w2 …… wn 由于是回路，記 wn+1=w1。它其實(shí)是 1， …… ， n的一個循環(huán)排列。要注意 w1，w2， …… ， wn是互不相同的。 167。 遺傳算法的基本機(jī)理 二 .適應(yīng)度函數(shù) 為了體現(xiàn)染色體的適應(yīng)能力而引入的對問題中的每一個染色體都能進(jìn)行度量的函數(shù)。 通過適應(yīng)度函數(shù)來決定染色體的優(yōu)、劣程度，它體現(xiàn)了自然進(jìn)化中的優(yōu)利劣汰原則 。 例如： 對優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。 TSP的目標(biāo)是路徑總長度為最短，路徑總長度的倒數(shù)就可以為 TSP的適應(yīng)度函數(shù)： 適應(yīng)度函數(shù)要有效反映每一個染色體與問題的最優(yōu)解染色體之間的差距，一個染色體與問題的最優(yōu)解染色體之間的差距小，則對應(yīng)的適應(yīng)度函數(shù)值之差就小，否則就大。適應(yīng)度函數(shù)的取值大小與求解問題對象的意義有很大的關(guān)系。 167。 遺傳算法的基本機(jī)理 三 .遺傳操作 簡單遺傳算法的遺傳操作主要有三種 :選擇 (selection)、交叉 (crossover)、變異 (mutation)。改進(jìn)的遺傳算法大量擴(kuò)充了遺傳操作，以達(dá)到更高的效率。 也叫復(fù)制操作， 對自然界 “ 適者生存 ” 的模擬 。 根據(jù)個體的適應(yīng)度函數(shù)值所度量的優(yōu)、劣程度決定它在下一代是被淘汰還是被遺傳。 一般地說，選擇將使適應(yīng)度較大 (優(yōu)良 )個體有較大的存在機(jī)會，而適應(yīng)度較?。ǖ土樱┑膫€體繼續(xù)存在的機(jī)會也較小。簡單遺傳算法采用賭輪選擇機(jī)制，令 Σfi表示群體的適應(yīng)度值之總和， fi表示種群中第 i個染色體的適應(yīng)度值，它產(chǎn)生后代的能力正好為其適應(yīng)度值所占份額 fi／ Σfi。 167。 遺傳算法的基本機(jī)理 是 GA中最主要的遺傳操作，其工作于選擇過程結(jié)束后產(chǎn)生的下一代群體。交叉操作應(yīng)用于從這一群體中隨機(jī)選擇的一系列個體對（串對）。 SGA采用的是單點(diǎn)交換。設(shè)串長為 L，交換操作將隨機(jī)選擇一個交換點(diǎn)（對應(yīng)于從 1到 L1的某個位置序號），緊接著兩串交換點(diǎn)右邊的子串互換，從而產(chǎn)生了兩個新串。例如，設(shè) Ａ 1， Ａ 2為要交換的串，交換點(diǎn)被隨機(jī)選擇為 7（串長為 10）。 Ａ 1＝ 1000011111 Ａ 2＝ 1111111011 交換得新串 Ａ 139。， Ａ 239。： Ａ 139。＝ 1000011011 Ａ 239。＝ 1111111111 當(dāng)然，并非所有選中的串對都會發(fā)生交換。這些串對發(fā)生交換的概率是 Pc。Pc為事先指定的 0－ 1之間的值，稱為交換率。 167。 遺傳算法的基本機(jī)理 一般在交換后進(jìn)行。突變操作的對象是個體（即串），旨在改變串中的某些位的值，即由 0變?yōu)?1，或由 1變?yōu)?0。并非所有位都能發(fā)生變化，每一位發(fā)生變化的概率是 Pm。 Pm為事先指定的 0－1之間的某個值，稱為變異率。串中每一位的突變是獨(dú)立的，即某一位是否發(fā)生突變并不影響其它位的變化。 變異的作用是引進(jìn)新的遺傳物質(zhì)或恢復(fù)已失去的遺傳物質(zhì) 。例如，若群體的各串中每一位的值均為 0，此時無論如何交換都不能產(chǎn)生有 1的位，只有通過突變。 例如： 10100110 對從右往左的第 5位進(jìn)行變異操作 10110110 167。 遺傳算法的基本機(jī)理 四 .控制參數(shù) 并不是所有被選擇了的染色體都要進(jìn)行交叉操作和變異操作，而是以一定的概率進(jìn)行，一般在程序設(shè)計中交叉發(fā)生的概率要比變異發(fā)生的概率選取得大若干個數(shù)量級，交叉概率取 ；變異概率取 的值。 指種群的染色體總數(shù)，它對算法的效率有明顯的影響，規(guī)模太小不得于進(jìn)化，而規(guī)模太大將導(dǎo)致程序運(yùn)行時間長。對不同的問題可能有各自適合的種群規(guī)模，通常種群規(guī)模為 30至 100。 有定長和變長兩種。它對算法的性能也有影響。 167。 遺傳算法的基本機(jī)理 舉例 ： 來說明遺傳算法的一個進(jìn)化循環(huán)。設(shè)每一串的長度為 10，共有 4個串組成第一代群體（ POP1），目標(biāo)函數(shù)（適應(yīng)函數(shù)）為各位值之和 167。 遺傳算法的求解步驟 一 .遺傳算法的特點(diǎn) 遺傳算法是一種基于空間搜索的算法，它通過自然選擇、遺傳、變異等操作以及達(dá)爾文適者生存的理論，模擬自然進(jìn)化過程來尋找所求問題的解答。遺傳算法具有以下特點(diǎn)： 1. 遺傳算法是對參數(shù)集合的編碼而非針對參數(shù)本身進(jìn)行進(jìn)化； 2. 遺傳算法是從問題解的編碼組開始而非從單個解開始搜索； 3. 遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來指導(dǎo)搜索； 4. 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(jī)操作。 167。 遺傳算法的求解步驟 最主要的特點(diǎn)體現(xiàn)在下述兩個方面 : .智能性 進(jìn)化算法的智能性包括自組織、自適應(yīng)和自學(xué)習(xí)等。應(yīng)用進(jìn)化算法求解問題時 ,在確定了編碼方案、適應(yīng)值函數(shù)和遺傳算子以后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。進(jìn)化算法的這種智能性特征同時賦予了它具有根據(jù)環(huán)境的變化自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力。 .本質(zhì)并行性 進(jìn)化算法的本質(zhì)并行性表現(xiàn)在兩個方面 :一是進(jìn)化算法是內(nèi)在并行的，即進(jìn)化算法本身非常適合大規(guī)模并性。二是進(jìn)化算法的內(nèi)含并行性，由于進(jìn)化算法采用種群的方式組織搜索，因而它可以搜索解空間內(nèi)的多個區(qū)域，并相互交流信息。 167。 遺傳算法的求解步驟 二 .遺傳算法的框圖 簡單遺傳算法框圖如圖所示。 (1) 初始化群體 。 (2) 計算群體上每個個體的適應(yīng)度值 。 (3) 按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進(jìn)入下一代的個體 。 (4) 按概率 Pc進(jìn)行交叉操作 。 (5) 按概率 Pc進(jìn)行突變操作 。 (6) 沒有滿足某種停止條件，則轉(zhuǎn)第 (2)步，否則進(jìn)入 (7)。 (7) 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。 算法的停止條件最簡單的有如下二種：（ 1）完成了預(yù)先給定的進(jìn)化代數(shù)則停止；（ 2）群體中的最優(yōu)個體在連續(xù)若干代沒有改進(jìn)或平均適應(yīng)度在連續(xù)若干代基本沒有改進(jìn)時停止。 167。 遺傳算法的求解步驟 一般遺傳算法的主要步驟如下： (1) 隨機(jī)產(chǎn)生一個由確定長度的特征字符串組成的初始群體。 (2) 對該字符串群體迭代的執(zhí)行下面的步 (a)和(b)，直到滿足停止標(biāo)準(zhǔn)： (a) 計算群體中每個個體字符串的適應(yīng)值； (b) 應(yīng)用復(fù)制、交叉和變異等遺傳算子產(chǎn)生下一代群體。 (3) 把在后代中出現(xiàn)的最好的個體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個結(jié)果可以表示問題的一個解。 167。 遺傳算法的求解步驟 三 .遺傳算法求解舉例 用遺傳算法求解函數(shù) f(x)=(10?.x)+ 的最大值，其中 x?[1,2]。 首先用高等數(shù)學(xué)的方法求解， 先求導(dǎo)數(shù)，令其為 0， … 最后求得 x≈ f(x)≈ 167。 遺傳算法的求解步驟 用二進(jìn)制矢量表示一個染色體。 假設(shè)精度取小數(shù)點(diǎn)后 6位數(shù)。 [1， 2]將被均勻地分為 3 1000000個等長的區(qū)間。因?yàn)? 2097152=221＜ 3000000≤2 22=4194304，每個染色體由 22位字節(jié)的二進(jìn)制矢量表示。 二進(jìn)制串 b21b20… b0和區(qū)間 [1， 2]中的 x之間的映射關(guān)系為 ⑴將二進(jìn)制串 b21b20… b0轉(zhuǎn)化為相應(yīng)的十進(jìn)制： 21 (b21b20… b0)2=(∑ )10=x’ i=0 ⑵ 找到相應(yīng)的實(shí)數(shù) x: x= + x’.3/(2221) 例如：二進(jìn)數(shù) (1000101110110101000111) x’=(1000101110110101000111)2=2288967 x=1+ 167。 遺傳算法的求解步驟 隨機(jī)產(chǎn)生一定數(shù)量的染色體，每個染色體為 22位字節(jié)的二進(jìn)制數(shù)即可。 由于目標(biāo)本身為求函數(shù)最優(yōu)，適應(yīng)度函數(shù)取目標(biāo)函數(shù)即可。 eval(v)=f(x) v代表染色體 例如： v=(1000100000110101000111) 對應(yīng) x= eval(v)=f(x)= 包括復(fù)制、交叉和變異。同上面介紹。 種群規(guī)模 popsize=50，交叉概率 pc=，變異概率 pm=。 167。 遺傳算法的求解步驟 結(jié)果表明： 隨著代數(shù)的增加，適應(yīng)值也不斷增加，直到第 150代，最佳染色體為vmax=(1111001101000100000101),它對應(yīng) xmax=, f(xmax)= 遺傳算法計算結(jié)果 代數(shù) 適應(yīng)度函數(shù)值 代數(shù) 適應(yīng)度函數(shù)值 1 6 8 9 10 12 39 40 51 99 137 150