1、人工智能,計(jì)算智能,2016年秋季,羅平 ,本章內(nèi)容,概述 演化計(jì)算 模糊計(jì)算,本章內(nèi)容,概述 演化計(jì)算 模糊計(jì)算,計(jì)算智能（Computational Intelligence，CI） 計(jì)算智能是在神經(jīng)網(wǎng)絡(luò)（Neural Networks,NN）、演化計(jì)算（Evolutionary Computation,EC）及模糊系統(tǒng)（Fuzzy System,FS）這3個(gè)領(lǐng)域發(fā)展相對(duì)成熟的基礎(chǔ)上形成的一個(gè)統(tǒng)一的學(xué)科概念。,什么是計(jì)算智能,神經(jīng)網(wǎng)絡(luò)是一種對(duì)人類(lèi)智能的結(jié)構(gòu)模擬方法，它是通過(guò)對(duì)大量人工神經(jīng)元的廣泛并行互聯(lián)，構(gòu)造人工神經(jīng)網(wǎng)絡(luò)系統(tǒng)去模擬生物神經(jīng)系統(tǒng)的智能機(jī)理。 演化計(jì)算是一種對(duì)人類(lèi)智能的演化模擬

2、方法，它是通過(guò)對(duì)生物遺傳和演化過(guò)程的認(rèn)識(shí)，用進(jìn)化算法去模擬人類(lèi)智能的進(jìn)化規(guī)律的。 模糊計(jì)算是一種對(duì)人類(lèi)智能的邏輯模擬方法，它是通過(guò)對(duì)人類(lèi)處理模糊現(xiàn)象的認(rèn)知能力的認(rèn)識(shí)，用模糊邏輯去模擬人類(lèi)的智能行為的。,本章內(nèi)容,概述 演化計(jì)算 模糊計(jì)算,7,演化計(jì)算（Evolutionary Computation,EC）： 在基因和種群層次上模擬自然界生物進(jìn)化過(guò)程與機(jī)制的問(wèn)題求解技術(shù)和計(jì)算模型。 思想源于生物遺傳學(xué)和適者生存的自然規(guī)律 基于達(dá)爾文（Darwin）的進(jìn)化論和孟德?tīng)枺∕endel）的遺傳變異理論 典型代表： 遺傳算法（Genetic Algorithm，GA） 進(jìn)化策略（Evolutionary

3、 Strategy,ES） 進(jìn)化規(guī)劃（Evolutionary Programming,EP） 遺傳規(guī)劃（Genetic Programming,GP）,演化計(jì)算,達(dá)爾文的自然選擇學(xué)說(shuō)是一種被人們廣泛接受的生物進(jìn)化學(xué)說(shuō)： 生物要生存下去，就必須進(jìn)行生存斗爭(zhēng)。 具有有利變異的個(gè)體容易存活下來(lái)，并且有更多的機(jī)會(huì)將有利變異傳給后代；具有不利變異的個(gè)體就容易被淘汰，產(chǎn)生后代的機(jī)會(huì)也少的多。 適者生存，不適者淘汰：自然選擇。 遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。（相對(duì)穩(wěn)定+新的物種）,演化計(jì)算,9,孟德?tīng)柣蜻z傳原理 遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。 每個(gè)基因有特殊的位置并控制某種

4、特殊性質(zhì)；所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性。 基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。 經(jīng)過(guò)存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來(lái)。,演化計(jì)算,10,演化計(jì)算：一種模擬自然界生物進(jìn)化過(guò)程與機(jī)制進(jìn)行問(wèn)題求解的自組織、自適應(yīng)的隨機(jī)搜索技術(shù)。 演化規(guī)則：“物競(jìng)天擇、適者生存” 演化操作： 繁殖（Reproduction） 變異（Mutation） 競(jìng)爭(zhēng)（Competition） 選擇（Selection）,演化計(jì)算及其生物學(xué)基礎(chǔ),遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個(gè)體，并通過(guò)雜交、變異來(lái)產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目標(biāo)為止

5、基本概念： 種群（Population）：多個(gè)備選解的集合。 個(gè)體（Individual）：種群中的單個(gè)元素，通常由一個(gè)用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來(lái)表示。例如，長(zhǎng)度為L(zhǎng) 的0、1串 染色體（Chromos）：對(duì)個(gè)體仿照基因編碼進(jìn)行編碼后所得到的編碼串。染色體中的每一位稱為基因，染色體上由若干個(gè)基因構(gòu)成的一個(gè)有效信息段稱為基因組。,遺傳算法,基本概念： 適應(yīng)度（Fitness）函數(shù)：用來(lái)對(duì)種群中各個(gè)個(gè)體的環(huán)境適應(yīng)性進(jìn)行度量的函數(shù)，函數(shù)值是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要依據(jù) 遺傳操作（Genetic Operator）：作用于種群而產(chǎn)生新的種群的操作。 選擇（Selection） 交叉（Cros

6、s-over） 變異（Mutation）,遺傳算法,遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳操作設(shè)計(jì)等幾大部分所組成， 算法基本步驟： 選擇編碼策略，將問(wèn)題搜索空間中每個(gè)可能的點(diǎn)用相應(yīng)的編碼策略表示出來(lái)，即形成染色體； 定義遺傳策略，包括種群規(guī)模N，交叉、變異方法，以及選擇概率Pr、交叉概率Pc、變異概率Pm等遺傳參數(shù)； 令t=0，隨機(jī)選擇N個(gè)染色體初始化種群P(0)； 定義適應(yīng)度函數(shù)f； 計(jì)算P(t)中每個(gè)染色體的適應(yīng)值； t=t+1； 運(yùn)用選擇算子，從P(t-1)中得到P(t)； 對(duì)P(t)中的每個(gè)染色體，按概率Pc參與交叉； 對(duì)染色體中的基因，以概率Pm參與變異運(yùn)算；

7、 判斷群體性能是否滿足預(yù)先設(shè)定的終止標(biāo)準(zhǔn)，若不滿足返回(5)。,遺傳算法,遺傳算法,遺傳算法生物進(jìn)化 適應(yīng)函數(shù) 環(huán)境 適應(yīng)函數(shù)值 適應(yīng)性 適應(yīng)函數(shù)值最大的解被保留的概率最大 適者生存 問(wèn)題的一個(gè)解 個(gè)體 解的編碼 染色體 編碼的元素 基因 被選定的一組解 群體 根據(jù)適應(yīng)函數(shù)選擇的一組解（以編碼形式表示） 種群 以一定的方式由雙親產(chǎn)生后代的過(guò)程 繁殖 編碼的某些分量發(fā)生變化的過(guò)程 變異,遺傳算法與生物進(jìn)化之間對(duì)應(yīng)關(guān)系,二進(jìn)制編碼（Binary encoding） 二進(jìn)制編碼是將原問(wèn)題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。假設(shè)某一參數(shù)的取值范圍是A，B，A來(lái)表示。 優(yōu)點(diǎn)：易于理解和實(shí)現(xiàn)，可表示的模式數(shù)最多

8、 主要缺點(diǎn): 海明懸崖。 例如，7和8的二進(jìn)制數(shù)分別為0111和1000，當(dāng)算法從7改進(jìn)到8時(shí)，就必須改變所有的位。,遺傳編碼,格雷編碼（Gray encoding） 要求兩個(gè)連續(xù)整數(shù)的編碼之間只能有一個(gè)碼位不同，其余碼位都是完全相同的。有效地解決了海明懸崖問(wèn)題。 基本原理： 二進(jìn)制碼-格雷碼（編碼）：從最右邊一位起，依次將每一位與左邊一位異或(XOR)，作為對(duì)應(yīng)格雷碼該位的值，最左邊一位不變； 格雷碼-二進(jìn)制碼（解碼）：從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值，最左邊一位依然不變。,遺傳編碼,符號(hào)編碼（Symbol encoding） 個(gè)體染色體編碼串中的基因值取自

9、一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集。,由于是回路，記wn+1= w1。 它其實(shí)是1，n的一個(gè)循環(huán)排列。 要注意w1， w2， wn是互不相同的。,遺傳編碼,例如，對(duì)于TSP問(wèn)題，采用符號(hào)編碼方法，按一條回路中城市的次序進(jìn)行編碼，一般情況是從城市w1開(kāi)始，依次經(jīng)過(guò)城市w2 ， wn，最后回到城市w1，我們就有如下編碼表示：,適應(yīng)度函數(shù)是一個(gè)用于對(duì)個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。個(gè)體的適應(yīng)度值越大，它被遺傳到下一代種群中的概率越大 常用的適應(yīng)度函數(shù) 原始適應(yīng)度函數(shù): 直接將待求解問(wèn)題的目標(biāo)函數(shù)f(x)定義為遺傳算法的適應(yīng)度函數(shù)。 例如：求最大值 時(shí)，f(x)即為x的原始適應(yīng)度函數(shù)。 優(yōu)點(diǎn)：能夠直接

10、反映出待求解問(wèn)題的最初求解目標(biāo)， 缺點(diǎn)：有可能出現(xiàn)適應(yīng)度值為負(fù)的情況,適應(yīng)度函數(shù),TSP的目標(biāo)是路徑總長(zhǎng)度為最短，路徑總長(zhǎng)度可作為T(mén)SP問(wèn)題的適應(yīng)度函數(shù)：,適應(yīng)度函數(shù),標(biāo)準(zhǔn)適應(yīng)度函數(shù) 在遺傳算法中，一般要求適應(yīng)度函數(shù)非負(fù)，并其適應(yīng)度值越大越好。這就往往需要對(duì)原始適應(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)。 例：對(duì)極小化問(wèn)題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為 其中，fmax (x)是原始適應(yīng)函數(shù)f(x)的一個(gè)上界。如果fmax (x) 未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最大值來(lái)代替。 fmax (

11、x) 是會(huì)隨著進(jìn)化代數(shù)的增加而不斷變化的。,適應(yīng)度函數(shù),極大化問(wèn)題 對(duì)極大化問(wèn)題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為 其中，fmin(x)是原始適應(yīng)函數(shù)f(x)的一個(gè)下界。如果fmin(x) 未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最小值來(lái)代替。,適應(yīng)度函數(shù),遺傳算法中的基本遺傳操作包括選擇、交叉和變異。 選擇(selection)操作: 根據(jù)選擇概率按某種策略從當(dāng)前種群中挑選出一定數(shù)目的個(gè)體，使它們能夠有更多的機(jī)會(huì)被遺傳到下一代中 常用的選擇策略可分為比例選擇、排序選擇和競(jìng)技選擇三種類(lèi)型。 比例選擇 基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。,基本遺傳操作,輪盤(pán)賭選擇 個(gè)體被選

12、中的概率取決于該個(gè)體的相對(duì)適應(yīng)度。而相對(duì)適應(yīng)度的定義為： 其中，P(xi)是個(gè)體xi的相對(duì)適應(yīng)度，即個(gè)體xi被選中的概率；f(xi)是個(gè)體xi的原始適應(yīng)度；是種群的累加適應(yīng)度。 輪盤(pán)賭選擇算法的基本思想是：根據(jù)每個(gè)個(gè)體的選擇概率P(xi)將一個(gè)圓盤(pán)分成N個(gè)扇區(qū)，其中第i個(gè)扇區(qū)的中心角為： 并再設(shè)立一個(gè)固定指針。當(dāng)進(jìn)行選擇時(shí)，可以假想轉(zhuǎn)動(dòng)圓盤(pán)，若圓盤(pán)靜止時(shí)指針指向第i個(gè)扇區(qū)，則選擇個(gè)體i。,基本遺傳操作,從統(tǒng)計(jì)角度看，個(gè)體的適應(yīng)度值越大，其對(duì)應(yīng)的扇區(qū)的面積越大，被選中的可能性也越大。這種方法有點(diǎn)類(lèi)似于發(fā)放獎(jiǎng)品使用的輪盤(pán)，并帶有某種賭博的意思，因此亦被稱為輪盤(pán)賭選擇。,基本遺傳操作,交叉(cros

13、sover)操作: 按照某種方式對(duì)選擇的父代個(gè)體的染色體的部分基因進(jìn)行交配重組，從而形成新的個(gè)體。 常見(jiàn)的交叉操作： 二進(jìn)制交叉：二進(jìn)制編碼情況下所采用的交叉操作，它主要包括： 單點(diǎn)交叉 兩點(diǎn)交叉 多點(diǎn)交叉 均勻交叉,基本遺傳操作,單點(diǎn)交叉 先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，然后對(duì)這兩個(gè)父代個(gè)體交叉點(diǎn)前面或后面部分的基因進(jìn)行交換，并生成子代中的兩個(gè)新的個(gè)體。 假設(shè)兩個(gè)父代的個(gè)體串分別是： X=x1 x2 xk xk+1 xn Y=y1 y2 yk yk+1 yn 隨機(jī)選擇第k位為交叉點(diǎn)，交叉后生成的兩個(gè)新的個(gè)體是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk x

14、k+1 xn 設(shè)有兩個(gè)父代的個(gè)體串A=0 0 1 1 0 1 和B=1 1 0 0 1 0 ，若隨機(jī)交叉點(diǎn)為4，則交叉后生成的兩個(gè)新的個(gè)體是： A= 0 0 1 1 1 1 B= 1 1 0 0 0 0,基本遺傳操作,兩點(diǎn)交叉 先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定兩個(gè)交叉點(diǎn)，然后再按這兩個(gè)交叉點(diǎn)進(jìn)行部分基因交換，生成子代中的兩個(gè)新的個(gè)體。 假設(shè)兩個(gè)父代的個(gè)體串分別是： X=x1 x2 xi xj xn Y=y1 y2 yi yj ,yn 隨機(jī)設(shè)定第i、j位為兩個(gè)交叉點(diǎn)（其中ijn），交叉后生成的兩個(gè)新的個(gè)體是： X= x1 x2 xi yi+1 yj xj+1 xn Y= y1 y2 yi xi

15、+1 xj yj+1 yn 例: 設(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 0 1 0 1 1 B= 1 1 0 1 0 0,基本遺傳操作,均勻交叉 先隨機(jī)生成一個(gè)與父串具有相同長(zhǎng)度的二進(jìn)制串（交叉模版），然后再利用該模版對(duì)兩個(gè)父串進(jìn)行交叉，即將模版中1對(duì)應(yīng)的位進(jìn)行交換，而0對(duì)應(yīng)的位不交換，依此生成子代中的兩個(gè)新的個(gè)體。 事實(shí)上，這種方法對(duì)父串中的每一位都是以相同的概率隨機(jī)進(jìn)行交叉的。 例5.10 設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)生成的模版T=010011，則交叉

16、后的兩個(gè)新的個(gè)體是A=011010和B=100101。即 A： 0 0 1 1 0 1 B： 1 1 0 0 1 0 T： 0 1 0 0 1 1 A： 0 1 1 1 1 0 B：1 0 0 0 0 1,基本遺傳操作,實(shí)值交叉 在實(shí)數(shù)編碼情況下所采用的交叉操作，主要包括離散交叉和算術(shù)交叉 部分離散交叉：先在兩個(gè)父代個(gè)體的編碼向量中隨機(jī)選擇一部分分量，然后對(duì)這部分分量進(jìn)行交換，生成子代中的兩個(gè)新的個(gè)體。 整體交叉：對(duì)兩個(gè)父代個(gè)體的編碼向量中的所有分量，都以1/2的概率進(jìn)行交換，從而生成子代中的兩個(gè)新的個(gè)體。 假設(shè)兩個(gè)父代個(gè)體的n維實(shí)向量分別是 X=x1x2 xixkxn和Y=y1y2yiyky

17、n，若隨機(jī)選擇對(duì)第k個(gè)分量以后的所有分量進(jìn)行交換，則生成的兩個(gè)新的個(gè)體向量是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn,基本遺傳操作,變異(Mutation)操作: 對(duì)選中個(gè)體的染色體中的某些基因進(jìn)行變動(dòng)，以形成新的個(gè)體。遺傳算法中的變異操作增加了算法的局部隨機(jī)搜索能力，從而可以維持種群的多樣性。 變異雖然可以帶來(lái)群體的多樣性，但因其具有很強(qiáng)的破壞性，因此一般通過(guò)一個(gè)很小的變異概率來(lái)控制它的使用。 根據(jù)個(gè)體編碼方式的不同，變異操作可分為二進(jìn)制變異和實(shí)值變異兩種類(lèi)型。 二進(jìn)制變異 先隨機(jī)地產(chǎn)生一個(gè)變異位，然后將該變異位置上的基因值由“0”變?yōu)椤?”，或由“

18、1”變?yōu)椤?”，產(chǎn)生一個(gè)新的個(gè)體。 例5.12 設(shè)變異前的個(gè)體為A=0 0 1 1 0 1，若隨機(jī)產(chǎn)生的變異位置是2，則該個(gè)體的第2位由“0”變?yōu)椤?”。 變異后的新的個(gè)體是A= 0 1 1 1 0 1 。,基本遺傳操作,實(shí)值變異 用另外一個(gè)在規(guī)定范圍內(nèi)的隨機(jī)實(shí)數(shù)去替換原變異位置上的基因值，產(chǎn)生一個(gè)新的個(gè)體。最常用的實(shí)值變異操作有: 基于次序的變異: 先隨機(jī)地產(chǎn)生兩個(gè)變異位置，然后交換這兩個(gè)變異位置上的基因。 例: 設(shè)選中的個(gè)體向量D=20 12 16 19 21 30，若隨機(jī)產(chǎn)生的兩個(gè)變異位置分別時(shí)2和4，則變異后的新的個(gè)體向量是： D= 20 19 16 12 21 30,基本遺傳操作,精

19、英主義 （Elitism） 僅僅從產(chǎn)生的子代中選擇基因去構(gòu)造新的種群可能會(huì)丟失掉上一代種群中的很多信息。也就是說(shuō)當(dāng)利用交叉和變異產(chǎn)生新的一代時(shí)，我們有很大的可能把在某 個(gè)中間步驟中得到的最優(yōu)解丟失。 使用精英主義（Elitism）方法，在每一次產(chǎn)生新的一代時(shí)，我們首先把當(dāng)前最優(yōu)解原封不動(dòng)的復(fù)制到新的一代中，其他步驟不變。這樣任何時(shí)刻產(chǎn)生的一個(gè)最優(yōu)解都可以存活到遺傳算法結(jié)束。 上述各種算子的實(shí)現(xiàn)是多種多樣的，而且許多新的算子正在不斷地提出，以改進(jìn)GA某些性能。,基本遺傳操作,例5.15 用遺傳算法求函數(shù) f(x)=x2 的最大值，其中x為0，31間的整數(shù)。 解： (1) 編碼 由于x的定義域是區(qū)

20、間0，31上的整數(shù)，由5位二進(jìn)制數(shù)即可全部表示。因此，可采用二進(jìn)制編碼方法，其編碼串的長(zhǎng)度為5。 例如，用二進(jìn)制串00000來(lái)表示x=0,11111來(lái)表示x=31等。其中的0和1為基因值。 (2) 生成初始種群 若假設(shè)給定的種群規(guī)模N=4，則可用4個(gè)隨機(jī)生成的長(zhǎng)度為5的二進(jìn)制串作為初始種群。再假設(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,遺傳算法應(yīng)用,(3) 計(jì)算適應(yīng)度 要計(jì)算個(gè)體的適應(yīng)度，首先應(yīng)該定義適應(yīng)度函數(shù)。由于本例是求f(x)的最大值，因此可直接用f(x)來(lái)作為適應(yīng)度函數(shù)。即：

21、 f(s)=f(x) 其中的二進(jìn)制串s對(duì)應(yīng)著變量x的值。根據(jù)此函數(shù)，初始種群中各個(gè)個(gè)體的適應(yīng)值及其所占比例為。 可以看出，在4個(gè)個(gè)體中S02的適應(yīng)值最大，是當(dāng)前最佳個(gè)體。,遺傳算法應(yīng)用,（4) 選擇操作 假設(shè)采用輪盤(pán)賭方式選擇個(gè)體，且依次生成的4個(gè)隨機(jī)數(shù)（相當(dāng)于輪盤(pán)上指針?biāo)傅臄?shù)）為0.85、0.32、0.12和0.46，經(jīng)選擇后得到的新的種群為： S01=10010 S02=11001 S03=01101 S04=11001 其中，染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適應(yīng)值太小而被淘汰,14% 53% 5% 27% -|-|-|-*-| 個(gè)體1 個(gè)體2 個(gè)體3 0.8

22、5 個(gè)體4隨機(jī)數(shù)為0.85落在了個(gè)體4的端內(nèi).本次選擇了個(gè)體4.,遺傳算法應(yīng)用,(5) 交叉 假設(shè)交叉概率Pi為50%，則種群中只有1/2的染色體參與交叉。若規(guī)定種群中的染色體按順序兩兩配對(duì)交叉，且有S01與S02交叉，S03與S04不交叉，則交叉情況為： 可見(jiàn)，經(jīng)交叉后得到的新的種群為： S01=10001 S02=11010 S03=01101 S04=11001,遺傳算法應(yīng)用,(6) 變異 變異概率Pm一般都很小，假設(shè)本次循環(huán)中沒(méi)有發(fā)生變異，則變異前的種群即為進(jìn)化后所得到的第1代種群。即： S11=10001 S12=11010 S13=01101 S14=11001 然后，對(duì)第1代種群

23、重復(fù)上述(4)-(6)的操作，選擇情況如下： 其中若假設(shè)按輪盤(pán)賭選擇時(shí)依次生成的4個(gè)隨機(jī)數(shù)為0.14、0.51、0.24和0.82，經(jīng)選擇后得到的新的種群為： S11=10001 S12=11010 S13=11010 S14=11001 可以看出，染色體11010被選擇了2次，而原染色體01101則因適應(yīng)值太小而被淘汰。,遺傳算法應(yīng)用,對(duì)第1代種群，其交叉情況： 可見(jiàn)，經(jīng)雜交后得到的新的種群為： S11=10010 S12=11001 S13=11001 S14=11010 可以看出，第3位基因均為0，已經(jīng)不可能通過(guò)交配達(dá)到最優(yōu)解。這種過(guò)早陷入局部最優(yōu)解的現(xiàn)象稱為早熟。為解決這一問(wèn)題，需要采

24、用變異操作。,遺傳算法應(yīng)用,對(duì)第1代種群，其變異情況： 它是通過(guò)對(duì)S14的第3位的變異來(lái)實(shí)現(xiàn)的。變異后所得到的第2代種群為： S21=10010 S22=11001 S23=11001 S24=11110 接著，再對(duì)第2代種群同樣重復(fù)上述(4)-(6)的操作：,遺傳算法應(yīng)用,對(duì)第2代種群，同樣重復(fù)上述(4)-(6)的操作。 其中若假設(shè)按輪盤(pán)賭選擇時(shí)依次生成的4個(gè)隨機(jī)數(shù)為0.42、0.15、0.59和0.91，經(jīng)選擇后得到的新的種群為： S21=11001 S22=10010 S23=11001 S24=11110,遺傳算法應(yīng)用,對(duì)第2代種群，其交叉情況： 這時(shí)，函數(shù)的最大值已經(jīng)出現(xiàn)，其對(duì)應(yīng)的染

25、色體為11111，經(jīng)解碼后可知問(wèn)題的最優(yōu)解是在點(diǎn)x=31處。 求解過(guò)程結(jié)束。,遺傳算法應(yīng)用,例子：8皇后問(wèn)題,目標(biāo)：任何一個(gè)皇后都不會(huì)攻擊到其他的皇后（皇后可以攻擊和它在同一行、同一列或同一對(duì)角線上的皇后） 適應(yīng)度函數(shù)取作可以彼此攻擊的皇后對(duì)的數(shù)目（忽略障礙）,8皇后的例子，其中每個(gè)狀態(tài)用一個(gè)長(zhǎng)度為8的字符串來(lái)表示，適應(yīng)度函數(shù)取作不相互攻擊的皇后對(duì)數(shù)目。,問(wèn)題表示：從k個(gè)隨機(jī)生成的狀態(tài)（種群）開(kāi)始 每個(gè)個(gè)體用一個(gè)有限長(zhǎng)度的字符串表示-通常用0，1表示,例子：8皇后問(wèn)題,通過(guò)把兩個(gè)父狀態(tài)結(jié)合來(lái)生成后繼,例子：8皇后問(wèn)題,遺傳算法特點(diǎn) 自組織、自適應(yīng)和自學(xué)習(xí)性概率轉(zhuǎn)移準(zhǔn)則，非確定性規(guī)則 確定進(jìn)化方

26、案后，算法將利用進(jìn)化過(guò)程中得到的信息自行組織搜索；基于自然的選擇策略，優(yōu)勝劣汰； 遺傳算法很快就能找到良好的解，即使是在很復(fù)雜的解空間中 采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近 交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的復(fù)蓋 本質(zhì)并行性-群體搜索 算法本身非常適合大規(guī)模并行，各種群分別獨(dú)立進(jìn)化，不需要相互間交換信息；二是可以同時(shí)搜索解空間的多個(gè)區(qū)域并相互間交流信息，使得演化計(jì)算能以較少的計(jì)算獲得較大的收益。,遺傳算法特點(diǎn),不需要其他知識(shí)，只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù) 對(duì)待求解問(wèn)題的指標(biāo)函數(shù)沒(méi)有什么特殊的要求，如不要求連續(xù)性、導(dǎo)數(shù)存在、單峰值等假設(shè) 容易形成通用

27、算法程序 遺傳算法不能解決那些“大海撈針”的問(wèn)題，所謂“大海撈針”問(wèn)題就是沒(méi)有一個(gè)確切的適應(yīng)度函數(shù)表征個(gè)體好壞的問(wèn)題，遺傳算法對(duì)這類(lèi)問(wèn)題無(wú)法找到收斂的路徑。 應(yīng)用廣泛 遺傳算法擅長(zhǎng)解決的問(wèn)題是全局最優(yōu)化問(wèn)題，例如，解決時(shí)間表安排問(wèn)題就是它的一個(gè)特長(zhǎng)，很多安排時(shí)間表的軟件都使用遺傳算法,遺傳算法特點(diǎn),理論上證明算法的收斂性很困難 多用于解決實(shí)際問(wèn)題 汽車(chē)設(shè)計(jì)，包括材料選擇、多目標(biāo)汽車(chē)組件設(shè)計(jì)、減輕重量等。 機(jī)電系統(tǒng)設(shè)計(jì)。 分布計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。 電路設(shè)計(jì)，此類(lèi)用途的遺傳算法叫做進(jìn)化電路。 移動(dòng)通訊優(yōu)化結(jié)構(gòu)。 煤氣管道的最優(yōu)控制、通信網(wǎng)絡(luò)鏈接長(zhǎng)度的優(yōu)化問(wèn)題、鐵路運(yùn)輸計(jì)劃優(yōu)化、噴氣式收音機(jī)渦輪機(jī)

28、的設(shè)計(jì)、VLSI版面設(shè)計(jì)、鍵盤(pán)排列優(yōu)化 抓到老鼠的貓都是好貓,本章內(nèi)容,概述 演化計(jì)算 模糊計(jì)算,模糊計(jì)算,美國(guó)加州大學(xué)扎德(Zadeh)教授于1965年提出的模糊集合與模糊邏輯理論是模糊計(jì)算的數(shù)學(xué)基礎(chǔ)。 發(fā)表了文章模糊集 (Fuzzy sets，Information and Control, 8, 338-353) 主要用來(lái)處理現(xiàn)實(shí)世界中因模糊而引起的不確定性。 模糊理論已經(jīng)在推理、控制、決策等方面得到了非常廣泛的應(yīng)用,模糊計(jì)算,“模糊不是罪過(guò)”： 模糊 ”糊涂”, “朦朧”, ”傻冒”, “癡呆” 取得精確數(shù)據(jù)不可能或很困難 例如：粒種子肯定不能叫一堆，粒也不是，粒也不是那么多少粒種子叫

29、一堆呢？適當(dāng)?shù)慕缦拊谀睦锬?？我們能否說(shuō)粒種子不叫一堆，而粒種子叫一堆呢？ 沒(méi)有必要獲取精確數(shù)據(jù) 例如：要從一片西瓜地里找出一個(gè)最大的西瓜，那是件很麻煩的事。必須 把西瓜地里所有的西瓜都找出來(lái)，再比較一下，才知道哪個(gè)西瓜最大。西瓜越多，工作量就越大。如果按通常說(shuō)的，到西瓜地里去找一個(gè)較大的西瓜，這時(shí)精確的問(wèn)題就轉(zhuǎn)化成模糊的問(wèn)題，反而容易多了。由此可見(jiàn)，適當(dāng)?shù)哪：苁箚?wèn)題得到簡(jiǎn)化。,清晰的概念: 對(duì)象是否屬于這個(gè)概念是明確的。 例如；人、自然數(shù)、正方形。 模糊性的概念：對(duì)象從屬的界限是模糊的，隨判斷人的思維而定 “最大的”與“較大的”都是有區(qū)別的兩個(gè)概念。但是它們的區(qū)別都是逐漸的，而不是突變的，兩

30、者之間并不存在明確的界限 一個(gè)人很高或很胖，但是究竟多少厘米才算高，多少千克才算胖呢？高和胖都很模糊。 飯什么時(shí)候才算熟了？衣服什么樣才能算洗干凈？ 例如：美不美？早不早？便宜不便宜？ 在客觀世界中，上述的模糊概念要比清晰概念多得多。,模糊計(jì)算,要使計(jì)算機(jī)能夠模仿人腦，對(duì)復(fù)雜系統(tǒng)進(jìn)行識(shí)別和判斷，出路何在？ 1965年扎德(Zadeh)教授開(kāi)創(chuàng)了對(duì)“模糊數(shù)學(xué)”的研究。他認(rèn)為數(shù)學(xué)是可以模糊的，主張從精度方面“后退”一步。他提出用隸屬函數(shù)使模糊概念數(shù)學(xué)化。 例如“年輕”和“年老”這兩個(gè)模糊概念。扎德教授本人根據(jù)統(tǒng)計(jì)資料，擬合了這兩個(gè)概念的隸屬函數(shù)圖象。圖中橫坐標(biāo)表示年齡，縱坐標(biāo)表示隸屬程度。,模糊計(jì)

31、算,定義 設(shè)U是給定論域， 是把任意uU映射為0, 1上某個(gè)實(shí)值的函數(shù)，即 ：U0, 1 則稱 為定義在U上的一個(gè)隸屬函數(shù)，由 （對(duì)所有 ）所構(gòu)成的集合F稱為U上的一個(gè)模糊集， 稱為u對(duì)F的隸屬度。 模糊集F完全是由隸屬函數(shù) 來(lái)刻畫(huà)的， 把U中的每一個(gè)元素u都映射為0, 1上的一個(gè)值 。 的值表示u隸屬于F的程度，其值越大，表示u隸屬于F的程度越高。當(dāng) 僅取0和1時(shí)，模糊集F便退化為一個(gè)普通集合。,模糊集的定義,55,例5.15 設(shè)論域U=20, 30, 40, 50, 60給出的是年齡，請(qǐng)確定一個(gè)刻畫(huà)模糊概念“年輕”的模糊集F。 解：由于模糊集是用其隸屬函數(shù)來(lái)刻畫(huà)的，因此需要先求出描述模糊概

32、念“青年”的隸屬函數(shù)。假設(shè)對(duì)論域U中的元素，其隸屬函數(shù)值分別為： 則可得到刻畫(huà)模糊概念“年輕”的模糊集 F= 1, 0.8, 0.4, 0.1, 0,模糊集的定義,隨機(jī)與模糊：是否與多少,模糊性: 事件發(fā)生的程度，而不是一個(gè)事件是否發(fā)生. 隨機(jī)性: 描述事件發(fā)生的不確定性,即,一個(gè)事件發(fā)生與否.,離散且為有限論域的表示方法 設(shè)論域 U=u1, u2, , un為離散論域，則其模糊集可表示為： F= , , , 為了能夠表示出論域中的元素與其隸屬度之間的對(duì)應(yīng)關(guān)系，扎德引入了一種模糊集的表示方式：先為論域中的每個(gè)元素都標(biāo)上其隸屬度，然后再用“+”號(hào)把它們連接起來(lái)，即 也可寫(xiě) 其中， 為ui對(duì)F的隸

33、屬度；“ / ui ”不是相除關(guān)系，只是一個(gè)記號(hào)；“+”也不是算術(shù)意義上的加，只是一個(gè)連接符號(hào)。,模糊集的表示,在這種表示方法中，當(dāng)某個(gè)ui對(duì)F的隸屬度=0時(shí)，可省略不寫(xiě)。 例如，模糊集F可表示為： F= 1/20+ 0.8/30+ 0.6/40+ 0.2/50 有時(shí)，模糊集也可寫(xiě)成如下兩種形式： 其中，前一種稱為單點(diǎn)形式，后一種稱為序偶形式。,模糊集的表示,連續(xù)論域的表示方法 如果論域是連續(xù)的，則其模糊集可用一個(gè)實(shí)函數(shù)來(lái)表示。 例如，扎德以年齡為論域，取U=0, 100，給出了“年輕”與“年老”這兩的模糊概念的隸屬函數(shù) 一般表示方法 不管論域U是有限的還是無(wú)限的，是連續(xù)的還是離散的，扎德又給

34、出了一種類(lèi)似于積分的一般表示形式： 這里的記號(hào)不是數(shù)學(xué)中的積分符號(hào)，也不是求和，只是表示論域中各元素與其隸屬度對(duì)應(yīng)關(guān)系的總括。,模糊集的表示,定義 設(shè)F、G分別是U 上的兩個(gè)模糊集，對(duì)任意uU，都有 成立，則稱F等于G，記為F=G。,定義 設(shè)F、G分別是U上的兩個(gè)模糊集，對(duì)任意uU，都有 成立，則稱F包含G，記為F G。,模糊集的運(yùn)算,定義 設(shè)F、G分別是U上的兩個(gè)模糊集，則FG、FG分別稱為F與G的并集、交集，它們的隸屬函數(shù)分別為：,定義 設(shè)F為U上的模糊集，稱F為F的補(bǔ)集，其隸屬函數(shù)為：,模糊集的運(yùn)算,62,例5.16 設(shè)U=1,2,3，F(xiàn)和G分別是U上的兩個(gè)模糊集，即 F=小=1/1+0

35、.6/2+0.1/3 G=大=0.1/1+0.6/2+1/3 則 FG=(10.1)/1+(0.60.6)/2+(0.11)/3=1/1+0.6/1+1/3 FG=(10.1)/1+(0.60.6)/2+(0.11)=0.1/1+0.6/2+0.1/3 F=(1-1)/1+(1-0.6)/2+(1-0.1)/3=0.4/2+0.9/3 兩個(gè)模糊集之間的運(yùn)算實(shí)際上就是逐點(diǎn)對(duì)隸屬函數(shù)作相應(yīng)的運(yùn)算。,模糊集的運(yùn)算,“又矮又瘦”,U = 甲, 乙, 丙, 丁 A = “矮子” 隸屬函數(shù) (0.9, 1, 0.6, 0) B = “瘦子” 隸屬函數(shù) (0.8, 0.2, 0.9, 1) 找出 C = “

36、又矮又瘦” C = AB = ( 0.90.8 , 10.2 , 0.60.9 , 01 ) = ( 0.8, 0.2, 0.6, 0) 因此， 甲和丙比較符合條件,描述數(shù)據(jù),一組學(xué)生共10人，考試成績(jī)?yōu)椋?72 68 71 70 86 69 70 82 72 75 如何評(píng)價(jià)上述數(shù)據(jù)？,這些學(xué)生平均分73.5分,這次考試成績(jī)大多數(shù)在分左右，個(gè)別在分以上,精確，但是不直觀,“大多在70分左右，個(gè)別在80分以上”,“大多數(shù)” 0.5/6+0.8/7+1/8+1/9+1/10 “70分左右” 0.5/68+1/69+1/70+1/71+1/72+0.8/73+0.5/74+0.5/75 “個(gè)別” 1

37、/1+1/2+0.5/3 “80分以上” 1/80+1/81+1/82+.+1/100,對(duì)分?jǐn)?shù)問(wèn)題的分析,首先，對(duì)10個(gè)分?jǐn)?shù)求“70分左右”的隸屬度： 1 + 0.5 + 1 + 1 + 0 + 1 + 1 + 0 + 1 + 0.5 = 7 表示約7個(gè)人次在70分左右。 7對(duì)于“大多數(shù)”的隸屬度是0.8 T(“大多數(shù)”) = 0.8 80分以上有2人，2對(duì)于“個(gè)別”的隸屬度為1 T(“個(gè)別”) = 1,72 68 71 70 86 69 70 82 72 75,笛卡爾積：設(shè)V與W是兩個(gè)普通集合，V與W的笛卡爾乘積為 VW =(v,w)任意 ，任意 從V到W的關(guān)系R：VW上的一個(gè)子集，即 R

38、VW 記為 對(duì)于VW中的元素(v,w)，若(v,w)R，則稱v與w有關(guān)系R； 若(v,w) R，則稱v與w沒(méi)有關(guān)系。,模糊關(guān)系的定義,例5.17 設(shè)V=1班，2班，3班，W=男隊(duì)，女隊(duì) 則VW中有6個(gè)元素，即 VW =(1班，男隊(duì))，(2班，男隊(duì))，(3班，男隊(duì))，(1班，女隊(duì))，(2班，女隊(duì))，(3班，女隊(duì)) 其中，每個(gè)元素是一代表隊(duì)。假設(shè)要進(jìn)行一種雙方對(duì)壘的比賽，所有的比賽形成關(guān)系。,模糊關(guān)系的定義,定義 設(shè)Fi是Ui(i=1,2,n)上的模糊集，則稱,為F1,F2,Fn的笛卡爾乘積，它是U1U2Un上的一個(gè)模糊集。,定義 在U1U2Un上的一個(gè)n元模糊關(guān)系R是指以U1U2Un為論域的一個(gè)模糊集，記為,模糊關(guān)系的定義,例 設(shè)有一組學(xué)生 U=u1,u2=秦學(xué)，郝玩，一些在計(jì)算機(jī)上的活動(dòng)V=v1,v2,v3=編程，上網(wǎng)，玩游戲 并設(shè)每個(gè)學(xué)生對(duì)各種活動(dòng)的愛(ài)好程度分別為 i=1,2；j=1,2,3，即 則UV上的模糊關(guān)系R為,模糊關(guān)系的定義,定義 設(shè)R1與R2分別是UV與VW上的兩個(gè)模糊關(guān)系，則R1與R2的合成是從U到W的一個(gè)模糊關(guān)系，記為 R1R2 。其隸屬函數(shù)為 其中，和分別表示取最小和取最大。,模糊關(guān)系的合成,例 設(shè)有以下兩個(gè)