劉恩海，宋瑞平，樊世燕

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

0 引 言

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

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

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

1.1 問題描述

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

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

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

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

1.2 提取補集

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

例1自體集合為 ｛100000，101101，111001｝。在r＝3時，產(chǎn)生的關于自體集的補集為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 檢測器生成算法

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

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

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

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

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

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

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

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

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

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

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

圖1 檢測器鏈接過程

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

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

2 實驗分析

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

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

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

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

3 結(jié)束語

本文提出的針對集合的劃分與覆蓋關系的檢測器生成算法，能用最小的檢測器集合覆蓋最大的非自體空間，降低了產(chǎn)生檢測器的時間消耗，同時提高了檢測器的檢測性能。為了進一步提高算法的性能，可以考慮在匹配規(guī)則，如何選擇參數(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］.通信學報，2013，34 （1）：159－170.］

［3］YANG Mingkui.Improved variable－length detector generation algorithm ［J］.Computer Engineering，2010，36 （15）：174－175（in Chinese）.［楊銘魁.改進的變長檢測器產(chǎn)生算法［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）.［柴爭義，吳慧欣，吳勇.用于異常檢測的免疫實值檢測器優(yōu)化生成算法 ［J］.吉林大學學報，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］.電子與信息學報，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)學報，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］.重慶：重慶大學計算機學院，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］.計算機科學，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］.電子設計工程，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）.［蔡濤，鞠時光，牛德嬌.快速否點選擇算法的研究與分析［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）.［劉星寶，蔡自興.負選擇算法中的檢測器快速生成策略 ［J］.小型微型計算機系統(tǒng)，2009，7 （7）1263－1267.］

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