1、第6章 計(jì)算智能,1,6.1 神經(jīng)網(wǎng)絡(luò) 6.2 遺傳算法 6.3 模糊計(jì)算 6.4 粒群優(yōu)化 6.5 人工免疫 CI AI BI,AArtificial BBiological CComputational,6.1神經(jīng)網(wǎng)絡(luò),2,3.5.1 神經(jīng)網(wǎng)絡(luò)的基本知識(shí),(neural net),神經(jīng)元、連接權(quán)值、閾值，激勵(lì)函數(shù)、, 神經(jīng)元模型(B-P), 激勵(lì)函數(shù)（作用,非線性體現(xiàn)）,Sigmoid函數(shù) f = 1/(1+ex ) 壓縮映射，多階連續(xù)可微,神經(jīng)網(wǎng)絡(luò)例子,x1 x2 Z 0 0 0 0 1 1 1 0 1 1 1 0,Yj=f( xi wij ) =U( xi wij ) w11 =5.2

2、4；w12 = 5.23； w21 = 6.68； w22 = 6.64； 1 = 8.01； 2 = 2.98； T1 = 10； T2 = 10； = 4.79,T1= U(0 5.24 + 0 5.23 8.01 )= U ( 8.01) =0 T2= U(0 6.68 + 0 6.64 2.98 )= U ( 2.98 ) =0 Z= U(0 )( 10) + (0 10) 4.79 )= U ( 4.79) =0 T1= U(0 5.24 + 1 5.23 8.01 )= U ( 2.85) =0 T2= U(0 6.68 + 1 6.64 2.98 )= U (3.66 ) =1

3、Z= U(0 )( 10) + (1 10) 4.79 )= U (5.21) =1,識(shí)別四個(gè)動(dòng)物的神經(jīng)網(wǎng)絡(luò)例子,模式識(shí)別,四個(gè)動(dòng)物的樣本 (1) 某動(dòng)物特征是暗斑點(diǎn)、黃褐色、有毛發(fā)、吃肉，它就是豹。 (2) 某動(dòng)物特征是黃褐色、有毛發(fā)、吃肉、黑條紋，它就是虎。 (3) 某動(dòng)物特征是不飛、黑白色、會(huì)游泳、有羽毛，它就是企鵝。 (4) 某動(dòng)物特征是有羽毛、善飛，它就是信天翁。,暗斑點(diǎn) 黃褐色 有毛發(fā) 吃肉 黑條紋 不飛 黑白色 會(huì)游泳 有羽毛 善飛 編 碼 動(dòng)物名 1 111 0 0 0 0 0 0 1 0 0 0 豹 0 111 1 0 0 0 0 0 0 1 0 0 虎 0 000 0 1

4、1 1 1 0 0 0 1 0 企鵝 0 000 0 0 0 0 1 1 0 0 0 1 信天翁,結(jié)果,輸入輸 出 輸出相近 暗 黃 毛 肉 紋 不飛 黑白 泳 羽 飛 豹 虎 企鵝 信天翁 1 0 1 0 0 0 0 0 0 0.8463 0.0245 0.048l 0.0950 豹 0 1 0 1 1 0 0 0 0 0.0200 0.9473 0.0204 0.0030 虎 0 0 0 0 1 1 1 1 1 0.0148 0.2133 0.8971 0.0978 企鵝 0 0 0 0 0 0 0 1 0 0.1156 0.0298 0.1262 0.6662 信天翁 1 1 1 0 0

5、 0 0 0 0 0.8677 0.0231 0.0647 0.071l 豹 0 0 0 0 0 0 0 0 0 0.1798 0.0283 0.0125 0.9043 信天翁 0 0 1 1 1 1 0 0 0 0.0140 0.9286 0.0368 0.0029 虎 1 0 0 1 0 0 0 0 0 0.8486 0.0193 0.0550 0.1618 豹 0 1 0 0 1 0 0 0 0 0.0241 0.9291 0.0358 0.0044 虎 0 0 0 0 0 0 1 0 1 0.0735 0.0296 0.6562 0.1502 企鵝 0 1 1 1 0 0 0 0 0

6、0.3394 0.4203 0.0317 0.0135 豹，虎 1 1 0 0 0 1 1 0 0 0.6774 0.0200 0.3668 0.0461 豹，企鵝 0 0 1 1 0 0 1 1 0 0.0455 0.2547 0.4704 0.0124 虎，企鵝 1 1 1 0 0 1 1 0 1 0.4067 0.0236 0.1170 0.0577 豹，企鵝,B-P神經(jīng)網(wǎng)絡(luò),1 給定神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu) （三層： 輸入層（輸入神經(jīng)元=輸入維數(shù)） 隱含層、（?） 輸出層： （輸出神經(jīng)元=輸出個(gè)數(shù)） 2 給定初始權(quán)值、閾值。 3 運(yùn)用樣本，按公式計(jì)算每個(gè)神經(jīng)遠(yuǎn)的輸出，直至輸出神經(jīng)元 4 求出誤差

7、5 反向送回。 根據(jù)誤差的大?。ㄌ荻认陆?，確定步長(zhǎng)），修正權(quán)值、閾值 6 直至誤差在允許范圍內(nèi)。 注意問題 收斂性（能否，速度） 局部最優(yōu)問題（梯度）,BACK-PROPAGATION,神經(jīng)網(wǎng)絡(luò)特點(diǎn),1)學(xué)習(xí)能力。學(xué)習(xí)能力是神經(jīng)網(wǎng)絡(luò)具有智能的重要表現(xiàn)，即通過訓(xùn)練可抽 象出訓(xùn)練本的主要特征，表現(xiàn)出強(qiáng)大的自適應(yīng)能力。 2)分布式。信息則分散分布在神經(jīng)元的聯(lián)接上，神經(jīng)元組合起來，就能從 宏觀上反映一定的信息特征。對(duì)個(gè)別神經(jīng)元和連接權(quán)值的損壞，并不會(huì)對(duì) 信息特征造成太大的影響，現(xiàn)了神經(jīng)網(wǎng)絡(luò)強(qiáng)大的魯棒性和容錯(cuò)能力。 3)并行性。神經(jīng)網(wǎng)絡(luò)偏重對(duì)結(jié)構(gòu)的模擬。各種神元在處理信息時(shí)是各自 獨(dú)立的，它們分別接受輸

8、入，作用后產(chǎn)生輸出。并行計(jì)算可能用于適時(shí) 快速處理信息。 4)非線性。可有效地實(shí)現(xiàn)輸入空間到輸出空間的非線性映射。尋求輸入到 出間的非線性關(guān)系模型，成為非線性系統(tǒng)研究的重要工具。 黑箱映射,6.2遺傳算法,9, 生物學(xué)知識(shí)： 染色體、基因、基因座、 個(gè)體、種群、適應(yīng)度、 物種選擇、雜交、變異。 選擇、雜交與變異3個(gè)主要的算子：,(genetic algorithmGA),物競(jìng)天擇，適者生存, 1參數(shù)編碼,10,遺傳算法一般不能直接處理問題空間的參數(shù)，必須把它們轉(zhuǎn)化成遺傳空間 由基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，這種轉(zhuǎn)換操作就稱為編碼。 (1) 完備性：?jiǎn)栴}的所有候選解都能被遺傳空間中的點(diǎn)(染色

9、體)所表現(xiàn) ； (2) 健全性：遺傳空間的染色體能對(duì)應(yīng)所有問題空間的候選解； (3) 非冗余性：染色體和候選解一一對(duì)應(yīng)。 2初始種群的生成 遺傳算法具有群體型操作的特點(diǎn)，必須為其準(zhǔn)備一個(gè)由若干初始解組成的 初始種群。遺傳算法以此為起點(diǎn)經(jīng)過一代代進(jìn)化直到終止，得到最后一代 (或種群)。初始種群中的個(gè)體一般是隨機(jī)產(chǎn)生的。 初始種群的確定原則： (1)基于問題的先驗(yàn)知識(shí)，確定最優(yōu)解所占空間在整個(gè)問題空間中的分布 范圍，然后在此范圍內(nèi)設(shè)定初始種群； (2)先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑選出最好的個(gè)體加入到初始 種群中去。,110 01 00 10 11 010, 3適應(yīng)度函數(shù)的設(shè)計(jì),11,設(shè)計(jì)適

10、應(yīng)度函數(shù)的主要方法是把問題的目標(biāo)函數(shù)轉(zhuǎn)換成合適的適應(yīng)度函數(shù) 評(píng)價(jià)指標(biāo)； 能滿足強(qiáng)約束條件 4. 遺傳操作設(shè)計(jì) 遺傳操作包括選擇、雜交與變異3個(gè)主要的算子： 確定選擇算子的方法主要有： (1) Montecarlo方法，也叫賭輪方法； (2) 最佳個(gè)體保存方法； (3) 期望值方法； (4) 排序方法； (5) 聯(lián)賽選擇方法；, 4雜交算子,12,雜交算子是遺傳算法中的核心操作算子，該算子與自然界生物基因的 重組的作用相當(dāng)。 雜交操作就是把配好對(duì)的兩個(gè)父本個(gè)體的部分結(jié)構(gòu)加以替換重組， 而生成新個(gè)體的操作?；镜碾s交算子有： (1)一點(diǎn)雜交(onepoint crossover)； (2)兩點(diǎn)雜交

11、(two-point crossover)； (3)多點(diǎn)雜交(multi-point crossover)； (4)一致雜交(uniform crossover)等。 變異算子的功能就是對(duì)個(gè)體串的某些基因座上的基因值作變動(dòng)。10，01） 5. 控制參數(shù)設(shè)定 (主要指種群的規(guī)模和采用的遺傳操作的概率等)。,Schaffer漣漪函數(shù),13,遺傳算法例子MAX: f(x1,x2)=x12+x22,14,MAX: f(x1,x2)=x12+x22 x1,x2 (空間很?。?個(gè)體編號(hào)初始群體P(0) 適應(yīng)度 f / f 選擇次數(shù)(輪盤概率) 1 011 101 3534 f= 143 0.24 1 01

12、1101(1) 2 101 011 5334 fMAX =50 0.24 1 111001 (4) 3 011 100 3425 0. 17 0 101011 (2) 4 111 001 7 1 50 f均=35.75 0.35 2 111001 (4) 配對(duì)交叉點(diǎn)位置交叉結(jié)果變異點(diǎn)變異結(jié)果（子代P(1) ） 3 011001 4 011101 f= 235 3，5 1-2 3111101 5 111111 fMAX =98 7，7 3-4 5111001 2 111001 7，1 5111011 6 111010 f均=58.75 7，2,遺傳算法的特點(diǎn),15,(1) 以決策變量的編碼作為運(yùn)

13、算對(duì)象?？梢赃m合一些無數(shù)值概念或很 難有數(shù)值概念。(步驟，顏色，） (2) 遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息。 遺傳算法僅使用由目標(biāo)函數(shù)值變換來的適應(yīng)度函數(shù)值，就可確定進(jìn)一步 的搜索方向和搜索范圍，無需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。 搜索范圍集中到適應(yīng)度較高的部分搜索空間中，從而提高了搜索效率。 (3) 遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。 （初始種群的位置，隱含并行性。） (4) 遺傳算法使用概率搜索技術(shù)。 不同很多傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法， 增加了其搜索過程的靈活性。,6.3 模糊計(jì)算,16,(思路方法）,“非此即彼”, “亦此亦彼”的現(xiàn)象。 不相容原理 人腦

14、的思維活動(dòng)具有兩重性 運(yùn)用數(shù)學(xué)方法來描述模糊概念，其關(guān)鍵的思想是承認(rèn)由于客觀事物的差異所 引起的中介過渡的“不分明性”，允許“漸變的關(guān)系”，即承認(rèn)一個(gè)集合可以有 部分屬于它的元素，一個(gè)命題也可能部分為真和部分為假。 模糊搜索、模糊決策、模糊控制、模糊專家系統(tǒng)、模糊數(shù)據(jù)庫、 模糊模式識(shí)別、模糊數(shù)字模擬電路，模糊神經(jīng)網(wǎng)絡(luò)以及 模糊計(jì)算機(jī)和模糊軟件,17,6.3 模糊信息處理,3.7.1 模糊集合的基本概念 1 模糊子集的定義 定義給定論域U上的一個(gè)模糊子集A，對(duì)于任意uU，都指定了一個(gè)數(shù) A(u)0，1，叫做u對(duì)A的隸屬程度。 即映射：A(u)：U0，1uA(u) ,則A叫u對(duì)A的隸屬函數(shù) 模糊子

15、集完全由其隸屬函數(shù)所刻劃。 例 1。 某人的個(gè)子高矮 例 2。如圖所示.在此論域上定義一模糊子集A 表示“軸心軌跡為橢圓形這一模糊概念， 則各元素 U：a，b，c，d，e 對(duì)A的隸屬度可以定為 a 0.9 ，b0.8，c0.4，d0.2，e0.0 用向量來表示A=(0.9 ，0.8，0.4，0.2，0),6.3.2 隸屬函數(shù)的確定方法,18,3.7.2.1 專家打分法 專家打分法就是根據(jù)專家的經(jīng)驗(yàn)，直接給予打分。方法表面上看起來是主觀的，但是專家經(jīng)驗(yàn)是狀態(tài)在專家頭腦中的客觀反映，受客觀的制約，實(shí)際上是客觀的。 3.7.2.2 二元對(duì)比排序法 二元對(duì)比排序法就是將研究對(duì)象排成優(yōu)先順序，根據(jù)此優(yōu)先

16、順序建立模糊子集A的隸屬值。A的隸屬函數(shù)的大致輪廓就出來了。,0.25 0.50 1 2 3 4 o,3.7.2.3 模糊統(tǒng)計(jì)法,模糊統(tǒng)計(jì)法是通過模糊統(tǒng)計(jì)實(shí)驗(yàn)得到隸屬函數(shù)，,6.3.3 常用的隸屬函數(shù)類型,19,1) 正態(tài)型2) 型3) 戒下型4) 戒上型,6.3.4. 基本運(yùn)算,20,定義設(shè)A，BF (U)，AB，AB，AC它們分別具有隸屬函數(shù) 并集 交集 余集 例在例中，若定義。 A(0.9，0.8，0.4，0.2，0) (橢圓形) B(0.2，0.3，0.6，0.1，0) (雙環(huán)橢圓形) 則AB (0.9，0.5，0.6，0.2， 0) (或橢圓或雙環(huán)橢圓) AB (0.2，0.3，0.

17、4，0.1，0) (亦橢圓或雙環(huán)橢圓) AC (0.1，0.1，0.6，0.8，0) (不是橢圓),6.3.5 模糊推理 -最大隸屬判別原則,21,設(shè)A1，A2，AnF（U）。uoU若i 1，2，n ， 使Ai（uo）= maxA1(uo)，A2(uo)，Ain (uo) 則認(rèn)為uo相對(duì)隸屬于Ai。 在故障診斷中，已經(jīng)認(rèn)識(shí)的故障種類是有限的，且任何兩種故障都可同時(shí)并發(fā)，所以難找全模糊子集，即被識(shí)別對(duì)象uo 有可能是A1(uo)，A2(uo)，Ain (uo)均較小， 但Ai（uo）= maxA1(uo)，A2(uo)，Ain (uo)總是存在的， 若用最大隸屬原則判斷，則必然存在誤判的可能性。

18、 因此，在故障診斷中若要應(yīng)用最大隸屬原則，需加一條限制，即增加一個(gè)閾值T，Ai（uo）不僅滿足式(2-13)，還需滿足Ai（uo）T這樣才能判斷uo隸屬于Ai。,6.4群優(yōu)化算法,6.4.1 群智能和粒群優(yōu)化概述 1群智能 群定義為某種交互作用的組織或Agent之結(jié)構(gòu)集合。 群體中的個(gè)體在結(jié)構(gòu)上是很簡(jiǎn)單的，群提供了個(gè)體間交換經(jīng)驗(yàn)知識(shí)的通信通道，因?yàn)閭€(gè)體行為和全局群行為之間存在某種緊密的聯(lián)系，而使它們的集體行為卻可能變得相當(dāng)復(fù)雜和完善。 個(gè)體的集體行為構(gòu)成和支配了群行為，群行為又決定了個(gè)體執(zhí)行其作用的條件。這些作用可能改變環(huán)境，因而也可能改變這些個(gè)體自身的行為及其地位。由群行為決定的條件包括空間

19、和時(shí)間兩種模式。群行為不能僅由獨(dú)立于其他個(gè)體的個(gè)體行為所確定。個(gè)體間的交互作用在構(gòu)建群行為中起到重要的作用，個(gè)體間的交互作用幫助改善對(duì)環(huán)境的經(jīng)驗(yàn)知識(shí)，增強(qiáng)了到達(dá)優(yōu)化的群進(jìn)程。,22,t=2時(shí)刻,個(gè)體的渺小，群體的偉大,2粒群優(yōu)化概念,粒群優(yōu)化(particle swarm optimization，PSO)算法是一種基于群體搜索的算法， 粒群優(yōu)化中的粒子的個(gè)體是通過超維搜索空間“流動(dòng)”的。粒子在搜索空間中的位置變化是以個(gè)體成功地超過其他個(gè)體的社會(huì)心理意向?yàn)榛A(chǔ)的。 群中粒子的變化是受其鄰近粒子(個(gè)體)的經(jīng)驗(yàn)或知識(shí)影響的，一個(gè)粒子的搜索行為受到群中其他粒子的搜索行為的影響，粒群優(yōu)化是一種共生合作

20、算法。建立這種社會(huì)行為模型的結(jié)果是：在搜索過程中，粒子隨機(jī)地回到搜索空間中一個(gè)原先成功的區(qū)域。,23,t=2時(shí)刻,particle swarm optimization，PSO,3粒群優(yōu)化算法,粒群優(yōu)化是以鄰域原理為基礎(chǔ) 。群是粒子的集合，每個(gè)粒子的位置代表一個(gè)潛在的解答。每個(gè)粒子的位置按照其經(jīng)驗(yàn)和鄰近粒子的位置而發(fā)生變化，粒子在超空間流動(dòng)，與最佳解答的接近度-適應(yīng)度函數(shù)正比的速度矢量推動(dòng)優(yōu)化過程。 1個(gè)體最佳算法pbest每一個(gè)體只把它的當(dāng)前位置與自己的最佳位置相比較。 2全局最佳算法 gbest 每個(gè)粒子能與其他粒子(個(gè)體)進(jìn)行通信，形成一個(gè)全連接的社會(huì)網(wǎng)絡(luò)，用于驅(qū)動(dòng)各粒子移動(dòng)的社會(huì)知識(shí)包

21、括全群中選出的最佳粒子位置。此外，每個(gè)粒子還根據(jù)先前已發(fā)現(xiàn)的最好的解答來運(yùn)用它的歷史經(jīng)驗(yàn)。 3局部最佳算法lbest 每個(gè)粒子與它的鄰近粒子通信。粒子受它們鄰域的最佳位置和自己過去經(jīng)驗(yàn)的影響。,24,星形(star) 鄰域拓?fù)浣Y(jié)構(gòu),3蟻群算法基本原理,蟻群的集體行為便表現(xiàn)出一種信息(外激素)正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻個(gè)體之間就是通過信息的交流達(dá)到搜索食物的目的。,25,t=2時(shí)刻,t=1時(shí)刻,意大利學(xué)者-多里戈實(shí)驗(yàn),實(shí)例-蟻群TSP系統(tǒng)模型1,模擬實(shí)際螞蟻的行為。 m表示蟻群中螞蟻的數(shù)量； dij (il，2.n)表示城市i和城市j之間的距離；

22、bi(t)表示t時(shí)刻位于城市i的螞蟻個(gè)數(shù)； ij表示t時(shí)刻在ij連線上殘留的信息量。 在初始時(shí)刻，設(shè)ij(0)C(C為常數(shù))，各條路徑上信息量相等。 螞蟻k(k=l,2m)在運(yùn)動(dòng)過程中，根據(jù)各條路徑上的信息量決定轉(zhuǎn)移方向。 表示在t時(shí)刻螞蟻由位置i轉(zhuǎn)移到位置j 的概率：,26,應(yīng)用-蟻群TSP系統(tǒng)模型2,上述蟻群系統(tǒng)模型是一個(gè)遞歸過程，計(jì)算機(jī)上實(shí)現(xiàn)過程可用偽代碼如下： begin ncycle: = 0; bestcycle: = 0; ij=C; ij(0) =0; ij由某種啟發(fā)算法定 tabuk=; while (not termination condition) ncycle =nc

23、ycle+1; for (index =0; indexn;index+ +) index表示當(dāng)前已經(jīng)走過的城市個(gè)數(shù) for (k = 0; km;k+) 以概率選擇城市j; j0,1,n-1tabuk; 將剛剛選擇的城市j加到tabuk中 計(jì)算(index)，ij (index+n) 確定本次循環(huán)中找到的最佳路徑 輸出最佳路徑及最佳結(jié)果 end,27,應(yīng)用,電話網(wǎng)絡(luò)路徑選擇 數(shù)據(jù)通信網(wǎng)絡(luò)的路由優(yōu)化 機(jī)器人建模和優(yōu)化等。它們合作搬運(yùn)的特性產(chǎn)生了機(jī)器人式的實(shí)現(xiàn)。 二次分配問題； 作業(yè)調(diào)度問題； 圖表著色問題； 最短公超序問題； 蟻群算法源于對(duì)自然界中的螞蟻尋找蟻巢到食物以及食物回到蟻巢的最短 路

24、徑方法的研究。它是一種并行算法，所有“螞蟻”均獨(dú)立行動(dòng)，沒有監(jiān)督 機(jī)構(gòu)。它又是一種合作算法，依靠群體行為進(jìn)行尋優(yōu)；它還是一種魯棒算 法，只要對(duì)算法稍作修改，就可以求解其他組合優(yōu)化問題。,28,6.5人工免疫。,生物系統(tǒng)中的信息處理系統(tǒng)四種類型(人是最完美的系統(tǒng)) 腦神經(jīng)系統(tǒng)(神經(jīng)網(wǎng)絡(luò))、遺傳系統(tǒng)(進(jìn)化計(jì)算)、 免疫系統(tǒng)(人工免疫系統(tǒng))和內(nèi)分泌系統(tǒng)。 自然免疫系統(tǒng)是復(fù)雜自適應(yīng)系統(tǒng)，免疫系統(tǒng)的主要作用是識(shí)別所有身體內(nèi)的細(xì)胞，并將分類為自體（我要）和非自體（我不要）。免疫系統(tǒng)在外部病原體和身體自己的細(xì)胞之間進(jìn)行辨別，產(chǎn)生抗體消除病原體，通過進(jìn)化學(xué)習(xí)、記憶和模式識(shí)別能力，有效地使用多種機(jī)制防御外部病原體。免疫系統(tǒng)對(duì)外來抗原的識(shí)別過程是一個(gè)尋找能夠和抗原結(jié)合力最大的抗體的過程。 免疫系統(tǒng)不依靠任何中心控制，具有分布式任務(wù)處理能力，具有在局部采取行動(dòng)的智能，也通過起交流作用的化學(xué)信息構(gòu)成網(wǎng)絡(luò)，形成全局觀念。,29,定義,抗原(antigen)是指所有可能錯(cuò)誤的基因，即非最佳個(gè)體的基因； 疫苗(vaccine)