高級人工智能計(jì)算智能資料課件

人工智能計(jì)算智能2016年秋季

羅平luop@人工智能計(jì)算智能2016年秋季

羅平luop@ict.a本章內(nèi)容概述演化計(jì)算模糊計(jì)算本章內(nèi)容概述本章內(nèi)容概述演化計(jì)算模糊計(jì)算本章內(nèi)容概述計(jì)算智能（ComputationalIntelligence，CI）

計(jì)算智能是在神經(jīng)網(wǎng)絡(luò)（NeuralNetworks,NN）、演化計(jì)算（EvolutionaryComputation,EC）及模糊系統(tǒng)（FuzzySystem,FS）這3個(gè)領(lǐng)域發(fā)展相對成熟的基礎(chǔ)上形成的一個(gè)統(tǒng)一的學(xué)科概念。

什么是計(jì)算智能如果一個(gè)系統(tǒng)僅處理低層的數(shù)值數(shù)據(jù)，含有模式識別部件，沒有使用人工智能意義上的知識，且具有計(jì)算適應(yīng)性、計(jì)算容錯(cuò)力、接近人的計(jì)算速度和近似于人的誤差率這4個(gè)特性，則它是計(jì)算智能的。計(jì)算智能（ComputationalIntelligenc神經(jīng)網(wǎng)絡(luò)是一種對人類智能的結(jié)構(gòu)模擬方法，它是通過對大量人工神經(jīng)元的廣泛并行互聯(lián)，構(gòu)造人工神經(jīng)網(wǎng)絡(luò)系統(tǒng)去模擬生物神經(jīng)系統(tǒng)的智能機(jī)理。演化計(jì)算是一種對人類智能的演化模擬方法，它是通過對生物遺傳和演化過程的認(rèn)識，用進(jìn)化算法去模擬人類智能的進(jìn)化規(guī)律的。模糊計(jì)算是一種對人類智能的邏輯模擬方法，它是通過對人類處理模糊現(xiàn)象的認(rèn)知能力的認(rèn)識，用模糊邏輯去模擬人類的智能行為的。神經(jīng)網(wǎng)絡(luò)是一種對人類智能的結(jié)構(gòu)模擬方法，它是通過對大量人工神本章內(nèi)容概述演化計(jì)算模糊計(jì)算本章內(nèi)容概述7演化計(jì)算（EvolutionaryComputation,EC）：在基因和種群層次上模擬自然界生物進(jìn)化過程與機(jī)制的問題求解技術(shù)和計(jì)算模型。思想源于生物遺傳學(xué)和適者生存的自然規(guī)律基于達(dá)爾文（Darwin）的進(jìn)化論和孟德爾（Mendel）的遺傳變異理論典型代表：遺傳算法（GeneticAlgorithm，GA）進(jìn)化策略（EvolutionaryStrategy,ES）進(jìn)化規(guī)劃（EvolutionaryProgramming,EP）遺傳規(guī)劃（GeneticProgramming,GP）演化計(jì)算7演化計(jì)算（EvolutionaryComputation達(dá)爾文的自然選擇學(xué)說是一種被人們廣泛接受的生物進(jìn)化學(xué)說：生物要生存下去，就必須進(jìn)行生存斗爭。具有有利變異的個(gè)體容易存活下來，并且有更多的機(jī)會將有利變異傳給后代；具有不利變異的個(gè)體就容易被淘汰，產(chǎn)生后代的機(jī)會也少的多。適者生存，不適者淘汰：自然選擇。遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。（相對穩(wěn)定+新的物種）演化計(jì)算達(dá)爾文的自然選擇學(xué)說是一種被人們廣泛接受的生物進(jìn)化學(xué)說：演化9孟德爾基因遺傳原理遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個(gè)基因產(chǎn)生的個(gè)體對環(huán)境具有某種適應(yīng)性。基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。演化計(jì)算9孟德爾基因遺傳原理演化計(jì)算10演化計(jì)算：一種模擬自然界生物進(jìn)化過程與機(jī)制進(jìn)行問題求解的自組織、自適應(yīng)的隨機(jī)搜索技術(shù)。演化規(guī)則：“物競天擇、適者生存”演化操作：繁殖（Reproduction）變異（Mutation）競爭（Competition）選擇（Selection）演化計(jì)算及其生物學(xué)基礎(chǔ)10演化計(jì)算：一種模擬自然界生物進(jìn)化過程與機(jī)制進(jìn)行問題求解的遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個(gè)體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目標(biāo)為止基本概念：種群（Population）：多個(gè)備選解的集合。個(gè)體（Individual）：種群中的單個(gè)元素，通常由一個(gè)用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來表示。例如，長度為L

的0、1串染色體（Chromos）：對個(gè)體仿照基因編碼進(jìn)行編碼后所得到的編碼串。染色體中的每一位稱為基因，染色體上由若干個(gè)基因構(gòu)成的一個(gè)有效信息段稱為基因組。遺傳算法遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的基本概念：適應(yīng)度（Fitness）函數(shù)：用來對種群中各個(gè)個(gè)體的環(huán)境適應(yīng)性進(jìn)行度量的函數(shù)，函數(shù)值是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要依據(jù)遺傳操作（GeneticOperator）：作用于種群而產(chǎn)生新的種群的操作。選擇（Selection）交叉（Cross-over）變異（Mutation）遺傳算法基本概念：遺傳算法遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳操作設(shè)計(jì)等幾大部分所組成，算法基本步驟：

選擇編碼策略，將問題搜索空間中每個(gè)可能的點(diǎn)用相應(yīng)的編碼策略表示出來，即形成染色體；定義遺傳策略，包括種群規(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)；對P(t)中的每個(gè)染色體，按概率Pc參與交叉；對染色體中的基因，以概率Pm參與變異運(yùn)算；判斷群體性能是否滿足預(yù)先設(shè)定的終止標(biāo)準(zhǔn)，若不滿足返回(5)。遺傳算法遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度，并進(jìn)行評價(jià)滿足終止條件嗎？終止選擇交叉變異Y編碼和生成初始種群N選擇遺傳算法計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度，并進(jìn)行評價(jià)滿足終止條件嗎？終止選

遺傳算法 生物進(jìn)化適應(yīng)函數(shù) 環(huán)境適應(yīng)函數(shù)值 適應(yīng)性適應(yīng)函數(shù)值最大的解被保留的概率最大 適者生存問題的一個(gè)解

個(gè)體解的編碼 染色體編碼的元素 基因被選定的一組解 群體根據(jù)適應(yīng)函數(shù)選擇的一組解（以編碼形式表示）種群以一定的方式由雙親產(chǎn)生后代的過程 繁殖編碼的某些分量發(fā)生變化的過程 變異遺傳算法與生物進(jìn)化之間對應(yīng)關(guān)系遺傳算法與生物進(jìn)化之間對應(yīng)關(guān)系二進(jìn)制編碼（Binaryencoding）二進(jìn)制編碼是將原問題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。假設(shè)某一參數(shù)的取值范圍是[A，B]，A<B。用長度為L的二進(jìn)制編碼串來表示該參數(shù)，將[A，B]等分成2L-1個(gè)子部分，記每一個(gè)等分的長度為δ。例：假設(shè)變量x的定義域?yàn)閇5，10)，要求的計(jì)算精度為10-5，則需要將[5，10)至少分為1000000個(gè)等長小區(qū)間，每個(gè)小區(qū)間用一個(gè)二進(jìn)制串表示。于是，串長至少等于20，原因是：524288=219<1000000<220=1048576這樣，對應(yīng)于區(qū)間[5，10)內(nèi)滿足精度要求的每個(gè)值x，都可用一個(gè)20位編碼的二進(jìn)制串<b19,b18,…,b0>來表示。優(yōu)點(diǎn)：易于理解和實(shí)現(xiàn)，可表示的模式數(shù)最多主要缺點(diǎn):海明懸崖。

例如，7和8的二進(jìn)制數(shù)分別為0111和1000，當(dāng)算法從7改進(jìn)到8時(shí)，就必須改變所有的位。

遺傳編碼二進(jìn)制編碼（Binaryencoding）遺傳編碼格雷編碼（Grayencoding）要求兩個(gè)連續(xù)整數(shù)的編碼之間只能有一個(gè)碼位不同，其余碼位都是完全相同的。有效地解決了海明懸崖問題。基本原理：二進(jìn)制碼->格雷碼（編碼）：從最右邊一位起，依次將每一位與左邊一位異或(XOR)，作為對應(yīng)格雷碼該位的值，最左邊一位不變；格雷碼-〉二進(jìn)制碼（解碼）：從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值，最左邊一位依然不變。遺傳編碼格雷編碼（Grayencoding）遺傳編碼符號編碼（Symbolencoding）個(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義、而只有代碼含義的符號集。由于是回路，記wn+1=w1。它其實(shí)是1，……，n的一個(gè)循環(huán)排列。要注意w1，w2，……，wn是互不相同的。遺傳編碼例如，對于TSP問題，采用符號編碼方法，按一條回路中城市的次序進(jìn)行編碼，一般情況是從城市w1開始，依次經(jīng)過城市w2

，……，wn，最后回到城市w1，我們就有如下編碼表示：符號編碼（Symbolencoding）由于是回路，記wn適應(yīng)度函數(shù)是一個(gè)用于對個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。個(gè)體的適應(yīng)度值越大，它被遺傳到下一代種群中的概率越大常用的適應(yīng)度函數(shù)原始適應(yīng)度函數(shù):直接將待求解問題的目標(biāo)函數(shù)f(x)定義為遺傳算法的適應(yīng)度函數(shù)。例如：求最大值時(shí)，f(x)即為x的原始適應(yīng)度函數(shù)。優(yōu)點(diǎn)：能夠直接反映出待求解問題的最初求解目標(biāo)，缺點(diǎn)：有可能出現(xiàn)適應(yīng)度值為負(fù)的情況適應(yīng)度函數(shù)適應(yīng)度函數(shù)是一個(gè)用于對個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。個(gè)體的適應(yīng)TSP的目標(biāo)是路徑總長度為最短，路徑總長度可作為TSP問題的適應(yīng)度函數(shù)：適應(yīng)度函數(shù)TSP的目標(biāo)是路徑總長度為最短，路徑總長度可作為TSP問題的標(biāo)準(zhǔn)適應(yīng)度函數(shù)

在遺傳算法中，一般要求適應(yīng)度函數(shù)非負(fù)，并其適應(yīng)度值越大越好。這就往往需要對原始適應(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)。例：對極小化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmax(x)是原始適應(yīng)函數(shù)f(x)的一個(gè)上界。如果fmax(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最大值來代替。fmax(x)是會隨著進(jìn)化代數(shù)的增加而不斷變化的。

適應(yīng)度函數(shù)標(biāo)準(zhǔn)適應(yīng)度函數(shù)適應(yīng)度函數(shù)極大化問題對極大化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmin(x)是原始適應(yīng)函數(shù)f(x)的一個(gè)下界。如果fmin(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最小值來代替。適應(yīng)度函數(shù)極大化問題適應(yīng)度函數(shù)遺傳算法中的基本遺傳操作包括選擇、交叉和變異。選擇(selection)操作:根據(jù)選擇概率按某種策略從當(dāng)前種群中挑選出一定數(shù)目的個(gè)體，使它們能夠有更多的機(jī)會被遺傳到下一代中常用的選擇策略可分為比例選擇、排序選擇和競技選擇三種類型。①比例選擇基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。基本遺傳操作遺傳算法中的基本遺傳操作包括選擇、交叉和變異。基本遺傳操作輪盤賭選擇個(gè)體被選中的概率取決于該個(gè)體的相對適應(yīng)度。而相對適應(yīng)度的定義為：其中，P(xi)是個(gè)體xi的相對適應(yīng)度，即個(gè)體xi被選中的概率；f(xi)是個(gè)體xi的原始適應(yīng)度；是種群的累加適應(yīng)度。輪盤賭選擇算法的基本思想是：根據(jù)每個(gè)個(gè)體的選擇概率P(xi)將一個(gè)圓盤分成N個(gè)扇區(qū)，其中第i個(gè)扇區(qū)的中心角為：并再設(shè)立一個(gè)固定指針。當(dāng)進(jìn)行選擇時(shí)，可以假想轉(zhuǎn)動圓盤，若圓盤靜止時(shí)指針指向第i個(gè)扇區(qū)，則選擇個(gè)體i?；具z傳操作輪盤賭選擇基本遺傳操作P(x1)P(x2)P(xN)……P(xi)2πp(xi)從統(tǒng)計(jì)角度看，個(gè)體的適應(yīng)度值越大，其對應(yīng)的扇區(qū)的面積越大，被選中的可能性也越大。這種方法有點(diǎn)類似于發(fā)放獎品使用的輪盤，并帶有某種賭博的意思，因此亦被稱為輪盤賭選擇?；具z傳操作P(x1)P(x2)P(xN)……P(xi)從統(tǒng)計(jì)角度看，個(gè)交叉(crossover)操作:按照某種方式對選擇的父代個(gè)體的染色體的部分基因進(jìn)行交配重組，從而形成新的個(gè)體。常見的交叉操作：①二進(jìn)制交叉：二進(jìn)制編碼情況下所采用的交叉操作，它主要包括：單點(diǎn)交叉兩點(diǎn)交叉多點(diǎn)交叉均勻交叉基本遺傳操作交叉(crossover)操作:按照某種方式對選擇的父代個(gè)單點(diǎn)交叉先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，然后對這兩個(gè)父代個(gè)體交叉點(diǎn)前面或后面部分的基因進(jìn)行交換，并生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代的個(gè)體串分別是：

X=x1x2…xkxk+1…xn

Y=y1y2…ykyk+1…yn隨機(jī)選擇第k位為交叉點(diǎn)，交叉后生成的兩個(gè)新的個(gè)體是：

X’=x1x2…xkyk+1…yn

Y’=y1y2…ykxk+1…xn

設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為4，

則交叉后生成的兩個(gè)新的個(gè)體是：A’=001111B’=110000基本遺傳操作單點(diǎn)交叉基本遺傳操作兩點(diǎn)交叉先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定兩個(gè)交叉點(diǎn)，然后再按這兩個(gè)交叉點(diǎn)進(jìn)行部分基因交換，生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代的個(gè)體串分別是：

X=x1x2…xi…xj…xn

Y=y1y2…yi…yj…,yn隨機(jī)設(shè)定第i、j位為兩個(gè)交叉點(diǎn)（其中i<j<n），交叉后生成的兩個(gè)新的個(gè)體是：

X’=x1x2…xi

yi+1…yj

xj+1…xn

Y’=y1y2…yi

xi+1…xj

yj+1

…yn

例:設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為3和5，則交叉后的兩個(gè)新的個(gè)體是：A’=001011

B’=110100基本遺傳操作兩點(diǎn)交叉基本遺傳操作均勻交叉先隨機(jī)生成一個(gè)與父串具有相同長度的二進(jìn)制串（交叉模版），然后再利用該模版對兩個(gè)父串進(jìn)行交叉，即將模版中1對應(yīng)的位進(jìn)行交換，而0對應(yīng)的位不交換，依此生成子代中的兩個(gè)新的個(gè)體。事實(shí)上，這種方法對父串中的每一位都是以相同的概率隨機(jī)進(jìn)行交叉的。例5.10

設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)生成的模版T=010011，則交叉后的兩個(gè)新的個(gè)體是A’=011010和B’=100101。即

A：001101B：110010

T：010011A’：01111

0

B’：10000

1基本遺傳操作均勻交叉基本遺傳操作實(shí)值交叉在實(shí)數(shù)編碼情況下所采用的交叉操作，主要包括離散交叉和算術(shù)交叉部分離散交叉：先在兩個(gè)父代個(gè)體的編碼向量中隨機(jī)選擇一部分分量，然后對這部分分量進(jìn)行交換，生成子代中的兩個(gè)新的個(gè)體。整體交叉：對兩個(gè)父代個(gè)體的編碼向量中的所有分量，都以1/2的概率進(jìn)行交換，從而生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代個(gè)體的n維實(shí)向量分別是X=x1x2…xi…xk…xn和Y=y1y2…yi…yk…yn，若隨機(jī)選擇對第k個(gè)分量以后的所有分量進(jìn)行交換，則生成的兩個(gè)新的個(gè)體向量是：

X’=x1x2…xk

yk+1…yn

Y’=y1y2…yk

xk+1…xn

基本遺傳操作實(shí)值交叉基本遺傳操作變異(Mutation)操作:對選中個(gè)體的染色體中的某些基因進(jìn)行變動，以形成新的個(gè)體。遺傳算法中的變異操作增加了算法的局部隨機(jī)搜索能力，從而可以維持種群的多樣性。變異雖然可以帶來群體的多樣性，但因其具有很強(qiáng)的破壞性，因此一般通過一個(gè)很小的變異概率來控制它的使用。根據(jù)個(gè)體編碼方式的不同，變異操作可分為二進(jìn)制變異和實(shí)值變異兩種類型。①二進(jìn)制變異先隨機(jī)地產(chǎn)生一個(gè)變異位，然后將該變異位置上的基因值由“0”變?yōu)椤?”，或由“1”變?yōu)椤?”，產(chǎn)生一個(gè)新的個(gè)體。例5.12設(shè)變異前的個(gè)體為A=001101，若隨機(jī)產(chǎn)生的變異位置是2，則該個(gè)體的第2位由“0”變?yōu)椤?”。變異后的新的個(gè)體是A’=011101?；具z傳操作變異(Mutation)操作:對選中個(gè)體的染色體中的某些基②實(shí)值變異用另外一個(gè)在規(guī)定范圍內(nèi)的隨機(jī)實(shí)數(shù)去替換原變異位置上的基因值，產(chǎn)生一個(gè)新的個(gè)體。最常用的實(shí)值變異操作有:

基于次序的變異:先隨機(jī)地產(chǎn)生兩個(gè)變異位置，然后交換這兩個(gè)變異位置上的基因。

例:設(shè)選中的個(gè)體向量D=201216192130，若隨機(jī)產(chǎn)生的兩個(gè)變異位置分別時(shí)2和4，則變異后的新的個(gè)體向量是：D’=201916122130基本遺傳操作②實(shí)值變異基本遺傳操作精英主義（Elitism）僅僅從產(chǎn)生的子代中選擇基因去構(gòu)造新的種群可能會丟失掉上一代種群中的很多信息。也就是說當(dāng)利用交叉和變異產(chǎn)生新的一代時(shí)，我們有很大的可能把在某個(gè)中間步驟中得到的最優(yōu)解丟失。使用精英主義（Elitism）方法，在每一次產(chǎn)生新的一代時(shí)，我們首先把當(dāng)前最優(yōu)解原封不動的復(fù)制到新的一代中，其他步驟不變。這樣任何時(shí)刻產(chǎn)生的一個(gè)最優(yōu)解都可以存活到遺傳算法結(jié)束。上述各種算子的實(shí)現(xiàn)是多種多樣的，而且許多新的算子正在不斷地提出，以改進(jìn)GA某些性能?；具z傳操作精英主義（Elitism）基本遺傳操作例5.15

用遺傳算法求函數(shù)f(x)=x2的最大值，其中x為[0，31]間的整數(shù)。解：(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個(gè)隨機(jī)生成的長度為5的二進(jìn)制串作為初始種群。再假設(shè)隨機(jī)生成的初始種群（即第0代種群）為：s01=01101s02=11001s03=01000s04=10010遺傳算法應(yīng)用例5.15用遺傳算法求函數(shù)f(x)=x2的最大(3)計(jì)算適應(yīng)度要計(jì)算個(gè)體的適應(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ù)，初始種群中各個(gè)個(gè)體的適應(yīng)值及其所占比例為?？梢钥闯?，在4個(gè)個(gè)體中S02的適應(yīng)值最大，是當(dāng)前最佳個(gè)體。編號個(gè)體串（染色體）x適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S01011011316914.4414.441S02110012562552.8867.182S03010008645.4172.590S04100101832427.411001遺傳算法應(yīng)用(3)計(jì)算適應(yīng)度編號個(gè)體串（染色體）x適應(yīng)值百分比%累計(jì)百（4)選擇操作假設(shè)采用輪盤賭方式選擇個(gè)體，且依次生成的4個(gè)隨機(jī)數(shù)（相當(dāng)于輪盤上指針?biāo)傅臄?shù)）為0.85、0.32、0.12和0.46，經(jīng)選擇后得到的新的種群為：

S01=10010S02=11001S03=01101S04=11001其中，染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適應(yīng)值太小而被淘汰14%

53%

5%

27%

----------|----------------------------|------------|-*-------------------------|

個(gè)體1

個(gè)體2

個(gè)體3

^0.85

個(gè)體4

隨機(jī)數(shù)為0.85落在了個(gè)體4的端內(nèi).本次選擇了個(gè)體4.

遺傳算法應(yīng)用（4)選擇操作14%

53%

(5)交叉假設(shè)交叉概率Pi為50%，則種群中只有1/2的染色體參與交叉。若規(guī)定種群中的染色體按順序兩兩配對交叉，且有S01與S02交叉，S03與S04不交叉，則交叉情況為：可見，經(jīng)交叉后得到的新的種群為：S01=10001S02=11010S03=01101S04=11001編號個(gè)體串（染色體）交叉對象交叉位子代適應(yīng)值S0110010S02310001289S0211001S01311010676S0301101S04N01101169S0411001S03N11001625遺傳算法應(yīng)用(5)交叉編號個(gè)體串（染色體）交叉對象交叉位子代適

(6)變異變異概率Pm一般都很小，假設(shè)本次循環(huán)中沒有發(fā)生變異，則變異前的種群即為進(jìn)化后所得到的第1代種群。即：

S11=10001S12=11010S13=01101S14=11001然后，對第1代種群重復(fù)上述(4)-(6)的操作，選擇情況如下：

其中若假設(shè)按輪盤賭選擇時(shí)依次生成的4個(gè)隨機(jī)數(shù)為0.14、0.51、0.24和0.82，經(jīng)選擇后得到的新的種群為：

S11=10001S12=11010S13=11010S14=11001可以看出，染色體11010被選擇了2次，而原染色體01101則因適應(yīng)值太小而被淘汰。遺傳算法應(yīng)用編號個(gè)體串（染色體）x適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S11100012728916.4316.4371S12110102667638.4354.862S1301101131699.6164.470S14110012562535.531001(6)變異遺傳算法應(yīng)用編號個(gè)體串（染色體）x適應(yīng)值百分對第1代種群，其交叉情況：可見，經(jīng)雜交后得到的新的種群為：

S11=10010S12=11001S13=11001S14=11010

可以看出，第3位基因均為0，已經(jīng)不可能通過交配達(dá)到最優(yōu)解。這種過早陷入局部最優(yōu)解的現(xiàn)象稱為早熟。為解決這一問題，需要采用變異操作。編號個(gè)體串（染色體）交叉對象交叉位子代適應(yīng)值S1110001S12310010324S1211010S11311001625S13110101411001傳算法應(yīng)用對第1代種群，其交叉情況：編號個(gè)體串（染色體）交叉對象交叉位對第1代種群，其變異情況：它是通過對S14的第3位的變異來實(shí)現(xiàn)的。變異后所得到的第2代種群為：

S21=10010S22=11001S23=11001S24=11110

接著，再對第2代種群同樣重復(fù)上述(4)-(6)的操作：編號個(gè)體串（染色體）是否變異變異位子代適應(yīng)值S1110010N10010324S1211001N11001625S1311001N11001625S1411010Y311110900遺傳算法應(yīng)用對第1代種群，其變異情況：編號個(gè)體串（染色體）是否變

對第2代種群，同樣重復(fù)上述(4)-(6)的操作。

其中若假設(shè)按輪盤賭選擇時(shí)依次生成的4個(gè)隨機(jī)數(shù)為0.42、0.15、0.59和0.91，經(jīng)選擇后得到的新的種群為：

S21=11001S22=10010S23=11001S24=11110編號個(gè)體串（染色體）x適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S21100101832423.9223.921S22110012562522.1246.041S23110012562522.1268.161S24111103090031.841001遺傳算法應(yīng)用對第2代種群，同樣重復(fù)上述(4)-(6)的操作。編號個(gè)

對第2代種群，其交叉情況：

這時(shí)，函數(shù)的最大值已經(jīng)出現(xiàn)，其對應(yīng)的染色體為11111，經(jīng)解碼后可知問題的最優(yōu)解是在點(diǎn)x=31處。

求解過程結(jié)束。編號個(gè)體串（染色體）交叉對象交叉位子代適應(yīng)值S2111001S22311010676S2210010S21310001289S2311001S24411000576S2411110S23411111961遺傳算法應(yīng)用對第2代種群，其交叉情況：編號個(gè)體串（染色體）交叉對例子：8皇后問題目標(biāo)：任何一個(gè)皇后都不會攻擊到其他的皇后（皇后可以攻擊和它在同一行、同一列或同一對角線上的皇后）適應(yīng)度函數(shù)取作可以彼此攻擊的皇后對的數(shù)目（忽略障礙）8皇后的例子，其中每個(gè)狀態(tài)用一個(gè)長度為8的字符串來表示，適應(yīng)度函數(shù)取作不相互攻擊的皇后對數(shù)目。例子：8皇后問題目標(biāo)：任何一個(gè)皇后都不會攻擊到其他的皇后（皇問題表示：從k個(gè)隨機(jī)生成的狀態(tài)（種群）開始每個(gè)個(gè)體用一個(gè)有限長度的字符串表示-通常用0，1表示每列八個(gè)皇后的位置：如********8765432132753411011010111101011100001001例子：8皇后問題問題表示：從k個(gè)隨機(jī)生成的狀態(tài)（種群）開始每列八個(gè)皇后的位置通過把兩個(gè)父狀態(tài)結(jié)合來生成后繼例子：8皇后問題通過把兩個(gè)父狀態(tài)結(jié)合來生成后繼例子：8皇后問題遺傳算法特點(diǎn)自組織、自適應(yīng)和自學(xué)習(xí)性—概率轉(zhuǎn)移準(zhǔn)則，非確定性規(guī)則確定進(jìn)化方案后，算法將利用進(jìn)化過程中得到的信息自行組織搜索；基于自然的選擇策略，優(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)遺傳算法特點(diǎn)不需要其他知識，只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)對待求解問題的指標(biāo)函數(shù)沒有什么特殊的要求，如不要求連續(xù)性、導(dǎo)數(shù)存在、單峰值等假設(shè)容易形成通用算法程序遺傳算法不能解決那些“大海撈針”的問題，所謂“大海撈針”問題就是沒有一個(gè)確切的適應(yīng)度函數(shù)表征個(gè)體好壞的問題，遺傳算法對這類問題無法找到收斂的路徑。應(yīng)用廣泛遺傳算法擅長解決的問題是全局最優(yōu)化問題，例如，解決時(shí)間表安排問題就是它的一個(gè)特長，很多安排時(shí)間表的軟件都使用遺傳算法遺傳算法特點(diǎn)不需要其他知識，只需要影響搜索方向的目標(biāo)函數(shù)和相遺傳算法特點(diǎn)理論上證明算法的收斂性很困難多用于解決實(shí)際問題汽車設(shè)計(jì)，包括材料選擇、多目標(biāo)汽車組件設(shè)計(jì)、減輕重量等。機(jī)電系統(tǒng)設(shè)計(jì)。分布計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。電路設(shè)計(jì)，此類用途的遺傳算法叫做進(jìn)化電路。移動通訊優(yōu)化結(jié)構(gòu)。煤氣管道的最優(yōu)控制、通信網(wǎng)絡(luò)鏈接長度的優(yōu)化問題、鐵路運(yùn)輸計(jì)劃優(yōu)化、噴氣式收音機(jī)渦輪機(jī)的設(shè)計(jì)、VLSI版面設(shè)計(jì)、鍵盤排列優(yōu)化抓到老鼠的貓都是好貓遺傳算法特點(diǎn)理論上證明算法的收斂性很困難本章內(nèi)容概述演化計(jì)算模糊計(jì)算本章內(nèi)容概述模糊計(jì)算美國加州大學(xué)扎德(Zadeh)教授于1965年提出的模糊集合與模糊邏輯理論是模糊計(jì)算的數(shù)學(xué)基礎(chǔ)。

發(fā)表了文章《模糊集》(Fuzzysets，InformationandControl,8,338-353)

主要用來處理現(xiàn)實(shí)世界中因模糊而引起的不確定性。模糊理論已經(jīng)在推理、控制、決策等方面得到了非常廣泛的應(yīng)用模糊計(jì)算美國加州大學(xué)扎德(Zadeh)教授于1965年提出的模糊計(jì)算“模糊不是罪過”：模糊≠

”糊涂”,≠

“朦朧”,≠”傻冒”,≠“癡呆”取得精確數(shù)據(jù)不可能或很困難例如：１粒種子肯定不能叫一堆，２粒也不是，３粒也不是……那么多少粒種子叫一堆呢？適當(dāng)?shù)慕缦拊谀睦锬?？我們能否說１２３４５６粒種子不叫一堆，而１２３４５７粒種子叫一堆呢？沒有必要獲取精確數(shù)據(jù)例如：要從一片西瓜地里找出一個(gè)最大的西瓜，那是件很麻煩的事。必須把西瓜地里所有的西瓜都找出來，再比較一下，才知道哪個(gè)西瓜最大。西瓜越多，工作量就越大。如果按通常說的，到西瓜地里去找一個(gè)較大的西瓜，這時(shí)精確的問題就轉(zhuǎn)化成模糊的問題，反而容易多了。由此可見，適當(dāng)?shù)哪：苁箚栴}得到簡化。模糊計(jì)算“模糊不是罪過”：模糊≠”糊涂”,≠“清晰的概念:對象是否屬于這個(gè)概念是明確的。例如；人、自然數(shù)、正方形。模糊性的概念：對象從屬的界限是模糊的，隨判斷人的思維而定“最大的”與“較大的”都是有區(qū)別的兩個(gè)概念。但是它們的區(qū)別都是逐漸的，而不是突變的，兩者之間并不存在明確的界限一個(gè)人很高或很胖，但是究竟多少厘米才算高，多少千克才算胖呢？高和胖都很模糊。飯什么時(shí)候才算熟了？衣服什么樣才能算洗干凈？例如：美不美？早不早？便宜不便宜？在客觀世界中，上述的模糊概念要比清晰概念多得多。模糊計(jì)算清晰的概念:對象是否屬于這個(gè)概念是明確的。模糊計(jì)算要使計(jì)算機(jī)能夠模仿人腦，對復(fù)雜系統(tǒng)進(jìn)行識別和判斷，出路何在？1965年扎德(Zadeh)教授開創(chuàng)了對“模糊數(shù)學(xué)”的研究。他認(rèn)為數(shù)學(xué)是可以模糊的，主張從精度方面“后退”一步。他提出用隸屬函數(shù)使模糊概念數(shù)學(xué)化。例如“年輕”和“年老”這兩個(gè)模糊概念。扎德教授本人根據(jù)統(tǒng)計(jì)資料，擬合了這兩個(gè)概念的隸屬函數(shù)圖象。圖中橫坐標(biāo)表示年齡，縱坐標(biāo)表示隸屬程度。模糊計(jì)算要使計(jì)算機(jī)能夠模仿人腦，對復(fù)雜系統(tǒng)進(jìn)行識別和判斷，出路何在？

定義

設(shè)U是給定論域，是把任意u∈U映射為[0,1]上某個(gè)實(shí)值的函數(shù)，即

：U→[0,1]則稱為定義在U上的一個(gè)隸屬函數(shù)，由（對所有）所構(gòu)成的集合F稱為U上的一個(gè)模糊集，

稱為u對F的隸屬度。模糊集F完全是由隸屬函數(shù)來刻畫的，把U中的每一個(gè)元素u都映射為[0,1]上的一個(gè)值。的值表示u隸屬于F的程度，其值越大，表示u隸屬于F的程度越高。當(dāng)僅取0和1時(shí)，模糊集F便退化為一個(gè)普通集合。模糊集的定義定義設(shè)U是給定論域，是把任意u∈U映射為[0,55

例5.15設(shè)論域U={20,30,40,50,60}給出的是年齡，請確定一個(gè)刻畫模糊概念“年輕”的模糊集F。

解：由于模糊集是用其隸屬函數(shù)來刻畫的，因此需要先求出描述模糊概念“青年”的隸屬函數(shù)。假設(shè)對論域U中的元素，其隸屬函數(shù)值分別為：

則可得到刻畫模糊概念“年輕”的模糊集

F={1,0.8,0.4,0.1,0}

模糊集的定義55例5.15設(shè)論域U={20,30,40,隨機(jī)與模糊：是否與多少模糊性:

事件發(fā)生的程度，而不是一個(gè)事件是否發(fā)生.隨機(jī)性:

描述事件發(fā)生的不確定性,即,一個(gè)事件發(fā)生與否.隨機(jī)與模糊：是否與多少模糊性:離散且為有限論域的表示方法

設(shè)論域U={u1,u2,…,un}為離散論域，則其模糊集可表示為：

F={,,…,}為了能夠表示出論域中的元素與其隸屬度之間的對應(yīng)關(guān)系，扎德引入了一種模糊集的表示方式：先為論域中的每個(gè)元素都標(biāo)上其隸屬度，然后再用“+”號把它們連接起來，即也可寫其中，為ui對F的隸屬度；“/ui”不是相除關(guān)系，只是一個(gè)記號；“+”也不是算術(shù)意義上的加，只是一個(gè)連接符號。

模糊集的表示離散且為有限論域的表示方法模糊集的表示在這種表示方法中，當(dāng)某個(gè)ui對F的隸屬度=0時(shí)，可省略不寫。例如，模糊集F可表示為：

F=1/20+0.8/30+0.6/40+0.2/50

有時(shí)，模糊集也可寫成如下兩種形式：其中，前一種稱為單點(diǎn)形式，后一種稱為序偶形式。模糊集的表示在這種表示方法中，當(dāng)某個(gè)ui對F的隸屬度=0時(shí)，可省略不寫。連續(xù)論域的表示方法如果論域是連續(xù)的，則其模糊集可用一個(gè)實(shí)函數(shù)來表示。例如，扎德以年齡為論域，取U=[0,100]，給出了“年輕”與“年老”這兩的模糊概念的隸屬函數(shù)

一般表示方法不管論域U是有限的還是無限的，是連續(xù)的還是離散的，扎德又給出了一種類似于積分的一般表示形式：

這里的記號不是數(shù)學(xué)中的積分符號，也不是求和，只是表示論域中各元素與其隸屬度對應(yīng)關(guān)系的總括。模糊集的表示連續(xù)論域的表示方法模糊集的表示

定義設(shè)F、G分別是U上的兩個(gè)模糊集，對任意u∈U，都有成立，則稱F等于G，記為F=G。

定義設(shè)F、G分別是U上的兩個(gè)模糊集，對任意u∈U，都有成立，則稱F包含G，記為FG。

模糊集的運(yùn)算定義設(shè)F、G分別是U上的兩個(gè)模糊集，對任意u∈U定義

設(shè)F、G分別是U上的兩個(gè)模糊集，則F∪G、F∩G分別稱為F與G的并集、交集，它們的隸屬函數(shù)分別為：

定義

設(shè)F為U上的模糊集，稱﹁F為F的補(bǔ)集，其隸屬函數(shù)為：

模糊集的運(yùn)算定義設(shè)F、G分別是U上的兩個(gè)模糊集，則F∪G、F∩G分別62

例5.16設(shè)U={1,2,3}，F(xiàn)和G分別是U上的兩個(gè)模糊集，即

F=小=1/1+0.6/2+0.1/3G=大=0.1/1+0.6/2+1/3則F∪G=(1∨0.1)/1+(0.6∨0.6)/2+(0.1∨1)/3=1/1+0.6/1+1/3F∩G=(1∧0.1)/1+(0.6∧0.6)/2+(0.1∧1)=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)對隸屬函數(shù)作相應(yīng)的運(yùn)算。模糊集的運(yùn)算62例5.16設(shè)U={1,2,3}，F(xiàn)和G分別是U上“又矮又瘦”U={甲,乙,丙,丁}A=“矮子”隸屬函數(shù)(0.9,1,0.6,0)B=“瘦子”隸屬函數(shù)(0.8,0.2,0.9,1)找出C=“又矮又瘦”C=A∩B=(0.9∧0.8,1∧0.2,0.6∧0.9,0∧1)

=(0.8,0.2,0.6,0)因此，甲和丙比較符合條件“又矮又瘦”U={甲,乙,丙,丁}描述數(shù)據(jù)一組學(xué)生共10人，考試成績?yōu)椋?/p>

72687170866970827275如何評價(jià)上述數(shù)據(jù)？這些學(xué)生平均分73.5分這次考試成績大多數(shù)在７０分左右，個(gè)別在８０分以上精確，但是不直觀描述數(shù)據(jù)一組學(xué)生共10人，考試成績?yōu)椋哼@些學(xué)生平均分73.5“大多在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/1+1/2+0.5/3“80分以上”1/80+1/81+1/82+...+1/100“大多在70分左右，個(gè)別在80分以上”“大多數(shù)”對分?jǐn)?shù)問題的分析首先，對10個(gè)分?jǐn)?shù)求“70分左右”的隸屬度：1+0.5+1+1+0+1+1+0+1+0.5=7表示約7個(gè)人次在70分左右。7對于“大多數(shù)”的隸屬度是0.8T(“大多數(shù)”)=0.880分以上有2人，2對于“個(gè)別”的隸屬度為1T(“個(gè)別”)=172687170866970827275對分?jǐn)?shù)問題的分析首先，對10個(gè)分?jǐn)?shù)求“70分左右”的隸屬度：笛卡爾積：設(shè)V與W是兩個(gè)普通集合，V與W的笛卡爾乘積為

V×W={(v,w)∣任意，任意}從V到W的關(guān)系R：V×W上的一個(gè)子集，即RV×W記為對于V×W中的元素(v,w)，若(v,w)∈R，則稱v與w有關(guān)系R；若(v,w)R，則稱v與w沒有關(guān)系。模糊關(guān)系的定義笛卡爾積：設(shè)V與W是兩個(gè)普通集合，V與W的笛卡爾乘積為模糊關(guān)

例5.17設(shè)V={1班，2班，3班}，W={男隊(duì)，女隊(duì)}則V×W中有6個(gè)元素，即

V×W={(1班，男隊(duì))，(2班，男隊(duì))，(3班，男隊(duì))，(1班，女隊(duì))，(2班，女隊(duì))，(3班，女隊(duì))}

其中，每個(gè)元素是一代表隊(duì)。假設(shè)要進(jìn)行一種雙方對壘的比賽，所有的比賽形成關(guān)系。

模糊關(guān)系的定義例5.17設(shè)V={1班，2班，3班}，W={男隊(duì)，

定義

設(shè)Fi是Ui(i=1,2,…,n)上的模糊集，則稱

為F1,F2,…,Fn的笛卡爾乘積，它是U1×U2×…×Un上的一個(gè)模糊集。

定義

在U1×U2×…×Un上的一個(gè)n元模糊關(guān)系R是指以U1×U2×…×Un為論域的一個(gè)模糊集，記為模糊關(guān)系的定義定義設(shè)Fi是Ui(i=1,2,…,n)上的模糊集，則稱例

設(shè)有一組學(xué)生U={u1,u2}={秦學(xué)，郝玩}，一些在計(jì)算機(jī)上的活動V={v1,v2,v3}={編程，上網(wǎng)，玩游戲}并設(shè)每個(gè)學(xué)生對各種活動的愛好程度分別為i=1,2；j=1,2,3，即則U×V上的模糊關(guān)系R為模糊關(guān)系的定義例設(shè)有一組學(xué)生U={u1,u2}={秦學(xué)，郝玩}，一些在定義

設(shè)R1與R2分別是U×V與V×W上的兩個(gè)模糊關(guān)系，則R1與R2的合成是從U到W的一個(gè)模糊關(guān)系，記為R1οR2

。其隸屬函數(shù)為其中，∧和∨分別表示取最小和取最大。模糊關(guān)系的合成定義設(shè)R1與R2分別是U×V與V×W上的兩個(gè)模糊關(guān)系，則R例

設(shè)有以下兩個(gè)模糊關(guān)系

則R1與R2的合成是

把R1的第i行元素分別與R2的第j列的對應(yīng)元素相比較，兩個(gè)數(shù)中取最小者，然后再在所得的一組最小數(shù)中取最大的一個(gè)，并以此數(shù)作為R1οR2的元素R(i,j)。模糊關(guān)系的合成類比矩陣乘法例設(shè)有以下兩個(gè)模糊關(guān)系則R1與R2的合成是把R1的第i例

設(shè)有：一組學(xué)生U={u1,u2}={秦學(xué)，郝玩}，一些在計(jì)算機(jī)上的活動V={v1,v2,v3}={編程，上網(wǎng)，玩游戲}一些對學(xué)生的評價(jià)G={g1,g2,g3}={好，中等，差}若已知U和V的模糊關(guān)系，V和G的模糊關(guān)系，那么，我們就可以合成出U和G的模糊關(guān)系模糊關(guān)系合成舉例例設(shè)有：模糊關(guān)系合成舉例74

模糊邏輯：定義模糊謂詞、模糊量詞、模糊修飾語等模糊謂詞設(shè)x∈U，F(xiàn)為模糊謂詞，即U中的一個(gè)模糊關(guān)系，則模糊命題可表示為

xisF其中的模糊謂詞F可以是大、小、年輕、年老、冷、暖、長、短等。模糊量詞模糊邏輯中使用的模糊量詞，如極少、很少、幾個(gè)、少數(shù)、多數(shù)、大多數(shù)、幾乎所有等。

模糊邏輯74模糊邏輯：定義模糊謂詞、模糊量詞、模糊修飾語等模75

模糊修飾語設(shè)m是模糊修飾語，x是變量，F(xiàn)謂模糊謂詞，則模糊命題可表示為xismF，模糊修飾語也稱為程度詞，常用的程度詞有“很”、“非?！?、“有些”、“絕對”等。模糊修飾語的四種主要運(yùn)算：①求補(bǔ)

表示否定，如“不”、“非”等，其隸屬函數(shù)的表示為

②集中

表示“很”、“非?！钡?，其效果是減少隸屬函數(shù)的值：

③擴(kuò)張表示“有些”、“稍微”等，其效果是增加隸屬函數(shù)的值：

模糊邏輯75模糊修飾語②集中表示“很”、“非常”等76④加強(qiáng)對比

表示“明確”、“確定”等，其效果是增加0.5以上隸屬函數(shù)的值，減少0.5以下隸屬函數(shù)的值：

模糊邏輯76④加強(qiáng)對比表示“明確”、“確定”等，其效果77

模糊假言三段論推理

設(shè)F、G、H分別是U、V、W上的3個(gè)模糊集，且由知識

IFxisFTHENyisGIFyisGTHENzisH則可推出:IFxisFTHENzisH

這種推理模式稱為模糊假言三段論推理。它可表示為：知識：IFxisFTHENyisG

證據(jù)：IFyisGTHENzisH---------------------------------------------------------

結(jié)論：IFxisFTHENzisH模糊推理方法77模糊假言三段論推理模糊推理方法78

模糊假言三段論推理在模糊假言三段論推理模式下，模糊知識

r1:IFxisFTHENyisG表示在F與G之間存在著確定的因果關(guān)系，設(shè)此因果關(guān)系為R1。模糊知識

r2:IFyisGTHENzisH表示在G與H之間存在著確定的因果關(guān)系，設(shè)此因果關(guān)系為R2。若模糊假言三段論成立，則模糊結(jié)論

r3：IFxisFTHENzisH的模糊關(guān)系R3可由R1與R2的合成得到。即

R3=R1οR2

模糊推理方法78模糊假言三段論推理模糊推理方法79

模糊假言三段論推理

例：

已知：E×F上的關(guān)系R1

和F×G上的關(guān)系R2

模糊推理方法

求E×G上的關(guān)系R

79模糊假言三段論推理和F×G上的關(guān)系R280大多數(shù)成績好的學(xué)生學(xué)習(xí)都很刻苦。很少有成績好的學(xué)生特別貪玩。模糊邏輯知識表示舉例80大多數(shù)成績好的學(xué)生學(xué)習(xí)都很刻苦。模糊邏輯知識模糊集的應(yīng)用模式識別圖像視覺語音識別智能控制智能家電…洗衣機(jī)、攝像機(jī)、照相機(jī)、電飯鍋、空調(diào)、電梯日本:地鐵列車自動運(yùn)轉(zhuǎn)，自來水廠凈化處理數(shù)據(jù)挖據(jù)模糊集的應(yīng)用模式識別模糊數(shù)學(xué)領(lǐng)域

期刊Int.J.ofFuzzySetsandSystemsInt.J.ofApproximateReasoningInt.J.FuzzyMathematicsInt.J.Uncertainty,Fuzziness,knowledge-basedSystemsIEEETransactionsonFuzzySystemsIFSA(Int.FuzzySystemsAssociation)EUFIT、NAFIP、Fuzzy-IEEE、IPMU

國際會議模糊代數(shù)，模糊拓?fù)?，模糊邏輯，模糊分析，模糊概率，模糊圖論，模糊優(yōu)化等模糊數(shù)學(xué)分支

領(lǐng)域模糊數(shù)學(xué)領(lǐng)域期刊Int.J.ofFuzzySets人工智能計(jì)算智能2016年秋季

羅平luop@人工智能計(jì)算智能2016年秋季

羅平luop@ict.a本章內(nèi)容概述演化計(jì)算模糊計(jì)算本章內(nèi)容概述本章內(nèi)容概述演化計(jì)算模糊計(jì)算本章內(nèi)容概述計(jì)算智能（ComputationalIntelligence，CI）

計(jì)算智能是在神經(jīng)網(wǎng)絡(luò)（NeuralNetworks,NN）、演化計(jì)算（EvolutionaryComputation,EC）及模糊系統(tǒng)（FuzzySystem,FS）這3個(gè)領(lǐng)域發(fā)展相對成熟的基礎(chǔ)上形成的一個(gè)統(tǒng)一的學(xué)科概念。

什么是計(jì)算智能如果一個(gè)系統(tǒng)僅處理低層的數(shù)值數(shù)據(jù)，含有模式識別部件，沒有使用人工智能意義上的知識，且具有計(jì)算適應(yīng)性、計(jì)算容錯(cuò)力、接近人的計(jì)算速度和近似于人的誤差率這4個(gè)特性，則它是計(jì)算智能的。計(jì)算智能（ComputationalIntelligenc神經(jīng)網(wǎng)絡(luò)是一種對人類智能的結(jié)構(gòu)模擬方法，它是通過對大量人工神經(jīng)元的廣泛并行互聯(lián)，構(gòu)造人工神經(jīng)網(wǎng)絡(luò)系統(tǒng)去模擬生物神經(jīng)系統(tǒng)的智能機(jī)理。演化計(jì)算是一種對人類智能的演化模擬方法，它是通過對生物遺傳和演化過程的認(rèn)識，用進(jìn)化算法去模擬人類智能的進(jìn)化規(guī)律的。模糊計(jì)算是一種對人類智能的邏輯模擬方法，它是通過對人類處理模糊現(xiàn)象的認(rèn)知能力的認(rèn)識，用模糊邏輯去模擬人類的智能行為的。神經(jīng)網(wǎng)絡(luò)是一種對人類智能的結(jié)構(gòu)模擬方法，它是通過對大量人工神本章內(nèi)容概述演化計(jì)算模糊計(jì)算本章內(nèi)容概述89演化計(jì)算（EvolutionaryComputation,EC）：在基因和種群層次上模擬自然界生物進(jìn)化過程與機(jī)制的問題求解技術(shù)和計(jì)算模型。思想源于生物遺傳學(xué)和適者生存的自然規(guī)律基于達(dá)爾文（Darwin）的進(jìn)化論和孟德爾（Mendel）的遺傳變異理論典型代表：遺傳算法（GeneticAlgorithm，GA）進(jìn)化策略（EvolutionaryStrategy,ES）進(jìn)化規(guī)劃（EvolutionaryProgramming,EP）遺傳規(guī)劃（GeneticProgramming,GP）演化計(jì)算7演化計(jì)算（EvolutionaryComputation達(dá)爾文的自然選擇學(xué)說是一種被人們廣泛接受的生物進(jìn)化學(xué)說：生物要生存下去，就必須進(jìn)行生存斗爭。具有有利變異的個(gè)體容易存活下來，并且有更多的機(jī)會將有利變異傳給后代；具有不利變異的個(gè)體就容易被淘汰，產(chǎn)生后代的機(jī)會也少的多。適者生存，不適者淘汰：自然選擇。遺傳和變異是決定生物進(jìn)化的內(nèi)在因素。（相對穩(wěn)定+新的物種）演化計(jì)算達(dá)爾文的自然選擇學(xué)說是一種被人們廣泛接受的生物進(jìn)化學(xué)說：演化91孟德爾基因遺傳原理遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個(gè)基因產(chǎn)生的個(gè)體對環(huán)境具有某種適應(yīng)性。基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。演化計(jì)算9孟德爾基因遺傳原理演化計(jì)算92演化計(jì)算：一種模擬自然界生物進(jìn)化過程與機(jī)制進(jìn)行問題求解的自組織、自適應(yīng)的隨機(jī)搜索技術(shù)。演化規(guī)則：“物競天擇、適者生存”演化操作：繁殖（Reproduction）變異（Mutation）競爭（Competition）選擇（Selection）演化計(jì)算及其生物學(xué)基礎(chǔ)10演化計(jì)算：一種模擬自然界生物進(jìn)化過程與機(jī)制進(jìn)行問題求解的遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個(gè)體，并通過雜交、變異來產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目標(biāo)為止基本概念：種群（Population）：多個(gè)備選解的集合。個(gè)體（Individual）：種群中的單個(gè)元素，通常由一個(gè)用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來表示。例如，長度為L

的0、1串染色體（Chromos）：對個(gè)體仿照基因編碼進(jìn)行編碼后所得到的編碼串。染色體中的每一位稱為基因，染色體上由若干個(gè)基因構(gòu)成的一個(gè)有效信息段稱為基因組。遺傳算法遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的基本概念：適應(yīng)度（Fitness）函數(shù)：用來對種群中各個(gè)個(gè)體的環(huán)境適應(yīng)性進(jìn)行度量的函數(shù)，函數(shù)值是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要依據(jù)遺傳操作（GeneticOperator）：作用于種群而產(chǎn)生新的種群的操作。選擇（Selection）交叉（Cross-over）變異（Mutation）遺傳算法基本概念：遺傳算法遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳操作設(shè)計(jì)等幾大部分所組成，算法基本步驟：

選擇編碼策略，將問題搜索空間中每個(gè)可能的點(diǎn)用相應(yīng)的編碼策略表示出來，即形成染色體；定義遺傳策略，包括種群規(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)；對P(t)中的每個(gè)染色體，按概率Pc參與交叉；對染色體中的基因，以概率Pm參與變異運(yùn)算；判斷群體性能是否滿足預(yù)先設(shè)定的終止標(biāo)準(zhǔn)，若不滿足返回(5)。遺傳算法遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度，并進(jìn)行評價(jià)滿足終止條件嗎？終止選擇交叉變異Y編碼和生成初始種群N選擇遺傳算法計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度，并進(jìn)行評價(jià)滿足終止條件嗎？終止選

遺傳算法 生物進(jìn)化適應(yīng)函數(shù) 環(huán)境適應(yīng)函數(shù)值 適應(yīng)性適應(yīng)函數(shù)值最大的解被保留的概率最大 適者生存問題的一個(gè)解

個(gè)體解的編碼 染色體編碼的元素 基因被選定的一組解 群體根據(jù)適應(yīng)函數(shù)選擇的一組解（以編碼形式表示）種群以一定的方式由雙親產(chǎn)生后代的過程 繁殖編碼的某些分量發(fā)生變化的過程 變異遺傳算法與生物進(jìn)化之間對應(yīng)關(guān)系遺傳算法與生物進(jìn)化之間對應(yīng)關(guān)系二進(jìn)制編碼（Binaryencoding）二進(jìn)制編碼是將原問題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。假設(shè)某一參數(shù)的取值范圍是[A，B]，A<B。用長度為L的二進(jìn)制編碼串來表示該參數(shù)，將[A，B]等分成2L-1個(gè)子部分，記每一個(gè)等分的長度為δ。例：假設(shè)變量x的定義域?yàn)閇5，10)，要求的計(jì)算精度為10-5，則需要將[5，10)至少分為1000000個(gè)等長小區(qū)間，每個(gè)小區(qū)間用一個(gè)二進(jìn)制串表示。于是，串長至少等于20，原因是：524288=219<1000000<220=1048576這樣，對應(yīng)于區(qū)間[5，10)內(nèi)滿足精度要求的每個(gè)值x，都可用一個(gè)20位編碼的二進(jìn)制串<b19,b18,…,b0>來表示。優(yōu)點(diǎn)：易于理解和實(shí)現(xiàn)，可表示的模式數(shù)最多主要缺點(diǎn):海明懸崖。

例如，7和8的二進(jìn)制數(shù)分別為0111和1000，當(dāng)算法從7改進(jìn)到8時(shí)，就必須改變所有的位。

遺傳編碼二進(jìn)制編碼（Binaryencoding）遺傳編碼格雷編碼（Grayencoding）要求兩個(gè)連續(xù)整數(shù)的編碼之間只能有一個(gè)碼位不同，其余碼位都是完全相同的。有效地解決了海明懸崖問題?；驹恚憾M(jìn)制碼->格雷碼（編碼）：從最右邊一位起，依次將每一位與左邊一位異或(XOR)，作為對應(yīng)格雷碼該位的值，最左邊一位不變；格雷碼-〉二進(jìn)制碼（解碼）：從左邊第二位起，將每位與左邊一位解碼后的值異或，作為該位解碼后的值，最左邊一位依然不變。遺傳編碼格雷編碼（Grayencoding）遺傳編碼符號編碼（Symbolencoding）個(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義、而只有代碼含義的符號集。由于是回路，記wn+1=w1。它其實(shí)是1，……，n的一個(gè)循環(huán)排列。要注意w1，w2，……，wn是互不相同的。遺傳編碼例如，對于TSP問題，采用符號編碼方法，按一條回路中城市的次序進(jìn)行編碼，一般情況是從城市w1開始，依次經(jīng)過城市w2

，……，wn，最后回到城市w1，我們就有如下編碼表示：符號編碼（Symbolencoding）由于是回路，記wn適應(yīng)度函數(shù)是一個(gè)用于對個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。個(gè)體的適應(yīng)度值越大，它被遺傳到下一代種群中的概率越大常用的適應(yīng)度函數(shù)原始適應(yīng)度函數(shù):直接將待求解問題的目標(biāo)函數(shù)f(x)定義為遺傳算法的適應(yīng)度函數(shù)。例如：求最大值時(shí)，f(x)即為x的原始適應(yīng)度函數(shù)。優(yōu)點(diǎn)：能夠直接反映出待求解問題的最初求解目標(biāo)，缺點(diǎn)：有可能出現(xiàn)適應(yīng)度值為負(fù)的情況適應(yīng)度函數(shù)適應(yīng)度函數(shù)是一個(gè)用于對個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。個(gè)體的適應(yīng)TSP的目標(biāo)是路徑總長度為最短，路徑總長度可作為TSP問題的適應(yīng)度函數(shù)：適應(yīng)度函數(shù)TSP的目標(biāo)是路徑總長度為最短，路徑總長度可作為TSP問題的標(biāo)準(zhǔn)適應(yīng)度函數(shù)

在遺傳算法中，一般要求適應(yīng)度函數(shù)非負(fù)，并其適應(yīng)度值越大越好。這就往往需要對原始適應(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)。例：對極小化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmax(x)是原始適應(yīng)函數(shù)f(x)的一個(gè)上界。如果fmax(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最大值來代替。fmax(x)是會隨著進(jìn)化代數(shù)的增加而不斷變化的。

適應(yīng)度函數(shù)標(biāo)準(zhǔn)適應(yīng)度函數(shù)適應(yīng)度函數(shù)極大化問題對極大化問題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為其中，fmin(x)是原始適應(yīng)函數(shù)f(x)的一個(gè)下界。如果fmin(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最小值來代替。適應(yīng)度函數(shù)極大化問題適應(yīng)度函數(shù)遺傳算法中的基本遺傳操作包括選擇、交叉和變異。選擇(selection)操作:根據(jù)選擇概率按某種策略從當(dāng)前種群中挑選出一定數(shù)目的個(gè)體，使它們能夠有更多的機(jī)會被遺傳到下一代中常用的選擇策略可分為比例選擇、排序選擇和競技選擇三種類型。①比例選擇基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比?；具z傳操作遺傳算法中的基本遺傳操作包括選擇、交叉和變異?；具z傳操作輪盤賭選擇個(gè)體被選中的概率取決于該個(gè)體的相對適應(yīng)度。而相對適應(yīng)度的定義為：其中，P(xi)是個(gè)體xi的相對適應(yīng)度，即個(gè)體xi被選中的概率；f(xi)是個(gè)體xi的原始適應(yīng)度；是種群的累加適應(yīng)度。輪盤賭選擇算法的基本思想是：根據(jù)每個(gè)個(gè)體的選擇概率P(xi)將一個(gè)圓盤分成N個(gè)扇區(qū)，其中第i個(gè)扇區(qū)的中心角為：并再設(shè)立一個(gè)固定指針。當(dāng)進(jìn)行選擇時(shí)，可以假想轉(zhuǎn)動圓盤，若圓盤靜止時(shí)指針指向第i個(gè)扇區(qū)，則選擇個(gè)體i。基本遺傳操作輪盤賭選擇基本遺傳操作P(x1)P(x2)P(xN)……P(xi)2πp(xi)從統(tǒng)計(jì)角度看，個(gè)體的適應(yīng)度值越大，其對應(yīng)的扇區(qū)的面積越大，被選中的可能性也越大。這種方法有點(diǎn)類似于發(fā)放獎品使用的輪盤，并帶有某種賭博的意思，因此亦被稱為輪盤賭選擇。基本遺傳操作P(x1)P(x2)P(xN)……P(xi)從統(tǒng)計(jì)角度看，個(gè)交叉(crossover)操作:按照某種方式對選擇的父代個(gè)體的染色體的部分基因進(jìn)行交配重組，從而形成新的個(gè)體。常見的交叉操作：①二進(jìn)制交叉：二進(jìn)制編碼情況下所采用的交叉操作，它主要包括：單點(diǎn)交叉兩點(diǎn)交叉多點(diǎn)交叉均勻交叉基本遺傳操作交叉(crossover)操作:按照某種方式對選擇的父代個(gè)單點(diǎn)交叉先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，然后對這兩個(gè)父代個(gè)體交叉點(diǎn)前面或后面部分的基因進(jìn)行交換，并生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代的個(gè)體串分別是：

X=x1x2…xkxk+1…xn

Y=y1y2…ykyk+1…yn隨機(jī)選擇第k位為交叉點(diǎn)，交叉后生成的兩個(gè)新的個(gè)體是：

X’=x1x2…xkyk+1…yn

Y’=y1y2…ykxk+1…xn

設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為4，

則交叉后生成的兩個(gè)新的個(gè)體是：A’=001111B’=110000基本遺傳操作單點(diǎn)交叉基本遺傳操作兩點(diǎn)交叉先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定兩個(gè)交叉點(diǎn)，然后再按這兩個(gè)交叉點(diǎn)進(jìn)行部分基因交換，生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代的個(gè)體串分別是：

X=x1x2…xi…xj…xn

Y=y1y2…yi…yj…,yn隨機(jī)設(shè)定第i、j位為兩個(gè)交叉點(diǎn)（其中i<j<n），交叉后生成的兩個(gè)新的個(gè)體是：

X’=x1x2…xi

yi+1…yj

xj+1…xn

Y’=y1y2…y