动态克隆选择算法论文

2024-06-19

动态克隆选择算法论文（精选6篇）

动态克隆选择算法论文第1篇

近年来, 基于生物免疫原理构建网络入侵检测系统正逐渐成为新的研究热点, 通过对生物免疫系统的模拟构建系统体系结构, 可以使系统具有自然免疫机理的众多优点, 从而有效地提高系统的检测性能, 增加系统的健壮性、自适应性和动态防护性。

自从Burnet提出了克隆选择原理以来, 克隆选择算法受到了很多人的关注。De Castro提出了克隆选择算法模型, 并在模式识别、组合优化和多峰值函数优化中得到了验证。Kim将克隆选择原理应用于网络入侵检测, 为生物免疫原理在入侵检测中的应用提出新的思路。Kim和Bentley提出的动态克隆选择算法对记忆检测器集合的生成进行改进, 提高了非自体被检测出来概率TP (true-positive) , 减少了自体被误检的概率FP (falsepositive) , 同时使得基因库不断进化。

本文对动态克隆选择算法进行扩展, 提出了一种基于DC-SA的分布式网络入侵检测模型, 有效降低了误检率, 提高了系统的整体检测性能和自适应性。

1、动态克隆选择算法

免疫系统克隆选择原理描述了免疫应答的基本特征:免疫细胞在抗原刺激下产生克隆增殖, 只有能够识别抗原的细胞才能被选择出来进行分裂扩增, 并且通过亲和力成熟过程对被选择的细胞和抗原之间的亲和力进行改善。

与克隆选择算法相比, Kim和Bentley提出的动态克隆选择算法加入了记忆免疫细胞的删除和被删除记忆免疫细胞的变异, 当外部环境发生变化时, 具有一定的自适应性, 仍能正确识别自体和非自体, 从而提高TP, 减少FP。动态克隆选择算法[1]的具体步骤如下:

用随机生成的检测子建立原始的未成熟检测器集合;

其中生命周期L (Life Span) :指成熟检测器的生命期;激活阈值A (Activation Threshold) :指成熟检测器被激活成为记忆检测器所需要的匹配成功次数;耐受期T (Toleration Period) :指未成熟检测器进化为成熟检测器所要经历的代数 (循环次数) 。

动态克隆选择算法对记忆检测器集合采用了动态替换策略, 当记忆检测器集合数目超过设定值时, 在集合中选择一段时间内匹配次数最少的记忆检测器, 对其进行变异后添加到未成熟检测器集合中重新进行阴性选择, 有效的提高了系统的检测率并降低了误检率。

2、基于DCSA的分布式网络入侵检测模型

2.1 模型的基本结构

借鉴生物免疫系统 (Immune System, IS) 的工作机制, 本文给出了一种分布式网络入侵检测模型, 如图1所示。网络中的每一个节点称为检测节点 (LIDS) , 由数据采集模块、数据解析模块、入侵检测模块、响应单元和输出模块组成。

入侵检测模块中的检测器动态更新, 有未成熟、成熟和记忆三种状态。每个检测器由定长度的二进制字符串表示, 随机产生的未成熟检测器经过一定时间的耐受期, 成为成熟检测器。匹配次数超过设定值的成熟检测器被激活成为记忆检测器。

2.2 数据预处理

(1) 数据采集

本文利用网卡的混杂工作模式, 在局域网中基于winpcap获得经过本网段的所有数据信息, 从而实现获取网络数据的功能。

(2) 数据解析

WinPcap使用回调 (callback) 函数的方式, 在实现数据包捕获的同时, 进行协议分析。在捕获数据包的过程中, 调用以太网数据报解析函数由底层向高层逐层进行协议解析, 并将结果以设定的方式保存以备检测器生成和检测过程所使用。

(3) 编码

通过分析和比较, 本文采用112位二进制数位表示网络连接。网络连接每个属性的意义如下所述:第0-31位表示源IP地址, 第32-63位表示目标IP地址, 第64-65位表示协议类型, 第66-73位表示生存时间TTL (Time To Live) , 第74-111位针对不同的协议表示内容不同。本文主要针对TCP、UDP、ICMP这三种协议, 前面四项源IP地址、目标IP地址、协议类型和生存时间对于上述协议通用, 后面各项如果没有的则填0。

2.3 算法描述

本文在动态克隆选择算法的基础上进行了如下改进:

(1) 根据专家知识对已知入侵建立检测规则, 直接添加进记忆检测器集合;

(2) 在系统中采用协同信号机制以减少虚警, 并进一步增加检测系统的自适应能力。

(3) 对于记忆检测器, 其生命期是无限的, 但如果记忆检测器对新的抗原表现出较低的自身耐受, 则需要对记忆检测器进行动态替换。本文采取如下策略:当记忆检测器集合的数目超过预先设定的最大值时, 在集合中选择一段时间内匹配次数最少的记忆检测器, 高频变异后加入未成熟检测器集合中重新进行阴性选择。

算法流程主要分为训练阶段和检测阶段, 如图2所示:

检测器集合在检测过程中动态更新、不断进化, 进化过程如下:

(1) 记忆检测器集合:检测过程中将每个记忆检测器与抗原Ag匹配。若匹配成功, 则等待协同激发信号, 如协同激发信号为True则认定该抗原是异常数据, 报警;否则继续等待协同抑制信号, 如协同抑制信号为True则认定为虚警, 删除相应的记忆检测器。每次成功匹配后将相应记忆检测器的匹配数加1, 同时考察记忆检测器集合的数目, 若超过预先设定的最大值时, 则选择一段时间内匹配次数最少的记忆检测器, 高频变异后加入未成熟检测器集合。

(2) 成熟检测器集合:检测过程中将每个成熟检测器与抗原Ag匹配, 若匹配成功, 则等待协同激发信号, 如反馈信号为True则认定该抗原异常, 报警;否则等待协同抑制信号, 如反馈信号为True则认定为虚警, 删除该成熟检测器。当成熟检测器与抗原成功匹配时, 其匹配数加1。训练阶段, 考察各成熟检测器的匹配数是否超过了预定义的激活阈值A, 如超过则进化为记忆检测器;同时考察是否有成熟检测器的年龄到达了预定生命周期L, 如到达, 则删除该成熟检测器。

(3) 未成熟检测器集合:采用阴性选择算法将未成熟检测器和自体集Self相匹配, 若匹配成功则删除相应未成熟检测器, 否则其年龄加1。一段时间后, 将年龄大于耐受期T的未成熟检测器进化为成熟检测器。

3、总结

本文借鉴生物免疫原理, 在对动态克隆选择算法进行改进的基础上提出了一种分布式网络入侵检测模型。该模型利用专家知识对已知入侵建立检测规则, 有效提高对已知入侵的检测能力;采用协同激励信号机制减少虚警, 有效降低了检测器的误报率;对被删除的记忆检测器高频变异后加入未成熟检测器集合, 使得基因库不断进化, 进一步提高了系统的检测性能。

摘要：本文在分析动态克隆选择算法 (Dynamic Clonal Selection Algorithm, DCSA) 的基础上, 针对其存在的问题, 提出了一种基于DCSA的分布式网络入侵检测模型。该模型通过专家知识建立规则、基因库自动进化、优化检测器生成过程等策略, 提高了检测器对已知入侵和未知入侵的识别能力, 从而有效的提高了系统的检测性能和自适应性。

关键词：入侵检测,DynamicCS,基因库优化

参考文献

[1].Kim J, Bentley P J.A Model of Gene Library Evolution in the DynamicClonal Selection Algorithm (ICARIS) , 2002:57-65.

[2].Kim J, Bentley P J.Towards an Artificial Immune System for Networ In-trusion Detection:An Investigation of Dynamic Clonal Selection.Proc-ceeding of Congress on Evolutionary Computation, 2002:1015-1020.

[3].Kim J, Bentley P J.Towards an Artificial Immune System for NetworkIntrusion Detection:An Investigation of Clonal Selection with a NegativeSelection Operator.In Proc.of CEC2001, the Congress on EvolutionaryComputation, 2001:1244-1252.

[4].Hofmeyr S., An Immunological Model of Distributed Detection and ItsApplication to Computer Security, PhD Thesis, Dept of Computer Science, University of New Mexico, 1999.

动态克隆选择算法论文第2篇

关键词：阴性选择算法,克隆选择,邻域搜索,故障检测

0 引言

在设备故障诊断领域中,实现对设备异常和故障的在线快速检测和定位引起了人们的重视。受生物免疫系统阴性选择机制的启发,Forrest等[1]最先提出了基于字符串编码的阴性选择算法,用于计算机病毒和网络异常的检测。Fabio等[2]基于阴性选择的思想,提出了实值形式的阴性选择算法用于故障检测。Zhou等[3,4]在其基础上提出了可变检测半径的实值阴性选择算法V-detector。

V-detector算法通过随机试探法确定检测器的中心点,生成的检测器集合未经过优化,致使检测器集合中的检测器数量过多,在实时检测应用时受到了一定的限制。文献[5]提出了一种将检测器半径加倍进行迭代搜索的方法用于网络异常检测,该方法减少了检测器集合中检测器的数量,但不能保证检测器集合是全局最优的。文献[6]提出了一种基于减少各检测器重合度的试探搜索算法,大幅缩减了检测器数目,但是检测效率有待更进一步提高。文献[7]提出了一种基于拟随机序列和遗传变异搜索的阴性选择算法(genetic algorithm based real-valued negative selection,GA-RVNS),该算法获得的检测器集合数目较V-detector算法大大减少,但是该算法只考虑了全局搜索,而且遗传算法在一定情况下会出现早熟收敛、退化等现象[8,9]。

克隆选择是生物免疫系统理论的重要学说,de Castro等[10,11]通过模拟生物免疫系统中的抗体克隆选择机理,提出了克隆选择算法。该算法兼顾了全局和局部搜索,在提高收敛速度的同时,较好地保持了种群多样性,从而能够比较有效地解决诸如早熟收敛等问题[12]。

本文在文献[7]的基础上,提出了一种改进的阴性选择算法——基于克隆选择和邻域搜索的改进阴性选择算法(clonal selection and neighborhood search based real-valued negative selection,CSNS-RVNS)。该算法通过克隆选择搜索得到拟随机序列内的优化检测器集,然后对该检测器集进行邻域搜索,最终得到N维空间内优化的检测器集,实现了以较少数量的检测器即可满足对非我空间的一定覆盖。同GA-RVNS算法相比,改进的算法优化了检测器集,在相同检测器集数目的情况下,获得了更高的检测率,更加适用于实时故障检测。

1 实值阴性选择算法

基于生物免疫系统中的阴性选择原理,RVNS算法将整个计算空间划分为自我空间和非我空间,自我空间对应着系统正常运行的状态,非我空间则对应着系统异常或故障的状态。

它用一组N维归一化的实数向量X=(x1, x2,…,xN)和自我空间半径RS来描述系统正常状态。记自我空间S={Xi|i=1, 2,…,m; RS=r},Xi=(xi1,xi2,…,xiN), i=1,2,…,m。

全体状态空间I⊆[0,1]N,则异常状态对应的非我空间NS=I-S。

RVNS算法通过训练自我空间的数据集来生成覆盖非我空间的检测器集。在N维空间中,可以用dj=(Cj,R(d)j)来表示检测器,j=1,2,…,f,f为检测器的数目。其中,Cj为N维实数向量,Cj=(cj1,cj2,…,cjN),R(d)j为该检测器的对应半径。一个检测器可以认为是一个以Cj为中心、R(d)j为半径的超球面。检测器与训练集之间的距离度量通常采用欧氏距离,即

$\begin{array}{l} L (X_{i}, C_{j}) = \\ \sqrt{(x_{i 1} - c_{j 1})^{2} + (x_{i 2} - c_{j 2})^{2} + \dots + (x_{i Ν} - c_{j Ν})^{2}} (1) \end{array}$

在检测器集的构造过程中,RVNS算法采用了随机生成检测器中心的方式,通过假设检验来判断检测器集是否达到了对非我空间的覆盖率。最终生成的检测器集虽然达到了对非我空间的覆盖率,但检测器集是未经过优化的,检测器数量往往比较庞大,因而增加了故障异常检测的计算量,在需要实时性检测的场合一般较难满足要求。

2 改进的CSNS-RVNS算法

针对RVNS算法生成的检测器集数量过大的问题,改进的CSNS-RVNS算法利用人工免疫系统中的克隆选择计算方法来搜索合适的检测器集合。该检测器集合既可满足一定的非我空间覆盖率,同时保证检测器数目较少。

给定自我空间训练集S,非我空间覆盖率η0,检测器集搜索问题可以描述为

其中,|D(S)|表示检测器集合D(S)的数量。

2.1 构造思想

尽管从实际意义上说,拟随机序列并不具有随机性质,但在许多情况下,拟随机序列在多维空间中的超均匀分布比伪随机数的均匀分布能更好地覆盖搜索空间。文献[7]的计算结果也表明了拟随机方式相对于常用的伪随机方法能更好地覆盖搜索空间。但是不足的是,该方法中检测器的中心点仅限于在拟随机序列中搜索,虽然考虑了对全局空间的覆盖,但是却忽略了局部搜索。

因此,在文献[7]中引入的拟随机序列的基础上,通过克隆选择在拟随机序列空间内进行全局搜索,然后对已生成的检测器进行邻域搜索,从而可改进文献[7]方法在局部搜索的不足。

本算法中抗体采用实数编码方式,每个抗体表示一个备选的检测器集合。首先生成拟随机序列SR,记为

SR={Xi∣Xi∈[0,1]N,i=1,2,…,NR} (3)

在全局搜索中,序列中的向量Xi对应为某一检测器的中心Ci,NR为该序列的长度,因此抗体可以用一个整型序列Ab来表达,序列Ab中每一点的整数值i代表了拟随机序列SR中标号i对应的检测器中心向量。Ab可表示为

Ab=[q1q2 … qNk] (4)

式中,Nk为最大的检测器数目;qNk表示第k个检测器中心在拟随机序列SR中的标号。

记种群规模为Na,则第j代的抗体种群可表示为

A(j)B=[A(j)b1A(j)b2 … A(j)bNa]T (5)

定义亲和度函数F(Ab)为抗体Ab所代表的检测器集合覆盖非我空间的“体积”。计算数据在经过归一化处理后,生成的检测器属于[0,1]N空间。记自我空间体积为VS,则非我空间体积为

VNS=1-VS (6)

F(Ab)无法直接进行求解,可以用Monte Carlo方法计算求得。在非我空间内随机采集t个数据点X′j,则

X′j={x′j1,x′j2,…,x′jN} j=1,2,…,t (7)

设P为要求的非我空间覆盖率,α为显著性水平,其中,zα可由标准的正态分布表查得[13]。采用文献[14]中假设检验的方法来判断“检测器集合是否达到了非我空间覆盖率P”:

$\frac{\sum_{j = 1}^{t} f (X^{'}_{j}) - t Ρ}{\sqrt{t Ρ (1 - Ρ)}} \geq z_{α}$ (8)

$f (X^{'}_{j}) = {\begin{cases} 1 X^{'}_{j} \in V_{A_{b}} \\ 0 X^{'}_{j} \notin V_{A_{b}} \end{cases}$

X′j∈VAb表明X′j被抗体检测器集所覆盖,即∃dj,使得L(X′j,Cj)<R(d)j。如果计算结果满足式(8),接受“检测器集合达到了非我空间覆盖率P”,反之则继续搜索检测器。

2.2 算法流程

算法步骤如下:

(1)生成拟随机序列SR,随机初始化规模为Na的抗体群AB。

(2)计算各抗体的亲和度,并按亲和度由大到小排序。选取亲和度最高的前K(K≪Na)个抗体,作为记忆库M。

(3)对抗体群AB中前J个抗体进行克隆,得到规模为NC的克隆抗体群ABC。

(4)对克隆抗体群ABC进行变异操作得到变异抗体群ABM,用ABM替代AB中亲和度最低的抗体,剔除重复多余的抗体。

(5)对新抗体群AB进行亲和度由大到小排序,更新记忆库M。

(6)判断是否满足全局搜索终止条件。如果不满足全局搜索终止条件,则转步骤(3)继续执行,满足全局搜索终止条件,则继续步骤(7)。全局搜索终止条件为:①搜索次数达到全局搜索最大迭代次数Ig;②记忆库M连续h代不变化。

(7)对记忆库M中的最优抗体,解码得到该检测器集D。如果D达到非我空间覆盖率P,则转步骤(10),反之继续步骤(8)。

(8)对检测器集D复制,对复制的检测器集中的检测器d进行高斯变异,得到新检测器集D′,计算D′的非我空间覆盖率P′。

(9)如果P′大于D的非我空间覆盖率,则用D′代替D。

(10)判断是否满足邻域搜索终止条件。如果不满足,则转步骤(8)继续执行。邻域搜索终止条件为:①搜索次数达到邻域搜索最大迭代次数In或者②检测器集D的空间覆盖率P′≥P。

2.2.1 初始化

拟随机序列SR生成的方法有Sobol、Faure和Halton[15]。Faure和Halton方法在高维两序列间呈现强相关性,而且生成序列的时间一般要长于Sobol方法,因此本文采用Sobol方法生成长度为NR的序列SR,SR中的每一个向量Xi均不在自我空间内。

随机选取序列SR中的向量Xi,构成初始化抗体群A $_{B}^{(0)}$ 。

2.2.2 克隆操作

克隆操作是对亲和度高的抗体按一定比例进行复制的过程。定义克隆算子为T $_{c}^{C}$ ,第i代抗体群A $_{B}^{(i)}$ 中亲和度最高的前J个抗体记为A(i)BJ,则克隆抗体群为

A(i)BC=T $_{c}^{C}$ (A(i)BJ)=

[T $_{c}^{C}$ (A(i)b1) T $_{c}^{C}$ (A(i)b2) … T $_{c}^{C}$ (A(i)bJ)]T (9)

T $_{c}^{C}$ (A(i)bj)=Ij×A(i)bj=AC(i)bjj=1,2,…,J (10)

其中,Ij为(J+1-j)维单位行向量,它使得抗体克隆复制的数目正比于该抗体的亲和度,AC(i)bj为(J+1-j)×Nk矩阵。

2.2.3 变异选择操作

根据免疫学原理,亲和度成熟和抗体多样性的产生主要依靠抗体的高频变异。定义变异算子为TCm,记变异抗体群为

A(i)BM=TCm(A(i)BC)=

[T $_{m}^{C}$ (AC(i)b1) T $_{m}^{C}$ (AC(i)b2) … T $_{m}^{C}$ (AC(i)bJ)]T (11)

对抗体克隆集的变异如下:

TCm(AC(i)bj)=TCm(Ij×A(i)bj) (12)

对于单个抗体A(i)bj=[q $_{1}^{(i)}$ q $_{2}^{(i)}$ … q(i)Nk],采用对抗体的单元变异的策略,取变异概率为Pm,随机选取抗体A(i)bj中Int(NR·Pm)个单元,用1～NR的随机整数代替,表示为

q(i+1)k=random([1:NR]) (13)

2.2.4 邻域搜索

在克隆选择搜索的基础上,对记忆库M中的最优抗体解码,得到检测器集D。记检测器集D的邻域为Π(D),Π(D)定义为D中任一检测器dj=(Cj,R(d)j)变化后所得到的所有新的D′的集合,其中D′的非我空间覆盖率满足大于D的非我空间覆盖率。

邻域搜索策略采用对检测器d的中心Cj进行高斯变异,对Cj=(cj1,cj2,…,cjN)随机选取其中的某一维数据c(i)jk,对其加上一个高斯扰动得

c(i+1)jk=c(i)jk+ρ ξk (14)

$ρ = \frac{λ}{Ι_{n} + Ι_{c}}$ (15)

式中,ξk为一个随机变量,服从N(0,1)分布;ρ为步长调节因子,用于调节邻域搜索的变异步长;λ为一常数;Ic为当前迭代次数。

ρ随着迭代次数的增加而减小,使得检测器的变异步长在进化初期较大,在进化后期较小,使得邻域搜索在后期趋于稳定,直至迭代达到最大代数或满足非我空间覆盖率要求。

3 应用与实验对比分析

为了测试CSNS-RVNS算法的效果,采用在文献[4,7]中应用的标准的滚动轴承数据集来进行实验对比。该数据集是某型轴承在不同状态下运行的振动加速度的时间序列信号,分别为在新轴承、无明显磨损、保持架损坏、保持架断裂以及外圈完全损坏这五种状态下采集。时间序列数据经过统计矩处理,为5维数据,并且经过了归一化处理。

取新轴承状态的数据为正常状态,定为自我空间;外圈完全损坏作为异常故障状态,定为非我空间。文献[7]中检测器集数目为100,为便于比较,采用CSNS-RVNS方法进行计算时,取抗体规模为100,抗体变异概率为75%,自我空间半径为0.01,邻域搜索半径为0.001,克隆选择和邻域搜索迭代次数为150,抗体假设检验的非我空间覆盖率为99.9%。三次计算的结果见表1所示。

为了测试算法的性能,将抗体规模取为90,自我空间半径增大到0.02,其他参数同上,三次计算的结果如表2所示。

将上述计算结果平均,同文献[4] 中采用的Boundary-Aware算法、文献[7]中采用的GA-RVNS算法计算结果进行比较,结果如表3所示。

由上述计算结果可以看出,应用本文提出的改进算法得到的检测器集在自我空间半径增大到0.02、检测器数目减少到90的情况下,仍然获得了较高的非我空间数据检测率。

通过上述实验数据比较可以看出,CSNS-RVNS算法相对于Boundary-Aware算法,检测器数目减少了99.8%,而检测效率提高了3.3%;相对于GA-RVNS算法,在检测器数目相同的情况下,检测效率提高了2.9%。这在实时在线检测场合,有大量待检数据的情况下,可降低检测数据的误警率和漏报率,缩短设备的停机检修时间。

4 结语

本文提出了一种改进的实值阴性选择算法,结合了克隆选择计算良好的全局寻优能力,并引入了邻域搜索,提高了算法的搜索效率,实现了以较少数量的检测器即可满足对非我空间的一定覆盖的要求。滚动轴承数据集计算结果验证了该算法的有效性,其生成的检测器集可适用于设备实时故障检测领域。

动态克隆选择算法论文第3篇

关键词：混合流水车间,调度,克隆选择,人工免疫系统

0 引言

混合流水车间调度问题HFSP(Hybrid Flow-shop Scheduling Problem)是制造型企业生产车间中常见的调度模型,相当普遍地存在于化工、钢铁、制药等流程工业中。由于HFSP属于NP-hard问题,目前针对此问题的求解主要有数学规划法、启发式算法、遗传算法等,然而,当问题规模比较大时,这些方法都存在着一些不足[1]。

人工免疫系统AIS(Artificial immune system)是模仿免疫系统功能的一种智能计算方法,它具有噪声忍耐、无教师学习、自组织、记忆等进化学习机理,目前已被广泛应用于解决各种工程和科学问题中[2]。然而,与其它进化算法一样,一般免疫算法也存在容易陷入局部最优的平衡态以及进化后期停滞不前的缺陷。于是,受到生物免疫抗体克隆选择理论的启发,De Castro于2000年提出了免疫克隆选择算法ICSA(Immune clonal selection algorithm)。该算法的基本思想[3]是:通过对候选解进行克隆变异操作,产生一个候选解的领域解,通过扩大搜索范围加强局部搜索,并通过领域解和候选解的竞争(选择),促进算法的快速收敛全局搜索能力。另一方面,与其它算法(如遗传算法)不同,免疫算法不单纯以适应度作为个体的评价标准,而是用亲合度、相似度、浓度的概念衡量个体的特性,并基于此,动态调整变异概率,保持种群在进化过程中的多样性变化。鉴于CSA算法的这些特性,该算法在解决较复杂的模式识别、组合优化问题,表现出显著的能力[4,5,6,7,8]。

基于以上分析,针对HFSP问题的特点,本文首先给出了HFSP调度问题的数学模型;在此基础上,将免疫克隆选择算法应用于HFSP问题的求解;为提高算法的有效性,引入种群分组策略,根据种群优劣实施变异、交叉、死亡操作;最后通过仿真实例,验证了算法求解HFSP问题的可行性和有效性。

1 数学规划模型

如图1所示,HFSP调度问题[1]可描述为:需要加工n个同质工件,所有工件的加工路线都相同,都需要依次通过m道工序(车间),在工序j(j=1,2,…,m),有Mj台并行同质机器。需要解决的问题是确定并行机器的分配情况以及同一台机器上工件的加工顺序,使得调度指标最小。

1.1 基本假设及符号说明

为了保证HFSP调度问题数学规划模型的正确、有效,需要做一些必要的简化假设:

(1) 工件之间相互独立;

(2) 各阶段所有工件加工优先顺序相同;

(3) 工件在工序之间可以等待,并且暂时存储容量不受限制;

(4) 工件在每道工序的每台机器上的加工时间为固定值;

(5) 不考虑机器故障的情况。

动态克隆选择算法论文第4篇

关键词：克隆选择算法,小生境共享技术,个体多样性

0 引言

旅行商问题(TSP问题)是一个经典的组合优化问题,也是一个NP难问题。它在实际中的应用却非常广泛。近二十年,随着仿生计算技术悄然兴起,人们利用各种进化算法来解决此问题,都能从不同程度上取得问题的近似解;其中,基于生物免疫学中的克隆选择原理而提出的克隆选择算法相比于其他进化算法在解决旅行商问题时显示出良好的特点:收敛速度快,局部搜索能力强。但在研究过程中同时发现解决此问题时易陷入局部收敛中。为了改进此算法解决旅行商问题的能力,本文将生物学中小生境共享思想应用到克隆选择算法中,通过持续扰动迭代种群的多样性增强了算法全局搜索的能力。最后为了验证所提算法的有效性,选择复杂组合优化领域中的经典问题旅行商问题(TSP问题)进行了仿真实验。实验结果表明在解决TSP问题时改进算法相比原算法提高了全局搜索能力。

1 小生境共享克隆选择算法

1.1 克隆选择算法的基本原理

1959年免疫学家Bernet提出了生物学上的克隆选择学说[1];后来,巴西Campinas大学De Castro博士基于克隆选择基本原理提出了解决复杂问题的克隆选择算法CSA[2],并且通过实例验证了该算法在解决复杂机器学习问题,如模式识别和多模式优化上有很好的效果。在算法中,他将待求解的问题视为抗原,待求问题的解作为抗体,抗体与抗原的匹配程度叫作亲和度,用抗体和抗原的亲和度作为抗体的评价函数,通过模拟生物体的克隆选择机制来优化抗体,从而找到相应的优化解。算法的具体步骤是:

①产生候选方案的集合P,该集合为记忆细胞子集(M)和剩余群体(Pr)的总和(P=Pr+M)

②根据亲和度大小从P中选择n个最佳个体组成群体Pn。

③克隆这n个最佳个体,生成临时克隆群体C,克隆的规模是抗原亲和度度量的单调递增函数。

④对克隆生成的群体施加变异操作,变异概率与抗体的亲和度成反比,从而生成一个成熟的抗体群体C*。判断是否停止迭代,是则结束,否则转(e)。

⑤在新产生的群体C*中重新选择一些好的个体构成记忆群体。P集合中的一些个体可以被新群体C*中的其他改进的个体取代替换。

⑥插入新个体替换d个低亲和度个体,以保持群体多样性。

此算法的流程图可以参考图1,将图1中的虚线框部分删除掉,即是CSA算法的流程图。

很多学者的研究表明,CSA算法具有许多好的特点,例如强的局部搜索能力,具有学习记忆性,好的噪声容忍性等;但它也有自己的不足,对复杂的组合优化问题易于陷入局部搜索,影响了算法的搜索能力。

为了改善算法易陷入局部搜索的缺点,本文将小生境技术[3]引入CSA算法中,设计了以小生境共享为基础的评价函数,代替以抗原抗体适应度为基础的评价函数,通过维护群体中的小规模低适应度物种的生存,保持了物种多样性,提高了算法寻找到更好抗体的可能性。

1.2 小生境共享克隆选择算法

小生境是生物学上物种生存的一种组织结构。 “物以类聚,人以群分”,生物总是倾向于与自己相类似的同类生活在一起,一般总是与同类交配繁殖后代,加上地理位置的限制,使得若干物种的生物形成了一个个小生境。无论这些小生境的规模是大还是小,他们的共同存在实现了大自然的多样性。这种组织结构可以引入CSA算法中:每一代种群中的个体,基于相互之间的相似性,也会形成类似自然中的不同的小生境。有的小生境中个体数数目较多,有的则较少,如果只是以个体适应度作为评价函数,会导致具有较高适应度的小生境中个体容易进入下一代种群,而适应度低的小生境中的个体很有可能得不到进入下一代种群的机会。基于此,本文参考小生境共享原理设计了一种新的评价函数来改善原算法的种群多样性。

1.2.1 基本原理

设d(i,j)为个体i和j之间的距离,L为个体的十进制基因位数,其计算公式为:

其中,bit(i,k)表示第i个个体第k位的十进制值,符号⊙表示“同或”,即当bit(i,k)=bit(j,k)时tk(i,j)=1;当bit(i,k)!=bit(j,k)时,tk(i,j)=0。

个体i和个体j之间的共享函数为:

undefined

其中,δ为事先指定的共享半径。

得到所有个体之间的共享值之后,可以用以下公式计算个体的小生境个体数。

undefined

其中,N为种群中个体的数目。显然,个体的小生境个体数越大,聚集在该个体周围的个体就越多。

然后,计算共享后个体i的适应值:

undefined

其中,fi为共享前的个体适应值。演化过程中,使用共享后的个体适应值作为最终的评价函数,如果某个物种有较多的个体,那么该物种中个体的评价函数值将以较大的幅度降低,从而鼓励较少个体的物种繁衍。

1.2.2 算法的有效性

克隆选择算法与遗传算法的编码方式和迭代过程具有很大的相似性,不同仅仅是前者去掉了遗传算法中的交叉算子,而增加了克隆操作。所以,我们可以使用分析遗传算法的理论来分析改进后克隆选择算法的有效性。在文献[4]中,作者定义了个体邻域和局部极值逃逸能力的概念并且通过数学分析得出了结论。

定义1 个体x0的邻域S(R):S(R)={x:x-x0<ε},其中,x-x0表示个体x和个体x0的海明距离,ε为事先给定的一个整数。

定义2 逃逸能力:是指跳出局部极值点的足够大邻域的能力。

结论局部极值点的邻域越大,则算法在此点的逃逸能力越小。

下面来分析本文所提算法的有效性。算法I代表标准克隆选择算法(CSA),算法II代表应用小生境共享技术改进后算法(NSCSA)。

设种群规模为N,第k代种群为Qk={A1,A2,…,Am},其中Aii∈{1,2,…,m}是一个小生境物种,并且A1,A2,…,Am是按照平均适应度依次降低的,定义

Aundefined(I)——表示运行算法I时第k代物种Ai中所含个体数目;

Aundefined(II)——表示运行算法II时第k代物种Ai中所含个体数目;

设x0是一个局部极小值,且x0∈A1,定义

SRk(x0)(I)——表示运行算法I时在第k代时x0的邻域;

SRk(x0)(II)——表示运行算法II时在第k代时x0的邻域;

则有

undefined

由1.2.1节基本原理的说明,容易得到undefined,从而SRk(x0)(II)≤SRk(x0)(I),即运行算法II在第k代时得到的点x0的邻域小。由文献[4]中的结论得到,算法II比算法I在陷入局部极值点x0时,从x0逃逸的可能性更大;即算法II的全局搜索性更好。

1.2.3 算法步骤

基于小生境技术的克隆选择算法的出发点是在选择算子中采取策略以吸收那些个体数少且适应度较低生境中的个体进入迭代种群。本算法的基本内容是在标准克隆选择算法的基础上,利用小生境共享的思想对抗体适应值进行调整。算法步骤如下:

小生境共享克隆选择算法(简写为NSCSA)如下:

①②③步骤与克隆选择算法中的对应步骤相同;

④克隆这n个最佳个体,生成临时克隆群体C,克隆的规模是抗原亲和度度量的单调递增函数;

⑤对克隆生成的群体施加变异操作,生成一个成熟的抗体群体C*;

⑥根据公式(1)计算个体之间的距离d(i,j);

⑦根据公式(2)计算个体之间的共享函数值sh(d(i,j));

⑧根据公式(3)计算每一个体所在小生境的个体数mi;

⑨根据公式(4)计算并设定每一个体共享后的适应值f′i;判断是否停止迭代,是则结束,否则转(j);

⑩在新产生的群体C*中重新选择一些好的个体构成记忆群体。P集合中的一些个体可以被新群体C*中的其他改进的个体取代替换;

(11)插入新个体替换d个低亲和度个体,以保持群体多样性。

2 在标准TSQ中的仿真实验

从TSPLIB(TSP问题标准数据库)中选取三个TSP实例进行测试(分别是Eil51,Berlin52,KrocA100);测试环境是Pentium4 2.8GHz,512M内存,用VC++6.0运行实验程序产生结果数据,用Matlab7.0画对比示意图揭示内在规律。

试验中选择的参数是:克隆规模NC=8,进化代数50,变异概率Pm=0.01,群体规模为50。为了避免初始种群好坏对算法最终结果的影响,两种算法使用相同的初始种群。采用算法求得的最好解作为评价的标准,为避免随机因素,分别对两种算法运行10次求平均值。具体测试结果如表1所示。

其中,

undefined

其中,公布的问题Eil51和Berlin52的已知最优解分别是426和7542,求得的最优解分别是428.827,7544.363,如果进行圆整(两个城市间距离四舍五入取整数)也是426和7542,这说明算法确实搜索到了已知最优解。

再以Eil51问题为例,来看算法改进前后收敛情况,如图2和图3所示。

两图都反映出算法CSA收敛快(10代以前已经收敛),但易陷入局部收敛;而NSCSA算法由于采用了小生境共享技术,延缓了收敛,搜索到了更好解。

3 结束语

克隆选择算法具有局部搜索能力强的特点,在本文中将小生境技术融合进克隆选择算法中,提出了小生境共享克隆选择算法;所做的仿真实验证明了此算法在提升原算法的全局搜索能力方面是有效的,能够更好地推迟或避免陷入局部最优。

参考文献

[1]Bernet FM.“Self-recognition”in colonial marie forms and floweringplants in relation to the evolution of immunity[J].Nature,1971,232(5308):230-235.

[2]Leandro Nunes de Castro,Fernando Jose Von Zubenmm.Artificial ImmuneSystems:PartI-Basic Theory and Applications[D].1999(1):76-85.

[3]Goldbberg D E,Rechardson J.Genetic Algorithms with Sharing forMultimodal Function Optimization[C].Genetic Algorithms and TheirApplications:Proceeding of the Second International Conference on Ge-netic Algorithms,1987:41-49.

[4]阎岭,等.进化学习策略收敛性和逃逸能力的研究[J].自动化学报,2005(11).

[5]崔逊学,李森,方廷健.基于免疫原理的多目标进化算法群体多样性研究[J].模式识别与人工智能,2001,14(3).

[6]郑金华.多目标进化算法及其应用[M].科学出版社,2007.

动态克隆选择算法论文第5篇

船舶电力系统作为一种高阶、非线性、强耦合和多变量的复杂系统,是现代船舶的重要组成部分。它的安全性和抗扰性对于船舶,特别是船舶的生命力和战斗力意义重大。随着船舶电气化、自动化程度的日益提高,对船舶电力系统供电的可靠性和生命力提出了更高的要求,要求系统在出现故障时快速地重构系统,以最大限度地恢复供电。目前,对船舶电力系统的故障恢复的研究还处于起步阶段,文献[1]运用启发式方法—贪婪式算法进行故障区域的重构,尽管运算简单,但不能保证最大限度地恢复重要负载的供电;文献[2]应用专家系统的方法恢复故障区域的供电,其处理恢复控制时需要建立庞大的专家知识库,而且知识的全部获取也非常困难;文献[3]用网络流法研究系统的恢复,但没有考虑负载的优先性。由于船舶电力系统的故障恢复属于典型的非线性、组合优化问题,而遗传算法以其良好的鲁棒性、并行性、高效性等优点被广泛应用于求解大规模组合优化问题,故文献[4]中提出了一种启发式遗传算法对系统进行故障恢复,考虑了负载优先性以及最大限度恢复负载供电等条件,实现了供电恢复。但由于遗传算法本身还存在着一些缺陷,如易出现未成熟收敛而陷入局部最优、进化过程中不能很好地利用系统信息、进化后期易出现振荡现象等,因此,其算法不能保证以最大概率收敛到全局最优解。

本文将免疫克隆选择算法应用到船舶电力系统故障恢复中,通过克隆亲和力高的抗体放入记忆细胞,在克隆抗体放入记忆细胞前,由于亲和力高的抗体接近最优解,因此在克隆的同时,对克隆抗体的基因进行变异,针对船舶电力系统的特点和系统重构对快速性的要求,并对算法的变异算子进行了改进,使其有效地利用了高频变异和柯西变异两种变异算子各自的特点,以用来提高算法的搜索能力和收敛速度,防止了抗体浓度过早饱和同时增加了找到最优解的概率,由于克隆算子的作用,不断更新种群克隆的规模,因而具有更好的种群多样性。理论分析及算例结果表明,克隆选择算法作为一种新的优化搜索算法,在其算法实现上兼顾全局搜索和局部搜索,吸取了遗传算法并行搜索优点,通过接种疫苗和计算亲合力,使得算法快速收敛,同时保持一定的多样性,抑制了早熟现象,较好地实现了船舶电力系统的故障恢复。

1 免疫克隆选择算法

1.1 免疫克隆算法的原理

克隆选择是人体免疫系统的重要学说,克隆选择原理最先由Burnet在1959年提出,后来1978年Burnet又予以完整阐述[5]。总的来说,克隆选择原理的基本思想为:只有那些能够识别抗原的细胞才进行扩增,只有这些细胞才能被免疫系统选择并保留下来,而那些不能识别抗原的细胞不被选择,也不进行扩增。克隆算法,正是基于免疫学中的克隆选择原理而提出的一种人工免疫算法,该方法对具有较高亲和力的抗体(可行解)进行克隆,以贪婪搜索为特征,通过累积的盲目变异以及受体编辑方法保持抗体的多样性,从而更有利于产生复杂优化问题的最优解。克隆选择算法中应用了人体免疫系统中克隆选择的几个特点:选择亲和力最大的细胞进行克隆;淘汰没被激活的细胞;对克隆的细胞进行变异并且根据亲和力进行重新选择。

1.2 免疫克隆算法

免疫克隆算法的实质是在一代的进化过程中,在候选解的附近,根据亲和力的大小产生一个变异解的群体,以扩大搜索范围,从而能同时进行全局搜索和局部搜索,算法中主要提出了克隆算子,包括三个步骤:克隆、克隆变异和克隆选择[6]。其抗体群的状态转移情况可以表示成如下的随机过程:

1.2.1 抗体克隆

设A=(a 1,a 2,…,am)是大小为m的初始抗体群,对当前代初始群体中的抗体进行克隆,生成一个临时的克隆群体。每个抗体的克隆规模可以根据抗体与抗原的亲合力大小按比例分配,与抗原的亲和力越大,抗体的克隆规模也就越大。每个抗体的克隆规模为:

其中:int()为上取整函数,M为克隆后的群体规模,f(a i)是抗体与抗原的亲和力函数。克隆后的临时抗体群为A'={A 1',A'2,L,Ai',L,A'm},其中A′i={ai1,ai2,…,ain};ail=ai2=…ain=ai,n为抗体ia的克隆数量。

1.2.2 抗体变异

通过克隆扩大了群体的规模后,对克隆后的临时群体中每个抗体进行变异可以提高群体中抗体的多样性,扩大搜索的范围,以用来寻找更优秀的抗体。为了扩大算法的搜索范围,增强算法的全局收敛性,防止过早收敛,同时还要保证算法精确的局部搜索能力,本文采用了高频变异和柯西变异相结合的变异方法,根据抗体亲和力的大小而实行不同的变异,当抗体的亲和力大于当前抗体群的平均亲和力时,则对抗体进行如式(2)的高频变异操作:

当抗体的亲和力小于当前抗体群的平均亲和力时,则对抗体进行如式(3)的柯西变异操作:

其中:ai,a'i分别表示变异前后的基因位值,N(0,1)是一个服从标准正态分布的随机数,σi为尺度参数t=1时的柯西随机变量,ρ为变异常数,用来控制子群中个体进行局部搜索的范围,其大小根据种群中的个体数量选取,通常取0.1即可。

1.2.3 抗体选择

首先对克隆变异后临时群体中的抗体进行亲和力的计算,设Ai'={a i1,ai2,…,ain}中亲和力最大的抗体为aij,i=1,2,…,m,如果f(aij)>f(ai),则用克隆变异后亲和力更大的抗体aij代替初始抗体群A中它的父抗体ai,从而使初始抗体群得以更新。因此抗体选择实际是从抗体各自克隆后的子代中选择优秀的个体,从而形成新的种群。

1.3 克隆选择算法的详细步骤

1)随机初始化种群,种群大小为n。

2)根据目标函数计算所有抗体的亲和力。

3)从An中选择m个亲和力最高的抗体构成一个新的关于抗原的高亲和力抗体集合Am。

4)对于3)所选择的抗体种群Am中的抗体分别进行克隆。

5)克隆抗体种群发生变异,产生一个变异的克隆抗体种群C'。

6)确定变异克隆抗体种群C'中每个抗体关于抗原的亲和力f。

7)从变异克隆种群C'中重新选择n个亲和力最高的抗体A'n。

8)随机产生d个全新抗体构成新抗体种群Ad,并用Ad中的d个新抗体替换此时'An中d个亲和力较低的抗体构成下一代的抗体种群An。

9)重复2)~8),循环中止的条件应该满足使抗体种群的平均亲和力达到一个稳定值。这时从循环最终产生的抗体种群中选择出亲和力最高的抗体作为最优解。

2 基于克隆算法的故障恢复策略

2.1 系统故障恢复的数学模型

船舶电力系统的发电机一般通过主配电板以环形相互联接,通常重要负载直接接在主配电板上,其它负载由区段配电板即负载中心供电,允许任意一台发电机向任一负载供电。对于重要负载,经过自动转换开关(ABT)或手动转换开关(MBT),提供两路电源供电,以保证其供电的可靠性,此外重要负载和非重要负载是相互隔离的,如果电路发生故障,由断路器或其它保护装置隔离故障负载或发电机,通过调整ABT或MBT,保证重要负载在满足系统约束条件下,最大程度得到恢复供电,并在必要时切除非重要负载。

图1为一船舶电力系统简化结构图,其中,实线代表正常供电路径,虚线表示备用路径[4]。船舶负载一般分为三级:一级负载,也就是最重要负载;二级负载即较重要负载;三级负载,为不重要负载。在任何情况下,一定要保证一级负载的供电。图中共20个负载,其中:8个一级负载:L1、L5、L6、L8、L11、L13、L16、L17;4个二级负载:L3、L10、L15、L20,其余的8个为三级负载:L2、L4、L7、L9、L12、L14、L18、L19。

2.1.1 目标函数

故障恢复的主要任务是在战损、故障时,确定网络中哪些开关需要闭合,哪些开关需要打开,以使重要负载快速恢复供电,且失电负荷最少。同时还要保证系统恢复供电的快速性,为此要尽量减少开关操作的次数。因此它是多目标决策问题。

(1)负载的供电恢复

船舶负载按重要程度可分为三级,其中,一、二级负载为重要负载,考虑这些负载的恢复,其目标函数为:

如果考虑非重要负载的故障恢复,此时,目标函数为:

式中:i=1,2,…,k;j=1,2,…,t;f=1,2,…,p;Lg1为一级负载,Lg2为二级负载,Lg3为三级负载,xi,xj,xf=1或0,表示负载的供电与不供电。

(2)考虑开关操作次数最少的故障恢复[7]

由于开关操作需要投入一定的时间和人力,恢复过程中,开关操作数越少,操作所需的时间越少,因此开关操作越少越好,且备用开关的转换尽量采用自动转换开关。此时,目标函数可以表示为:

式中:yi=1或0,分别表示仅有一路供电负荷开关i在重构中保持闭合状态或由闭合变为打开状态;zMj,zAr=1或0,分别表示转换开关在重构中由正常供电路径转换到备用路径或保持正常的供电路径供电;Y=[y1,y2,L,ym]T,为单路供电负载开关在重构中的变化情况;ZM=[zM1,zM 2,L,zMn]T,为手动转换开关在重构中的变化情况;ZA=[zA1,zA2,L,zAs]T,为自动转换开关在重构中的变化情况。对自动转换开关转换时,可给以小于1的权重αr。

2.1.2 约束条件

在故障恢复时需要满足以下约束条件:

(1)系统的辐射状运行约束限制

对于能够恢复供电的重要负载,正常供电路径或备用路径有且仅有一条连通。

(2)系统的容量限制

容量限制指非故障断电区的负荷转移到待恢复负荷上时,不能引起支路或发电机过载,如果过载,要考虑卸载。用公式表示为:

式中:xij=0或1表示负荷i支路j的连接开关或支路i与配电板j的连接开关的断或通;Si为负荷或支路的用电量。Mj为支路j的容量裕度。

(3)系统电流限制

(4)电压约束

2.2 故障恢复的克隆选择算法及实现策略

克隆选择算法作为一种新的优化搜索方法,由于它具有记忆功能并具有较好的收敛特性,本文将其应用于船舶电力系统的故障恢复中,算法实现的具体步骤如下:

(1)抗体编码。结合船舶电力系统的特点,对本文所用模型的负载进行与上文相同的0、1、2编码。对只有一路供电的负载只需0、1编码,对有备用路径的负载则用0、1、2编码。每一位编码对应一个负载,则抗体长度为20位,这样有效地缩短了编码长度。

(2)种群初始化。通过模型把确定动作的开关所对应的编码定下来,在此基础上随机产生种群,从而提高原始种群的质量。

(3)亲和力计算。亲和力是用来表明抗体与抗原之间的匹配程度,亲和力越高,说明抗体越接近抗原,也就越接近所求问题的解。根据船舶的具体任务,结合式(4)(6)所示的目标函数,综合考虑重要负载的供电恢复以及开关操作的次数最少,抗体关于抗原的亲和力可以表示为

(4)选择。从已确定的n个抗体中选择m个亲和力最高的抗体构成一个新的关于抗原的高亲和力抗体集合。

(5)克隆。在抗体克隆过程中,对m个亲和力较高的抗体分别进行克隆,这里本文首先对这m个抗体按照亲和力升序排列,即亲和力最大的抗体其序号为i=1,亲和力最小的抗体其序号为i=n,根据克隆规模对种群进行克隆操作。

(6)变异。根据亲和力的大小对临时群体中的抗体进行变异,变异常数ρ=0.1。

(7)在变异后的临时群体中寻找更优秀的抗体代替初始群体中相应的父抗体,以实现初始抗体群的更新,跳转到第(3)步继续执行。

(8)终止条件判断。当进化代数达到最大设定值时,终止计算,输出个体。

3 算法仿真结果分析与比较

针对图1所示的典型的船舶电力系统为算例,各负载属性见表1[8]。

用本文提出的克隆选择算法对图1所示的船舶电力系统中几个典型故障的恢复在Matlab 7.0环境下运行仿真程序,计算机为P4 2.66G 256M内存,Windows操作系统,并与简单遗传算法(GA)、启发式遗传算法(HGA)以及混沌遗传算法(CGA)在处理上述同一问题的结果进行比较,以相同的进化代数k=50为结束条件,取种群数N=100,个体编码长度为20位。

假设支路B10,B63发生故障,L3,L10,L12,L13为受损负载,从图1中可以发现L10只能由正常路径供电,L12失电,L3,L13只能由备用路径供电,为了恢复重要负载的供电,系统一定要进行全局优化,计算结果见表2,表中所列结果是经过多次仿真后取得的最好结果。其中P%为收敛到最佳适应值的概率,最优个体即最优染色体表示了开关动作的最佳组合,0表示对应的负载卸载,1表示开关不动作,2表示对应的负载由备用路径供电。恢复方法是对最优染色体具体内涵的进一步详细说明,为了便于对上述几种方法的比较,把恢复方案分成3类:由备用路径恢复,改由备用路径恢复,以及卸载。

从仿真结果可以看出:几种方法都能最大限度给重要负载恢复供电,但最少开关操作次数和收敛代数不同,最后的卸载量也不同。可以看出克隆算法比混沌遗传算法随着迭代次数的增加,更容易接近最优解,即收敛速度更快。这主要是因为在克隆选择算法中,是根据亲和度函数的大小来确定克隆种群的规模,即亲合度函数值较大的个体其被克隆的种群规模较大,亲合度较小的个体其被克隆的规模较小,这样就可以使得个体种群始终在较优的种群中来寻找搜索空间的所有的局部最优。

4 结论

针对船舶电力系统故障恢复问题,本文采用了一种免疫克隆选择算法来优化开关操作。该算法兼顾了精确的局部搜索与全局搜索的优点,由于克隆算子的作用,因而具有更好的种群多样性,而且克隆选择算法将变异算子作为其操作的主要算子,在一定代数内扩大了搜索空间。另外克隆算子本身具有记忆功能,使得算法以概率1收敛于全局最优解。仿真实验表明,免疫克隆选择算法能够以较小的迭代次数和较少的开关次数最大限度的给重要负载恢复供电,应用于船舶电力系统故障恢复中是非常有效的。

参考文献

[1]Bulter K L,Sarma N D R.General Reconfiguration Methodology for AC Radial Shipboard Power Systems[A].In:IEEE2000Power Engineering Society Winter Meeting[C].2000.1226-1230.

[2]Srivastava S K,Butler-Purry K L,Sarma N D R.Shipboard Power Restored for Active Duty[J].IEEE Computer Applications in Power,2002,15(3):16-23.

[3]Bulter K L,Sarma N D R,Prasad V R.Network Reconfiguration for Service Restoration in Shipboard Power Distribution Systems[J].IEEE Trans on Power System,2001,16(4):653-661

[4]杨秀霞,张晓锋,等.基于启发式遗传算法的舰船电力系统网络重构研究[J].中国电机工程学报,2003,23(10):42-46YANG Xiu-xia,ZHANG Xiao-feng,et al The Study of Network Reconfiguration of the Shipboard Power System Based on Heuristic Genetic Algorithm[J].Proceedings of the CSEE,2003,23(10):42-46

[5]莫宏伟.人工免疫系统原理与应用[M].哈尔滨:哈尔滨工业大学出版社,2003MO Hong-wei.Principle and Application of Artificial Immune System[M].Harbin:Harbin Institute of Technology Press,2003

[6]刘若辰,杜海峰,等.一种免疫单克隆算法[J].电子学报,2004,32(11):1880-1884.LIU Ruo-chen,DU Hai-feng,et al.An ImmuneMonoclonal Strategy Algorithm[J].Acta Electronica Sinica,2004,32(11):1880-1884.

[7]陈根军,李繼洸,唐国庆.基于Tabu搜索的配电网络重构算法[J].中国电机工程学报,2002,22(10):28-33.CHEN Gen-jun,LI K K,TANG Guo-qing.A Tabu Search Approach to Distribution Network Reconfiguration for Loss Reduction[J].Proceedings of the CSEE,2002,22(10):28-33.

基于聚类的动态集成选择算法第6篇

关键词：恶意软件,集成学习,动态集成选择,聚类

0 引言

互联网技术已经使人们的生活和工作发生了巨大的改变。然而, 人们在享受互联网提供的便利的同时, 也承受着恶意程序带来的威胁。在数字化时代的今天, 与恶意程序的对抗已成为信息领域的焦点。近年来, 由于机器学习能够很好地解决恶意软件检测问题, 因而受到了广泛的关注。为了进一步提高恶意软件的检测性能, 本文将机器学习中最新提出的动态集成选择应用到恶意软件检测中。

1 算法背景

1.1 算法提出背景

恶意软件最早出现在上个世纪八十年代, 它是一种利用计算机软、硬件所固有的脆弱性所编制的具有破坏功能的程序。随着个人计算机的普及和网络技术的迅猛发展, 一方面, 信息技术已深入到社会各个领域, 人们享受着这些信息技术带来的巨大进步;另一方面, 计算机病毒的数量和种类日益增多, 人们又不得不面对着越来越严重的信息安全威胁, 特别是计算机病毒、蠕虫和木马等各种恶意软件带来的安全威胁。

恶意软件检测技术特别是未知恶意软件的检测已成为当前网络安全技术领域内的一个研究热点, 目前已有的各种检测技术如启发式代码扫描、基于免疫原理的病毒检测技术和基于程序行为的病毒检测技术等各有特点, 但是应用起来仍然不够成熟, 且均有其局限性。比如基于行为特征的检测方法无法对抗垃圾行为插入等行为混淆方法的干扰。针对传统方法的这些缺陷, 机器学习成为恶意软件检测的新方向。基于机器学习的检测恶意软件技术主要通过学习恶意软件和正常程序的差异性发现有关的识别模式, 并利用这些模式进行相似性分类以发现含有类似模式的恶意软件。这种方法不仅能够检测出未知恶意软件, 对于混淆变形的恶意软件也有较高的检测率, 已成为恶意软件检测发展的重要方向。

对恶意软件检测问题, 由于当前各种恶意软件的个性化差异极强, 使用同一组分类器组成集成分类器检测, 显然不能满足实际需求。而动态集成选择针对每一个恶意软件的特殊性, 动态地选择不同的集成分类器, 因而更适合恶意软件的检测。与此同时, 针对恶意软件检测的实时性需求, 本文提出了一种新的动态集成选择策略用于恶意软件检测。

1.2 本文研究内容

本文将机器学习领域中最新的动态集成选择学习的方法引用到未知恶意软件检测中。尽管动态集成选择方法能够提高分类性能, 但是由于该策略在测试阶段要为每一个测试样本选择分类器, 不能满足恶意软件检测的实时性需求。基于此, 本文提出了基于聚类的动态集成选择方法CDES用于恶意软件检测。相比于传统的动态集成选择, 基于聚类的动态集成选择方法通过分析训练样本得到一个分类模型, 利用该模型对测试样本库中的样本进行分类和预测, 并对已知恶意软件构造分类自动推导出给定样本的推广描述, 从而能对未知恶意软件进行预测。该方法在训练阶段完成了分类器的选择, 因而在测试阶段可以满足检测的实时性需求。

将机器学习方法应用于实际分类问题时, 通常可以分为两步, 即训练和分类预测。训练过程通过对训练集进行特征提取, 用样本的特征属性构造一个分类器。训练集通常是由包含一组特征属性的训练样本组成, 每个训练样本属于一个预定义的类别, 由类标签标记。分类预测就是利用训练得到的分类器模型对新样本所属的类别进行判决。这个过程描述的是单个分类器的训练和分类流程。但是在实际应用中, 单一的分类器往往不能完全解决所面临的问题。而集成学习可以把若干个分类器以一定的方式融合, 通过对多个分类器的分类结果进行某种组合以实现对新数据的分类, 能够取得比单个分类器更好的性能。这里, 单个分类器之间的独立性和差异性越大, 该集成系统的泛化能力就越强, 即根据已有训练数据集建立的分类器能够更好地分析和处理新数据。

2 相关技术概述

2.1 现有的集成学习技术

集成学习[1]是一种新的机器学习范式, 它使用多个学习机来解决同一个问题。它通过调用一些简单的分类算法, 以获得一组相互独立而又比较精确的分类学习机, 然后采用某种方式将这些学习机组合成一个集成学习机, 最后采用一定的算法将各个学习机产生的输出结果融合, 做出综合的判别。目前, 各种集成学习算法已经被广泛应用于生物、工程、医学、计算机视觉以及图像处理等多个领域[2,3,4]。

一个集成系统通常由两部分组成:子分类器的产生方式和多个预测结果的合并策略。接下来将从这两方面分别介绍。

1) 集成学习中子分类器生成方式

在构建集成学习机时, 子分类器的准确性和它们之间的多样性是两个重要因素。集成学习系统中子分类器的构造主要可以分为两类:

(1) 基于不同训练数据集的构造方式[5]

这种方式将同一学习算法应用于不同的训练集。首先通过划分训练样本集合产生多个训练样本子集, 学习算法分别在这些子集上进行训练, 然后生成多个子分类器。这种方式有两种不同的划分方法。一种是将数据集划分成若干个组, 利用每一组数据分别训练分类器, 然后通过组合这些分类器, 得到一个集成学习机。另一种方法则是通过随机抽样技术产生训练样本集合。对于相同的原始训练集, 通过采用不同的抽样技术产生多个训练数据集, 然后使用特定的学习算法训练多个子分类器, 得到一个集成学习系统。这类方法有代表性的算法主要有基于Bagging[6]和Boosting[7]的集成学习算法。

(2) 基于不同特征集的构造方式[8]

这种构造方式实际上也是一种基于不同训练数据集的构造方式, 与基于不同训练数据集合不同的是, 这种方式更注重对同一训练数据集的不同特征表示。目前常用的方法是通过特征选择来获得特征子集, 这种方法选择多个特征子集生成多个子分类器来提高个体的差异性。

2) 集成学习算法中的融合方法

目前, 在集成学习方法中, 常用的融合方法有如下几种:

(1) 投票法:对所有子分类器的分类结果, 通过某种投票原则做出最终的决策。常用的有最小投票、一票否决、多数投票和一致表决等。

(2) 加权平均法:在对各分类器的判决输出并且求平均时, 通过某种加权策略反映各输出的不同重要性。普通平均法可以看作是加权平均法的一种特殊形式。

(3) 其他方法:合并策略也可以是几种合并方法的综合, 如加权方法也可以是对投票法进行加权等。

集成学习有效地提高了分类算法的泛化性能, 并在理论和应用方面取得了很多研究成果。然而, 集成学习仍然存在很多问题需要进一步解决, 比如如何提高集成学习的泛化能力、集成结果合成问题等等。

2.2 选择性集成

尽管集成学习能够获得更好的性能。但是随着子分类器数目的增加, 学习算法的计算和存储开销越来越大, 并且分类器之间的差异性也越来越难以获得。另外, 常用的分类器融合方法在一定条件下都能提高集成学习算法的性能。然而, 这些方法均没有考虑各个样本的具体情况, 都只是根据分类器的统计性能赋予该分类器一个权值, 这些子分类器的输出结果总是按照固定的权值集成在一起, 这显然是不合理的。为了解决以上问题, 有学者提出了选择性集成。该方法通过某种策略选择一部分子分类器组成集成分类器, 其分类性能优于使用所有子分类器构建的集成分类器。

为了证明选择性集成的有效性, 周志华等人提出GASEN算法[9]。该算法为每个子分类器指派一个权重, 该权重度量其对应的分类器在集成中的重要性, 然后通过遗传算法对权重进行迭代计算, 权重高于阈值的分类器予以保留。然后使用保留下来的子分类器进行结论合成。以下是几种有代表性的方法:

(1) 基于遗传算法的选择性神经网络集成 (GASEN) 。该方法利用神经网络分类器作为子分类器, 然后利用遗传算法优化每一个子分类器的权值, 利用预先设定好的阈值选择出相应的子分类器, 作为最终的集成分类器。

(2) 基于克隆免疫的SVM选择性集成。该方法的主体思想与基于遗传算法的选择性神经网络集成一致。其区别在于所使用的子分类器为SVM, 因为SVM是小样本学习机制, 具有较强的泛化性能。另外, 对权值的训练采用克隆免疫的优化方法。

(3) 基于聚类的选择性集成。该方法首先利用训练样本训练好每个分类器, 然后利用聚类的方法对所有的分类器聚类, 对于集成分类器来说, 差异越大越好。因而在得到的聚类结果中选择出差异性大的分类器, 作为最终的集成分类器。

作为一种新的集成学习范式, 选择性集成学习以其良好的性能获得了广泛的研究和应用。然而, 作为一个比较新的研究领域, 还有很多内容值得进一步研究。

2.3 动态集成选择

由于动态集成选择针对不同的测试样本选择不同的集成分类器, 因而能够获得比传统选择性集成更好的分类性能。正因此, 近年来动态集成选择已受到越来越多的学者关注。

1) 动态集成选择的提出

由于集成学习主要利用多个子分类器来获得比单一分类器更好的性能, 因而大部分方法均是通过使用大量的子分类器来获得更好的性能。然而, 这些做法会带来一些负面影响, 首先使用更多的子分类器会导致更大的计算和存储开销;其次, 随着子分类器个数的增加, 各子分类器之间的差异性将越来越难获得。为了解决该问题, 周志华等人提出了选择性集成。由于该方法能够进一步提高集成学习的有效性和泛化性, 因而受到了广泛的关注。然而, 在实际问题中, 不同的测试样本往往具有不同的分类困难。如果所有的测试样本均选择同一组子分类器组成集成分类器, 其性能显然会受到影响。相反, 如果每一个测试样本选择不同的分类器, 会获得更高的分类精确性。动态分类器选择 (DCS) 就是这样一种方法, 该方法为每一个测试样本从多个分类器中选择一个对该测试样本分类性能最好的分类器。尽管DCS往往能够获得好的分类结果, 但有时也许会选择一个较低性能的分类器, 这样就会造成性能的降低。更有甚者, 如果一个错误的分类器被选择, 那么结果将非常糟糕。动态集成选择 (DES) 就是在这样的背景下提出的。为了针对每一个测试样本的差异性, 有学者提出了动态分类器集成选择 (DES) 。由于DES为每一个测试样本选择了多个分类器, 因而其同时具有选择性集成SE和动态分类器选择DCS的优点, 并且能够取得更好的性能。

2) 相关方法

由于动态分类器集成选择方法能够取得更好的性能, 因而得到了许多学者的关注, 并且提出了相应方法。这里我们主要介绍几种有代表性的方法。

(1) 基于K近邻的动态分类器集成选择

K-nearest-oracles (KNORA) 是将集成的精确性作为选择的标准[9]。对每一个测试样本, KNORA首先寻找到其K个近邻作为验证样本, 然后选择出能够正确分类该K个样本的子分类器作为针对该测试样本的子分类器。最后利用投票等融合方法得到该测试样本的分类结果。

(2) 基于动态分类器选择 (DCS) 的动态分类器集成选择 (DCES)

在集成选择时, 集成的差异性与精确性同等重要。为了同时考虑以上两种特性, 有学者提出了基于DCS的DCES方法。同时提出两种策略:聚类和选择策略 (C-V) , 以及K近邻和选择策略 (K-V) 。以上两种策略的主要区别在于:在C-V中, 所有的排序和选择均是在训练阶段执行, 而在K-V中, 这些步骤在测试阶段执行。

(3) 动态overproduce-and-choose策略

动态overproduce-and-choose策略 (DOCS) 由传统的overproduction和选择两步组成。而选择这一步又分为两步:优化和动态选择。第一步通过利用单目标或者多目标优化方法选择一个具有较高精确率的候选种群。第二步利用信度测量方法选择出信度最高的一组集成分类器作为当前测试样本的集成分类器。实验结果表明多目标优化通常能够得到比单目标优化更好的性能。

3 恶意软件检测需求分析

随着互联网的发展, 恶意软件的数量越来越多。因而所需检测算法不仅要能准确地检测出未知软件是否为恶意软件, 还要保证当需要检测大量甚至海量未知软件时, 系统能够实现实时检测。

3.1 恶意软件检测功能需求

由于集成学习首先通过一些简单的分类算法, 获得多个子分类器, 然后采用相应的方法将这些子分类器组合成集成分类器, 最后采用一定的算法将各子分类器产生的输出结果进行融合, 作出综合的判断, 因此, 恶意软件检测模块包括训练阶段和测试阶段。训练阶段主要用于训练恶意软件检测模型, 在该阶段我们将利用准备好的数据对所提出的模型进行训练。由于本系统采用的是集成分类器, 因而这里训练多个子分类器。

测试阶段则对未知软件进行检测, 以判断其是否为恶意软件。本文提出了一种新的动态集成选择策略, 即基于聚类的动态集成选择策略, 为每一个未知软件选择不同的集成分类器进行检测。

3.2 恶意软件检测的性能需求

为了全面客观反应恶意软件检测的性能需求, 我们采用恶意软件识别率、正常程序误报率和识别率来进行恶意软件检测的性能评价。

测试样本空间的分类结果可以分为以下四种情况:

将正常程序分类为正常程序的数目, 记为TP (True Positive) ;

将正常程序分类为恶意程序的数目, 称为FP (False Positive) ;

将恶意程序分类为恶意程序的数目, 称为TN (True Negative) ;

将恶意程序分类为正常程序的数目, 称为FN (False Negative) 。

本文通过实验来说明所提算法在恶意软件检测中的性能需求。实验的主要目标是通过得到的这四类值计算出该算法的恶意软件识别率、正常程序误报率和识别率, 计算方法如下所示:

即恶意程序被正确分类的百分比;

即正常程序被误认为是恶意程序的数目在所有正常程序中所占的比例;

即正确分类的程序占所有被分类程序的百分比。

本文中主要评价标准是识别率, 在识别率取得最高值的同时, 要保证恶意软件识别率最大而正常程序误报率最低。

4 利用聚类方法进行恶意软件检测的策略

4.1 CDES算法的提出

恶意软件检测模块主要包括训练阶段和测试阶段。训练阶段主要用于训练恶意软件检测模型, 测试阶段利用该检测模型判断未知软件是否为恶意软件。在训练阶段需要对训练样本进行分类, 并最终建立分类模型。由于当前各种恶意软件的个性化差异大, 因此, 使用同组子分类器组成集成分类器检测, 不能满足实际需求。而动态集成选择可以针对不同的样本, 动态的选择不同的集成分类器, 因而更适合用于恶意软件的检测, 但是该方法不能满足恶意软件检测中的实时性需求。而聚类分析法[10]可以在没有先验知识的情况下根据数据的相似性对数据进行分类, 并且利用聚类分析法在训练阶段已经为每一类数据寻找到了合适的集成分类器, 在测试阶段不再需要选择分类器, 所以满足了恶意软件检测的实时性需求。基于以上分析, 本文将聚类和动态集成选择方法进行结合, 提出了基于聚类的动态集成选择策略, 用于恶意软件的检测。

聚类就是将数据分组成为多个类[11,12]。在同一个类内, 对象之间具有较高的相似度, 不同类别之间的对象差别较大。与分类不同的是, 它所划分的类是未知的, 即聚类算法不需要“教师”的指导, 不需要提供训练数据, 它倾向于数据的自然划分。

聚类分析又被称为群分析, 根据“物以类聚”的原理, 对样品按照指标进行分类的多元统计分析方法, 聚类分析处理的对象是大量的样品, 要求能按各自的特性进行合理的分类, 没有任何模式可供参考或依循, 即在没有先验知识的情况下进行的处理。

聚类分析方法有三个基本特征:

(1) 适合没有先验知识的分类;

(2) 可以处理多个变量的分类;

(3) 聚类分析法是一种探索性的方法, 能够分析事物的内在规律和特点, 是数据挖掘中常用的一种技术。

由于恶意软件的检测对鲁棒性和实时性的要求很高, 因而需要简单、有效的聚类方法。K均值聚类[13]算法与其他聚类算法相比, 具有清晰的、全局的目标函数, 其聚类的过程高效并且鲁棒, 而且适用于多种类型的数据和大规模数据集。当前, K均值聚类在工程实际中已经得到了广泛的应用。基于此, 本文将K均值聚类算法用于恶意软件检测中。

K均值聚类最初由J.B.Mac Queen于1967年提出。其基本思想是首先从含有n个数据的数据集中随机选取K个数据作为初始的聚类中心, 然后计算数据集中所有数据到各聚类中心的距离, 以最近邻为原则, 所有数据对象将会被划分到离它最近的那个中心所代表的类中。然后计算新生成的簇中数据的均值并作为每一簇的新中心, 再将其与上一次的中心相比所发生的变化, 如果新的中心没有发生变化, 那么算法收敛, 否则, 根据新的中心对所有数据对象重新进行划分。该过程会一直迭代直到满足收敛条件为止。

4.2 子分类器的选择

由于大量恶意软件样本特征数据的收集非常困难, 因此需要利用在小样本情况下分类性能较好的分类器。支持向量机 (SVM) 是一种基于统计学理论的小样本学习机制, 它在有限个训练样本的学习精度和泛化能力之间取得了良好的平衡, 从而获得了较好的推广能力。它在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势, 并在多个领域都取得了成功的应用。因此, 本文决定选择SVM做集成学习的子分类器。

5 CDES检测算法实现

这里我们将从训练和测试两个阶段描述CDES算法。在训练阶段, 首先利用相应的方法, 比如Bagging等产生多个子分类器作为基分类器, 这些分类器将在接下来针对不同的验证样本动态的选择。第二, 利用K均值聚类等方法对训练样本聚类, 并且找到聚类中心。这些聚类中心可以表示这一类样本。在测试阶段我们将首先判断该测试样本属于哪一类。第三, 为每个聚类中心寻找其N个近邻, 并将N个近邻作为验证样本集合, 以验证个体分类器是否作为该类验证样本的子分类器。只有当前的个体分类器能够将这N个近邻准确地分类, 我们才认为该子分类器可以作为当前聚类中心的分类器。如果采用N个近邻不能选择出子分类器, 那么令N=N-1, 直到找到满足条件的子分类器。如果近邻个数为1时仍旧找不到个体分类器, 那么该聚类中心将利用全部子分类器检测。当为所有的聚类中心都寻找到相应的子分类器组成的集成分类器时, 训练阶段结束。由于在训练阶段已经为每一类数据寻找到了合适的集成分类器, 在测试阶段不再需要选择分类器, 所以极大地降低了计算复杂度。

CDES的训练阶段算法流程如图1所示。

CDES训练阶段算法描述如下:

步骤1设训练样本为S={s1, s2, …, sp}, 对训练样本利用bootstrp进行抽样产生n组数据, 利用Bagging等方法产生n个基本分类器集, C={c1, c2, …, ck}。

步骤2对训练样本S={s1, s2, …, sp}, 采用K均值聚类将训练样本聚为K类, 每一类的聚类中心为C={c1, c2, …, ck}。

步骤3对每一类训练样本的聚类中心ci, i=1, 2, …, K, 计算验证样本与每个聚类中心的欧氏距离, 然后对距离进行排序, 以最近邻为原则, 分别寻找每个聚类中心的N个近邻作为验证样本集合, V={v11, …, v1n;…;vk1, …, vkn}。

步骤4对个体分类器进行验证, 能够正确分类N个近邻的基分类器作为该类样本的子分类器。并组成集成分类器。如果所有的基分类器均不能正确的分类N个近邻, 令N=N-1, 返回步骤3;如果当n=1时, 仍找不到个体分类器, 那么选择所有的基分类器作为该聚类中心的分类器, 并组成集成分类器。

步骤5当所有的聚类中心都已经寻找到集成分类器之后, 算法停止。

在CDES的测试阶段, 当测试样本输入后, 首先根据其与聚类中心之间的距离判断该测试样本属于哪一类, 找到其所属的聚类中心之后, 再利用该聚类中心所对应的集成分类器对当前测试样本进行检测, 并将每个个体分类器的检测结果采用投票机制进行融合, 最后得到最终的检测结果。

CDES的测试阶段算法为:

步骤1假设未知样本为X, 计算X与所有聚类中心ci, i=1, 2, …, K之间的欧氏距离, 并记为di, i=1, 2, …, K。

步骤2对距离排序, 以最近邻为原则, 提取测试样本X与聚类中心最短的距离dmin=min (di) , i=1, 2, …, K, 并提取该聚类中心对应的集成分类器。

步骤3利用该聚类中心所对应的集成分类器对X检测, 输出每个个体分类器的结果, 并利用投票融合策略得到最终的检测结果。

测试阶段算法流程如图2所示。

6 CDES算法测试与分析

6.1 分类数据

用于实验的样本数据如表1所示。样本空间中样本总数为797, 分为正常程序和恶意程序, 正常程序从操作系统平台中选择, 选择的是Windows XP首次安装后, 机器中的PE文件371个, 以及一些常见的应用程序的安装和卸载程序52个, 总共是423个。样本空间中训练集总共为590个, 其中正常程序423个, 恶意程序167。

通过各种途径收集PE格式的恶意软件总共167个, 主要为木马和蠕虫程序, 如表2所示, 主要选择了Banker、DDo S、和Spy三个家族。

6.2 系统测试及结果分析

6.2.1 六种恶意软件检测算法对比

为了验证CDES在恶意软件检测中的有效性, 我们将其与另外五种有代表性的方法作比较。这里所采用的子分类器均为线性SVM分类器, 采用5倍交叉验证。这五种方法分别为: (1) 单个SVM分类器。 (2) 基于bagging的集成分类器。这里将应用所有的子分类器。 (3) DCS-LA, 该方法是一种动态分类器选择方法 (DCS) 。 (4) KNORA, 这是一种典型的动态集成选择策略。该策略主要利用K近邻方法实现对每一个测试样本的动态选择。 (5) DRSE[11], 该方法称为数据相关选择性集成, 通过数据之间的相关性来选择集成分类器。

这里我们采用bagging产生个体分类器, 所产生的个体分类器数量为20。子分类器为线性SVM分类器。采用K均值聚类, 聚类类别数为20。在利用验证样本集合为每一个聚类中心选择子分类器时, 所提取的验证样本个数为20。我们将每一个算法独立运行10次。图3为六种算法的识别率。从图中可以看出, 在大部分实验中, CDES的识别率均高于其他五种算法。

图4给出了六种算法在十次实验中恶意软件的识别率。该识别率越高表明对恶意软件的识别率越高。从图中可以看出, CDES对恶意软件的识别率要高于另外五种算法。

图5展示了正常软件的误报率。CDES对正常软件的误报率在大部分实验中低于另外五种算法。

6.2.2 参数分析

本文所提出的CDES算法中包括以下参数: (1) 聚类的类别数量; (2) 利用k近邻选择验证集合时近邻的个数。为了说明以上两个参数对CDES性能的影响, 我们对参数作以下分析。

首先对聚类类别数量进行分析。我们将聚类的类别数量从11~20变化, 来分析聚类类别数对恶意软件检测性能的影响。图6, 图7以及图8分别展示了识别率, 恶意软件识别率以及正常软件误报率随着聚类类别数量的变化情况。这里的近邻个数取20。从图6可以看出, 当聚类类别数为17时, 识别率的性能可以达到最高。与此同时, 从图8可以看出, 对正常软件的误报率也达到了最低。从图7可以看出, 当聚类类别数为15时, 恶意软件识别率最高。

接下来我们将分析近邻的个数对CDES算法的影响。图9, 图10及图11分别展示了识别率, 恶意软件识别率以及正常软件误报率随着近邻个数的变化情况。

从图9可以看出, 当近邻个数为17时, 总体识别率达到最高。从图11可以看出, 当近邻个数为17时, 对正常软件的误报率也达到了最低。从图10可以看出, 当近邻个数为20时, 对恶意软件的识别率达到了最高。

6.2.3 计算复杂度分析

为了说明CDES算法的计算复杂度, 我们将计算时间与另外两种相关的方法DCS-LA和KNORA做比较。其原因是这三种方法均属于动态选择策略。我们对每一个算法均独立运行10次, 其实验设置与以上实验一致。图12展示了三种算法在10次实验中计算时间。从图中可以看出, CDES算法所需要的时间远远少于另外两种算法。而恶意软件检测对实时性要求较高, 本文所提算法满足了该问题的需求。

7 结语

近年来, 机器学习技术应用于恶意软件检测领域, 取得了一定的成果。利用机器学习技术, 可以从大量的样本数据中学习到用以区分恶意程序和正常程序的分类规则, 可以利用这些分类规则构建分类器, 对未知程序的类别进行预测。

集成学习利用多个分类器解决同一个问题, 能够显著地提高学习算法的泛化能力。越来越多的人投入到集成学习的理论和算法研究中, 集成学习已经成为了机器学习领域的一个热点, 并取得了相当多的成果, 但是从集成学习的实际应用状况来看, 还存在许多问题需要进一步解决。

选择性集成通过对分类器进行适当的选择, 剔除对学习系统整体性能有负作用的分类器, 只选择部分性能最优的子分类器组成集成分类器, 进一步提高了集成学习的性能。然而, 在实际问题中, 针对不同的测试样本, 会有不同的测试困难, 如果为所有的测试样本均选择相同的集成分类器分类测试样本, 其性能会降低。相反, 如果为不同的测试样本选择不同的集成分类器, 其性能会极大地提高。因而本文采用动态集成选择学习算法检测恶意软件。

另外, 在实际检测过程中, 有很多测试样本是非常相似的, 对于这些样本我们可以选择一个相同的集成分类器分类, 这样不仅能保持较好的性能, 而且能够降低计算复杂度, 而这也满足恶意软件检测的实时性需求。基于此, 本文提出了基于聚类的动态集成选择算法。

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【动态克隆选择算法论文】相关文章：

克隆算法08-27

克隆选择05-22

动态休眠算法07-10

克隆论文题目04-08