【正文】 1 0 ，若隨機(jī)交叉點為 4，則交叉后生成的兩個新的個體是： A’= 0 0 1 1 1 0 B’= 1 1 0 0 0 1 遺傳算法 5. 基本遺傳操作 (5/11) 60 兩點交叉 兩點交叉是指先在兩個父代個體的編碼串中隨機(jī)設(shè)定兩個交叉點，然后再按這兩個交叉點進(jìn)行部分基因交換，生成子代中的兩個新的個體。 下面以 m=3為例進(jìn)行討論。 例 設(shè)有兩個父代的個體串 A=001101和 B=110010，若隨機(jī)生成的模版 T=010011，則交叉后的兩個新的個體是 A’=011010和 B’=100101。 以部分離散交叉為例， 假設(shè)兩個父代個體的 n維實向量分別是 X=x1x2… xi…x k…x n和 Y=y1y2…y i…y k…y n，若隨機(jī)選擇對 第 k個分量 以后的所有分量進(jìn)行交換，則生成的兩個新的個體向量是： X’ = x1 x2 … x k yk+1 … yn Y’= y1 y2 … y k xk+1 … xn 例 設(shè)有兩個父代個體向量 A=20 16 19 32 18 26和 B=36 25 38 12 21 30，若隨機(jī)選擇對 第 3個分量 以后的所有分量進(jìn)行交叉，則交叉后兩個新的個體向量是： A’= 20 16 19 12 21 30 B’= 36 25 38 32 18 26 遺傳算法 5. 基本遺傳操作 (9/11) 64 (3) 變異操作 變異（ Mutation）是指對選中個體的染色體中的某些基因進(jìn)行變動，以形成新的個體。 ① 二進(jìn)制變異 當(dāng)個體的染色體采用二進(jìn)制編碼表示時，其變異操作應(yīng)采用二進(jìn)制變異方法。 遺傳算法 5. 基本遺傳操作 (10/11) 65 ②實值變異 當(dāng)個體的染色體采用實數(shù)編碼表示時，其變異操作應(yīng)采用實值變異方法。 例 設(shè)選中的個體向量 D=20 12 16 19 21 30，若隨機(jī)產(chǎn)生的兩個變異位置分別時 2和 4，則變異后的新的個體向量是： D’= 20 19 16 12 21 30 遺傳算法 5. 基本遺傳操作 (11/11) 66 例 用遺傳算法求函數(shù) f(x)=x2 的最大值，其中 x為 [0， 31]間的整數(shù)。因此，可采用二進(jìn)制編碼方法，其編碼串的長度為 5。再假設(shè)隨機(jī)生成的初始種群（即第 0代種群）為： s01=0 1 1 0 1 s02=1 1 0 0 1 s03=0 1 0 0 0 s04=1 0 0 1 0 遺傳算法 6. 遺傳算法應(yīng)用簡例 (1/10) 67 (3) 計算適應(yīng)度 要計算個體的適應(yīng)度，首先應(yīng)該定義適應(yīng)度函數(shù)。 表 45 初始種群情況表 編號 個體串（染色體） x 適應(yīng)值 百分比% 累計百分比% 選中次數(shù) S01 01101 13 169 1 S02 11001 25 625 2 S03 01000 8 64 0 S04 10010 18 324 100 1 遺傳算法 6. 遺傳算法應(yīng)用簡例 (2/10) 可以看出，在 4個個體中 S02的適應(yīng)值最大，是當(dāng)前最佳個體。即： S11=10001 S12=11010 S13=01101 S14=11001 然后，對第 1代種群重復(fù)上述 (4)(6)的操作 遺傳算法 6. 遺傳算法應(yīng)用簡例 (5/10) 71 其中若假設(shè)按輪盤賭選擇時依次生成的 4個隨機(jī)數(shù)為 、 、 ，經(jīng)選擇后得到的新的種群為： S’ 11=10001 S’ 12=11010 S’ 13=11010 S’ 14=11001 可見，染色體 11010被選擇了 2次，而原染色體 01101則因適應(yīng)值太小而被淘汰。這種過早陷入局部最優(yōu)解的現(xiàn)象稱為早熟。變異后所得到的第 2代種群為： S21=10010 S22=11001 S23=11001 S24=11110 接著，再對第 2代種群同樣重復(fù)上述 (4)(6)的操作： 編號 個體串（染色體） 是否變異 變異位 子代 適應(yīng)值 S’’ 11 10010 N 10010 324 S’’ 12 11001 N 11001 625 S’’ 13 11001 N 11001 625 S’’ 14 11010 Y 3 11110 900 遺傳算法 6. 遺傳算法應(yīng)用簡例 (8/10) 對第 1代種群，其變異情況如表 49所示。 求解過程結(jié)束。目前，模糊理論已經(jīng)在推理、控制、決策等方面得到了非常廣泛的應(yīng)用。當(dāng) μF(u)僅取 0和 1時，模糊集 F便退化為一個普通集合。 0)60(,)50(,)40(,)30(,1)20(?????FFFFF????? 模糊集及其運算 1. 模糊集的定義 (2/2) 79 模糊集及其運算 2. 模糊集的表示 (1/3) (1) 離散且為有限論域的表示方法 設(shè)論域 U={u1, u2, … , u n}為離散論域，則其模糊集可表示為。 解： 由于模糊集是用其隸屬函數(shù)來刻畫的 ， 因此需要先求出描述模糊概念 “ 青年 ” 的隸屬函數(shù) 。 說明： ① 模糊集 F完全是由隸屬函數(shù) 來刻畫的 μF ， μF把 U中的每一個元素 u都映射為 [0, 1]上的一個值 μF(u) 。 圖 第 2代種群的交叉情況 76 概述 神經(jīng)計算 進(jìn)化計算 模糊計算 模糊集及模糊運算 模糊關(guān)系及其運算 粗糙集 第 4章 計算智能 美國加州大學(xué)扎德 (Zadeh)教授于 1965年提出的模糊集合與模糊邏輯理論是模糊計算的數(shù)學(xué)基礎(chǔ)。其選擇情況如表 410所示。 編號 個體串（染色體） 交叉對象 交叉位 子代 適應(yīng)值 S’ 11 10001 S’ 12 3 10010 324 S’ 12 11010 S’ 11 3 11001 625 S’ 13 11010 S’ 14 2 11001 625 S’ 14 11001 S’ 13 2 11010 675 遺傳算法 6. 遺傳算法應(yīng)用簡例 (7/10) 對第 1代種群，其交叉情況如表 48所示。其選擇情況如表 47所示。若規(guī)定種群中的染色體按順序兩兩配對交叉，且有 S’01與 S’02交叉， S’03與 S’04不交叉，則交叉情況如表 46所示。即： f(s)=f(x) 其中的二進(jìn)制串 s對應(yīng)著變量 x的值。其中的 0和 1為基因值。但作為一個例子，它有著較好的示范性和可理解性。最常用的實值變異操作有 : 基于位置的變異方法 該方法是先隨機(jī)地產(chǎn)生兩個變異位置，然后將第二個變異位置上的基因移動到第一個變異位置的前面。 例 設(shè)變異前的個體為 A=0 0 1 1 0 1，若隨機(jī)產(chǎn)生的變異 位置是 2，則該個體的第 2位由“ 0”變?yōu)椤?1”。遺傳算法中的變異操作增加了算法的局部隨機(jī)搜索能力，從而可以維持種群的多樣性。 部分離散交叉 是先在兩個父代個體的編碼向量中隨機(jī)選擇一部分分量，然后對這部分分量進(jìn)行交換，生成子代中的兩個新的個體。交叉后生成的兩個新的個體是： X’ = x1 x2 … x i yi+1 … y j xj+1 … x k yk+1 … y n Y’= y1 y2 … y i xi+1 … x j yj+1 … y k xk+1 … x n 例 設(shè)有兩個父代的個體串 A= 0 0 1 1 0 1 和 B= 1 1 0 0 1 0 ，若隨機(jī)交叉點為 3和 5，則交叉后的兩個新的個體是： A’= 0 1 0 1 0 0 B’= 1 0 1 0 1 1 遺傳算法 5. 基本遺傳操作 (7/11) 62 均勻交叉 均勻交叉（ Uniform Crossover）是先隨機(jī)生成一個與父串具有相同長度，并被稱為交叉模版（或交叉掩碼）的二進(jìn)制串，然后再利用該模版對兩個父串進(jìn)行交叉，即將模版中 1對應(yīng)的位進(jìn)行交換 ，而 0對應(yīng)的位不交換，依此生成子代中的兩個新的個體。 假設(shè)交叉點個數(shù)為 m，則可將個體串劃分為 m+1個分段，其劃分方法是： 當(dāng) m為偶數(shù)時，對全部交叉點依次進(jìn)行兩兩配對，構(gòu)成 m/2個交叉段。 ①二進(jìn)制交叉 二進(jìn)制交叉（ Binary Valued Crossover）是指二進(jìn)制編碼情況下所采用的交叉操作，它主要包括 單點交叉、兩點交叉、多點交叉和均勻交叉 等方法。這種方法有點類似于發(fā)放獎品使用的輪盤，并帶有某種賭博的意思，因此亦被稱為輪盤賭選擇。 輪盤賭選擇算法的基本思想是：根據(jù)每個個體的選擇概率 P(xi)將一個圓盤分成 N個扇區(qū)，其中第 i個扇區(qū)的中心角為： 再設(shè)立一個移動指針，將圓盤的轉(zhuǎn)動等價為指針的移動。 ① 比例選擇 比例選擇方法（ Proportional Model）的基本思想是：各個個體被選中的概率與其適應(yīng)度大小成正比。目的是通過 M拉開不同染色體適應(yīng)度值的差距。 適應(yīng)度函數(shù)的加速變換有兩種基本方法 線性加速 的適應(yīng)度函數(shù)的定義如下： f’(x)=αf(x)+β 其中， f(x)是加速轉(zhuǎn)換前的適應(yīng)度函數(shù)； f’(x)是加速轉(zhuǎn)換后的適應(yīng)度函數(shù)； α和 β是轉(zhuǎn)換系數(shù) ,它們應(yīng)滿足如下條件： ① 變化后得到的新的適應(yīng)度函數(shù)平均值要等于原適應(yīng)度函數(shù)的平均值。 遺傳算法 4. 適應(yīng)度函數(shù) (2/5) ??? ??? 否則當(dāng)0 )()()()()( m a xm a x xfxfxfxfxf nomal52 極大化問題 對極大化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為 () 其中， fmin(x)是原始適應(yīng)函數(shù) f(x)的一個下界。這就往往需要對原始適應(yīng)函數(shù)進(jìn)行某種變換，將其轉(zhuǎn)換為標(biāo)準(zhǔn)的度量方式，以滿足進(jìn)化操作的要求，這樣所得到的適應(yīng)度函數(shù)被稱為標(biāo)準(zhǔn)適應(yīng)度函數(shù) fNormal(x)。 (1) 常用的適應(yīng)度函數(shù) 在遺傳算法中，有許多計算適應(yīng)度的方法，其中最常用的適應(yīng)度函數(shù)有以下兩種： ① 原始適應(yīng)度函數(shù) 它是直接將待求解問題的目標(biāo)函數(shù) f(x)定義為遺傳算法的適應(yīng)度函數(shù)。由于實數(shù)編碼使用的是變量的真實值，因此這種編碼方法也叫做真值編碼方法。它有效地解決了漢明懸崖問題，其基本原理如下： 設(shè)有二進(jìn)制串 b1,b2,…,b n，對應(yīng)的格雷串為 a1,a2,…,a n，則從二進(jìn)制編碼到格雷編碼的變換為： () 其中， ⊕ 表示模 2加法。 二進(jìn)制編碼存在的主要缺點 是漢明（ Hamming）懸崖。 (1)二進(jìn)制編碼（ Binary encoding） 二進(jìn)制編碼是將原問題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。其函數(shù)值是遺傳算法實現(xiàn)優(yōu)勝劣汰的主要依據(jù) 遺傳操作 （ Geic Operator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。例如，可以用 0、 1組成的長度為 l的串來表示個體。 進(jìn)化計算概述 3. 進(jìn)化計算的基本結(jié)構(gòu) 44 遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目標(biāo)為止。 進(jìn)化計算概述 2. 進(jìn)化計算的產(chǎn)生與發(fā)展 (2/2) 43 進(jìn)化計算盡管有多個重要分支，并且不同分支的編碼方案、選擇策略和進(jìn)化操作也有可能不同，但它們卻有著共同的進(jìn)化框架。 進(jìn)化計算概述 2. 進(jìn)