【正文】 crossover)、順序交叉 (order crossover)、循環(huán)交叉 (cycle crossover) 二 .基本算法 28 2. GA的構(gòu)成要素 ? 交叉 ? 實(shí)數(shù)編碼：離散重組（ discrete rebination） 、中間重組（ intermediate rebination） 線性重組（ linear rebination） 二 .基本算法 29 2. GA的構(gòu)成要素 ? 變異 ? 變異率：染色體上基因發(fā)生變異的概率，用Pm表示，一般設(shè)定得比較小，在 ? 二進(jìn)制及整數(shù)編碼：位變異 ? 順序編碼： 2opt或者 kopt ? 實(shí)數(shù)編碼：實(shí)值變異 二 .基本算法 30 3. 計(jì)算舉例 ? 產(chǎn)生初始種群 ? 計(jì)算適值 二 .基本算法 0001100000 0101111001 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 （ 8） （ 5） （ 2） （ 10） （ 7） （ 12） （ 5） （ 19） （ 10） （ 14） 31 3. 計(jì)算舉例 ? 選擇 二 .基本算法 個(gè)體 染色體 適值 選擇概率 累積概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 12 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 8 8＋ 5＋ 2＋ 10＋ 7＋ 12＋ 5＋ 19＋ 10＋ 14 5 8＋ 5＋ 2＋ 10＋ 7＋ 12＋ 5＋ 19＋ 10＋ 14 32 3. 計(jì)算舉例 ? 選擇 二 .基本算法 個(gè)體 染色體 適值 選擇概率 累積概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 12 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 33 3. 計(jì)算舉例 ? 選擇 二 .基本算法 在 01之間產(chǎn)生 隨機(jī)數(shù)： 個(gè)體 染色體 適應(yīng)度 選擇概率 累積概率 1 0001100000 8 2 0101111001 5 3 0000000101 2 4 1001110100 10 5 1010101010 7 6 1110010110 12 7 1001011011 5 8 1100000001 19 9 1001110100 10 10 0001010011 14 淘汰！ 淘汰！ 34 3. 計(jì)算舉例 ? 交叉（ pc=） 在 01之間產(chǎn)生隨機(jī)數(shù) 二 .基本算法 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011 0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011 0001 1110 100000 010110 111 100 0010110 1011011 110000 100111 0100 0001 1001110100 1100000001 1010101 0001010 010 011 35 3. 計(jì)算舉例 ? 變異（ pm=） 在 01之間產(chǎn)生隨機(jī)數(shù) 二 .基本算法 0001010110 1111011011 1100000100 1001110100 1010101011 1110100000 1000010110 1001110001 1100000001 0001010010 0001010110 1111011011 1100000100 1001100100 1010101011 1110100000 1000010110 1001010001 1100000001 0101010000 36 3. 計(jì)算舉例 ? 至下一代，適應(yīng)度計(jì)算 → 選擇 → 交叉 → 變異，直至滿足終止條件 二 .基本算法 37 1. 基本概念 ? 模板： 若干位確定，若干位不確定的一類個(gè)體的總稱，用 S表示，如 0 ? ? ? ?或 1 ? ? ? ? ? 模板的長(zhǎng)度 l(s)：模板第一個(gè)確定位與最后一個(gè)確定位之間的長(zhǎng)度 ? 模板的階數(shù) K(s)：模板中確定位的個(gè)數(shù) 例如 若 S : ? ? 0 ? 1 ? 1 ? ， 則 l(s)=4， K(s)=3 三 .模板理論 38 1. 基本概念 ? 常識(shí) ? n位編碼總長(zhǎng) n1 ? 階數(shù)為 K(s) 的模板 S中的個(gè)體總數(shù)為 ? 對(duì)于一個(gè) n位二進(jìn)制表達(dá)，染色體長(zhǎng)度為 n，則模板數(shù) 個(gè)體數(shù) (3n2n) ，即分類方法數(shù) 個(gè)體總數(shù)，因模板因子、個(gè)體因子分別為 (0,1,?)、 (0,1) 。 一 .前言 11 2. GA的生物學(xué)原理 ? 達(dá)爾文的自然選擇說 ? 遺傳：子代和父代具有相同或相似的性狀，保證物種穩(wěn)定性 ? 變異：子代與父代，子代不同個(gè)體之間總有差異，是生命多樣性的根源 ? “ 自然選擇、適者生存 ” ：具有適應(yīng)性變異的個(gè)體被保留，不具適應(yīng)性變異的個(gè)體被淘汰，這是一個(gè)長(zhǎng)期的、緩慢的、連續(xù)的過程 一 .前言 12 2. GA的生物學(xué)原理 ? 遺傳學(xué)的基本術(shù)語 ? 染色體（ chromosome）：遺傳物質(zhì)的載體 ? 脫氧核糖核酸（ DNA）：大分子有機(jī)聚合物，雙螺旋結(jié)構(gòu) ? 遺傳因子（ gene）： DNA長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位 一 .前言 13 2. GA的生物學(xué)原理 ? 遺傳學(xué)的基本術(shù)語 ? 基因型（ genotype）：遺傳因子組合的模型 ? 表現(xiàn)型（ phenotype）：由染色體決定性狀的外部表現(xiàn) 一 .前言 1 1 1 1 1 1 1 1 1 1 0 1 1 1 14 2. GA的生物學(xué)原理 ? 遺傳學(xué)的基本術(shù)語 ? 基因座（ locus）：遺傳基因在染色體中所占據(jù)的位置，同一基因座可能有的全部基因稱為等位基因（ allele） ? 個(gè)體（ individual）：帶有染色體特征的實(shí)體 ? 種群（ population）：個(gè)體的集合 一 .前言 15 2. GA的生物學(xué)原理 ? 遺傳學(xué)的基本術(shù)語 ? 進(jìn)化（ evolution）：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化 ? 適應(yīng)度（ fitness）：度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。 一 .前言 10 1. 遺傳算法的產(chǎn)生與發(fā)展 ? 幾個(gè)名詞 ? 人工智能 AI：二十世紀(jì)七十年代以來被稱為世界三大尖端技術(shù)之一（空間技術(shù)、能源技術(shù)、 人工智能 ）。這些方法具備的要素：自適應(yīng)的結(jié)構(gòu)、隨機(jī)產(chǎn)生的或指定的初始狀態(tài)、適應(yīng)度的評(píng)測(cè)函數(shù)、修改結(jié)構(gòu)的操作、系統(tǒng)狀態(tài)存儲(chǔ)器、終止計(jì)算的條件、指示結(jié)果的方法、控制過程的參數(shù)。后來，遺傳規(guī)劃和差分進(jìn)化也被歸納到 EA范疇之內(nèi)。直到 90年代，才有所交流。1 第五章 遺傳算法 2 第五章 遺傳算法 一 .前言 二 .基本算法 三 .模板理論 四 .算法變形 五 .算法應(yīng)用 六 .學(xué)習(xí)遺傳算法的幾點(diǎn)體會(huì) 3 1. 遺傳算法的產(chǎn)生與發(fā)展 ? 早在 50年代 ，一些生物學(xué)家開始研究運(yùn)用數(shù)字計(jì)算機(jī)