人工智能ai4章計算智能-資料下載頁

　　

【正文】 變異（ Mutation）是指對選中個體的染色體中的某些基因進(jìn)行變動，以形成新的個體。變異也是生物遺傳和自然進(jìn)化中的一種基本現(xiàn)象，它可增強種群的多樣性。遺傳算法中的變異操作增加了算法的局部隨機搜索能力，從而可以維持種群的多樣性。根據(jù)個體編碼方式的不同，變異操作可分為二進(jìn)制變異和實值變異兩種類型。 ① 二進(jìn)制變異 當(dāng)個體的染色體采用二進(jìn)制編碼表示時，其變異操作應(yīng)采用二進(jìn)制變異方法。該變異方法是先隨機地產(chǎn)生一個變異位，然后將該變異位置上的基因值由“ 0”變?yōu)椤?1”，或由“ 1”變?yōu)椤?0”，產(chǎn)生一個新的個體。 例 設(shè)變異前的個體為 A=0 0 1 1 0 1，若隨機產(chǎn)生的變異 位置是 2，則該個體的第 2位由“ 0”變?yōu)椤?1”。 變異后的新的個體是 A’= 0 1 1 1 0 1 。 遺傳算法 5. 基本遺傳操作 (10/11) 65 ②實值變異 當(dāng)個體的染色體采用實數(shù)編碼表示時，其變異操作應(yīng)采用實值變異方法。該方法是用另外一個在規(guī)定范圍內(nèi)的隨機實數(shù)去替換原變異位置上的基因值，產(chǎn)生一個新的個體。最常用的實值變異操作有 : 基于位置的變異方法 該方法是先隨機地產(chǎn)生兩個變異位置，然后將第二個變異位置上的基因移動到第一個變異位置的前面。 例 設(shè)選中的個體向量 C=20 16 19 12 21 30，若隨機產(chǎn)生的兩個變異位置分別時 2和 4，則變異后的新的個體向量是： C’= 20 12 16 19 21 30 基于次序的變異 該方法是先隨機地產(chǎn)生兩個變異位置，然后交換這兩個變異位置上的基因。 例 設(shè)選中的個體向量 D=20 12 16 19 21 30，若隨機產(chǎn)生的兩個變異位置分別時 2和 4，則變異后的新的個體向量是： D’= 20 19 16 12 21 30 遺傳算法 5. 基本遺傳操作 (11/11) 66 例 用遺傳算法求函數(shù) f(x)=x2 的最大值，其中 x為 [0， 31]間的整數(shù)。 解： 這個問題本身比較簡單，其最大值很顯然是在 x=31處。但作為一個例子，它有著較好的示范性和可理解性。 按照遺傳算法，其求解過程如下： (1) 編碼 由于 x的定義域是區(qū)間 [0， 31]上的整數(shù)，由 5位二進(jìn)制數(shù)即可全部表示。因此，可采用二進(jìn)制編碼方法，其編碼串的長度為 5。 例如，用二進(jìn)制串 00000來表示 x=0,11111來表示 x=31等。其中的 0和 1為基因值。 (2) 生成初始種群 若假設(shè)給定的種群規(guī)模 N=4，則可用 4個隨機生成的長度為 5的二進(jìn)制串作為初始種群。再假設(shè)隨機生成的初始種群（即第 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ù)。由于本例是求 f(x)的最大值，因此可直接用 f(x)來作為適應(yīng)度函數(shù)。即： f(s)=f(x) 其中的二進(jìn)制串 s對應(yīng)著變量 x的值。根據(jù)此函數(shù)，初始種群中各個個體的適應(yīng)值及其所占比例如表 45所示。 表 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)前最佳個體。 68 (4) 選擇操作 假設(shè)采用輪盤賭方式選擇個體，且依次生成的 4個隨機數(shù)（相當(dāng)于輪盤上指針?biāo)傅臄?shù)）為 、 、 ，經(jīng)選擇后得到的新的種群為： S’01=10010 S’02=11001 S’03=01101 S’04=11001 其中，染色體 11001在種群中出現(xiàn)了 2次，而原染色體 01000則因適應(yīng)值太小而被淘汰 遺傳算法 6. 遺傳算法應(yīng)用簡例 (3/10) 69 (5) 交叉 假設(shè)交叉概率 Pi為 50%，則種群中只有 1/2的染色體參與 交叉。若規(guī)定種群中的染色體按順序兩兩配對交叉，且有 S’01與 S’02交叉， S’03與 S’04不交叉，則交叉情況如表 46所示。 表 46 初始種群的交叉情況表 編號 個體串（染色體） 交叉對象 交叉位 子代 適應(yīng)值 S’01 10010 S’02 3 10001 289 S’02 11001 S’01 3 11010 676 S’03 01101 S’04 N 01101 169 S’04 11001 S’03 N 11001 625 遺傳算法 6. 遺傳算法應(yīng)用簡例 (4/10) 可見，經(jīng)交叉后得到的新的種群為： S’’01=10001 S’’02=11010 S’’03=01101 S’’04=11001 70 (6) 變異 變異概率 Pm一般都很小，假設(shè)本次循環(huán)中沒有發(fā)生變異，則變異前的種群即為進(jìn)化后所得到的第 1代種群。即： S11=10001 S12=11010 S13=01101 S14=11001 然后，對第 1代種群重復(fù)上述 (4)(6)的操作 遺傳算法 6. 遺傳算法應(yīng)用簡例 (5/10) 71 其中若假設(shè)按輪盤賭選擇時依次生成的 4個隨機數(shù)為 、 、 ，經(jīng)選擇后得到的新的種群為： S’ 11=10001 S’ 12=11010 S’ 13=11010 S’ 14=11001 可見，染色體 11010被選擇了 2次，而原染色體 01101則因適應(yīng)值太小而被淘汰。 編號 個體串（染色體） x 適應(yīng)值 百分比 % 累計百分比 % 選中次數(shù) S11 10001 17 289 1 S12 11010 26 676 2 S13 01101 13 169 0 S14 11001 25 625 100 1 遺傳算法 6. 遺傳算法應(yīng)用簡例 (6/10) 對第 1代種群，同樣重復(fù)上述 (4)(6)的操作。其選擇情況如表 47所示。 表 47 第 1代種群的選擇情況表 72 可見，經(jīng)雜交后得到的新的種群為： S’’11=10010 S’’12=11001 S’’13=11001 S’’14=11010 可以看出，第 3位基因均為 0，已經(jīng)不可能通過交配達(dá)到最優(yōu)解。這種過早陷入局部最優(yōu)解的現(xiàn)象稱為早熟。為解決這一問題，需要采用變異操作。 編號 個體串（染色體） 交叉對象 交叉位 子代 適應(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所示。 表 48 第 1代種群的交叉情況表 73 它是通過對 S’’14的第 3位的變異來實現(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所示。 表 49 第 1代種群的變異情況表 74 其中若假設(shè)按輪盤賭選擇時依次生成的 4個隨機數(shù)為 、 、 ，經(jīng)選擇后得到的新的種群為： S’ 21=11001 S’ 22=10010 S’ 23=11001 S’ 24=11110 編號 個體串（染色體） x 適應(yīng)值 百分比 % 累計百分比 % 選中次數(shù) S21 10010 18 324 1 S22 11001 25 625 1 S23 11001 25 625 1 S24 11110 30 900 100 1 遺傳算法 6. 遺傳算法應(yīng)用簡例 (9/10) 對第 2代種群，同樣重復(fù)上述 (4)(6)的操作。其選擇情況如表 410所示。 表 410 第 2代種群的選擇情況表 75 這時，函數(shù)的最大值已經(jīng)出現(xiàn)，其對應(yīng)的染色體為 11111，經(jīng)解碼后可知問題的最優(yōu)解是在點 x=31處。 求解過程結(jié)束。 編號 個體串（染色體） 交叉對象 交叉位 子代 適應(yīng)值 S’ 21 11001 S’ 22 3 11010 676 S’ 22 10010 S’ 21 3 10001 289 S’ 23 11001 S’ 24 4 11000 576 S’ 24 11110 S’ 23 4 11111 961 遺傳算法 6. 遺傳算法應(yīng)用簡例 (10/10) 對第 2代種群，其交叉情況如表 411所示。 圖 第 2代種群的交叉情況 76 概述 神經(jīng)計算 進(jìn)化計算 模糊計算 模糊集及模糊運算 模糊關(guān)系及其運算 粗糙集 第 4章 計算智能 美國加州大學(xué)扎德 (Zadeh)教授于 1965年提出的模糊集合與模糊邏輯理論是模糊計算的數(shù)學(xué)基礎(chǔ)。它主要用來處理現(xiàn)實世界中因模糊而引起的不確定性。目前，模糊理論已經(jīng)在推理、控制、決策等方面得到了非常廣泛的應(yīng)用。 本節(jié)主要討論模糊理論的基礎(chǔ)，對于模糊推理將放到下一章討論 77 模糊集及其運算 1. 模糊集的定義 (1/2) 定義 設(shè) U是給定論域 ， μF(u)是把任意 u∈ U映射為 [0, 1]上某個實值的函數(shù) ， 即 μF(u) ： U→[ 0, 1] u→ μF(u) 稱 μF(u)為定義在 U上的一個隸屬函數(shù)，由 μF(u) 對所有 u∈ U 所構(gòu)成的集合 F={ μF(u) | u ∈ U } 則稱 F為 U上的一個模糊集， μF(u)稱為 u對 F的隸屬度。 說明： ① 模糊集 F完全是由隸屬函數(shù) 來刻畫的 μF ， μF把 U中的每一個元素 u都映射為 [0, 1]上的一個值 μF(u) 。 ② μF(u)的值表示 u隸屬于 F的程度，其值越大，表示 u隸屬于 F的程度越高。當(dāng) μF(u)僅取 0和 1時，模糊集 F便退化為一個普通集合。 78 例 設(shè)論域 U={20, 30, 40, 50, 60}給出的是年齡 ， 請確定一個刻畫模糊概念 “ 年輕 ” 的模糊集 F。 解： 由于模糊集是用其隸屬函數(shù)來刻畫的 ， 因此需要先求出描述模糊概念 “ 青年 ” 的隸屬函數(shù) 。 假設(shè)對論域 U中的元素 ， 其隸屬函數(shù)值分別為： 則可得到刻畫模糊概念 “ 年輕 ” 的模糊集 F={ 1, , , , 0} 說明其含義。 0)60(,)50(,)40(,)30(,1)20(?????FFFFF????? 模糊集及其運算 1. 模糊集的定義 (2/2) 79 模糊集及其運算 2. 模糊集的表示 (1/3) (1) 離散且為有限論域的表示方法 設(shè)論域 U={u1, u2, … , u n}為離散論域，則其模糊集可表