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

3112 Journal of Software 软件学报 Vol.32, No.10, October 2021

7. }
8. for (i=0;i<D.num;i++){ /*根据每种构造方式生成的检测器 weight 属性值更新其在加权轮盘赌选择
机制中的累计概率,如图 6 中步骤 7*/
9. if (D i .construction==random){weightofrandom+=D i .weight;}
10. elseif (D i .construction==chaotic){weightofchaotic+=D i .weight;}
11. else {weightofgenetic+=D i .weight;}
12. }
13. sum=weightofrandom+weightofchaotic+weightofgenetic;
14. p r [0]=weightofrandom/sum;
15. p r [1]=weightofchaotic/sum;
16. p r [2]=weightofgentic/sum;
17. End

2.4 算法分析
(1) 时间复杂度分析
设 N s 为自体数量,待检测样本规模为 N,则检测器生成所需要的总时间复杂度为 O((k+3m)N c N s ),检测所需
总时间复杂度为 O(N d N).
证明:在检测器生成阶段,初始化参数和选定生成源的时间复杂度均为 O(1).随机和混沌映射方式的时间代
价为 O(N c ).采用遗传变异构造候选检测器时,计算种群 k 个个体适应度和选择 m 个优势个体的时间复杂度为
O(k+m),交叉和变异操作的时间复杂度均为 O(((k+3m)N c N s )m).因此,遗传变异构造候选检测器的时间复杂度
为 O(k+3m)N c .从而有,检测器生成所需要的总时间复杂度为 O((k+3m)N c N s ),这种时间代价在检测器生成阶段
[9]
是可接受的 .
在检测阶段,需待检测样本与检测器进行亲和力计算,所需总时间复杂度为 O(N d N),这种时间代价在检测
阶段也是可接受的. □
(2) 检测器生成的收敛性分析
建立吸收态 Markov 过程模型,证明其是可收敛到全局最优解的.

定义 1. 设{( )}tX t 0 对任意 n 个不同的 t 1 ,t 2 ,…,t n T 且 t 1 <t 2 <…<t n1 ,有:
P(X(t n )≤X n |X(t n1 )=X n1 ,…,X(t 1 )≤X 1 )=P(X(t n )≤X n |X(t n1 )=X n1 ),
[9]

则称{( )}tX t 0 为 Markov 过程 .
*
定义 2. 任意给定某一区域 Markov 过程{( )}tX  t 0 和该区域的最优状态空间 Y Y,若满足:
*
*
P(X(t+1)Y |X(t)Y )=0,

[9]
则称{( )}tX t 0 为一个吸收态 Markov 过程 .
引理 1. 设生成检测器至最优状态的过程为{( )}tX  t 0 ,则{( )}tX  t 0 具有 Markov 性.同时,{( )}tX  t 0 也是一个
[9]
吸收态 Markov 过程 .
证明:由多源邻域检测器生成过程可知,{( )}tX  t 0 为离散时间的随机过程.因为检测器在当前迭代中的状态
X(t)只由 X(t1)决定,X(0)在初始化时可随机选取,因此,
P(X(t)|X(t1),X(t2),…,X(0))=P(X(t)|X(t1)).
即{( )}tX  t 0 具有 Markov 性.
*
由算法流程可知,解空间是有限的状态空间;由检测器多源生成过程可知:当 X(t)Y 为最优解空间时,
*
X(t+1)Y .因此,
*
*
P(X(t+1)Y |X(t)Y )=0.