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