基于克隆選擇原理的免疫識(shí)別算法研究

傅慧

南昌陸軍學(xué)院 江西 330103

0 引言

人工免疫系統(tǒng)(Artificial Immune Systems，AIS)是繼神經(jīng)計(jì)算、進(jìn)化計(jì)算之后的自然計(jì)算的研究新方向，己經(jīng)迅速成為研究熱點(diǎn)，主要是通過(guò)深入探索生物免疫系統(tǒng)所蘊(yùn)含的信息處理機(jī)制，建立相應(yīng)的工程模型和算法，用于解決各種復(fù)雜問(wèn)題。

1 免疫系統(tǒng)

生物免疫系統(tǒng)將所有的細(xì)胞分為兩類：Self細(xì)胞(自我)和NonSelf細(xì)胞(非我)。Self細(xì)胞指自身健康，沒(méi)有被感染、破壞的細(xì)胞；NonSelf細(xì)胞指病毒、細(xì)菌、寄生蟲等有害物質(zhì)和自身被感染、破壞的細(xì)胞。免疫就是識(shí)別Self和NonSelf，并消滅NonSelf，是為了保證機(jī)體完整性的一種生理學(xué)反應(yīng)。用集合表示有這么一個(gè)關(guān)系：對(duì)于集合域X，它包括兩個(gè)子集自體集合S和非自體集合N，則有自體集合S?X和非自體集合N?X，而且S∪F=X且S∩F=φ。

2 人工免疫算法

人工免疫系統(tǒng)抽取生物免疫系統(tǒng)所蘊(yùn)含的信息處理機(jī)制，建立用于解決各種復(fù)雜問(wèn)題的工程模型和算法，這些模型和算法都力圖集中體現(xiàn)以上的生物免疫系統(tǒng)的相應(yīng)特點(diǎn)。

人工免疫算法(Artificial Immune Algorithlum，AIA)是模擬人體免疫學(xué)原理而設(shè)計(jì)的一種新型算法，是自然免疫系統(tǒng)在進(jìn)化計(jì)算的一個(gè)實(shí)現(xiàn)。

人工免疫算法的基本流程如圖1。

STEP1：初始化AIA的抗原。對(duì)運(yùn)行過(guò)程所需參數(shù)和數(shù)據(jù)進(jìn)行設(shè)置，包括初始化運(yùn)行參數(shù)、基因庫(kù)以及確定抗體的編碼方式和構(gòu)造初始抗體集，通常可以在解空間中隨機(jī)產(chǎn)生N個(gè)候選解作為初始抗體，N為抗體群中抗體的數(shù)目。

圖1 人工免疫算法的基本流程

STEP2：計(jì)算親和力(affinity)。親和力是一個(gè)抗體結(jié)合部位與一個(gè)抗原決定基結(jié)合的牢固性，結(jié)合自抗原分離的可能越小。用來(lái)表示抗原和抗體之間、抗體和抗體之間結(jié)構(gòu)的相信程度。設(shè)定親和力的計(jì)算函數(shù)為 Affinity(B,G)，一般使用介于0到1之間的實(shí)數(shù)表示，Affinity(B,G)值越大說(shuō)明抗體B和抗原G之間匹配得越好。

STEP3：產(chǎn)生新的抗體。調(diào)用人工免疫算法，初識(shí)抗體通過(guò)人工免疫算法的作用產(chǎn)生新的抗體。

STEP4：調(diào)用Affinity(B,G)，計(jì)算新抗體的親和力。

STEP5：若新抗體中有與抗原匹配的抗體，則結(jié)束，否則轉(zhuǎn)到STEP6。

STEP6：抗體選擇。按照“優(yōu)勝劣汰”的自然選擇機(jī)制，在原有的N個(gè)有效抗體和新產(chǎn)生的若干個(gè)體抗體中選擇出N個(gè)與抗原匹配得較好的抗體構(gòu)成新的抗體群，在進(jìn)行選擇操作時(shí)，應(yīng)依據(jù)抗體之間的排斥力限制進(jìn)入新抗體群中的相同抗體的數(shù)目，以保持抗體群中抗體的多樣性，增強(qiáng)抗體群的免疫力，選擇完成后轉(zhuǎn)到STEP3。

3 基于克隆選擇的免疫識(shí)別算法

克隆選擇學(xué)說(shuō)早在1958年就由Burnet建立，描述了獲得性免疫的基本特性，并且生命只有成功識(shí)別抗原的免疫細(xì)胞才得以增殖，經(jīng)變異后的免疫細(xì)胞分化為效應(yīng)細(xì)胞(抗體)和記憶細(xì)胞兩種。但計(jì)算領(lǐng)域的克隆選擇算法(Colonel Selection Algorithm，CSA)卻直到2001年才由D.castro和von Zuben明確提出，能夠完成機(jī)器學(xué)習(xí)和模式識(shí)別的任務(wù)，并可以用來(lái)解決優(yōu)化問(wèn)題。其核心是復(fù)制(克隆)和變異。前者與個(gè)體的親和度成正比，保證群體親和度逐步增大，后者與個(gè)體的親和度成反比，保留最佳個(gè)體并改進(jìn)較差個(gè)體。

克隆選擇算法是基于群體的免疫算法，是一種模擬免疫系統(tǒng)的學(xué)習(xí)過(guò)程的進(jìn)化算法，它模擬這一過(guò)程進(jìn)行優(yōu)化。也是抗體集進(jìn)行群體更新的策略(如圖2)。

圖2 基于克隆選擇的免疫識(shí)別算法

STEP1：抽取抗原集合中的一個(gè)抗原。

STEP2：計(jì)算與抗體集合中每個(gè)抗體的親和力；從中選擇n個(gè)親和力最高的抗體。

STEP3：對(duì)選擇出來(lái)的抗體進(jìn)行克隆增殖，目的是確定對(duì)各抗體所在鄰域做局部搜索的次數(shù)。克隆規(guī)模正比于抗體的親和度，即親和度高的抗體得到的局部搜索的機(jī)會(huì)較多。

STEP4：對(duì)克隆產(chǎn)生的個(gè)體進(jìn)行突變，用來(lái)對(duì)各抗體所在的鄰域進(jìn)行局部搜索，變異位數(shù)反比于其同抗原的親和力，即對(duì)親和度較高的抗體，則在其較小的鄰域范圍內(nèi)做精細(xì)搜索。

STEP5：壓縮選擇，在抗體群中選擇具有最高親和度的n個(gè)抗體組成新一代抗體群，更新抗體集合。

STEP6：如果滿足終止條件，則結(jié)束；否則轉(zhuǎn)至STEP1繼續(xù)執(zhí)行。

從算法流程分析得知，克隆選擇的主要特征是免疫細(xì)胞在抗原刺激下產(chǎn)生克隆增殖，隨后通過(guò)遺傳變異分化為多樣性效應(yīng)細(xì)胞(如抗體細(xì)胞)和記憶細(xì)胞。克隆選擇對(duì)應(yīng)著一個(gè)親和力成熟(affinity maturation)的過(guò)程，即對(duì)抗原親和力較低的個(gè)體在克隆選擇機(jī)制的作用下，經(jīng)歷增殖復(fù)制和變異操作后，其親和力逐步提高而“成熟”的過(guò)程，本質(zhì)上是一個(gè)達(dá)爾文式的選擇和變異的過(guò)程。

4 結(jié)論

利用人工免疫的基本原理來(lái)解決計(jì)算機(jī)系統(tǒng)的安全問(wèn)題，主要也是區(qū)分“自體”和“非自體”的問(wèn)題，人工免疫系統(tǒng)是具有自學(xué)習(xí)、自適應(yīng)、自組織的高度復(fù)雜性系統(tǒng)的代表，己經(jīng)迅速成為研究熱點(diǎn)，其研究成果已應(yīng)用到計(jì)算機(jī)安全、模式識(shí)別、機(jī)器學(xué)習(xí)、機(jī)器人控制、異常和故障檢測(cè)、數(shù)據(jù)挖掘和分析及復(fù)雜優(yōu)化問(wèn)題求解等諸多領(lǐng)域。

[1]劉若辰,杜海峰,焦李成.免疫多克隆策略[J].計(jì)算機(jī)研究與發(fā)展.2004.