門 洪, 陳 鵬

(東北電力大學(xué) 自動(dòng)化工程學(xué)院, 吉林 吉林 132012)

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

門 洪, 陳 鵬

(東北電力大學(xué) 自動(dòng)化工程學(xué)院, 吉林 吉林 132012)

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

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

0 引 言

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

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

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

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

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

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

定義二維模式空間全集為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表示所處空間維度, 本文設(shè)V=2.

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

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

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

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

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

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

2 致病檢測器的判別方法

2.1初次判定方法

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

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

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

2.2二次判定方法

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果分析

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

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

綜上可見, 檢測器的生成是陰性選擇算法的關(guān)鍵環(huán)節(jié), 本文在學(xué)習(xí)基于檢測劃分實(shí)值檢測器生成算法的基礎(chǔ)上, 針對基于檢測劃分實(shí)值檢測器生成算法中存在的自身免疫性缺陷提出了一種優(yōu)化方法, 并利用不同的空間分布數(shù)據(jù)進(jìn)行了仿真測試, 結(jié)果表明這種優(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].計(jì)算機(jī)學(xué)報(bào), 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]張鳳斌, 王天博.實(shí)值n維混沌映射否定選擇算法 [J].計(jì)算機(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]李貴洋, 郭濤.一種基于受體編輯的實(shí)值陰性選擇算法 [J].計(jì)算機(jī)科學(xué), 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)學(xué)報(bào), 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]王玉健.實(shí)值檢測器生成算法研究 [D].合肥: 中國科學(xué)技術(shù)大學(xué), 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].自動(dòng)化學(xué)報(bào), 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—), 男, 漢族, 博士, 教授, 從事智能化測控技術(shù)、新型傳感器和圖像處理的研究, E-mail: menhong_bme@163.com.通信作者： 陳 鵬(1990—), 男, 漢族, 碩士研究生, 從事模式識(shí)別方法和仿生智能計(jì)算的研究, E-mail: chenpeng16899199@126.com.

吉林省科技發(fā)展計(jì)劃項(xiàng)目(批準(zhǔn)號(hào)： 20130101053JC).

TP18

A

1671-5489(2014)06-1255-06

10.13413/j.cnki.jdxblxb.2014.06.28

韓 嘯)