劉恩海，宋瑞平，樊世燕

（河北工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與軟件學(xué)院，天津300401）

0 引 言

主要的人工免疫算法有否定選擇算法、克隆選擇算法以及免疫網(wǎng)絡(luò)模型［1］。否定選擇算法是Forrest博士在1994年依據(jù)生物體中T細(xì)胞成熟過程的機(jī)制提出的一種免疫算法。算法首先定義一部分自體集合，然后隨機(jī)產(chǎn)生部分候選檢測器集合，在特定的匹配規(guī)則下，如果候選檢測器集合和自體匹配，則將這些檢測器丟棄，只有那些與所有自體都不匹配的檢測器集合才能被留下來，作為檢測器用以檢測異常。由于候選檢測產(chǎn)生的隨機(jī)性，使得否定選擇算法的時(shí)間消耗與自體集合呈指數(shù)關(guān)系，當(dāng)自體集合很大時(shí)，該算法會(huì)造成時(shí)間和空間的巨大浪費(fèi)，檢測效率不高。否定選擇算法的主要技術(shù)要點(diǎn)包括［2］：問題空間和檢測器的表示形式、匹配規(guī)則的選擇、檢測器的生成機(jī)制和檢測器存儲(chǔ)形式。如何快速有效生成檢測器是否定選擇算法的關(guān)鍵。自否定選擇算法提出以來，大量的研究和改進(jìn)算法被相繼提出來。D’haeseleer提出了線性時(shí)間檢測器生成算法和貪心檢測器生成算法，使檢測器產(chǎn)生的時(shí)間大小與自體集合呈線性關(guān)系，盡管貪心算法使檢測器的覆蓋空間變大，但是這2種算法都不可避免的會(huì)產(chǎn)生冗余和漏洞現(xiàn)象。張衡，吳禮發(fā)等提出了一種r可變陰性選擇算法，通過調(diào)整匹配閾值大幅度降低黑洞數(shù)量。何申等提出了一種檢測器長度可變的否定選擇算法，通過檢測器長度的變化來提高檢測器的覆蓋范圍。楊銘魁［3］對(duì)該算法進(jìn)行了改進(jìn)。Lis－kiewicz M等［4］針對(duì)窮舉法存在的問題，提出了非窮舉法。Elberfeld M等［5］提出了壓縮法，將檢測器集進(jìn)行壓縮將時(shí)間復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)，減少了檢測器數(shù)量。柴爭義，張雄美等［6，7］將檢測器的表示形式從字符串空間轉(zhuǎn)到向量空間和矩陣空間。王輝，敖民等［8，9］采用可變模糊匹配陰性選擇算法，提出了具有一定連續(xù)相似度的模糊匹配。大多數(shù)文獻(xiàn)探討匹配閾值的變化，檢測器長度的變化和檢測器形狀的改變來生成檢測器。基于隨機(jī)搜索的策略，所產(chǎn)生的檢測器具有非常大的檢測漏洞，會(huì)造成時(shí)間和空間的巨大消耗。楊寧等［10］將小生境策略用于否定選擇算法以提高效率。張清華等［11］提出了一種新型的針對(duì)二進(jìn)制串的切割否點(diǎn)選擇算法。為了提高檢測器檢測非自體的效率，蔡濤等［12］提出了一種基于紅黑樹的快速否定選擇算法。劉星寶等［13］提出了一個(gè)檢測器快速生成策略，該算法充分利用自體信息，根據(jù)r值大小將自體集分段，得到自體集合相應(yīng)段的補(bǔ)集，通過二叉樹連接得到檢測器集合，該算法能保證所產(chǎn)生的檢測器不與自體匹配，加快檢測器生成的速度，但是該算法會(huì)產(chǎn)生大量的冗余，現(xiàn)有的去除冗余檢測器的方法是，當(dāng)新生成一個(gè)檢測器時(shí)，讓該檢測器與檢測器集合中的檢測器進(jìn)行匹配，如果匹配，即此檢測器能由已有檢測器集合中的檢測器代替，則舍棄此檢測器，但是該方法會(huì)產(chǎn)生二次冗余問題，因?yàn)闄z測器是順序產(chǎn)生的，先放入檢測器集合中的檢測器會(huì)與后放入檢測器集合中的覆蓋范圍相交，所以經(jīng)過一次去除冗余并不能保證檢測器集合中的檢測器不存在冗余。好的檢測集集合應(yīng)該保證：不與自體空間匹配且用最小的檢測器集合幾乎能夠完全覆蓋所有的非自體空間。

本文在層次匹配算法的基礎(chǔ)上，提取出所有自體集合的以r為大小的段的補(bǔ)集合，在連接策略上進(jìn)行改進(jìn)，盡量達(dá)到集合的劃分，產(chǎn)生能覆蓋最大非己空間的最小檢測器集合，降低檢測器產(chǎn)生的時(shí)間，減小檢測器個(gè)數(shù)，擴(kuò)大等量檢測器的覆蓋范圍，提高檢測效果。

1 基于集合的劃分與覆蓋的檢測器集生成算法

1.1 問題描述

否定選擇算法的目的是找到一個(gè)檢測器集合，在不與自體集合匹配的前提下，盡可能多的匹配非自體。由于計(jì)算機(jī)中的數(shù)據(jù)和文件都是由二進(jìn)制表示的，本文將問題空間U定義在二進(jìn)制串集合上即m＝2。U＝ ｛0，1｝L代表自體、檢測器、抗原都以長度為L的二進(jìn)制串表示。自體集為Self，非自體集為Nonself，根據(jù)定義有Self∩Nonself＝φ，Self∪Nonself＝U。Nx：集合X的大小。如Ns表示Self中字符串個(gè)數(shù)，NR表示檢測器集的大小。匹配規(guī)則仍采用r連續(xù)位匹配規(guī)則，即2個(gè)字符串若有連續(xù)r個(gè)位置相同，則2個(gè)字符串匹配。例如：11，10在r≤3時(shí)匹配。根據(jù)匹配規(guī)則，2個(gè)隨機(jī)字符串匹配的概率為

否定選擇算法需要首先隨機(jī)產(chǎn)生一定數(shù)量的候選檢測器NR0，在固定的匹配概率PM下大小與自體集呈指數(shù)關(guān)系

定義檢測失敗率Pf為一個(gè)抗原不能被檢測器集合中任一檢測器檢測到的概率

由于無需先驗(yàn)知識(shí)，只需利用有限數(shù)量的正常樣本便能檢測出無限的異常數(shù)據(jù)，使得NS算法被廣泛應(yīng)用，但同時(shí)由于候選檢測器產(chǎn)生的隨機(jī)性，每一個(gè)候選檢測器都要和自體進(jìn)行匹配，只有與自體集合中的所有自體都不匹配的候選檢測器將被保留下來。否定選擇算法的時(shí)間復(fù)雜度取決于2個(gè)因素：產(chǎn)生初始檢測器集合的時(shí)間以及檢測器集與自體集中每個(gè)數(shù)據(jù)匹配的時(shí)間?？臻g復(fù)雜度取決于自體集大小。在自體集合很大時(shí)，該算法會(huì)造成時(shí)間和空間的巨大浪費(fèi)，檢測效率不高。

1.2 提取補(bǔ)集

由于r連續(xù)位匹配規(guī)則的特殊性，傳統(tǒng)的免疫算法在產(chǎn)生候選檢測器的時(shí)候，需要和自體進(jìn)行連續(xù)r位匹配，如果匹配則刪除或者進(jìn)行位變異等方法；在檢測器抗原的時(shí)候，也是利用抗原與檢測器進(jìn)行連續(xù)r位匹配，不同的檢測器有可能包含同樣的檢測因子，使得在匹配的時(shí)候存在重復(fù)提取相同檢測器子串造成重復(fù)匹配，將耗費(fèi)大量的時(shí)間，使檢測效率降低。如果使不同的檢測器盡量包含不同的檢測因子，這將大大提高檢測器的性能。傳統(tǒng)的算法沒有充分利用自體集的模式信息，本文的檢測器生成算法，第一部分采用文獻(xiàn) ［14］中提取自體集每個(gè)分段補(bǔ)集的方法，即對(duì)長度為L的字符串集合，匹配位長度為r，其每個(gè)自體有L－r＋1個(gè)分段，依次提取自體集中每段r位字符串，由于包含這些段信息的字符串會(huì)與自體匹配，所以根據(jù)與2r所產(chǎn)生的全局空間比較得到所有自體段中每段r位字符串的補(bǔ)集，這些補(bǔ)集都不能與自體匹配，因此將作為檢測器的組成部分。

例1自體集合為 ｛100000，101101，111001｝。在r＝3時(shí)，產(chǎn)生的關(guān)于自體集的補(bǔ)集為C1～3＝ ［000，001，010，011，110］；C2～4＝ ［001，010，100，101，111］；C3～5＝［001，010，011，101，111］；C4～6＝ ［010，011，100，110，111］。

1.3 檢測器生成算法

上述各個(gè)補(bǔ)集的意義為，合格的檢測器的1～3位應(yīng)該為C1～3［］中的字符串；第2～4位應(yīng)該為C2～4［］中的字符串；第3～5位應(yīng)該為C3～5［］中的字符串，第4～6位應(yīng)該為C4～6［］中的字符串，也就是說若C1～3［］中某個(gè)字符串的2，3位與C2～4［］中某個(gè)字符串的1，2位相同，則可將C2～4［］中字符串的第3位鏈接到C1～3［］中對(duì)應(yīng)字符串的第4位，因?yàn)镃1～3［］中串的第4位只有0或1這2種形式，因此可以將串鏈接的過程表示為二叉樹鏈接的方式，以此類推，直到得到達(dá)到固定檢測率的檢測器集合，但上述做法，勢(shì)必會(huì)造成大量的冗余，因?yàn)槊總€(gè)補(bǔ)集段中的字符串只充當(dāng)一個(gè)檢測因子的作用，但是其會(huì)被多次鏈接為檢測器，這樣會(huì)造成大量的檢測器存在重復(fù)檢測因子，不但加大了工作量而且降低了檢測效率。

1.4 基于集合的劃分與覆蓋的檢測器生成算法

定義1 設(shè)A是任意幾乎，π是由A的若干子集組成的集合。如果下列3個(gè)條件成立：

（1）對(duì)于任意c∈π，均有Ai≠Φ；

（2）任意Ai，Aj∈π，i≠j，有Ai∩Aj＝Φ；

則稱π是集合A的一種劃分。

定義2 設(shè)A是集合，如果這些非空子集的并集等于A，則由A的若干非空子集構(gòu)成的集合稱為A的覆蓋。集合A的覆蓋不必要求2個(gè)不同的子集不相交［14］。

算法如下：設(shè)字符串長度為L，匹配位長為r，將自體集分段，在全局空間UL對(duì)應(yīng)產(chǎn)生自體集合的補(bǔ)集為C1［］，C2［］…Cs［］。C1［］，C2［］…Cs［］中各個(gè)補(bǔ)串的長度為r。

根據(jù)集合的覆蓋與劃分的定義，所產(chǎn)生的檢測器集合最理想的情況是鏈接上補(bǔ)集中所有的串，這樣就能產(chǎn)生覆蓋所有的非自體空間，同時(shí)使補(bǔ)集中的串鏈接且只鏈接一次，這樣就能保證所產(chǎn)生的檢測器集合最小，也就是產(chǎn)生補(bǔ)集的劃分，然而在真實(shí)的網(wǎng)絡(luò)檢測環(huán)境中，所產(chǎn)生的自體集的補(bǔ)集并不能保證都能鏈接成檢測器，有的補(bǔ)集中的串要被鏈接多次，有的補(bǔ)集中的串一次都不會(huì)被鏈接到。在這種情況下，就要盡可能地產(chǎn)生補(bǔ)集的覆蓋，盡可能多的鏈接上補(bǔ)集中的串，同時(shí)使補(bǔ)集中的串重復(fù)鏈接次數(shù)最小。

具體實(shí)現(xiàn)步驟如下：①從C1［］中的第一個(gè)串開始與C2［］中的串進(jìn)行比較，C1［］中每個(gè)串的第2…r位與C2［］中的1…r－1位進(jìn)行比較，這可能會(huì)出現(xiàn)3種情況，C1［］中的串的2…r位與多個(gè)C2［］中的串的1…r－1位匹配；C1［］中的串的2…r位與只與一個(gè)C2［］中的串的1…r－1位匹配；C1［］中的串的2…r位與C2［］中的串的1…r－1位無匹配。首先鏈接C1［］中的那些2…r位只與一個(gè)C2［］中的串的1…r－1位匹配的串，將C2［］中對(duì)應(yīng)串的第r位添加到C1［］中對(duì)應(yīng)串的后面，這樣就能盡可能的向集合的劃分靠攏，接著依此規(guī)則鏈接C2［］與C3［］中的串，直到Cs－1［］與Cs［］中的串鏈接完畢；②對(duì)C1［］中每個(gè)串的第2…r位與多個(gè)C2［］中的1…r－1位串匹配的串，從C2［］中未被鏈接的串中任選一個(gè)進(jìn)行鏈接，每次鏈接都依此規(guī)則，形成新的檢測器；③經(jīng)過前面兩部驟，補(bǔ)集中會(huì)剩下兩類串，一類是和本數(shù)組內(nèi)的串有前r－1位匹配，為了保證最大的非自體空間覆蓋率，對(duì)這類串進(jìn)行回溯，與前面的補(bǔ)集段中的串進(jìn)行鏈接，再向后遞歸，鏈接成檢測器；還有一類串是不管回溯和遞歸都不能鏈接成檢測串，對(duì)這些串就進(jìn)行放棄。

依據(jù)此算法，對(duì)例1中的補(bǔ)集鏈接成檢測器恰巧能構(gòu)成補(bǔ)集的一個(gè)劃分。如圖1所示。

圖1 檢測器鏈接過程

產(chǎn)生的檢測器集合為｛000100；001010；010011；011111；110110｝。這個(gè)檢測器集合把自體補(bǔ)集中的所有檢測因子都包含在此檢測器集中，因此這個(gè)檢測器集合能覆蓋所有的非自體空間，同時(shí)由于每個(gè)補(bǔ)集中的串鏈接且只連接了一次，因此這個(gè)檢測器集合所包含的檢測器個(gè)數(shù)是最少的，比經(jīng)過去除冗余之后產(chǎn)生的檢測器還要少。

復(fù)雜性分析：本算法的時(shí)間復(fù)雜度為產(chǎn)生自體集合相應(yīng)段的補(bǔ)集的時(shí)間和鏈接成檢測器的時(shí)間，對(duì)于Ns個(gè)自體集合依據(jù)r連續(xù)位匹配，每個(gè)自體產(chǎn)生L－r＋1個(gè)分段，因此算法第一步的時(shí)間復(fù)雜度為Ns＊ （L－r＋1）＊r，鏈接成檢測器這一步驟為取到每個(gè)補(bǔ)集段中的串按照劃分與覆蓋的原則進(jìn)行鏈接，其時(shí)間復(fù)雜度為Ns＊ （L－r＋1）＊ （r－1），所以總的時(shí)間復(fù)雜度為 Ns＊ （L－r＋1）＊（2r－1）?？臻g復(fù)雜度為鏈接成的檢測器集合的大小為：2r－Ns。

2 實(shí)驗(yàn)分析

為了驗(yàn)證本文提出的算法的性能和檢測效果，本文在Windows7平臺(tái)下進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為：CPU為intel雙核酷睿2P7450，內(nèi)存2G，運(yùn)行環(huán)境為Matlab7.10。為了與已有檢測器生成算法進(jìn)行比較以及簡便起見，在這部分的試驗(yàn)中，暫時(shí)不考慮檢測器的生命周期問題。實(shí)驗(yàn)分為兩組，第一組測試在同樣的檢測失敗率條件Pf下，去除冗余后的線性時(shí)間檢測器生成算法，檢測器快速生成算法［14］，本文算法，產(chǎn)生的檢測器個(gè)數(shù)比較以及所耗費(fèi)的時(shí)間比較。第二組實(shí)驗(yàn)驗(yàn)證在相同數(shù)量的檢測器個(gè)數(shù)下，3種算法能成功檢測非法集合的概率。實(shí)驗(yàn)參數(shù)設(shè)置及實(shí)驗(yàn)過程如下：①L＝8，生成256個(gè)8位的二進(jìn)制串，依次隨機(jī)選取8，16，32，64，128個(gè)二進(jìn)制字符串作為自體，其余的二進(jìn)制串作為抗原，位串間采用的匹配位長度r為6。Pf設(shè)為0.1，重復(fù)隨機(jī)產(chǎn)生自體個(gè)數(shù)的步驟50次，統(tǒng)計(jì)在不同的自體個(gè)數(shù)下，3種算法在確定的匹配概率下，需要的平均檢測器個(gè)數(shù)和消耗的平均時(shí)間比較；②采用①中產(chǎn)生的檢測器，對(duì)應(yīng)相同數(shù)量的自體，將剩下的檢測器作為抗原，統(tǒng)計(jì)在相同數(shù)量的檢測器個(gè)數(shù)下，3種算法成功檢測非自體的平均值。

由表1可以看出，本文算法相比于前2種算法，在同樣的檢測失敗率下，產(chǎn)生的檢測器數(shù)量大大減小，同時(shí)耗費(fèi)的時(shí)間也明顯降低。由表2可知，在同樣的檢測器數(shù)量下，本文算法的檢測效率最優(yōu)，檢測效果最好。

表1 3種算法在固定的檢測失敗率Pf下所需檢測器個(gè)數(shù)及消耗時(shí)間

表2 3種算法在相同數(shù)量的檢測器集合下檢測成功率

3 結(jié)束語

本文提出的針對(duì)集合的劃分與覆蓋關(guān)系的檢測器生成算法，能用最小的檢測器集合覆蓋最大的非自體空間，降低了產(chǎn)生檢測器的時(shí)間消耗，同時(shí)提高了檢測器的檢測性能。為了進(jìn)一步提高算法的性能，可以考慮在匹配規(guī)則，如何選擇參數(shù)，消除檢測器漏洞等方面進(jìn)行研究，降低誤報(bào)與漏報(bào)率，提高算法的實(shí)時(shí)性和有效性。

［1］Dasguptaa D，Yue S，Nino F.Recent advances in artifical immune systems： Models and applications ［J］.Applied Soft Computing，2011，11：1574－1587.

［2］JIN Zhangzan，LIAO Minghong，XIAO Gang.Survey of negative selection algorithms ［J］.Journal on Communications，2013，34 （1）：159－170 （in Chinese）.［金章贊，廖明宏，肖剛.否定選擇算法綜述 ［J］.通信學(xué)報(bào)，2013，34 （1）：159－170.］

［3］YANG Mingkui.Improved variable－length detector generation algorithm ［J］.Computer Engineering，2010，36 （15）：174－175（in Chinese）.［楊銘魁.改進(jìn)的變長檢測器產(chǎn)生算法［J］.計(jì)算機(jī)工程，2010，36 （15）：174－175.］

［4］Lisjuewicz M，Textor J.Negative selection algorithms without generating detectors［C］／／Porland，Oregon，USA：GECCO ACM，2010：1047－1054.

［5］Elderfeld M，Textor J.Efficient algorithms forstring＿based negative selection ［G］.LNCS 5666：Proc of ICARIS.Springer，2009：109－121.

［6］CHAI Zhengyi，WU Huixin，WU Yong.Optimization algorithm for immune real－value detector generation ［J］.Journal of Jilin University （Engineering and Technology Edition），2012，42 （5）：1251－1256 （in Chinese）.［柴爭義，吳慧欣，吳勇.用于異常檢測的免疫實(shí)值檢測器優(yōu)化生成算法 ［J］.吉林大學(xué)學(xué)報(bào)，2012，42 （5）：1251－1256.］

［7］ZHANG Xiongmei，YI Zhaoxiang，SONG Jianshe，et al.Re－search on negative selection algorithm based on matrix representation ［J］.Journal of Electronics ＆ Information Technology，2010，32 （11）：2701－2706 （in Chinese）.［張雄美，易昭湘，宋建社，等.基于矩陣形式的否定選擇算法研究 ［J］.電子與信息學(xué)報(bào)，2010，32 （11）：2701－2706.］

［8］WANG Hui，YU Lijun，WANG Kejun，et al.An adjustable fuzzy matching negative selection algorithm ［J］.CAAIT Transactions on Intelligent Systems，2011，6 （2）：178－184 （in Chinese）.［王輝，于立君，王科俊，等.一種可變模糊匹配陰性選擇算法 ［J］.智能系統(tǒng)學(xué)報(bào)，2011，6 （2）：178－184.］

［9］AO Min.Research on detector generating algorithm based on negative selection ［D］.Chongqing：College of Computer Science of Chongqing University，2010：29－43 （in Chinese）.［敖民.基于陰性選擇的檢測器生成算法研究 ［D］.重慶：重慶大學(xué)計(jì)算機(jī)學(xué)院，2010：29－43.］

［10］YANG Ning， WANG Qian.Negative selection algorithm based on niche strategy ［J］.Computer Science，2011，38（10A）：181－184 （in Chinese）.［楊寧，王茜.一種基于小生境策略的陰性選擇算法 ［J］.計(jì)算機(jī)科學(xué)，2011，38（10A）：181－184.］

［11］ZHANG Qinghua，ZHAO Hongxia，ZHU Yuejun，et al.Generate detector on novel negative selection algorithm ［J］.Electronic Design Engineering，2010，18 （11）：8－11 （in Chinese）.［張清華，趙紅霞，朱月君，等.一種新型的否定選擇算法生成檢測器的研究 ［J］.電子設(shè)計(jì)工程，2010，18 （11）：8－11.］

［12］CAI Tao，JU Shiguang，NIU Dejiao.Efficient negative selec－tion algorithm and its analysis［J］.Journal of Chinese Computer Systems，2009，30 （6）：1171－1174 （in Chinese）.［蔡濤，鞠時(shí)光，牛德嬌.快速否點(diǎn)選擇算法的研究與分析［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009，30 （6）：1171－1174.］

［13］LIU Xingbao，CAI Zixing.Fast detector generative strategy for negative selection algorithm ［J］.Journal of Chinese Com－puter Systems，2009，7 （7）：1263－1267 （in Chinese）.［劉星寶，蔡自興.負(fù)選擇算法中的檢測器快速生成策略 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009，7 （7）1263－1267.］

［14］DENG Huiwen.Discrete mathematics［M］.Beijing：Tsinghua University Press，2010：29－32 （in Chinese）.［鄧輝文.離散數(shù)學(xué) ［M］.北京：清華大學(xué)出版社，2010：29－32.］