6章-計算智能-人工智能研究生課程

1、第6章 計算智能,1,6.1 神經網絡 6.2 遺傳算法 6.3 模糊計算 6.4 粒群優(yōu)化 6.5 人工免疫 CI AI BI,AArtificial BBiological CComputational,6.1神經網絡,2,3.5.1 神經網絡的基本知識,(neural net),神經元、連接權值、閾值，激勵函數(shù)、, 神經元模型(B-P), 激勵函數(shù)（作用,非線性體現(xiàn)）,Sigmoid函數(shù) f = 1/(1+ex ) 壓縮映射，多階連續(xù)可微,神經網絡例子,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,識別四個動物的神經網絡例子,模式識別,四個動物的樣本 (1) 某動物特征是暗斑點、黃褐色、有毛發(fā)、吃肉，它就是豹。 (2) 某動物特征是黃褐色、有毛發(fā)、吃肉、黑條紋，它就是虎。 (3) 某動物特征是不飛、黑白色、會游泳、有羽毛，它就是企鵝。 (4) 某動物特征是有羽毛、善飛，它就是信天翁。,暗斑點 黃褐色 有毛發(fā) 吃肉 黑條紋 不飛 黑白色 會游泳 有羽毛 善飛 編 碼 動物名 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 信天翁,結果,輸入輸 出 輸出相近 暗 黃 毛 肉 紋 不飛 黑白 泳 羽 飛 豹 虎 企鵝 信天翁 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神經網絡,1 給定神經網絡結構 （三層： 輸入層（輸入神經元=輸入維數(shù)） 隱含層、（?） 輸出層： （輸出神經元=輸出個數(shù)） 2 給定初始權值、閾值。 3 運用樣本，按公式計算每個神經遠的輸出，直至輸出神經元 4 求出誤差

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

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

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

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

11、(two-point crossover)； (3)多點雜交(multi-point crossover)； (4)一致雜交(uniform crossover)等。 變異算子的功能就是對個體串的某些基因座上的基因值作變動。10，01） 5. 控制參數(shù)設定 (主要指種群的規(guī)模和采用的遺傳操作的概率等)。,Schaffer漣漪函數(shù),13,遺傳算法例子MAX: f(x1,x2)=x12+x22,14,MAX: f(x1,x2)=x12+x22 x1,x2 (空間很?。?個體編號初始群體P(0) 適應度 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) 配對交叉點位置交叉結果變異點變異結果（子代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,遺傳算法的特點,15,(1) 以決策變量的編碼作為運

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

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

15、集完全由其隸屬函數(shù)所刻劃。 例 1。 某人的個子高矮 例 2。如圖所示.在此論域上定義一模糊子集A 表示“軸心軌跡為橢圓形這一模糊概念， 則各元素 U：a，b，c，d，e 對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ù)專家的經驗，直接給予打分。方法表面上看起來是主觀的，但是專家經驗是狀態(tài)在專家頭腦中的客觀反映，受客觀的制約，實際上是客觀的。 3.7.2.2 二元對比排序法 二元對比排序法就是將研究對象排成優(yōu)先順序，根據(jù)此優(yōu)先

16、順序建立模糊子集A的隸屬值。A的隸屬函數(shù)的大致輪廓就出來了。,0.25 0.50 1 2 3 4 o,3.7.2.3 模糊統(tǒng)計法,模糊統(tǒng)計法是通過模糊統(tǒng)計實驗得到隸屬函數(shù)，,6.3.3 常用的隸屬函數(shù)類型,19,1) 正態(tài)型2) 型3) 戒下型4) 戒上型,6.3.4. 基本運算,20,定義設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,設A1，A2，AnF（U）。uoU若i 1，2，n ， 使Ai（uo）= maxA1(uo)，A2(uo)，Ain (uo) 則認為uo相對隸屬于Ai。 在故障診斷中，已經認識的故障種類是有限的，且任何兩種故障都可同時并發(fā)，所以難找全模糊子集，即被識別對象uo 有可能是A1(uo)，A2(uo)，Ain (uo)均較小， 但Ai（uo）= maxA1(uo)，A2(uo)，Ain (uo)總是存在的， 若用最大隸屬原則判斷，則必然存在誤判的可能性。

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

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

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

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

22、bi(t)表示t時刻位于城市i的螞蟻個數(shù)； ij表示t時刻在ij連線上殘留的信息量。 在初始時刻，設ij(0)C(C為常數(shù))，各條路徑上信息量相等。 螞蟻k(k=l,2m)在運動過程中，根據(jù)各條路徑上的信息量決定轉移方向。 表示在t時刻螞蟻由位置i轉移到位置j 的概率：,26,應用-蟻群TSP系統(tǒng)模型2,上述蟻群系統(tǒng)模型是一個遞歸過程，計算機上實現(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表示當前已經走過的城市個數(shù) for (k = 0; km;k+) 以概率選擇城市j; j0,1,n-1tabuk; 將剛剛選擇的城市j加到tabuk中 計算(index)，ij (index+n) 確定本次循環(huán)中找到的最佳路徑 輸出最佳路徑及最佳結果 end,27,應用,電話網絡路徑選擇 數(shù)據(jù)通信網絡的路由優(yōu)化 機器人建模和優(yōu)化等。它們合作搬運的特性產生了機器人式的實現(xiàn)。 二次分配問題； 作業(yè)調度問題； 圖表著色問題； 最短公超序問題； 蟻群算法源于對自然界中的螞蟻尋找蟻巢到食物以及食物回到蟻巢的最短 路

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