陰性選擇算法檢測器生成的優(yōu)化及仿真

門 洪, 陳 鵬

(東北電力大學 自動化工程學院, 吉林 吉林 132012)

陰性選擇算法檢測器生成的優(yōu)化及仿真

門 洪, 陳 鵬

(東北電力大學 自動化工程學院, 吉林 吉林 132012)

針對現(xiàn)有常規(guī)陰性選擇算法在非我空間覆蓋設計上未考慮自身免疫性檢測器發(fā)生的問題, 提出一種能檢測和剔除自身免疫性檢測器的方法, 并以MATLAB軟件為仿真實驗平臺, 分別對不規(guī)則分布數(shù)據(jù)、環(huán)形分布數(shù)據(jù)和近圓形分布數(shù)據(jù)3種空間數(shù)據(jù)分布進行仿真研究.仿真結果表明, 該方法能有效剔除90%的自身免疫性檢測器, 提升了免疫陰性選擇算法的魯棒性和自適應能力.

人工免疫系統(tǒng)； 陰性選擇； 自身免疫性檢測器； 算法優(yōu)化； 算法仿真

0 引 言

人工免疫系統(tǒng)中的陰性選擇算法[1]源于人體內(nèi)T淋巴細胞發(fā)育過程中的陰性選擇機制.該算法定義正常情況下的信息為自我集合, 異常狀態(tài)為非我集合, 從而實現(xiàn)自我與非我間的區(qū)分.檢測器生成是陰性選擇算法的關鍵環(huán)節(jié), 與問題表達的編碼方案緊密相關.目前主要有兩種編碼方案： 二進制編碼和實值編碼, 分別對應傳統(tǒng)陰性選擇算法和實值陰性選擇算法.其中傳統(tǒng)陰性選擇算法延續(xù)了Forrest陰性選擇算法的技術, 而實值陰性選擇算法因問題表示逼近實際空間、匹配規(guī)則容易建立等優(yōu)點而被廣泛應用[2-3].

實值陰性選擇算法根據(jù)檢測器在三維空間中的形狀可分為球形檢測器和立方體檢測器.其中球形檢測器通常分為固定半徑檢測器和可變半徑檢測器, 提出的目的是為了縮小陰性選擇算法中難以避免的“黑洞”問題[3].目前針對縮小陰性選擇算法黑洞的方法主要有檢測器移動檢測技術[4-5]、分布調(diào)整技術[6]、定向受體編輯技術[7]及可變模糊匹配技術[8]等, 但這些技術都只在一定程度上縮小了黑洞, 即提高了對非我空間的覆蓋率.王玉健[9]針對矩形檢測器提出了基于檢測劃分機制的檢測器生成算法, 該算法為確定性算法, 能確保非我區(qū)域的全覆蓋, 但生成的檢測器規(guī)模較大, 算法耗時.

針對陰性選擇算法檢測器生成耗時問題, 常見的解決方法是使檢測器的感受半徑能自適應的調(diào)整, 如劉芳等[10]提出的強制多目標優(yōu)化技術對檢測器的空間分布進行干涉, 有效提高了檢測器的生成效率.此外, 通過設計攜帶粒子群優(yōu)化功能的檢測器生成, 也能對檢測器的生成起精簡作用, 相關實驗結果證明了該方法也能同時提高陰性選擇算法的泛化能力[11].借鑒隨機思想, 楊東勇等[12]將多種群遺傳算法融入到檢測器生成環(huán)節(jié), 有效降低了原始檢測器生成算法的冗余問題和耗時過大問題.文獻[13]針對自我空間邊界容易被檢測器過境入侵的現(xiàn)象, 設計了帶進化邊界檢測器的陰性選擇檢測器生成算法, 提高了陰性選擇算法在異常檢測上的成功率.

實現(xiàn)成熟檢測器對非我空間全覆蓋的前提是自我個體空間能被自我個體全覆蓋, 即自我個體數(shù)量上的充分滿足, 但實際采集到的樣本總是有限, 且有隨機性, 這種漏洞極易引發(fā)檢測器生成的自身免疫問題, 針對該問題, 本文以矩形檢測器生成算法為基礎, 提出一種能避免檢測器生成自身免疫現(xiàn)象的方案, 計算機軟件仿真測試結果驗證了該方案的有效性.

正常狀態(tài)下， 生物體免疫系統(tǒng)是穩(wěn)定的， 當識別到非我信號時啟動免疫應答， 而對自體成分保持宏觀上的免疫耐受， 即能正確地識別“自我”和“非我”.一旦這種狀態(tài)被打破， 就會產(chǎn)生自身免疫性疾病， 作為動態(tài)的免疫系統(tǒng)， 由于T細胞受體和B細胞受體的基因序列隨機重排現(xiàn)象， 決定了暫態(tài)的自身免疫活動屬正常范圍， 且暫態(tài)的自身免疫活動會伴隨淋巴細胞成長過程中的克隆刪除和免疫失活而平息， 但如果發(fā)生持續(xù)性自身免疫現(xiàn)象就會演變成自身免疫性疾病.自身免疫性疾病由于和正常的免疫應答一樣會產(chǎn)生抗體， 從而對自身組織器官產(chǎn)生一定程度的損害， 具有反復發(fā)作和慢性遷延的特點.

1 實值檢測器生成算法自身免疫缺陷的分析

定義二維模式空間全集為U: {U(x,y)|x∈[0,1],y∈[0,1]},N表示非我模式空間,S表示自我模式空間, 并滿足U=S∪N.S的區(qū)域定義為

成熟檢測器集定義為d{dij=[cij,r0],cij=(c1,c2,…,cV)}, 其中V表示所處空間維度, 本文設V=2.

從自我區(qū)域內(nèi)隨機選取60個點作為自我個體集合, 定義每個自我個體的感受半徑rs=0.015； 應用基于實值劃分的檢測器生成程序生成對應的成熟檢測器, 控制最小檢測器探測半徑rmin分別為0.005,0.01,0.02,0.04, 觀察其對非我區(qū)域的覆蓋度、運行耗時t及生成的成熟檢測器數(shù)目n0.仿真結果如圖1所示.

圖1 成熟檢測器對非我空間的覆蓋仿真結果Fig.1 Simulation results of mature detector’s coverage for non-self space

為了說明基于檢測劃分實值檢測器生成算法存在的自身免疫缺陷, 下面給出兩個定義.

1) 致病檢測器： 檢測器d(c,r)所處空間完全為自我個體分布的空間內(nèi)部, 即d?S, 如圖1(A)和(B)就存在一定量的致病檢測器.

2) 半致病檢測器： 檢測器d(c,r)所處空間與自我個體的分布空間存在瀕臨關系或其所處空間位置為自我模式空間的邊緣部位, 沒有完全置于內(nèi)部, 如圖1中的黑色區(qū)域即為半致病檢測器存在的區(qū)域.

致病檢測器的存在與生物免疫系統(tǒng)中的自身免疫性疾病原理一致, 即致病檢測器將對自我元素啟動識別和判斷, 如果用于數(shù)據(jù)的分類, 則會將本屬于自我集合的元素判斷為非我元素.為了衡量檢測器是否為致病檢測器, 關鍵的問題是要判斷其是否處于自我空間內(nèi)部, 尤其是當自我模式空間為任意可能存在形狀的情況下.

2 致病檢測器的判別方法

2.1初次判定方法

圖2 初次判定規(guī)則的漏洞Fig.2 Preliminary determination rules’ loopholes

對于檢測器d(c,r)是否處于自我模式范圍內(nèi)部, 直觀條件是其周圍是否存在自我個體, 對于二維空間意義上的檢測器, 即以其中心為中心平面坐標系的4個象限內(nèi)均有自我元素存在, 可初步判斷檢測器d(c,r)產(chǎn)生在自我范圍內(nèi).本文通過計算每個生成檢測器與每個自我個體間的夾角θ, 判斷對應自我個體相對于待測檢測器所處的空間象限位置.夾角在同一象限的所有自我元素被分配相同的內(nèi)部系數(shù)(2W)-1, 其中W為所處空間的維度, 并被賦予相同的象限標簽nd.同時, 根據(jù)

計算待測檢測器d(c,r)的內(nèi)部因子τ(θ), 其中:n0為生成檢測器的數(shù)目;ns為自我集合空間中隨機選取的自我個體數(shù)目; numel和unique為MATLAB中的函數(shù).當τ(θ)i=1時, 則判定檢測器dij(cij,rj)為致病檢測器; 當τ(θ)i≤0.5時為成熟檢測器; 否則為半致病檢測器.

2.2二次判定方法

如果僅以檢測器周圍是否存在自我個體作為其是否為致病檢測器的判定尚不完備, 因為當自我個體在空間中的分布符合環(huán)形分布特點時, 環(huán)帶內(nèi)部生成的成熟檢測器將被初次規(guī)則定義為致病檢測器, 如圖2所示.

其中:c(j,m)表示第j個致病檢測器的空間坐標信息;m∈[1,W], 表示W(wǎng)維致病檢測器每個個體空間坐標有W個數(shù)值.通過累加計算求出該檢測器與自我個體S(i,m)的親和度qhd.

根據(jù)初步判定規(guī)則可知, 被判定為致病檢測器的內(nèi)部因子τ=1, 而深度判定規(guī)則的建立就是進一步對內(nèi)部因子τ進行重新修正, 修正方法如下:

其中系數(shù)ε為親和度閾值調(diào)節(jié)系數(shù).親和度閾值調(diào)節(jié)系數(shù)的引入是因為其閾值并非一個固定值, 而是隨數(shù)據(jù)的分散程度而定, 聚集度較高的數(shù)據(jù)親和度閾值較小; 反之, 離散程度較高的數(shù)據(jù)集, 其親和度閾值則較大.為了直觀分析其內(nèi)在關系, 本文定義一種數(shù)據(jù)離散度指數(shù)： 分散系數(shù)Fsd, 計算方法如下：

其中S1(i)表示每個自我個體S(i)所處位置的最近象限親子個體集, 每個象限取一個親和度最強個體, 這樣S1(i)最多有2W個個體, 至少有1個個體, 并指定n1表示其個體數(shù)目(n1∈[1,2W]); ∑表示對自我個體采取行計算并求和;m為維度計數(shù)變量, 每計算一次其值增加1, 直至達到W為止.

2.3數(shù)據(jù)分散系數(shù)Fsd的仿真驗證

自我空間的覆蓋率越低致病檢測器越易侵入, 但可通過調(diào)節(jié)親和度閾值調(diào)節(jié)系數(shù)ε控制致病檢測器的產(chǎn)生, 而ε與自我空間的覆蓋率緊密相關, 由于自我個體的感受半徑rs可變, 因此通過計算自我個體的總面積或總體積不可行.本文設計的分散系數(shù)Fsd則僅與自我個體的空間分布有關, 能反應自我集合數(shù)據(jù)的空間分布.

為了觀察數(shù)據(jù)分散系數(shù)對親和度閾值的影響, 本文構建一組環(huán)形數(shù)據(jù)集, 因為環(huán)帶分布的數(shù)據(jù)集其親和度閾值比普通分布數(shù)據(jù)更易受數(shù)據(jù)離散程度的影響.環(huán)形數(shù)據(jù)集的分布函數(shù)為

當自我集合分布為式(6)、采樣點數(shù)為197時的數(shù)據(jù)集空間分布及當采樣點由5增加到300, 步長為8時, 對應的數(shù)據(jù)分散系數(shù)隨采樣點數(shù)的變化曲線如圖3所示.圖3顯示了37組采樣數(shù)據(jù)集的分散系數(shù)變化情況, 每隔3組抽取一組數(shù)據(jù)集觀察數(shù)據(jù)分散系數(shù)對親和度閾值的影響, 共計13組樣本, 輸入到檢測器生成算法進行調(diào)試, 分別獲得了13組親和度閾值及對應的系數(shù)ε, 結果列于表1.

圖4為表1的折線圖.由圖4可見, 親和度閾值對數(shù)據(jù)的分散程度變化反應遲鈍, 通常一個合適的值會在一定區(qū)間內(nèi)產(chǎn)生相同效果, 而不需要跟隨分散系數(shù)的變化而變化.此外, 由于采樣點數(shù)的增加, 算法運行所消耗的時間也隨之增加, 因此, 在處理實際問題時采樣點數(shù)并非越多越好.

圖3 環(huán)形數(shù)據(jù)分散系數(shù)隨采樣點數(shù)的變化曲線Fig.3 Plot of dispersion coefficient of annular data vs sampling point

圖4 Fsd,ε及t隨采樣點數(shù)的變化關系Fig.4 Changing trends of Fsd,ε and t with sampling point

表1 Fsd,ε及耗時t隨采樣點數(shù)的變化規(guī)律Table 1 Changes of Fsd, ε and t with sampling point

3 仿真結果分析

應用本文優(yōu)化處理后的檢測器生成算法分別對圓環(huán)形分布數(shù)據(jù)集、橢圓環(huán)形分布數(shù)據(jù)集及不規(guī)則分布數(shù)據(jù)集分別進行兩次檢測器生成, 第一次為優(yōu)化前的檢測器生成, 第二次為優(yōu)化后的檢測器生成, 實驗結果如圖5所示.由圖5可見, 優(yōu)化后檢測器生成算法在很大程度上抑制了致病檢測器的生成, 避免了自身免疫缺陷的發(fā)生.同時由于檢測器數(shù)目的降低, 算法運行時間也提高了約30%.

圖5 陰性選擇檢測器生成算法優(yōu)化前后示意圖Fig.5 Scheme of detector’s generation before and after its optimization

綜上可見, 檢測器的生成是陰性選擇算法的關鍵環(huán)節(jié), 本文在學習基于檢測劃分實值檢測器生成算法的基礎上, 針對基于檢測劃分實值檢測器生成算法中存在的自身免疫性缺陷提出了一種優(yōu)化方法, 并利用不同的空間分布數(shù)據(jù)進行了仿真測試, 結果表明這種優(yōu)化是有效的, 致病檢測器生成的抑制和剔除, 使陰性選擇算法的整體性能得到了提升.

[1]Forrest S, Perelson A S, Allen L, et al.Self-nonself Discrimination in a Computer [C]//Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy.Los Alamitos, CA: IEEE Press, 1994: 202-212.

[2]Gonzalez F, Dasgupta D, Kozma R.Combining Negative Selection and Classification Techniques for Anomaly Detection [C]//Proc the 2002 IEEE Congress on Evolutionary Computation, CEC-2002.Honolulu: IEEE, 2002: 705-710.

[3]張衡, 吳禮發(fā), 張毓森, 等.一種r可變陰性選擇算法及其仿真分析 [J].計算機學報, 2005, 28(10): 1614-1619.(ZHANG Heng, WU Lifa, ZHANG Yusen, et al.An Algorithm ofrAdjustable Negative Selection Algorithm and Its Simulation Analysis [J].Journal of Computers, 2005, 28(10): 1614-1619.)

[4]Laurentys C A, Palhares R M, Caminhas W M.A Novel Artificial Immune System for Fault Behavior Detection [J].Expert Systems with Applications, 2011, 38: 6957-6966.

[5]張鳳斌, 王天博.實值n維混沌映射否定選擇算法 [J].計算機研究與發(fā)展, 2013, 50(7): 1387-1398.(ZHANG Fengbin, WANG Tianbo.Real Value Negative Selection Algorithm with then-Dimensional Chaotic Map [J].Journal of Computer Research and Development, 2013, 50(7): 1387-1398.)

[6]XU Aiqiang, LIU Yong, ZHAO Xiuli, et al.Optimization and Application of Real-Valued Negative Selection Algorithm [J].Procedia Engineering, 2011, 23: 241-246.

[7]李貴洋, 郭濤.一種基于受體編輯的實值陰性選擇算法 [J].計算機科學, 2012, 39(8): 246-251.(LI Guiyang, GUO Tao.Receptor Editing Based Real Valued Negative Selection Algorithm [J].Computer Science, 2012, 39(8): 246-251.)

[8]王輝, 于立君, 王科俊, 等.一種可變模糊匹配陰性選擇算法 [J].智能系統(tǒng)學報, 2011, 6(2): 178-184.(WANG Hui, YU Lijun, WANG Kejun, et al.An Adjustable Fuzzy Matching Negative Selection Algorithm [J].CAAI Transactions on Intelligent System, 2011, 6(2): 178-184.)

[9]王玉健.實值檢測器生成算法研究 [D].合肥: 中國科學技術大學, 2009.(WANG Yujian.Research on Real-Valued Detector Generation Algorithm [D].Hefei: University of Science and Technology of China, 2009.)

[10]LIU Fang, GONG Maoguo, MA Jingjing, et al.Optimizing Detector DistributioninV-Detector Negative Selection Using a Constrained Multiobjective Immune Algorithm [C]//2010 IEEE Congress on Evolutionary Computation (CEC).Barcelona, Spain: IEEE, 2010: 1-8.

[11]Heydenrych M, Ehlers E.A Charged PSO Inspired Method for Generating Immune Detectors for Network Intrusion Detection [C]//2011 IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom).[S.l.]: IEEE, 2011: 134-141.

[12]楊東勇, 陳晉音.基于多種群遺傳算法的檢測器生成算法研究 [J].自動化學報, 2009, 35(4): 425-432.(YANG Dongyong, CHEN Jinyin.Researeh on Deteetor Generation Algorithm Based on Multiplepopulations GA [J].Acta Automatica Sinica, 2009, 35(4): 425-432.)

[13]WANG Dawei, ZHANG Fengbin, XI Liang.Evolving Boundary Detector for Anomaly Detection [J].Expert Systems with Applications, 2011, 38: 2412-2420.

Real-ValuedDetector’sGenerationofNegativeSelectionAlgorithmOptimizationandSimulation

MEN Hong, CHEN Peng
(SchoolofAutomationEngineering,NortheastDianliUniversity,Jilin132012,JilinProvince,China)

Since current conventional negative selection algorithm does not pay attention to the occurrence of autoimmune detector, and the presence of autoimmune detector will reduces the accuracy of fault diagnosis and other analogous areas, a method which can discover and eliminate pathogenicity detector was proposed.We specially designed a rule to detecting the presence of pathogenicity detector.With the help of MATLAB software, we simulated irregular distributed self-data, annulus distributed self-data and nearly circle distributed self-data.Results show that our method can effectively eliminate 90% of the pathogenic detector, enhance the robustness and adaptive ability of the immune negative selection algorithm.

artificial immune system; negative selection; autoimmune detector; algorithm optimization; algorithm simulation

2013-12-17.

門 洪(1973—), 男, 漢族, 博士, 教授, 從事智能化測控技術、新型傳感器和圖像處理的研究, E-mail: menhong_bme@163.com.通信作者： 陳 鵬(1990—), 男, 漢族, 碩士研究生, 從事模式識別方法和仿生智能計算的研究, E-mail: chenpeng16899199@126.com.

吉林省科技發(fā)展計劃項目(批準號： 20130101053JC).

TP18

A

1671-5489(2014)06-1255-06

10.13413/j.cnki.jdxblxb.2014.06.28

韓 嘯)