Page 141 - 《软件学报》2021年第10期

席亮 等:邻域形态空间多源免疫检测器生成与检测 3113

即{( )}tX  t 0 是一个吸收态 Markov 过程.证毕. □
*
*
定义 3. 给定某一区域的吸收态 Markov 过程{( )} (tX  t 0  ( )t X Y ) 和最优状态空间 Y Y.记(t)=P(X(t)Y )
[9]
表示时刻 t 在某区域达到最优状态的概率.若 lim ( ) 1,t  则称{( )}tX  收敛 .
t t 0
定理 1. 多源邻域检测器生成过程是以概率 1 收敛的.
1
证明:通过 Markov 过程模型来描述本文算法中状态的转移过程,将初始群体的全部近似解认为是状态 S :S 1
2
1
n
2
N
等于 Y 中的某个点.中间种群规模为 S 的群体的全部近似解认为是 S ,S =Y .当没有必要区分 S 和 S 2
i
时,用 S 代替.用 s i S 表示 s i 是 S 中的一个状态, X 表示在第 t 代种群 X t 处于状态 s i ,设:
t
2
n
1
s i =(x ,x ,…,x )S.
n
1
2
记 f(s i )=(f(x ),f(x ),…,f(x )),若 f(s i )=f(s j )或者 f(s i )f(s j )的第 1 个非零分量为正,则记为 f(s i )≥f(s j ).此外,记 I={i|s i ≥
n
2
1
s j ,s j S}.由以上定义可知,若 iI,则 s i =(x ,x ,…,x )满足:
1
*
n
2
f(x )=f(x )=…=f(x )=f .
*
因此,s i Y .
设随机过程{X t }的转移概率为 p ij :

  X j 1 
() 
pt p  t i . 
ij
  X t  
本文算法采用 Monte Carlo 方法估计覆盖率来进行下一次检测器的生成,所以在任意的 t≥0 时,有 f(X t+1 )>f(X t ).
当 iI,jI 时,有:
p ij =0.
即:如果父代中出现了最优解,那么无论再经过多少代,它都不会变差.
当 iI,jI 时,因为 f(X t+1 )>f(X t ),所以:
p ij >0 (6)
设 p i (t)为种群 X t 处在状态 s i 的概率, ()pt   p i ( ),t 由 Markov 的性质可知:

iI
( p t  1)    p i ( )tp ij ( )t   p i ( )tp ij ( )t   p i ( )tp ij ( )t (7)


i s  S jI i I jI i I jI



由于:
() 
() p
()p
pt ij ()t   pt ij ()t    pt p t ,
i
i
i



iI j I iI j I iI


所以:
 pt ij ( ) p  t  p i () t p t (8)
()p t 
()
ij
i




iI j I iI j I
把公式(8)代入公式(6)和公式(7),可得:
n n

0≤ p t 1  p i ( )t p ij ( )t  p  t t . p


iI j I
因此, lim p  0. 又因为:
t
t
lim{ f  f * } 1 lim  p ( ) 1 limt    p ,
t t t i t t

iI
所以可得:
lim {pf  f * } 1.
t t
可证得该算法以概率 1 收敛.证毕. □
3 实验分析
衡量异常检测的检测性能需要测定检测器的计算效率、检测率(detection rate,简称 DR)和误报率(false-