【導(dǎo)讀】而采用AIS模型來完成數(shù)據(jù)挖掘任務(wù)的研究目前主要集中在數(shù)據(jù)聚。類分析、數(shù)據(jù)濃縮，分類任務(wù)等方面。該算法的問題表示采用了二進(jìn)制的位串編碼方式，把。的主要特點(diǎn)就是多次使用了陰性選擇機(jī)制來充當(dāng)過濾器。該算法先從預(yù)先選定的。結(jié)果表明該算法具備較好的分類性能。

　　

【正文】 顯示出 AIS 強(qiáng)大的信息處理和問題求解能力以及廣闊的研究前景。目前 ,由于認(rèn)識(shí)到 AIS 在機(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘等領(lǐng)域潛在的應(yīng)用前景 ,AIS 的研究得到了許多大 學(xué)、研究機(jī)構(gòu)和工業(yè)界的重視。英國 Kent 大學(xué)的 Timmis[7]對(duì)基于 AIS 的機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘技術(shù)進(jìn)行了系統(tǒng)性的理論研究 ,并開展了基于 AIS 的大規(guī)模數(shù)據(jù)挖掘應(yīng)用研究。作為計(jì)算智能的一個(gè)嶄新分支 ,AIS 已成為許多國際期刊的重要議題。 AIS 的定義 對(duì)于人工免疫系統(tǒng) ,有幾種不同的定義。 Starlab 的定義為 :“ AIS 是一種數(shù)據(jù)處理、歸類、表示和推理策略 ,該模型依據(jù)一種似是而非的生物范式 ,即人體免疫系統(tǒng)” [6]。 Dasgupta 給出的定義為 :“ AIS是由生物免疫系統(tǒng)啟發(fā)而來的智能策 中國圖象圖形網(wǎng) 略所組成 ,主要用于 信息處理和問題求解”。 Timmis[7]給出的定義為 :“ AIS 是一種由理論生物學(xué)啟發(fā)而來的計(jì)算范式 ,它借鑒了一些免疫系統(tǒng)的功能、原理和模型并用于復(fù)雜問題的解決”。 Starlab 僅從數(shù)據(jù)處理的角度對(duì) AIS 進(jìn)行了定義 ,而后兩者則著眼于生物隱喻機(jī)制的應(yīng)用 ,強(qiáng)調(diào)了 AIS 的免疫學(xué)機(jī)理 ,因而后兩者更為貼切。 免疫系統(tǒng)的基本概念 1. 免疫（ Immunity） 免疫系統(tǒng)抵御外部入侵 ,使其機(jī)體免受病原侵害的應(yīng)答反應(yīng)稱為免疫。 2. 抗原 (Antigen) 誘導(dǎo)免疫系統(tǒng)產(chǎn)生免疫應(yīng)答的物質(zhì)稱為抗原。 3. 抗體 (Antibody) 能與抗原進(jìn)行特異性結(jié)合的免疫細(xì)胞稱為抗體。 4. 免疫應(yīng)答 外部有害病原入侵機(jī)體并激活免疫細(xì)胞 ,誘導(dǎo)其發(fā)生反應(yīng)的過程稱為免疫應(yīng)答。免疫應(yīng)答分為固有性免疫和獲得性免疫兩種 ,前者為機(jī)體先天獲得 ,可對(duì)病原進(jìn)行快速清除，后者特異性識(shí)別并清除病原體 ,具有特異性、記憶、區(qū)分自我與非我、多樣性和自我調(diào)節(jié)等優(yōu)良特性。獲得性免疫所具有的優(yōu)良特性是 AIS 隱喻機(jī)制的不竭之源。一般免疫應(yīng)答分初次應(yīng)答和再次應(yīng)答，在初次應(yīng)答中利用免疫記憶功能，加快再次應(yīng)答時(shí)對(duì)同種抗原的檢測(cè)。 5. 自我和非我 (Self and Nonself) 自我對(duì)應(yīng)于機(jī)體自身的組織 ,非我對(duì)應(yīng)于外來有害病原或者體內(nèi)病變組織。 6. 免疫細(xì)胞， B細(xì)胞， T細(xì)胞（ Immunocyte,B cell,T cell） 免疫細(xì)胞泛指所有參與免疫應(yīng)答過程的相關(guān)細(xì)胞 ,包括吞噬細(xì)胞、 NK 細(xì)胞、淋巴細(xì)胞等。淋巴細(xì)胞又分為 B細(xì)胞和 T細(xì)胞兩種。成熟的 B細(xì)胞產(chǎn)生于骨髓中 ,成熟的 T細(xì)胞產(chǎn)生于胸腺之中。 B 細(xì)胞和 T細(xì)胞成熟之后進(jìn)行克隆增殖、分化并表達(dá)功能。 B 細(xì)胞的主要功能是產(chǎn)生抗體 , T 細(xì)胞的主要功能是調(diào)節(jié)其它細(xì)胞的活動(dòng)或直接對(duì)抗原實(shí)施攻擊。 AIS 的仿生機(jī)理 仿生機(jī)理概述 從信息處理的角度來看，免疫系統(tǒng)具備強(qiáng)大的識(shí)別、學(xué)習(xí)和記憶的能力及分布式、自組織和多樣性特性，這些顯著的特性不斷地吸引著研究人員從免疫系統(tǒng) 中國圖象圖形網(wǎng) 中抽取有用的隱喻機(jī)制，開發(fā)相應(yīng)的 AIS 模型和算法用于信息處理和問題求解。圖 給出了 AIS 仿生機(jī)理的主要內(nèi)容。 AIS 的仿生機(jī)理主要包括免疫識(shí)別，免疫學(xué)習(xí)，免疫記憶，克隆選擇，多樣性，分布式，自適應(yīng)及免疫網(wǎng)絡(luò)。下面對(duì)幾種重要的仿生隱喻機(jī)理進(jìn)行描述。 ＡＩＳ仿生機(jī)理免疫識(shí)別免疫學(xué)習(xí)免疫記憶克隆選擇多樣性分布式自適應(yīng)免疫網(wǎng)絡(luò) 圖 人工免疫系統(tǒng)的仿生機(jī)理 免疫識(shí)別 免疫識(shí)別是免疫系統(tǒng)的主要功能 ,同時(shí)也是 AIS 的核心之一 ,而識(shí)別的本質(zhì)是區(qū)分“自我”和“非我”。免疫識(shí)別是通過淋巴細(xì)胞上的抗原識(shí)別受體 (receptor)與抗原的結(jié)合實(shí)現(xiàn)的 ,結(jié)合的強(qiáng)度稱為親合度 (affinity)。未成熟的 T 細(xì)胞首先要經(jīng)歷一個(gè)審查環(huán)節(jié) ,只有那些不能與自我發(fā)生應(yīng)答的 T 細(xì)胞才可以執(zhí)行免疫應(yīng)答的任務(wù) ,從而防止免疫細(xì)胞對(duì)機(jī)體造成錯(cuò)誤攻擊。該過程稱為陰性選擇(negative selection), 它是免疫識(shí)別的一種主要方式。免疫細(xì)胞對(duì)抗原 的識(shí)別是通過結(jié)合 (或匹配 )過程實(shí)現(xiàn)的 ,相應(yīng)地 AIS 中的抗原識(shí)別通過特征匹配來實(shí)現(xiàn) ,其核心是定義一個(gè)匹配閾值。對(duì)匹配的度量可采用多種方法 ,如 Hamming 距離、 Euclidean 距離以及 Forrest[8]所提出的 R 連續(xù)位匹配方法等。陰性選擇原理對(duì)應(yīng) AIS 中的陰性選擇算法 ( 節(jié)有敘述 ),其核心是根據(jù)識(shí)別的對(duì)象特征進(jìn)行編碼 ,定義一個(gè)自我集合并隨機(jī)產(chǎn)生一系列檢測(cè)器 ,用于檢測(cè)自我集合的變化。根據(jù)陰性選擇原理 ,若檢測(cè)集合與自我集合匹配 ,則完成匹配任務(wù)，機(jī)體發(fā)現(xiàn)病變。 免疫學(xué)習(xí) 免疫識(shí)別過程同時(shí)也是 一個(gè)學(xué)習(xí)的過程 ,學(xué)習(xí)的結(jié)果是免疫細(xì)胞的個(gè)體親合度提高、群體規(guī)模擴(kuò)大 ,并且最優(yōu)個(gè)體以免疫記憶的形式得到保存。免疫學(xué)習(xí)大致可分為兩種 :一種發(fā)生在初次應(yīng)答階段 ,即免疫系統(tǒng)首次識(shí)別一種新的抗原時(shí) , 中國圖象圖形網(wǎng) 其應(yīng)答時(shí)間相對(duì)較長(zhǎng)；而當(dāng)機(jī)體重復(fù)遇到同一抗原時(shí) ,由于免疫記憶機(jī)制的作用 ,免疫系統(tǒng)對(duì)該抗原的應(yīng)答速度大大提高 ,并且產(chǎn)生高親合度的抗體去除病原 ,這個(gè)過程是一個(gè)增強(qiáng)式學(xué)習(xí) (reinforcement learning)過程 ,對(duì)應(yīng)于再次應(yīng)答。 免疫系統(tǒng)不僅可以實(shí)現(xiàn)對(duì)同一種抗原的識(shí)別 ,而且可以對(duì)結(jié)構(gòu)類似的抗原進(jìn)行識(shí)別 ,這是其一大特色 ，在 AIS 中得到了具體體現(xiàn)。免疫學(xué)習(xí)一般有以下幾種途徑 :(1)對(duì)同一抗原進(jìn)行重復(fù)學(xué)習(xí) ,屬于增強(qiáng)式學(xué)習(xí)。 (2)親合度成熟 ,對(duì)應(yīng)于AIS中的個(gè)體經(jīng)遺傳操作后其親合度逐步提高的過程 ,屬于遺傳學(xué)習(xí)。 (3)低度的重復(fù)感染 ,對(duì)應(yīng)于 AIS 的重復(fù)訓(xùn)練過程。 (4)對(duì)內(nèi)生和外生抗原的交叉應(yīng)答 ,屬于聯(lián)想式學(xué)習(xí) ,對(duì)應(yīng)于聯(lián)想記憶機(jī)制。免疫學(xué)習(xí)機(jī)理在 AIS 機(jī)器學(xué)習(xí)模型和算法構(gòu)造中得到了廣泛應(yīng)用并取得了良好的學(xué)習(xí)效果。 免疫記憶 當(dāng)免疫系統(tǒng)初次遇到一種抗原時(shí) ,淋巴細(xì)胞需要一定的時(shí)間進(jìn)行調(diào)整以更好地識(shí)別抗原 ,并在識(shí)別結(jié)束后以最 優(yōu)抗體的形式保留對(duì)該抗原的記憶信息。而當(dāng)免疫系統(tǒng)再次遇到相同或者結(jié)構(gòu)相似的抗原時(shí) ,在聯(lián)想記憶的作用下 ,其應(yīng)答速度將大大提高。免疫記憶主要體現(xiàn)在再次免疫應(yīng)答和交叉免疫應(yīng)答時(shí) ,而交叉應(yīng)答是免疫系統(tǒng)對(duì)結(jié)構(gòu)相似的抗原所產(chǎn)生的免疫應(yīng)答。 免疫記憶屬于聯(lián)想式記憶 ,是 AIS 區(qū)別于其它進(jìn)化算法的重要特性之一。Farmer[9]首先指出免疫記憶可以看作一種聯(lián)想式記憶 (associative memory)模型。 Smith[10]對(duì)免疫記憶模型與稀疏分布記憶 (SparseDistributedMemory,SDM)模型進(jìn)行了對(duì) 比 ,指出初次免疫應(yīng)答對(duì)應(yīng)著 SDM 向記憶中存儲(chǔ)信息的過程 ,而再次和交叉免疫應(yīng)答則可以看作是 SDM 讀取記憶信息的過程。免疫記憶機(jī)制可以大大加速優(yōu)化搜索過程 ,加快學(xué)習(xí)進(jìn)程并提高學(xué)習(xí)質(zhì)量。總之 ,免疫記憶是提高算法執(zhí)行效率的一種非常有效的手段。 克隆選擇 克隆選擇原理最先由 Jerne[11]提出 ,后由 Bur[12]給予完整闡述。其大致內(nèi)容為 :當(dāng)淋巴細(xì)胞實(shí)現(xiàn)對(duì)抗原的識(shí)別 (即抗體和抗原的親和度超過一定閾值 )后 ,B細(xì)胞被激活并增殖復(fù)制產(chǎn)生 B 細(xì)胞克隆 ,隨后克隆細(xì)胞經(jīng)歷變異過程 ,產(chǎn)生對(duì)抗原具有特異性的抗體?？?隆選擇理論描述了獲得性免疫的基本特性 ,并且聲明只有成功識(shí)別抗原的免疫細(xì)胞才得以增殖。經(jīng)歷變異后的免疫細(xì)胞分化為效應(yīng)細(xì)胞(抗體 )和記憶細(xì)胞兩種。 克隆選擇的主要特征是免疫細(xì)胞在抗原刺激下產(chǎn)生克隆增殖 ,隨后通過遺傳 中國圖象圖形網(wǎng) 變異分化為多樣性效應(yīng)細(xì)胞 (抗體細(xì)胞 )和記憶細(xì)胞?？寺∵x擇對(duì)應(yīng)著一個(gè)親合度成熟 (affinity maturation)的過程 ,即對(duì)抗原親合度較低的個(gè)體在克隆選擇機(jī)制的作用下 ,經(jīng)歷增殖復(fù)制和變異操作后 ,其親合度逐步提高而“成熟”的過程。因此親合度成熟本質(zhì)上是一個(gè)達(dá)爾文式的選擇和變異的過程 ,克隆選擇原理是 通過采用交叉、變異等遺傳算子和相應(yīng)的群體控制機(jī)制實(shí)現(xiàn)的。 根據(jù)克隆選擇原理 ,DeCastro[13]提出了克隆選擇算法模型 ,并在模式識(shí)別、組合優(yōu)化和多峰值函數(shù)優(yōu)化中得到了驗(yàn)證。 Kim[14]將克隆選擇原理用于網(wǎng)絡(luò)入侵檢測(cè)獲得成功。其算法的核心在于增殖復(fù)制算子和變異算子 ,前者與個(gè)體親合度成正比 ,保證群體親合度逐步增大，后者與個(gè)體的親合度成反比例關(guān)系 ,保留最佳個(gè)體并改進(jìn)較差個(gè)體。 免疫系統(tǒng)的仿生機(jī)理還包括自適應(yīng)，多樣性，分布式，免疫網(wǎng)絡(luò)。由于免疫系統(tǒng)中抗體的數(shù)目遠(yuǎn)小于外部抗原的數(shù)目，所以需要保證抗體類型的多樣性 ，用來檢測(cè)盡可能多的抗原。免疫系統(tǒng)的分布式特性有利于加強(qiáng)系統(tǒng)的健壯特性(robust),從而使得免疫系統(tǒng)不會(huì)因?yàn)榫植拷M織損傷而使整體功能受到很大影響。分布式和自適應(yīng)特性在提升系統(tǒng)的工作效率和故障容錯(cuò)能力方面得到了應(yīng)用。免疫網(wǎng)絡(luò)理論對(duì)免疫細(xì)胞活動(dòng)、抗體生成、免疫耐受、自我與非我識(shí)別、免疫記憶和免疫系統(tǒng)的進(jìn)化過程等做出了系統(tǒng)的假設(shè) ,并且將免疫系統(tǒng)視為由免疫細(xì)胞或者分子組成的調(diào)節(jié)網(wǎng)絡(luò) ,免疫細(xì)胞以抗體間的相互反應(yīng)和不同種類免疫細(xì)胞間的相互通信為基礎(chǔ) ,抗原識(shí)別是由抗原相互作用所形成的免疫網(wǎng)絡(luò)完成的。 AIS 常 用算法 一般免疫算法 目前 ,一般的免疫算法大多采用類似遺傳算法的搜索策略 ,借用了 GA 的選擇、交叉和變異算子。采用 GA 算子的免疫算法目前尚無統(tǒng)一框架 ,但已經(jīng)在求解諸如組合優(yōu)化等問題中顯示了強(qiáng)大的優(yōu)化搜索能力。從本質(zhì)上講免疫算法可以看作是對(duì) GA 的改進(jìn)。 Endoh[15]提出了基于兩種記憶模式的免疫算法 ,充分利用記憶機(jī)制在優(yōu)化迭代搜索過程中的作用 ,加速算法收斂并抑制算法早熟 ,數(shù)值實(shí)驗(yàn)表明它比遺傳算法的求解效率大大提高。肖人彬 [16]對(duì) AIS 的記憶機(jī)制進(jìn)行了進(jìn)一步研究 ,提出了融合迭代記憶和聯(lián)想記憶的改進(jìn) AIS 算法 ,數(shù)值實(shí)驗(yàn)表明該算法的計(jì)算效率較之一般遺傳算法有了進(jìn)一步提高 ,該算法比一般 GA 的求解時(shí)間平均減少近半。王磊 [17]提出了免疫規(guī)劃算法 , 其核心在于構(gòu)造一個(gè)包含免疫選擇和接種疫苗兩個(gè)步驟的免疫算子 ,該算法可以有效抑制進(jìn)化過程中出現(xiàn)的退化現(xiàn)象 ,其搜索性能有了很大的改善。其它基于 GA算子的免疫算法還有免疫遺傳算法 [18]、 中國圖象圖形網(wǎng) 免疫進(jìn)化策略 [19]和基于主體的免疫算法 [20]等。 陰性選擇算法 基于陰性選擇原理（見 節(jié)）， D39。haeseleer[21]給出了一種陰性選擇算法，用于監(jiān)測(cè)數(shù)據(jù)改 變。其中抗體與抗原的匹配采用 Forrest 提出的 r連續(xù)位匹配規(guī)則。該算法的流程如下 : Step1:有限字符表上，定義一組長(zhǎng)度為 L的字符串集合 S來代表自我，用于檢測(cè)。 Step2:產(chǎn)生檢測(cè)器集合 R，依據(jù)陰性選擇原理，對(duì)每個(gè)檢測(cè)器進(jìn)行審查。審查采用部分匹配規(guī)則，即兩個(gè)字符串匹配當(dāng)且僅當(dāng)至少有 r個(gè)連續(xù)位相同，其中r為參數(shù)。 Step3：通過連續(xù)地將 R 中的檢測(cè)器與 S比較來監(jiān)測(cè) S 的改變。如果檢測(cè)器發(fā)生匹配，則有改變發(fā)生。 該算法的優(yōu)點(diǎn)是簡(jiǎn)便、易于實(shí)現(xiàn)，主要問題是計(jì)算復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)，難以處理復(fù)雜問題。 Forrest[8]隨后給出了一種復(fù)雜度較低的高效檢測(cè)器生成算法。陰性選擇算法目前廣泛應(yīng)用于模式識(shí)別、病毒檢測(cè)、網(wǎng)絡(luò)入侵檢測(cè)、異常檢測(cè)等。該算法并沒有直接利用自我信息，而是由自我集合通過陰性選擇生成檢測(cè)子集，具備了并行性、健壯性和分布式檢測(cè)等特點(diǎn)。 克隆選擇算法 基于克隆選擇原理 (見 節(jié) )， DeCastro[13]提出了一種克隆選擇算法，核心是比例復(fù)制和比例變異算子 ,在解決諸如模式識(shí)別等復(fù)雜機(jī)器學(xué)習(xí)任務(wù)方面，該算法有顯著能力。算法流程如下 Step1：產(chǎn)生候選方案的集合 S(P)，該集合為記憶細(xì)胞子集 (M)和剩余群體(Pr)的總和 (P=Pr+M)。 Step2：基于親和度度量確定群體 P中的 b個(gè)最佳個(gè)體 Pb。 Step3：對(duì)群體中的這 b 個(gè)最佳個(gè)體進(jìn)行克隆 (復(fù)制 )，生成臨時(shí)克隆群體 C?？寺∫?guī)模是抗原親和度度量的單調(diào)遞增函數(shù)。 Step4：對(duì)克隆生成的群體施加變異操作，變異概率反比于抗體的親和度，從而生成一個(gè)成熟的抗體群體 (C*)。 Step5：從 C*中重新選擇改進(jìn)個(gè)體組成記憶集合， P 集合的一些成員可以由C*的其他改進(jìn)成員加以替換。 Step6：將群體中的 w個(gè)低親和度的抗體予以替換，從而維持抗體的多樣性。 中國圖象圖形網(wǎng) 該 算法成功應(yīng)用到了二進(jìn)制字符識(shí)別、多峰函數(shù)優(yōu)化和組合優(yōu)化中 [13]，取得了良好效果。對(duì)比遺傳算法，克隆選擇算法在編碼機(jī)制和評(píng)價(jià)函數(shù)的構(gòu)造上基本一致，但搜索的策略和步驟有所不同。而且通過免疫記憶機(jī)制，該算法可以保存各個(gè)局部最優(yōu)解，這對(duì)于多峰函數(shù)優(yōu)化十分重要。 AIS 在數(shù)據(jù)挖掘中的應(yīng)用 采用 AIS模型的數(shù)據(jù)挖掘任務(wù)目前主要集中在數(shù)據(jù)聚類分析、數(shù)據(jù)濃縮、歸類任務(wù)等方面。 Hunt 和 Cooker[22]研究了基于 AIS 模型的無監(jiān)督學(xué)習(xí)算法，將其用到了 DNA序列的分類任務(wù)中。 Cooker 首先利用了免疫系統(tǒng)學(xué)習(xí)和 適應(yīng)新抗原的特性，提出了一種有指導(dǎo)的機(jī)器學(xué)習(xí)機(jī)制 [39]。該機(jī)制用于將 DNA 序列分為發(fā)