2 基于網格的實值否定選擇算法

2.1 引言

在過去的十年間，人工免疫系統作為一種解決復雜計算問題的新方法引起了廣泛的關注。當前，對人工免疫的研究主要集中在四個方面：否定選擇算法、免疫網絡、克隆選擇、危險理論和樹突狀細胞算法。否定選擇算法通過模擬生物系統的T細胞成熟過程中的免疫耐受機制，刪除自反應候選檢測器來識別非自體抗原，并成功應用于模式識別、異常檢測、機器學習、故障診斷等。

否定選擇算法是由Forrest等提出的。該算法采用字符串或二進制串來編碼抗原（樣本）和抗體（檢測器），采用r-連續位匹配方法來計算抗原和檢測器間的親和力，被稱為SNSA。Forrest等提出的否定選擇算法中，采用二進制字符串表示抗原和抗體，并采用r連續位匹配算法計算抗體與抗原的匹配程度，成功應用于異常檢測系統。之后，Balthrop等指出了r-連續位匹配存在的漏洞并提出了改進的r-chunk匹配機制。張衡等提出了r-可變否定選擇算法，何申等提出了檢測器長度可變否定選擇算法。

Li指出，在SNSA算法中，檢測器的生成效率是非常低的。候選檢測器通過否定選擇變為成熟檢測器。假定Ns為訓練集大小，P′為任意抗原和抗體之間的匹配概率，Pf為失敗率；則候選檢測器的數量為N = - ln（Pf）/[P′(1 -P′) Ns]，與Ns成指數關系，且SNSA的時間復雜度為O（N·Ns）。

在實際應用中，很多問題都是在實值空間定義和研究的，Gonzalez等提出了實值否定選擇算法（RNSA）。該算法采用實值空間[0,1]n的n維向量對抗體和抗原進行編碼，采用Minkowski距離計算親和力。Ji等提出了一種變半徑的實值否定選擇算法（V-Detector），得出了更好的結果。該算法通過計算候選檢測器的中心與自體抗原的最近距離，來動態決定一個成熟檢測器的半徑。同時，該算法提出了一種基于概率的方法來計算檢測器的覆蓋率。Gao等提出了一種基于遺傳原理的否定選擇算法，Gao、Chow等提出了一種基于克隆優化的否定選擇算法。這兩種算法的檢測器通過優化算法的處理，來獲得更多的非自體空間覆蓋率。Shapiro等在否定選擇算法中引入了超橢圓體檢測器，Ostaszewski等引入了超矩形檢測器。這些檢測器相比球形檢測器，可以以較少的檢測器達到同樣的覆蓋率。Stibor等提出了自體檢測器分類方法。在該方法中，自體被看成是有初始半徑的自體檢測器，而且在訓練階段自體的半徑可以通過ROC（接收工作特征）分析動態確定，提高了檢測率。Chen等提出了一種基于自體集層次聚類的否定選擇算法。該算法通過對自體集進行層次聚類預處理來改進檢測器的生成效率。Gong等將檢測器分為自體檢測器和非自體檢測器，分別覆蓋自體空間和非自體空間，用自體檢測器代替自體元素從而減少計算代價。

還有一些研究將其他人工智能算法引入否定選擇算法中，來提高檢測器的生成效率。Gao等和Abdolahnezhad等提出了一種基于遺傳原理的否定選擇算法，Idris將粒子群優化策略與否定選擇算法結合起來，Lima等將小波變換引入否定選擇算法中。

由于成熟檢測器的生成效率較低，否定選擇算法的時間代價嚴重限制了它們的實際應用。本書提出了一種基于網格的實值否定選擇算法，記為GBRNSA。該算法分析了自體集在形態空間的分布，并引入了網格機制，來減少距離計算的時間代價和檢測器間的冗余覆蓋。理論分析和實驗結果表明，GBRNSA降低了檢測器的數量、時間復雜度及誤報率。