具有疫苗算子的可變模糊匹配陰性選擇算法

王 輝，于立君，畢曉君，張利軍

(1.哈爾濱工程大學自動化學院，150001哈爾濱，whjyylj@163.com; 2.哈爾濱工程大學信息與通信工程學院，150001哈爾濱)

機體免疫功能是對抗原刺激的應答，稱為免疫應答，這種應答分為先天性免疫應答和自適應免疫應答.接種疫苗可以建立自適應免疫應答，也稱為特異性免疫反應［1-2］.特異性免疫是機體通過記憶或借助外部力量調節自身以增強免疫能力的過程.免疫系統通過疫苗的作用，提高個體的環境適應能力.焦李成提出基于疫苗的免疫進化算法，把工程問題的某些先驗知識抽象成疫苗，通過接種疫苗和免疫選擇來提高候選解的適應度并防止解的退化［3］，大大改善候選解的質量，在該領域產生了深遠的影響.文獻［4］提出了在最優路徑中父代最優個體疫苗，王磊在遺傳算法中引入包括免疫疫苗的免疫算子，構造了一類免疫遺傳算法，并用于求解TSP問題［5］.文獻［6］提出了一個網絡入侵檢測模型，該模型集成了陰性選擇、克隆選擇與接種疫苗算子，具有分布式、自組織和輕量級的特性.本文將疫苗理論引入到陰性選擇算法中，建立可變模糊匹配陰性選擇免疫算法［7］的特異性免疫反應功能.由于陰性選擇算法中需多次遍歷檢測器集和自體集并計算抗原與檢測器匹配度，因此匹配算法的效率及檢測器集檢測自體集的效率是影響陰性選擇算法效率的關鍵因素，將疫苗算子加入到檢測器集中，并采用基因位r間隔迭次取用思想，可以大大提高檢測效率，縮短二次應答時間.同時利用疫苗提取與接種過程動態刷新抗體庫，增強抗體庫的記憶功能.仿真表明疫苗算子的加入使算法具有更快的運行速度和更低的檢測失敗率，抗體庫的更新具有自適應性.

1 可變模糊匹配陰性選擇免疫算法

可變模糊匹配陰性選擇免疫算法是基于普通陰性選擇算法提出的，該算法匹配閾值可變，通過檢測及調整匹配閾值來減少傳統陰性選擇算法中“黑洞”的數量.同時，由于抗體與抗原匹配時具有不確定性和模糊性，算法利用模糊思想，定義模糊相似度，實現了抗體與抗原的帶有控制參數的模糊匹配，從而提高系統的檢索率和性能.

2 疫苗算子

2.1 疫苗算子

在算法中加入疫苗算子可以增強算法的記憶功能，同時可以提高算法的響應速度.疫苗算子可以由算法自身在檢測過程中產生，這個過程與生物體免疫過程中所產生的記憶細胞類似，因此，疫苗能夠增強算法的記憶功能.同時，由于疫苗只是個體在某些基因位上的特征，其本身并不是個體，因此疫苗需要某種載體來存放.而疫苗是基于抗原產生的，因此疫苗算子的獲取在連續r位匹配規則下，應該是連續r個基因模式，而疫苗所在的抗原既具有特征基因位，又具有r個基因模式，將抗原作為該疫苗的載體進入疫苗抗體庫，可形成疫苗算子.利用可重用的檢測元作為疫苗抗體，既保證了疫苗的質量，又增加了抗體的多樣性.

2.2 正選擇算子

在生物免疫中，免疫細胞所經歷的逆于負選擇(陰性選擇)的另一個成熟抗體的過程就是正選擇過程，與負選擇同樣重要［8］.在以往的相關文獻中，往往都忽視了正選擇這一重要過程.抗體庫在生成時，是一個負選擇的過程，算法所關心的是沒有任何匹配發生時待選檢測器才能進入抗體庫.而在用疫苗進行檢測過程中，與疫苗發生匹配的是檢測到的二次入侵的抗原，算法所關心的就是匹配是不是發生了，因此是一個正選擇的過程.

2.3 提取疫苗

本算法中對疫苗的提取采用自適應的方法.針對self集首先利用可變模糊匹配陰性選擇免疫算法的有效檢測器集生成算法［9］生成有效檢測器集D，改變self集的某一個片段，模擬抗原的入侵，并用檢測器集D檢測.若發生了正選擇匹配，則將基因連同self集中的載體提取為疫苗，加入到抗體庫(檢測器集)中.此時抗體庫包含2部分:有效檢測器集D和疫苗.利用抗體庫繼續檢測self集的下一個元素:先由疫苗進行正選擇匹配，若有匹配發生，則產生報警(檢測到抗原);若沒有檢測到，再由有效檢測器集D進行檢測，將檢測到的匹配提取為疫苗，更新抗體庫.隨著self集的改變，抗體庫中的疫苗會自適應地產生，并參與下一輪的檢測，抗體庫得到動態的刷新.

疫苗提取算法步驟如下:1)由可變模糊匹配陰性選擇免疫算法生成有效檢測器集D;2)生成抗體庫;3)讀待檢文件，進行疫苗正選擇匹配.若有匹配發生，產生報警;否則，利用檢測器集D檢測;4)D檢測若有匹配發生，提取為疫苗，轉到第2步;5)否則，若檢測尚未完成，轉到第3步;6)若檢測完成，生成檢測報告.

3 具有疫苗算子的可變模糊匹配陰性選擇算法仿真

疫苗算子和正選擇算子的主要作用就是對抗原形成免疫記憶，從而建立二次免疫應答，并大大縮短二次應答時間，因此，這2種算子應加在可變模糊匹配陰性選擇免疫算法的監測系統異常部分.在監測階段加入疫苗算子和正選擇算子，可使算法在監測階段的二次應答時間大大縮短.由于提取疫苗時采用自適應方法，使抗體庫在每檢測到一個抗原時能得到動態刷新，從而使可變模糊匹配陰性選擇免疫算法的檢測效率明顯提高，并能對再次入侵的抗原作快速應答.

3.1 檢測率分析

設PMi為2個隨機串在ri連續位匹配規則下的匹配概率，則

對于一隨機串，在匹配閾值為ri時，不與任何self串匹配的概率為［10］

其中:NS為self集的大小，則該串成為匹配閾值為ri的成熟檢測器概率為

對于NR0個未成熟檢測器，根據上述概率關系可以生成成熟檢測器的個數為

則漏報率Pf滿足［11］:

進而可得檢測率為

由于疫苗的加入，使得抗體庫中成熟檢測器的個數NRi增大，根據式(6)可知抗原檢測率明顯提高.特別是對具有疫苗基因位的特定抗原，檢測失敗率大大降低，對于二次入侵的抗原，疫苗檢測率為100%，且應答時間明顯縮短.

3.2 基因位r間隔迭次取用思想

算法仿真時，生成長度為256字節的二進制文件作為self集NS.取初始匹配閾值r=7，最大匹配閾值rc=11，通過可變模糊匹配陰性選擇免疫算法生成有效檢測器集D.采用模糊匹配方法實現提取疫苗操作及監測self集的改變.由于self集的長度為256字節，共有2 048個二進制位，并且沒有形成獨立的字符串元素的形式，因此，首先要將self集劃分成若干個字符串的形式.本文在仿真時，采用基因位r間隔進行迭次取用，即第1個位串的起始位置為1，第2個起始位置為8，依此類推.這樣既可以減少計算的冗余度，又不會過多地丟失基因位，保證了算法的時間復雜度不會過大，降低檢測失敗率，提高算法的檢測效率.

3.3 仿真分析

仿真時，由于匹配閾值在7～11之間可調，所以D集中就包含匹配閾值7～11之間的檢測器.采用r=7進行疫苗匹配檢測，根據檢測器生成過程可知，匹配閾值大于7的檢測器，會與self集中的個體發生匹配，因此在沒改變self集時卻檢測到了某個匹配.為了保證了在self集沒有改變時，不會被檢測器檢測到，取初始匹配閾值r=6，最大匹配閾值rc=8，利用可變模糊匹配陰性選擇免疫算法重新生成檢測器集D.在加入疫苗算子的可變模糊匹配陰性選擇免疫算法中取迭次間隔為6，匹配閾值為9，分別改變self集的某一個片段，檢測算法的二次應答時間.結果發現算法的二次應答時間并沒有減少，這說明疫苗算子并沒有發揮其真正作用，因此，需進一步改進算法流程.

3.4 取self集整體為研究對象的仿真實現

由于二次應答時間除與self集的大小、機器的速度及抗體數、疫苗數等有關外，主要取決于算法本身的流程.由于在監測階段，算法的設計思想是針對self集中的每一個位串進行檢測，先用所有疫苗進行正選擇檢測，若沒有匹配發生，再用檢測器集進行檢測.初次應答時，抗體庫中的疫苗數較少，檢測相對較快，但二次應答時已經積累了經驗，疫苗數量多，這樣每一個位串在進行疫苗檢測時耗費的時間相對增多，而下一個位串要在前一個位串檢測器集D集檢測后才能進行檢測，檢測器集檢測也要耗費一定的二次應答時間，因此，當檢測到某一個二次入侵的抗原位串時，其前面的所有位串的檢測器集檢測耗費的時間與初次應答的基本相同，二次應答所耗費的時間并沒有減少.

取self集整體為研究對象，調整算法流程，檢測操作時仍然采用r間隔迭次取用.首先利用疫苗進行正選擇匹配檢測，掃描self集整體，提高抗體庫二次應答的速度，然后再用檢測器集檢測，提取疫苗并更新抗體庫.仿真實驗時改變原文件的某個片斷，對疫苗數、二次應答時間及檢測失敗率等進行檢測，每一種實驗重復100次，取平均值作為實驗最終結果，見表1及圖1、圖2所示.從實驗數據可以看出，算法進一步改進后，二次應答時間明顯減少，檢測失敗率顯著降低，檢測效率大大提高，增強了算法的免疫自適應性.表1中，最小抗體數與實際抗體數并不是成比例變化，這主要是由于初始抗體生成時的隨機性以及自我集的相似性，導致實際抗體的冗余性造成的.在各種類型的實驗中，單個字變化的檢測是最難的，所需的抗體數較多.但由于r間隔迭次取用的方法可以有效地避免因self文件的數據被等長劃分而造成的基因缺失，使得算法對單個字的應答可以擴展到字長度的1/4次數(8次)，因而對單個字的檢測率與其他算法相比大大增加.

表1 算法進一步改進后的實驗結果

3.5 與小生境克隆選擇算法的實驗對比

仿真時取m=2，l=32，NR0為初始抗體數，NR為實際抗體數(含疫苗)，Pf為檢測失敗率，并在檢測時間相同的情況下與文獻［11］的小生境克隆選擇算法進行了實驗對比分析，實驗結果如表2所示.可以看出，即使當self文件較大時，加入疫苗算子的可變模糊匹配陰性選擇免疫算法也仍然要明顯好于小生境克隆選擇算法.這是因為克隆選擇算法在克隆過程使抗體間具有極高的相似度，限制了抗體的空間分布，使抗體的多樣性受到抑制.而加入疫苗算子的可變模糊匹配陰性選擇免疫算法通過提取疫苗來獲得新的抗體，疫苗是來源于self信息之外的所遇到過的無限多樣的Nonself字符，這樣既保證了抗體的多樣性，也保證了檢測率的提高.表2中數據是在檢測時間幾乎相同的情況下得到的，從而也進一步驗證了加入疫苗算子的可變模糊匹配陰性選擇免疫算法的執行效率要明顯高于小生境克隆選擇算法.

圖1 應答時間對比

圖2 檢測失敗率對比

表2 檢測時間相同的實驗結果

3.6 疫苗算子對算法性能影響的分析

加入疫苗算子使算法獲得了自學習功能，只需要較少的初始種群，經過不斷地學習來逐步充實完善其抗體庫.同時，疫苗的提取過程保證了抗體的多樣性，并通過疫苗的“記憶”功能來增加算法的檢測經驗.事實上，疫苗能否發揮作用取決于算法能否積累到“學習經驗”，也就是能否檢測到Nonself.檢測效果的好壞也和學習次數的多少以及學習質量有很大的關系.此外，疫苗的存在使算法的時間復雜度增加.在進行疫苗的正選擇檢測過程中，時間復雜度取決于抗體庫中疫苗的數量，并與問題的規模成正比.由于疫苗算子的加入使算法中增加了線性階的時間復雜度，二次應答時間的縮短是以時間復雜度的增加為代價，但時間復雜度增加有限，而應答時間對檢測算法來說是重要的性能指標之一，疫苗算子顯著的提高了算法的快速性，增強了算法的免疫自適應能力，明顯地改善了算法的檢測性能.

4 結論

1)根據生物免疫系統中疫苗免疫的理論，提出了一種可變模糊匹配陰性選擇免疫算法的改進設計方案，在算法的異常監測階段加入了疫苗算子和正選擇算子.

2)分析了疫苗算子的提取過程，通過疫苗的提取，使正選擇算子記住了環境改變的方式，算法的記憶功能得到增強，算法的快速性得到提高，算法對再次入侵的抗原二次應答時間明顯減少.

3)采用基因位r間隔迭次取用的方法，保證了算法中位串基因信息的完整性，降低了檢測失敗率，檢測效率大大提高.疫苗算子的加入使抗體庫能夠隨著self集的改變而動態刷新，改善了算法的性能，可提高算法的免疫自適應性.

［1］丁永生，任立紅.人工免疫系統理論與應用［J］.模式識別與人工智能，2000，13(1):52-59.

［2］肖人彬，王磊.人工免疫系統原理、模型、分析及展望［J］.計算機學報，2002(12):1283-1293.

［3］JIAO Licheng，WANG Lei.A novel genetic algorithm based on immunity［J］.IEEE Transactions on Systems，Man，and Cybernetics:Systems and Humans，2000，30 (5):552-561.

［4］楊輝，康立山，陳毓屏.一種基于構建基因庫求解TSP問題的遺傳算法［J］.計算機學報，2003，26(12):1753 -1758.

［5］WANG Lei，PAN Jin，JIAO Licheng.The immune algorithm［J］.ActaElectronica Sinica:in Chinese，2000，28 (7):74-78.

［6］FANG Xianjin.An artificial immune model with vaccine operator for network intrusion detectio［C］//Proc of 2008 IEEE Pacific-Asia Workshop on Computational Intelligence andIndustrialApplication.Wuhan:IEEE CS Press，2008:488-491.

［7］王輝.可變模糊匹配陰性選擇免疫算法研究［D］.哈爾濱:哈爾濱工程大學，2007.

［8］BENTLEY P J，GORDON T，KIM J.New trends in evolutionary computation［C］//The Congress on Evolutionary Computation(CEC-2001).Seoul，Korea:［s.n.］，2001:162-169.

［9］王輝，王科俊.基于免疫的最小有效檢測器集生成算法［J］.計算機工程，2008，34(9):219-221.

［10］ZHANG Yajing，HOU Chaozhen，WANG Fang.A clone selection algorithm with niching strategy inspiring by biological immune principles for change detection［C］//IEEE International Symposium on Intelligent Control.Texas，US: The Westin Galleria Houston，2003:1000-1005.

［11］張海英，管洪娜，潘永湘.一種改進的陰性選擇算法［J］.西安理工大學學報，2005，21(3):306-309.