免疫算法介紹

1、2,免疫算法,生物免疫的啟示,在生物自然界中，免疫現(xiàn)象普遍存在，并對物種的 生存與繁衍 發(fā)揮著重要的作用； 生物的免疫功能主要是由參與免疫反應的細胞或由其構成的器官來完成的； 生物免疫主要有兩種類型： 特異性免疫（Specific Immunity）， 非特異性免疫反應（Nonspecific Immunity）； 生物免疫系統(tǒng)是通過自我識別、相互刺激與制約而構成了一個 動態(tài)平衡的網(wǎng)絡結構 。,3,免疫算法,抗原 是指能夠刺激和誘導機體的免疫系統(tǒng)使其產(chǎn)生免疫應答，并能與相應的免疫應答產(chǎn)物在體內(nèi)或體外發(fā)生特異性反應的物質(zhì)。 抗體 是指免疫系統(tǒng)受抗原刺激后，免疫細胞轉化為漿細胞并產(chǎn)生能與抗原發(fā)生特

2、異性結合的免疫球蛋白，該免疫球蛋白即為抗體。,4,免疫算法, 免疫防御 即機體防御病原微生物的感染； 免疫（自身）穩(wěn)定 即機體通過免疫功能經(jīng)常消除那些損傷和衰老的細胞以維持機體的生理平衡； 免疫監(jiān)視 即機體通過免疫功能防止或消除體內(nèi)細胞在新陳代謝過程中發(fā)生突變的和異常的細胞,5,免疫算法,大于閾值,不大于閾值,大于閾值,不大于閾值,隨機特征項,Y,N,6,免疫算法,1.免疫識別 2.免疫學習 3.免疫記憶 4.克隆選擇,基本免疫方法,7,免疫算法,免疫識別是免疫系統(tǒng)的主要功能，同時也是AIS的核心之一，而識別的本質(zhì)是區(qū)分“自我”和“非我”。 核心機制是根據(jù)識別的對象特征進行編碼，定義一個自我集

3、合并隨機產(chǎn)生一系列檢測器，用于檢測自我集合的變化。根據(jù)陰性選擇原理，若檢測集合與自我集合匹配，則完成匹配任務，機體發(fā)現(xiàn)病變。,8,免疫算法,(1)定義自己(self)為一個字符串集合S，每個字符串由n個字母組成，字符串可以是一個網(wǎng)絡數(shù)據(jù)包，電子郵件特征向量或程序的一般行為模式。 (2)產(chǎn)生一個初始監(jiān)測器集合R。 (3)監(jiān)測器集合中每個監(jiān)測器經(jīng)歷陰性選擇過程。其中每一個監(jiān)測器都不能與集合S中的任何一個字符串相匹配，否則就從監(jiān)測器集合中刪去對應的檢測器。 (4)通過與R集合的匹配不斷監(jiān)測S的變化，一旦發(fā)生任何匹配，則說明S集發(fā)生了變化，即有外來抗原侵入。,9,免疫算法,在最初的算法描述中，候選的監(jiān)

4、測器是隨機產(chǎn)生的，然后測試以刪除與自身字串相匹配的監(jiān)測器，算法中采用的匹配規(guī)則是r-連續(xù)位匹配，即當兩個字符串至少存在連續(xù)r位相同是才發(fā)生匹配。 該過程重復進行，直到所需數(shù)量的監(jiān)測器被產(chǎn)生出來。通常用概率分析方法來估算為了滿足一定的可靠性所應有的監(jiān)測器的數(shù)目。,10,免疫算法,免疫識別過程同時也是一個學習的過程，學習的結果是免疫細胞的個體親和度提高、群體規(guī)模擴大，并且最優(yōu)個體以免疫記憶的形式得到保存。 當機體重復遇到同一抗原時，由于免疫記憶機制的作用，免疫系統(tǒng)對該抗原的應答速度大大提高，并且產(chǎn)生高親和度的抗體去除病原，這個過程是一個增強式學習過程。而且可以對結構類似的抗原進行識別。,11,免疫

5、算法,當免疫系統(tǒng)初次遇到一種抗原時，淋巴細胞需要一定的時間進行調(diào)整以更好地識別抗原，并在識別結束后以最優(yōu)抗體的形式保留對該抗原的記憶信息。而當免疫系統(tǒng)再次遇到相同或者結構相似的抗原時，在聯(lián)想記憶的作用下，其應答速度將大大提高。 免疫記憶主要體現(xiàn)在再次免疫應答和交叉免疫應答時，可以大大加速優(yōu)化搜索過程，加快學習進程并提高學習質(zhì)量。,12,免疫算法,免疫學習一般有以下幾種途徑: (a)對同一抗原進行重復學習，屬于增強式學習。 (b)親合度成熟，對應于AIS中的個體經(jīng)遺傳操作后其親合度逐步提高的過程，屬于遺傳學習。 (c)低度的重復感染，對應于AIS的重復訓練過程。 (d)對內(nèi)生和外生抗原的交叉應答

6、，屬于聯(lián)想式學習，對應于聯(lián)想記憶機制。,13,免疫算法,克隆選擇,克隆選擇原理最先由Jerne提出，后由Burnet給予完整闡述。其大致內(nèi)容為:當淋巴細胞實現(xiàn)對抗原的識別(即抗體和抗原的親和度超過一定閾值)后，B細胞被激活并增殖復制產(chǎn)生B細胞克隆，隨后克隆細胞經(jīng)歷變異過程，產(chǎn)生對抗原具有特異性的抗體?？寺∵x擇理論描述了獲得性免疫的基本特性，并且聲明只有成功識別抗原的免疫細胞才得以增殖。經(jīng)歷變異后的免疫細胞分化為效應細胞(抗體)和記憶細胞兩種。,14,免疫算法,克隆選擇,克隆選擇的主要特征是免疫細胞在抗原刺激下產(chǎn)生克隆增殖，隨后通過遺傳變異分化為多樣性抗體細胞和記憶細胞。 克隆選擇對應著一個親和

7、度成熟的過程，即對抗原親和度較低的個體在克隆選擇機制的作用下，經(jīng)歷增殖復制和變異操作后，其親和度逐步提高而“成熟”的過程。因此親和度成熟本質(zhì)上是一個達爾文式的選擇和變異的過程，克隆選擇原理通過采用交叉、變異等遺傳算子和相應的群體控制機制實現(xiàn)。,15,免疫算法,免疫算法,一般的免疫算法可分為三種情況: 模仿免疫系統(tǒng)抗體與抗原識別，結合抗體產(chǎn)生過程而抽象出來的免疫算法; 基于免疫系統(tǒng)中的其他特殊機制抽象出的算法，例如克隆選擇算法; 與遺傳算法等其他計算智能融合產(chǎn)生的新算法，例如免疫遺傳算法。,16,免疫算法,免疫算法的一般步驟,Y,N,免疫算法,17,免疫算法,(1)識別抗原：免疫系統(tǒng)確認抗原入侵

8、。 (2)產(chǎn)生初始抗體群體：激活記憶細胞產(chǎn)生抗體，清除以前出現(xiàn)過的抗原，從包含最優(yōu)抗體(最優(yōu)解)的數(shù)據(jù)庫中選擇出來一些抗體。 (3)計算親和力：計算抗體和抗原之間的親和力。 (4)記憶細胞分化：與抗原有最大親和力的抗體加給記憶細胞。由于記憶細胞數(shù)目有限，新產(chǎn)生的與抗原具有更高親和力的抗體替換較低親和力的抗體。 (5)抗體促進和抑制：高親和力抗體受到促進，高密度抗體受到抑制。通常通過計算抗體存活的期望值來實施。 (6)抗體產(chǎn)生:對未知抗原的響應，產(chǎn)生新淋巴細胞,18,免疫算法,Procedure Begin 隨機生成大量的候選檢測器(即免疫細胞) /*初始化*/ While一個給定大小的檢測器集

9、合還沒有被產(chǎn)生do/*耐受*/ Begin 計算出每一個自體元素和一個候選檢測器之間的親和力; If這個候選的檢測器識別出了自體集合中的任何一個元素Then這個檢測器就要被消除掉; Else把這個檢測器放入檢測器集合里面; /*該檢測器成熟*/ 利用經(jīng)過耐受的檢測器集合，檢測系統(tǒng)以找出變種; End; End.,陰性選擇算法,19,免疫算法,克隆選擇算法,Begin 隨機生成一個屬性串(免疫細胞)的群體 While收斂標準沒有滿足do Begin While not所有抗原搜索完畢do;*/初始化*/ Begin 選擇那些與抗原具有更高親和力的細胞;*/選擇*/ 生成免疫細胞的副本:越高親和力

10、的細胞擁有更多的副本;*/再生*/ 根據(jù)它們的親和力進行變異:親和力越高，變異越小;*/遺傳變異*/ End.End.End.,20,免疫算法,免疫遺傳算法,隨機創(chuàng)建抗體和抗原的群體; 抗體和抗原匹配; 根據(jù)抗體的親和力對抗體做評價; 用標準遺傳算法進化抗體。 這個模型使免疫系統(tǒng)能夠通過學習，知道哪些抗體對抗原的識別有幫助。,21,免疫算法,免疫算法中的親和力計算方法,免疫算法中最復雜的計算是親和力計算。由于產(chǎn)生于確定克隆類型的抗體分子獨特型是一樣的，抗原與抗體的親和力也是抗體與抗體的親和力的測量。 一般計算親和力的公式 : 其中，tk是抗原和抗體k的結合強度。,22,免疫算法,抗體抗原的編碼

11、方式,目前一般免疫算法種抗體抗原，即解和問題的編碼方式主要有二進制編碼、實數(shù)編碼和字符編碼三種。 其中，二進制編碼因簡單而得到廣泛使用。編碼后親和力的計算一般是比較抗體抗原字符串之間的異同，根據(jù)上述親和力計算方法計算。,23,擴展：人工免疫系統(tǒng),人工免疫系統(tǒng)作為人工智能領域的重要分支，同神經(jīng)網(wǎng)絡及遺傳算法一樣也是智能信息處理的重要手段，已經(jīng)受到越來越多的關注。 它通過類似于生物免疫系統(tǒng)的機能，構造具有動態(tài)性和自適應性的信息防御體系，以此來抵制外部無用、有害信息的侵入，從而保證接受信息的有效性與無害性。,24,擴展：人工免疫系統(tǒng),在生物科學領域，人們對進化、遺傳和免疫等自然 現(xiàn)象已經(jīng)進行了廣泛而

12、深入的研究 ； 進化算法是建立在模仿生物遺傳與自然選擇基礎上的一種并行優(yōu)化算法，其性能優(yōu)異、應用廣泛； 進化算子在為每個個體提供了進化機會的同時，也無可避免地產(chǎn)生了退化的可能； 大多數(shù)待求問題有可以利用的先驗知識或特征信息，故可以利用這些信息來抑制進化過程中的退化現(xiàn)象； 生物免疫理論為改進原有算法的性能，建立集進化與免疫機制于一體的新型全局并行算法奠定了基礎。,25,擴展：人工免疫系統(tǒng),Farmer等人在1986年首先在工程領域提出免疫概念； Varela等人受免疫網(wǎng)絡學說的啟發(fā)，提出并進而完善免疫網(wǎng)絡模型。,26,擴展：人工免疫系統(tǒng),獨特型免疫網(wǎng)絡（Jerne）； 互聯(lián)耦合免疫網(wǎng)絡（Ishi

13、guro）； 免疫反應網(wǎng)絡（Mitsumoto）； 對稱網(wǎng)絡（Hoffmann）； 多值免疫網(wǎng)絡（Tang）.,人工免疫網(wǎng)絡模型,27,擴展：人工免疫系統(tǒng),反面選擇算法（Forrest）； 免疫學習算法（Hunt&Cooke）； 免疫遺傳算法（Chun）； 免疫Agent算法（Ishida）； 免疫網(wǎng)絡調(diào)節(jié)算法（Wang&Cao）； 免疫進化算法（Jiao&Wang）,免疫學習算法,28,擴展：人工免疫系統(tǒng),國際研究,1996年，日本，基于免疫性系統(tǒng)的國際專題討論會，提出并確認人工免疫系統(tǒng)（AIS）的概念； 1997年，IEEE的SMC組織專門成立了人工免疫系統(tǒng)及應用的分會組織； 目前，幾乎所

14、有有關人工智能領域的學術會議都收錄AIS方面的論文。,29,擴展：人工免疫系統(tǒng),應用,自動控制 故障診斷 模式識別 圖象識別 優(yōu)化設計 機器學習 網(wǎng)絡安全,30,擴展：人工免疫系統(tǒng),AIS在控制領域中的應用,PID型免疫反饋控制器（ Takahashi ）； 機器人控制（ Mitsumoto, Ishiguro, Lee）； 控制系統(tǒng)的設計（ Ishida ）； 復雜動態(tài)行為建模和自適應控制（Kumak）； 倒擺的控制（ Bersini ）。,31,擴展：人工免疫系統(tǒng),AIS在故障診斷中的應用,基于相關識別特性的免疫網(wǎng)絡模型用于故障診斷的方法（Ishida）； 通過構造大規(guī)模獨特型免疫網(wǎng)絡來建

15、立用于在線服務的故障診斷系統(tǒng)（Ishiguru）。,32,擴展：人工免疫系統(tǒng),AIS在優(yōu)化設計中的應用,永磁同步電動機的參數(shù)修正的優(yōu)化設計； 電磁設備的外形優(yōu)化； VLSI印刷線路板的布線優(yōu)化設計； 函數(shù)測試； 旅行商問題的求解； 約束搜索優(yōu)化問題和多判據(jù)設計問題；,33,擴展：人工免疫系統(tǒng),AIS在網(wǎng)絡安全的應用,數(shù)據(jù)檢測（Forrest ）； 病毒檢測（ Kephart）； UNIX過程監(jiān)控（ Forrest）。,34,擴展：人工免疫系統(tǒng),國際研究新動向之一,以開發(fā)新型的智能系統(tǒng)方法為背景，研究基于生物免疫系統(tǒng)機理的智能系統(tǒng)理論和技術，同時將AIS與模糊系統(tǒng)、神經(jīng)網(wǎng)絡和遺傳算法等軟計算技術

16、進行集成，并給出其應用方法。,35,擴展：人工免疫系統(tǒng),國際研究新動向之二,基于最新發(fā)展的免疫網(wǎng)絡學說進一步建立并完善模糊、神經(jīng)和其它一些專有類型的人工免疫網(wǎng)絡模型及其應用方法。,36,擴展：人工免疫系統(tǒng),國際研究新動向之三,將人工免疫系統(tǒng)與遺傳系統(tǒng)的機理相互結合，并歸納出各種免疫學習算法。比如：免疫系統(tǒng)的多樣性遺傳機理和細胞選擇機理可用于改善原遺傳算法中對局部搜索問題不是很有效的情況；獨特型網(wǎng)絡機理可用于免疫系統(tǒng)中的遺傳部分以避免系統(tǒng)出現(xiàn)早熟現(xiàn)象；發(fā)展用于處理受約束的遺傳搜索和多準則問題的免疫學習算法等。,37,擴展：人工免疫系統(tǒng),國際研究新動向之四,基于免疫反饋和學習機理，設計自調(diào)整、自組織和自學習的免疫反饋控制器。展開對基于免疫反饋機理的控制系統(tǒng)的設計方法和應用研究，這有可能成為工程領域中種新型的智能控制系統(tǒng)，具有重要的理論意義與