傅慧
南昌陸軍學(xué)院 江西 330103
人工免疫系統(tǒng)(Artificial Immune Systems,AIS)是繼神經(jīng)計算、進化計算之后的自然計算的研究新方向,己經(jīng)迅速成為研究熱點,主要是通過深入探索生物免疫系統(tǒng)所蘊含的信息處理機制,建立相應(yīng)的工程模型和算法,用于解決各種復(fù)雜問題。
生物免疫系統(tǒng)將所有的細胞分為兩類:Self細胞(自我)和NonSelf細胞(非我)。Self細胞指自身健康,沒有被感染、破壞的細胞;NonSelf細胞指病毒、細菌、寄生蟲等有害物質(zhì)和自身被感染、破壞的細胞。免疫就是識別Self和NonSelf,并消滅NonSelf,是為了保證機體完整性的一種生理學(xué)反應(yīng)。用集合表示有這么一個關(guān)系:對于集合域X,它包括兩個子集自體集合S和非自體集合N,則有自體集合S?X和非自體集合N?X,而且S∪F=X且S∩F=φ。
人工免疫系統(tǒng)抽取生物免疫系統(tǒng)所蘊含的信息處理機制,建立用于解決各種復(fù)雜問題的工程模型和算法,這些模型和算法都力圖集中體現(xiàn)以上的生物免疫系統(tǒng)的相應(yīng)特點。
人工免疫算法(Artificial Immune Algorithlum,AIA)是模擬人體免疫學(xué)原理而設(shè)計的一種新型算法,是自然免疫系統(tǒng)在進化計算的一個實現(xiàn)。
人工免疫算法的基本流程如圖1。
STEP1:初始化AIA的抗原。對運行過程所需參數(shù)和數(shù)據(jù)進行設(shè)置,包括初始化運行參數(shù)、基因庫以及確定抗體的編碼方式和構(gòu)造初始抗體集,通??梢栽诮饪臻g中隨機產(chǎn)生N個候選解作為初始抗體,N為抗體群中抗體的數(shù)目。
圖1 人工免疫算法的基本流程
STEP2:計算親和力(affinity)。親和力是一個抗體結(jié)合部位與一個抗原決定基結(jié)合的牢固性,結(jié)合自抗原分離的可能越小。用來表示抗原和抗體之間、抗體和抗體之間結(jié)構(gòu)的相信程度。設(shè)定親和力的計算函數(shù)為 Affinity(B,G),一般使用介于0到1之間的實數(shù)表示,Affinity(B,G)值越大說明抗體B和抗原G之間匹配得越好。
STEP3:產(chǎn)生新的抗體。調(diào)用人工免疫算法,初識抗體通過人工免疫算法的作用產(chǎn)生新的抗體。
STEP4:調(diào)用Affinity(B,G),計算新抗體的親和力。
STEP5:若新抗體中有與抗原匹配的抗體,則結(jié)束,否則轉(zhuǎn)到STEP6。
STEP6:抗體選擇。按照“優(yōu)勝劣汰”的自然選擇機制,在原有的N個有效抗體和新產(chǎn)生的若干個體抗體中選擇出N個與抗原匹配得較好的抗體構(gòu)成新的抗體群,在進行選擇操作時,應(yīng)依據(jù)抗體之間的排斥力限制進入新抗體群中的相同抗體的數(shù)目,以保持抗體群中抗體的多樣性,增強抗體群的免疫力,選擇完成后轉(zhuǎn)到STEP3。
克隆選擇學(xué)說早在1958年就由Burnet建立,描述了獲得性免疫的基本特性,并且生命只有成功識別抗原的免疫細胞才得以增殖,經(jīng)變異后的免疫細胞分化為效應(yīng)細胞(抗體)和記憶細胞兩種。但計算領(lǐng)域的克隆選擇算法(Colonel Selection Algorithm,CSA)卻直到2001年才由D.castro和von Zuben明確提出,能夠完成機器學(xué)習(xí)和模式識別的任務(wù),并可以用來解決優(yōu)化問題。其核心是復(fù)制(克隆)和變異。前者與個體的親和度成正比,保證群體親和度逐步增大,后者與個體的親和度成反比,保留最佳個體并改進較差個體。
克隆選擇算法是基于群體的免疫算法,是一種模擬免疫系統(tǒng)的學(xué)習(xí)過程的進化算法,它模擬這一過程進行優(yōu)化。也是抗體集進行群體更新的策略(如圖2)。
圖2 基于克隆選擇的免疫識別算法
STEP1:抽取抗原集合中的一個抗原。
STEP2:計算與抗體集合中每個抗體的親和力;從中選擇n個親和力最高的抗體。
STEP3:對選擇出來的抗體進行克隆增殖,目的是確定對各抗體所在鄰域做局部搜索的次數(shù)??寺∫?guī)模正比于抗體的親和度,即親和度高的抗體得到的局部搜索的機會較多。
STEP4:對克隆產(chǎn)生的個體進行突變,用來對各抗體所在的鄰域進行局部搜索,變異位數(shù)反比于其同抗原的親和力,即對親和度較高的抗體,則在其較小的鄰域范圍內(nèi)做精細搜索。
STEP5:壓縮選擇,在抗體群中選擇具有最高親和度的n個抗體組成新一代抗體群,更新抗體集合。
STEP6:如果滿足終止條件,則結(jié)束;否則轉(zhuǎn)至STEP1繼續(xù)執(zhí)行。
從算法流程分析得知,克隆選擇的主要特征是免疫細胞在抗原刺激下產(chǎn)生克隆增殖,隨后通過遺傳變異分化為多樣性效應(yīng)細胞(如抗體細胞)和記憶細胞??寺∵x擇對應(yīng)著一個親和力成熟(affinity maturation)的過程,即對抗原親和力較低的個體在克隆選擇機制的作用下,經(jīng)歷增殖復(fù)制和變異操作后,其親和力逐步提高而“成熟”的過程,本質(zhì)上是一個達爾文式的選擇和變異的過程。
利用人工免疫的基本原理來解決計算機系統(tǒng)的安全問題,主要也是區(qū)分“自體”和“非自體”的問題,人工免疫系統(tǒng)是具有自學(xué)習(xí)、自適應(yīng)、自組織的高度復(fù)雜性系統(tǒng)的代表,己經(jīng)迅速成為研究熱點,其研究成果已應(yīng)用到計算機安全、模式識別、機器學(xué)習(xí)、機器人控制、異常和故障檢測、數(shù)據(jù)挖掘和分析及復(fù)雜優(yōu)化問題求解等諸多領(lǐng)域。
[1]劉若辰,杜海峰,焦李成.免疫多克隆策略[J].計算機研究與發(fā)展.2004.