克隆选择算法（精选7篇）
克隆选择算法 篇1
一、引言
人工免疫系统是一个新兴的计算智能研究领域。近年来，人工免疫系统及其应用已逐渐成为了智能信息系统中的研究热点。生物免疫系统的免疫识别过程能在较短的时间内利用数量相对有限的抗体去识别近乎无限多的抗原，从信息处理的角度看，这是在资源受限条件下的一整套高效问题求解机制。克隆选择学说的基因重组、亲和度成熟、受体编辑等机制较好地从个体层次上阐述了这种高效问题求解能力的形成，因而成为多种人工免疫系统模型和算法的重要思想来源，免疫算法就是一种借鉴该系统特性而形成的启发式搜索算法．它具有保持种群分布多样性的特性，避免陷入局部最优解的优点。
二、克隆选择原理
克隆选择是生物免疫系统理论的重要学说，其原理 (如下图1所示) 的基本思想是只有那些能够识别抗原的细胞才进行扩增，只有这些细胞才能被选择并保留下来，而那些不能识别抗原的细胞则不选择，也不进行扩增。骨髓中微小的“休眠”的B细胞每一个都载有一个不同的抗体类型。这些细胞载有对于抗原特异的受体，扩增分化成浆细胞和记忆细胞。
免疫系统在成长的克隆中也是自适应的，同时也呈现了一种变异机制，在对抗体特异编码的基因中产生极高频率点变异。该机制（体细胞高频变异）与为改进抗原结合而进行的选择，共同导致细胞与抗原具有极高的亲和力匹配。
根据免疫系统中的克隆选择学说的思想，该算法在抗体种群和抗体优秀决定基中进行克隆选择操作，全面的模拟了生物免疫系统克隆选择的过程，很好的保持了抗体种群的多样性。
三、克隆选择算法
3.1抗体/抗原匹配算法
要确定一个B细胞对象与提呈的抗原结合得有多好，在抗原上任何点开始匹配；匹配算法计算每一位，在抗原与抗体之间以互补的方式进行匹配，得出匹配值，再从匹配分值得到结合值，根据抗体的结合值的大小可以看出抗体和抗原是否结合的完美，并且可以判定出结合完美的抗体中哪些决定基起到了关键的作用。
对于一个抗体结合一个抗原，结合必须是稳定的，也就是匹配分值在匹配发生之前必须超过一定的阈值。该设定阈值为抗体大小的一半。该方法是Hightower的匹配算法的修改，只是多种伪生物匹配的一种。
抗体/抗原匹配算法的描述：
(1）初始化抗体群，针对抗体与抗原的决定基逐位进行异或操作，若抗体和抗原相对应的决定基相同为0，不同为1，结果统记为c;
(2）将抗体与抗原的决定基逐位进行异或操作结果的累积和记为（公式一）；
(3）对由两个或者更多个1组成的每一区域记录长度为l;
(4) 记抗体的结合度为 (公式二) ;
(5) 定义阈值为
3.2克隆选择算法的实现
克隆选择算法的实质是在进化过程中，在每一代最优解的附近，根据亲和度的大小进行克隆，产生一个变异解的群体，从而扩大了搜索范围 (即增加了抗体的多样性) ，有助于防止进化的早熟和搜索限于局部极小值，同时通过克隆选择来加快收敛速度。其基本思想为：随机生成N个抗体组成的抗体群，对这些抗体进行一些操作后，选出抗体中优秀的决定基片段，针对这些优秀的决定基片段为人民提供良好的生活品质。
我们应该提倡设计的原创性！创造性的建筑设计可使事物再现其岁月流逝所失去的东西，它以一种异化和同化的作用过程，使我们再一次感受到它们的存在，而这正是“场所精神”的本质所在。
设计的本身就是积累与深化的过程，实现于主观世界的创造性思维向客观世界的物质实体转化。它并不是由人脑凭空产生，而通过物质基础的保证，生活经验的积累，艺术素养的沉淀，理论总结的升华。建筑，作为一门艺术，具有历史性，美观性。但她又不同于其他纯粹艺术的特征就在于她的功能性、实用性。脱离功能限定的“设计”概念，泛艺术化倾向的“设计”概念，都是人的欲望和道德相悖而需要协调的内容。这样对“美”的追求不符合建筑装饰行业可持续发展的原则。满足人的这种“欲望之美”的追求不应该作为建筑设计艺术原创性的定位。
建筑最现实的艺术，而不是高高在上，让人顶礼膜拜的艺术，作为生活中与人交流的方式，植根到普通人的日常生活中，帮助并给人们带来快乐。同时那些少数人的高尚品质无法代表正真意义上的“生活的高品质”。只有当设计普及大多数人，并让大多数人都能从中收益时，才是达成了正真的高度。在丹麦，融入大众拥有的设计，被看成是最崇高的，设计需要以人为本，更为完美生活和贴近心灵———这不是什么口号, 而是实实在在的事情, 当设计与人息息相通时, 它能让大众感到艺术和文化的气息, 获得善良、真诚以及美好情感的回馈。
对中国建筑设计行业而言，现在正是一个新的起点：一切充满了不确定、交锋和各种可能。正如矶崎新大师所说“那些未建成的建筑，非常有意义”。设计师独立意识和创新精神的培养以及行业的规范化，是开展一切的基础。我们应该更加注重独立思考和判断的能力，有意保持独立性，放下历史意识的包袱，崇尚自我发展道路，做自己喜欢的作品，有自己的见解和洞察力。
摘要：基于人工免疫系统的原理, 提出了一种克隆选择算法。该算法引入了克隆选择、受体编辑、抗体循环补充机制等思想, 并通过整合克隆选择过程中亲和度的成熟, 可在搜索过程中自动获取与积累相关联搜索空间的知识, 在有限资源的条件下高效的求得问题的解。
关键词：免疫原理,克隆选择,抗体循环补充
参考文献
[1]韦巍, 张国宏.人工免疫系统及其在控制系统中的应用.控制理论与应用, 2002, 19 (2) :157-160
[2]莫宏伟.人工免疫系统原理与应用.哈尔滨工业大学出版社.2003.1390
[3]罗小平.人工免疫遗传学习算法及其工程应用研究「学位论文」.浙江大学.2002.7.129
[4]Luh Guan-Chun, Chueh Chung-Huei.Multi-objective optimal design of truss structure with immune algorithm[J].Computers and Struc-tures, 2004.82:829-844
[5]Thomas M Cover.J A Thomas.Elements of Information Theory[M].北京:清华大学出版社, 2003
克隆选择算法 篇2
目前, 在以工期最短或资源均衡为目标的项目调度问题取得了很好的成果。例如, 文献[1]将单种资源均衡问题转化为多种资源均衡问题, 利用启发式算法对其进行求解。文献[2]基于多种优先规则设计启发式算法求解了多项目调度问题。文献[3]以最小时差为优先规则生成项目进度计划, 将任务的优先规则与遗传算法结合, 设计了遗传算法。文献[4]对每个任务进行赋值, 此值代表任务的优先权, 生成进度计划, 并设计了遗传算法。文献[5]引入自适应高斯变异算子, 设计了与遗传算法相结合的改进的免疫算法。文献[6]设计了遗传蚁群融合算法, 此算法克服了遗传算法及蚂蚁算法的不足。文献[7]设计了一种混合遗传算法, 此算法克服了遗传算法局部寻优能力不足的缺陷。文献[8]将各项目视为整体, 以资源均衡为目标建立了数学模型, 并设计了免疫遗传算法。文献[9]在文献[8]的基础上, 针对每个项目内部的工作数相同的情况, 建立了以资源均衡为目标的模型, 同时设计了免疫遗传算法。通过在企业调查发现, 每个项目内部的工作数有可能不同。另外, 由于企业自身资源的限制和外部环境因素的影响, 需要同时考虑资源均衡和工期最短两个问题。因此, 本文采用加权的方法将工期最短和资源均衡问题一起考虑, 建立改进的多项目多工作选择计划的数学模型, 并设计动态克隆选择算法DCSA (Dynamic Colonel Selection Algorithm) 求解。
1 问题描述
设项目集为C={ci|i=1, 2, …, N}, C中项目之间存在承继关系;ci有Mi (i=1, …, N) 个工作, 且在ci内, 工作与工作之间满足时序约束;cij是ci的第j个工作, Qi表示ci的所有紧前项目构成的集合, Pij表示cij的所有紧前工作构成的集合。对于项目ci, bi=1表示ci被选中执行, 否则, bi=0;若ci在第t天被选中执行, 则bit=1, 否则, bit=0;atij=1表示ci的第j个工作cij在第t天被选中执行, 否则, atij=0。ci的开始时间、合同截止日期、执行时间分别记为si、ei、Ti;sij和dij分别表示cij的开始时间和执行时间。企业共有R种资源, Rk、Rtk分别表示第k种资源的总限量、第k种资源第t天的总限量, cij每天使用第k种资源为rijk, 则建立改进的多项目多工作选择计划数学模型 (P) :
式 (1) 为目标函数, α为权重因子, Q为使目标函数第一项和第二项在同等的量级上引入的常数;式 (2) 为每个项目的执行时间;式 (3) 为所有项目的总工期;式 (4) 表示各项目各工作的时序约束;式 (5) 表示项目的合同约束;式 (6) 表示项目的承继约束;式 (7) 表示第k种资源在第t天的资源限制;式 (8) 表示第k种资源的总资源限制;式 (9) 表示第k种资源的资源利用偏差;式 (10) 表示资源的权重之和等于1。
2 动态克隆选择算法
克隆选择体现了生物体免疫系统对自适应抗原刺激的动态过程[10]。应答抗原能力强、亲和力高的免疫细胞通过克隆选择被选择繁殖一些克隆细胞。其基因进行重复突变, 产生应答能力更强、亲和力更高的细胞。借鉴此过程, 设计动态克隆选择算法 (DCSA) 求解上述问题。
2.1 编码
项目调度序列及对应内部工作的调度序列分别记为C=c1c2…cN、J=J1J2…JN, 且项目ci的工作调度序列记为。项目是否被选中执行用0、1字符串表示为B=b1b2…bN。抗体的编码记为Ab= (C;B;J) , 表示最终的调度方案。
2.2 初始抗体的产生规则
由于项目之间、项目内部工作之间不仅需要满足承继约束、时序约束, 而且还需要满足资源的限制。基于此, 采用拓扑排序生成项目及其工作的调度序列, 根据资源限制安排各工作的开始时间, 再由各工作的开始时间及执行时间确定项目的开始时间、完工时间。最后根据项目完工时间确定是否被选中, 从而生成一个抗体。进而产生所有需要的抗体。
2.3 亲和力的设计
项目总数、被选择执行的项目数分别记为N、N1, 抗体Ab在数学模型中的目标函数值记为f (Ab) , 亲和力记为aff (Ab) 。对于最小化问题, 亲和力与目标函数值成反比, 则aff (Ab) 设计为:
2.4 动态繁殖
首先将抗体群按亲和力从大到小排序, 按下式:
将排好序的群体划分成L个子群, Hi (i=1, …, L) 为每个子群的抗体数。对子群i (i=1, …, L) 进行动态繁殖:即对第i个子群中亲和力最好的抗体繁殖Hi-1个替换此子群中其余的抗体。
2.5 一点交叉
针对克隆群中的每个抗体, 生成一个0到1的随机数β, 如果β>0.5, 则从该群中随机选择一个不同的抗体与之进行一点交叉[11]。否则, 从记忆池中任选一个抗体与之进行一点交叉[11]。
2.6 变异
随机生成一个0到1的数β, 若β>Pc (Pc为变异概率) , 随机整数λ (1<λ<N) 作为抗体Ab的项目调度序列基因块C=c1c2…cN的变异点, 对该变异点进行插入式变异[12]。并按初始抗体规则中工作调度序列的产生方式重新生成该变异点对应项目的工作调度序列。若β<Pc, 按初始抗体产生规则重新生成项目及其工作的调度顺序。
2.7 克隆选择
首先将群体按目标函数值进行升幂排序, 按下式:
将排好序的群体划分成M层, 对于前M/2层, 从每层中随机挑选三分之二的抗体进入群体Dn且保证每层最好抗体进入Dn, 对于后M/2层, 从每层中随机选取三分之一的抗体进入Dn且每层最好抗体进入Dn。
2.8 动态克隆选择算法 (DCSA) 描述
Step1n←1, 生成M+m个初始抗体, 随机选取m个抗体进入记忆池Me中, 剩下的N个抗体进入一般抗体群An中;
Step2根据式 (11) 计算Me和An中抗体的亲和力;
Step3将An中抗体进行动态繁殖, 获Bn;
Step4将Bn进行变异、一点交叉操作, 得B'n和C'n;按式 (11) 计算B'n、C'n中抗体的亲和力;
Step5删除An∪B'n∪C'n中相同的个体, 然后进行克隆选择操作, 获Dn;
Step6根据随机抑制半径α, 删除Dn∪Me多余的抗体并对Me进行更新;
Step7对Dn进行更新操作, 得An+1;
Step8若满足终止条件, 则输出Me中最好抗体, 并结束;否则, n←n+1, 转到Step3。
3 数值实验
本文首次将资源均衡和工期最短两个目标一起考虑解决多项目多工作选择计划问题, 选取MaxR、Max TW、Long T、Min LF四种不同优先规则的启发式算法[13]与动态克隆选择算法 (DC-SA) 进行比较。MaxR、Max TW、Long T、Min LF仅各自执行1次;DCSA执行30次;迭代次数Max=300, 一般抗体群规模N=50, 记忆池规模m=15, 变异概率Pc=0.7。
问题企业承接了30个项目, 每个项目的工作数不同, 每个项目的工作数大于等于10小于等于25个, 项目必须在T=150 (天) 中完成, 企业一共有4种资源, 资源的权重分别为0.3, 0.2, 0.3, 0.2, 每天的资源量分别为10、10、10、10、10, 且在T天内的总资源量分别为1450、1400、1450、1400。由于资源的限制, 企业只能选择部分项目执行, 不被选中的项目实行外包 (省略其他相关数据) , 数值实验结果如表1-表3所示。
由表1-表3可知, 当模型的加权因子等于0.5时, 所有算法都获得了问题的决策方案, 并且被选中执行的项目都在合同规定的时间内完成, 各种资源使用量也没有超出限制。在四种启发式算法中, Min LF选中项目最多, MaxR资源利用最好;MaxR和Long T项目选中率相同, 但资源利用率和决策方案的总工期不同;Max TW选中项目最少, 资源利用最差。动态克隆选择算法的项目选中率与Min LF相同, 但是资源利用率为98.7962%, 最好方案的总工期121, 比其它四种启发式算法的结果好。此外, 当模型的加权因子为0时, 此问题就是资源均衡问题, 动态克隆选择算法的项目平均选中率与模型的加权因子为0.5时的选中率相同, 但是资源利用率和最好方案的总工期分别为99.1506%、127, 资源利用上好于模型的加权因子为0.5时的资源利用率;当模型的加权因子为1.0时, 此问题就是工期最短问题, 动态克隆选择算法的项目选中率与模型的加权因子为0.5时的选中率相同, 但是资源利用率和最好方案的总工期分别为98.3567%、118, 工期好于模型的加权因子为0.5时的总工期。不管模型的加权因子取何值, 四种启发式算法仅仅目标函数值发生变化, 最好方案的总工期及资源利用率均不变化。因为启发式算法的优先规则是已经确定的, 所以项目的调度顺序和工作的执行顺序就确定, 不会因模型的加权因子不同而不同。另外, 当项目数和工作数增多时, 本问题就变得更加复杂, 启发式算法很难处理这类复杂问题, 也不能获得较好决策方案, 而本文设计的动态克隆选择算法可以通过动态克隆、交叉、变异、克隆选择算子增加群体的多样性, 也可以扩大动态克隆选择算法的搜索范围, 进而能获得更好的解。
4 结语
克隆选择算法 篇3
随着互联网的高速发展, 网络上的信息也成指数增长, 为了从海量的Web信息中获取用户所需要的信息, 人们主要是借助于搜索引擎。CNNIC[1]2013年7月发布的报告称:中国网民中使用搜索引擎的比例为79.6%, 使用搜索引擎的用户规模达47 038万人。在各类网络应用中, 搜索引擎的使用在各类网络应用中稳居第二。而85%的搜索引擎使用者只会查看返回结果的第1页的内容, 也就是排名前10的查询结果[2,3]。而在检索结果中靠前的网站能得到更大的访问量, 增加网站的知名度, 增加广告等收入等。
因此, 有些网站就会采用不正当的手段来提高网页在搜索引擎中的排名, 这种以欺骗搜索引擎来获得较高排名的方法, 被称为搜索引擎作弊或网页作弊[4], 这样的网页被称为作弊网页或垃圾网页。垃圾网页不仅严重降低了搜索结果的质量, 使用户对搜索引擎提供商失去信任, 也使得人们花费更多的时间去寻找到有用的信息。同时也会浪费掉搜索引擎提供者大量的计算资源与存储资源, 对搜索引擎公司的物力与财力都是巨大的损失。
网页作弊技术分为两大类[4], 分别是提高评分技术和隐藏技术。提高评分的作弊技术可分为内容作弊和链接作弊, 隐藏作弊分为掩盖作弊和重定向作弊。随着互联网的发展, 网页作弊技术也越来越先进, 给垃圾网页的检测带来更大的难度。本文研究提出的使用基于克隆选择分类算法CSCA (Clonal Selection Classification Algorithm) [5]的垃圾网页检测技术, 利用人工免疫系统的识别、学习、记忆、自适应等特点, 在数据集WEBS-PAM-UK2006[6]的实验结果表明该技术能有效地检测垃圾网页。
1 相关工作
早在2002年Henzinger等人就指出, 网页作弊是搜索引擎面临的主要挑战之一[7], 为此, 国内外学者对垃圾网页的检测作出了大量的研究。Fetterly等[8]认为能通过一些统计特性来检测Web Spam。研究发现Spam页面的URL的点号、短划线、数字及长度等具有正常页面相比不寻常的值, 同时, Spam页面的内容也会经常变化。另外, 通过网页的入链及出链数目可以发现大量的作弊网页。垃圾网页检测可以看作是一个分类问题, 将一个网页分为正常或者垃圾页面。Abernethy等[9]利用内容和链接特征并运用SVM算法能有效地检测垃圾网页。Prieto等[10,11]提出基于C4.5分类器的Web spam检测系统SAAD (Spam Analyzer and Detector) 。Arauio等[12]提出了一种结合链接特征与语言模型的检测垃圾网页的分类器, 取得了不错的检测效果。
以上这些检测方法大多使用传统的分类器, 而要提高垃圾网页的检测效果, 通常是通过改进现有分类器或寻找新的适用于垃圾网页检测分类器。近年来, 人们从生物系统获取灵感, 越来越多的新方法被用于机器学习, 而这些方法在垃圾网页检测的应用中并获得不错的检测效果。Taweesiriwate等[13]提出了基于链接的蚁群优化学习算法用来检测spam host, 并能在spam和normal的识别上获得很高的精准率。Goh等[14]将网页的链接特征和内容特征输入多层感知神经网络, 利用其灵活的结构和非线性变换等特点能有效地检测垃圾网页。Zitar等[15]将遗传算法结合到人工免疫系统中进行垃圾邮件检测能获得比商用反垃圾软件更好的效果。Mahmoud等[16]用基于人工免疫系统的克隆选择来进行SMS spam的检测, 该方法能有效地区分正常短信与垃圾短信。诸多研究表明基于人工免疫的分类方法有着很好的分类特性, 在垃圾邮件的检测中, 用垃圾邮件和正常邮件训练分类器获得能识别邮件类别的检测器, 而垃圾网页与垃圾邮件有着许多类似的特征, 如热门词比例、单词平均长度等, 在本文中利用这种新兴的机器学习方法, 将人工免疫系统应用于垃圾网页的检测中, 实验表明这是一种有效的垃圾网页检测方法。
2 基于免疫克隆选择的垃圾网页检测算法
2.1 免疫克隆选择原理
人工免疫系统是基于生物免疫系统, 用来抵抗身体遭受的外部入侵的病原体, 如细菌、病毒等[17]。入侵的病原体就被称为抗原, 引起免疫系统产生的免疫细胞就称为抗体。抗体通过与抗原的特异性结合来消灭抗原。抗原与抗体之间的匹配程度被称为亲和度, 如果亲和度高, 那么抗原就将位于抗体的识别区内[18]。如果抗体能有效识别抗原, 那么它将成为记忆细胞, 在系统再次遭受同一类抗原入侵时, 系统就能通过记忆细胞快速作出二次免疫应答。
克隆选择的基本原理是能有效识别抗原的抗体才能进行克隆增殖, 即与抗原具有越高的亲合力的细胞能产生越多的后代。克隆选择算法就是通过候选解集的变异, 并由亲和度进行解集的筛选。克隆选择算法是全局优化搜索的算法, 同时具有全局搜索和局部搜索的功能, 有较好的记忆功能和收敛特性, 通过构造记忆细胞产生局部最优解, 最终形成全局最优解群体。
2.2 特征选择
特征选择主要是过滤掉一些不相关的或者冗余的特征, 以获取最有区分度的特征来提高检测系统的性能, 如果使用的特征较少就能减少算法的计算量, 节省资源。有许多经典的特征选择算法包括χ2 (Chi-squared) [19], SVM, IG (Information Gain) [20]等。文献[20, 21]比较了各类特征选择方法在文本分类中的效果, 证明了χ2和IG是比较有效的特征选择方法, 在本文中我们对比了基于χ2的特征选择方法和基于IG的特征选择方法在本检测方法中的效果。
基于χ2的特征选择方法是利用χ2统计原理, 通过计算特征的χ2值来选择特征。χ2值的计算方法如下:
其中, n是网页样本的类别数, m是特征值的区间数。Aij是第i个区间, 第j类别的样本数。Eij=Ri×Cj/N是Aij的期望值, 其中的Ri是第i个区间的样本总数, Cj是第j类别的样本总数, N是总的样本数。
当每个特征的χ2值被计算出来后, 将特征按χ2值由高到底排序, χ2值越高的特征越具有区分度。
基于信息增益的特征选择方法是通过计算特征对类别的信息增益, 反映的是特征出现前后的信息熵之差, 特征t的信息增益计算如下:
式中H (C) 为整个分类系统的熵, 表示为:
其中n为网页类别的数目, P (Ci) 为该类别网页所占比例。条件熵H (C|t) 表示为:
其中m为特征t的取值的数目, P (Ci|t=tj) 表示特征t取值为tj是属于类别Ci的概率。
同样地, 每个特征对类别的区分度由信息增益值决定, 特征选择时按信息增益值由高到低进行选择。
2.3 基于克隆选择分类算法的垃圾网页检测
克隆选择算法是一种基于免疫系统中克隆选择理论设计的免疫算法, 基于克隆选择原理的克隆选择分类算法CSCA最早由Jason Brownlee[5]提出, 是一种有效的机器学习方法。本文提出的垃圾网页检测方法基于克隆选择分类算法, 基于免疫克隆选择的垃圾网页检测方法的总体结构如图1所示。
免疫系统概念与检测算法的对应关系如表1所示。
算法的最终目的是生成能检测垃圾网页的记忆细胞集。算法中所有的抗体、抗原和记忆细胞都由向量表示, 定义如下:
其中, vij (j=1, 2, …, r) 是特征值, C是类标。对于网页, C表示的是垃圾网页或正常网页;对于抗体, C表示的是抗体能识别的网页类型。
算法详细步骤如下:
(1) 初始化
将所有网页样本作为抗原, 添加到抗原集AG中。从抗原集中随机选择S个抗原添加到抗体池AB中, 作为初始抗体池。
(2) 进行G次迭代
(1) 计算抗体池AB中每个抗体的适应度值fitnessi, 适应度值反映了分类器最大化准确率的优化问题, 就将分类问题表示为函数优化问题。计算方法如下:
其中, correcti表示第i个抗体识别正确的抗原数, 即识别出的抗原与抗体类别相同。incorrecti表示第i个抗体识别错误的抗原数, 即识别出的抗原与抗体类别不相同。对每个抗原找到与其最匹配的抗体, 就表明这个抗体识别到了该抗原。抗原与抗体的匹配程度由亲和力affinity度量, 亲和力affinity是由欧几里得距离进行度量的, 反映的是抗体对抗原的识别程度。计算方法如下:
其中, ag.vi表示抗原ag的第i个特征值, ab.vi表示抗体ab的第i个特征值。
然后将所有的抗体加入到候选集AB*中, 再按以下规则进行精简:
i.将候选集AB*中错分数incorrect为0的抗体从AB*中剔除。
ii.若抗体的正确分类数correct为0且错分数incorrect大于0, 则将他们的类标改为它们所识别的最多的抗原的类标。然后计算它们的适应度值。
iii.若抗体的适应度值低于阈值ε则将该抗体从候选集AB*以及抗体集AB中剔除。
(2) 对候选集AB*中的抗体再进行克隆和变异, 抗体的克隆个数为num Clonesi, 克隆的规模由抗体的适应度决定, 若抗体适应度值高, 克隆数目就大, 反之就小。克隆数目由下式计算:
其中, fitnessi为抗体的适应度值, n为AB*中总的抗体数目, α为克隆比例因子。
抗体的每个属性能变化的范围由它的适应度值来决定。每个属性的变异范围rangei由公式得出:
其中, ri为该属性的属性值范围。
(3) 新产生的克隆体添加到抗体集AB中, 同时随机选择n个抗原添加到AB中以保持抗体集的多样性。
(3) 记忆细胞的生成
再次计算抗体集AB中所有抗体的适应度值, 若抗体的适应度值低于阈值ε则将该抗体从抗体集中剔除。剩余的抗体添加到记忆细胞集MC中。
(4) 分类
对未知样本采用K-Nearest Neighbors分类算法进行判别, 即该样本的类别由记忆细胞集MC中与它最匹配的K个记忆细胞投票决定。
3 实验结果分析
3.1 数据集及评价指标
本实验采用WEBSPAM-UK2006数据集, 这些数据由米兰大学Web算法实验室于2006年5月收集, 并作为首届Web Spam Challenge使用的数据集。这是一个基于host页面的公共数据集, 所有的这些网页均是随机爬取自.uk域名, 包括spam页面和non-spam页面。其中spam页面有1978个而non-spam页面有6511个, 这是一个不平衡的数据集。数据集包含直接特征、内容特征和链接特征, 共139个。基于内容的特征包括网页标题长度、网页中含有的词数、平均单词长度、可见文本所占的比例等;基于链接的特征包括网页的入链数、出链数、PageRank值、TrustRank值等;直接特征包括host的page数、host name的字母数。
实验采用十倍交叉验证的方法, 将数据集分成十分, 每次用其中一份做测试, 其余九份用作训练。分类结果的评价方法采用召回率 (Recall) 、精准率 (Precision) 和F-Measure值来衡量。其中, 召回率是指实际为垃圾网页中预测正确的网页的比例, 精准率是指预测为垃圾网页中的实际为垃圾网页的比例, 而F-Measure值是取的召回率和精准率的一个平均, 它的计算方法为:
3.2 检测结果分析
为了比较两种不同特征选择方法对本检测算法的性能影响, 我们在数据集上作了测试, 由于数据集的不平衡性, 我们通过随机选择的方法从6511个non-spam样本中选择出1978的样本与全部spam样本组成平衡数据集。本实验中设置参数为G=8, S=100, α=1.0, ε=1.0, k=1。表2为测试结果。
从表2可以看出, 在特征数目为10至30个时, χ2方法在分类器上获得比IG方法更高的精准率, 但召回率略低;在特征数为10、20、40、60等数目较少时, χ2方法在分类器上获得更好的F-Measure值, IG方法仅在特征数为30、50、70、80、130时F-Measure值略高;χ2方法在特征数为60个时, 获得最好F-Measure值87.9%, 而IG方法需在特征数为80个时, 获得最好F-Measure值88.0%, 整体上说, 这两种特征选择方法在本检测算法中获取着相似的效果。
为了测试本算法的性能, 我们还与经典的分类算法Na6ve Bayes进行对比。同时, 实验数据采用在对比特征选择方法实验中平衡后的数据集。本检测实验中设置参数为G=8, S=100, α=1.0, ε=1.0, k=1。同时, 实验中的特征是按χ2值从高到低进行选取的。图2至图4为两种检测算法在不同的特征数下的实验统计结果。
从图2可以看出两种方法的召回率都随着特征数的增加都趋于减少, 但本检测方法的召回率要明显高于Na6ve Bayes。从图3可以看出在精准率上, 两种方法都随着特征数的增加都趋于平缓, 本方法要比Na6ve Bayes稍低一点。原因在于免疫克隆选择算法的动态检测机制, 使得被漏检的垃圾网页数目减少。抗体的适应度阈值的设定, 它体现了抗体的进化程度即问题的解的优化方向。其次, 训练时的迭代次数也会影响系统的动态性, 如果迭代次数过少会造成特征的遗漏, 而过多会产生冗余, 都会影响判断的准确度。
从图4可以看出, 本方法的F-Measure要明显高于Na6ve Bayes, 而且比较平缓稳定。本检测方法在特征数为40至60时, 可获得较高的召回率、精准率和F-Measure值, 能以较少的特征获得比较好的检测效果, 同时F-Measure最高可达87.8%, 而Na6ve Bayes最高仅能达到86.2%, 说明本方法用于检测垃圾网页优于Na6ve Bayes算法。
4 结语
本文利用新兴的机器学习方法, 提出了一种基于免疫克隆选择的垃圾网页检测方法, 通过在WEBSPAM-UK2006上的实验表明, 本研究方法能有效地进行垃圾网页的检测。今后的研究将从以下方面继续研究:对算法进行改进或寻求新的算法使之能适用于不平衡数据集的处理。利用遗传算法等改进现有的免疫克隆选择算法以提高检测效果。
摘要：垃圾网页是指一些网页通过不正当的手段来误导搜索引擎, 使网页获得高于其应有的排名, 从而获得更多的访问量。它不仅降低了网页的质量, 同时也导致了严重的Web信息安全问题。传统的垃圾网页检测通常使用经典的机器学习方法包括贝叶斯算法、SVM、C4.5等, 这些算法对垃圾网页的检测有一定的效果。在前人的研究基础上提出一种基于免疫克隆选择的垃圾网页检测方法。利用人工免疫系统的自学习及自适应能力来检测利用新作弊技术的垃圾网页, 并与广泛用于垃圾网页检测的贝叶斯算法对比。实验表明该方法能有效、可靠地检测出垃圾网页。
克隆选择算法 篇4
人工免疫系统(Artificial Immune Systems,AIS)是继神经计算、进化计算之后的自然计算的研究新方向,己经迅速成为研究热点,主要是通过深入探索生物免疫系统所蕴含的信息处理机制,建立相应的工程模型和算法,用于解决各种复杂问题。
1 免疫系统
生物免疫系统将所有的细胞分为两类:Self细胞(自我)和Non Self细胞(非我)。Self细胞指自身健康,没有被感染、破坏的细胞;Non Self细胞指病毒、细菌、寄生虫等有害物质和自身被感染、破坏的细胞。免疫就是识别Self和Non Self,并消灭Non Self,是为了保证机体完整性的一种生理学反应。用集合表示有这么一个关系:对于集合域X,它包括两个子集自体集合S和非自体集合N,则有自体集合S⊆X和非自体集合N⊂X,而且S∪F=X且S∩F=φ。
2 人工免疫算法
人工免疫系统抽取生物免疫系统所蕴含的信息处理机制,建立用于解决各种复杂问题的工程模型和算法,这些模型和算法都力图集中体现以上的生物免疫系统的相应特点。
人工免疫算法(Artificial Immune Algorithlum,AIA)是模拟人体免疫学原理而设计的一种新型算法,是自然免疫系统在进化计算的一个实现。
人工免疫算法的基本流程如图1。
STEP1:初始化AIA的抗原。对运行过程所需参数和数据进行设置,包括初始化运行参数、基因库以及确定抗体的编码方式和构造初始抗体集,通常可以在解空间中随机产生N个候选解作为初始抗体,N为抗体群中抗体的数目。
STEP2:计算亲和力(affinity)。亲和力是一个抗体结合部位与一个抗原决定基结合的牢固性,结合自抗原分离的可能越小。用来表示抗原和抗体之间、抗体和抗体之间结构的相信程度。设定亲和力的计算函数为Affinity(B,G),一般使用介于0到1之间的实数表示,Affinity(B,G)值越大说明抗体B和抗原G之间匹配得越好。
STEP3:产生新的抗体。调用人工免疫算法,初识抗体通过人工免疫算法的作用产生新的抗体。
STEP4:调用Affinity(B,G),计算新抗体的亲和力。
STEP5:若新抗体中有与抗原匹配的抗体,则结束,否则转到STEP6。
STEP6:抗体选择。按照“优胜劣汰”的自然选择机制,在原有的N个有效抗体和新产生的若干个体抗体中选择出N个与抗原匹配得较好的抗体构成新的抗体群,在进行选择操作时,应依据抗体之间的排斥力限制进入新抗体群中的相同抗体的数目,以保持抗体群中抗体的多样性,增强抗体群的免疫力,选择完成后转到STEP3。
3 基于克隆选择的免疫识别算法
克隆选择学说早在1958年就由Burnet建立,描述了获得性免疫的基本特性,并且生命只有成功识别抗原的免疫细胞才得以增殖,经变异后的免疫细胞分化为效应细胞(抗体)和记忆细胞两种。但计算领域的克隆选择算法(Colone Selection Algorithm,CSA)却直到2001年才由D.castro和von Zuben明确提出,能够完成机器学习和模式识别的任务,并可以用来解决优化问题。其核心是复制(克隆)和变异。前者与个体的亲和度成正比,保证群体亲和度逐步增大,后者与个体的亲和度成反比,保留最佳个体并改进较差个体。
克隆选择算法是基于群体的免疫算法,是一种模拟免疫系统的学习过程的进化算法,它模拟这一过程进行优化。也是抗体集进行群体更新的策略(如图2)。
STEP1:抽取抗原集合中的一个抗原。
STEP2:计算与抗体集合中每个抗体的亲和力;从中选择n个亲和力最高的抗体。
STEP3:对选择出来的抗体进行克隆增殖,目的是确定对各抗体所在邻域做局部搜索的次数。克隆规模正比于抗体的亲和度,即亲和度高的抗体得到的局部搜索的机会较多。
STEP4:对克隆产生的个体进行突变,用来对各抗体所在的邻域进行局部搜索,变异位数反比于其同抗原的亲和力,即对亲和度较高的抗体,则在其较小的邻域范围内做精细搜索。
STEP5:压缩选择,在抗体群中选择具有最高亲和度的n个抗体组成新一代抗体群,更新抗体集合。
STEP6:如果满足终止条件,则结束;否则转至STEP1继续执行。
从算法流程分析得知,克隆选择的主要特征是免疫细胞在抗原刺激下产生克隆增殖,随后通过遗传变异分化为多样性效应细胞(如抗体细胞)和记忆细胞。克隆选择对应着一个亲和力成熟(affinity maturation)的过程,即对抗原亲和力较低的个体在克隆选择机制的作用下,经历增殖复制和变异操作后,其亲和力逐步提高而“成熟”的过程,本质上是一个达尔文式的选择和变异的过程。
4 结论
利用人工免疫的基本原理来解决计算机系统的安全问题,主要也是区分“自体”和“非自体”的问题,人工免疫系统是具有自学习、自适应、自组织的高度复杂性系统的代表,己经迅速成为研究热点,其研究成果已应用到计算机安全、模式识别、机器学习、机器人控制、异常和故障检测、数据挖掘和分析及复杂优化问题求解等诸多领域。
参考文献
一种基于克隆选择的入侵检测算法 篇5
从对基于人工免疫的传统入侵检测技术中,可以发现它们的一些不足[1]。首先是对于自体的定义缺乏动态性:在第一次自体定义以后,就几乎没有任何的变化。这要求自体的定义是完备的,且不包含任何定义错误的自体,这在真实的网络环境中几乎是不可能实现的。第二,为了能检测未知入侵或误用,通常都需要一个庞大的自体集合来训练未成熟监测器,保证成熟的检测器尽量少地检测到自体,从而减少误报率,这通常给计算带来巨大的开销:在空间复杂度上,为了存放庞大的自体集合,需要保留足够大的空间;在时间复杂度上,因为生成成熟监测器的时间是与自体数量成指数关系,所以生成一定数量的成熟监测器,自体数量越大,需要的时间也就越多。
2. 克隆技术和入侵检测的介绍
入侵检测系统[2]是一种通过从计算机网络或计算机系统中的若干关键点收集信息并对其进行分析,从中发现网络或系统中是否有违反安全策略的行为和遭到袭击迹象的安全技术。作为一个成功的入侵检测系统,不仅可使系统管理员时刻了解网络系统(包括程序、文件和硬件设备等)的任何变更,还能给网络安全策略的制订提供依据,而且它应该具有简单的管理配置,使非专业人员可以容易地完成配置管理。入侵检测的规模还应根据网络规模、系统构造和安全需求的改变而改变。入侵检测系统在发现入侵后,应及时做出响应,包括切断网络连接、记录事件和报警等,保证网络安全稳定地运行。
克隆选择[3]是利用免疫选择、克隆、变异、克隆抑制、种群刷新等算子模拟生物免疫应答中的各种免疫操作,形成基于生物免疫系统克隆选择原理的进化规则和方法,实现对各种最优化问题的寻优搜索。
3. 基于克隆选择的入侵检测算法的模型结构
模型包括四个重要的模块:耐受模块、记忆细胞检测模块、成熟免疫细胞检测模块和协同刺激模块。
(1)耐受模块设计
在未成熟细胞进行耐受训练时,自体为s Ag中经过记忆免疫细胞以及成熟免疫细胞检测剩下的抗原。此时系统认为这些抗原已通过检测,被认定为自体抗原。未成熟细胞必须在一个耐受期a内经历否定选择后方能成熟。其中所有的耐受都是把随机生成的未成熟细胞与被一记忆细胞检测分类为自体抗原进行否定选择,满足匹配后成为成熟免疫细胞。
(2)记忆细胞检测模块设计
1)记忆免疫细胞中的抗体与抗原进行匹配。如果不匹配,则交给成熟免疫细胞检测:否则进行下一步骤。
2)把发生匹配的细胞拷贝放入激活待协同刺激集合,并把这些拷贝细胞中的年龄域清零,步入等待协同刺激生命期(协调刺激模块)。把相应的抗原隔离出来放入隔离集合。
3)把获得肯定的协同刺激的细胞加入到记忆细胞集合,并删除它们匹配的隔离集合中的抗原,表明的确检测到了非自体抗原。把该记忆细胞以种痘的方式发往其它主机,使整个网络对该抗原都能产生二次应答。
4)把获得否定的协同刺激或在指定时间内没有获得协同刺激的细胞从激活待协同刺激集合中删除,并把抗原交给成熟免疫细胞检测。这表明发生了错误肯定或无协同刺激及时参与。
(3)成熟免疫细胞检测模块设计
在成熟免疫细胞的检测时,抗原为s Ag中经过记忆免疫细胞检测剩下的抗原。包括以下具体步骤:
1)成熟免疫细胞中的抗体与抗原进行匹配。
2)把抗原送到未成熟细胞集合进行耐受训练。
3)检查细胞在生命周期中匹配数是否大于阈值,大于则被放入激活待协同刺激集合中;否则进入下一步骤。
4)判断所有成熟免疫细胞的年龄是否大于阈值,大于则走向死亡。否则转到1)。
(4)协同刺激模块
协调刺激模块主要处理进入Q集合的免疫细胞,并通过异步外部系统干预决定它们的行为。具体过程如下:
1)对于新加入的细胞,判断Q集合中是否己经存在,如存在,则放弃加入。
2)定时增加Q集合中免疫细胞的年龄,把年龄过大而又未获得协调刺激的细胞删除,并删除它能匹配的隔离集合中的抗原;若该细胞是一记忆细胞集合中某细胞的拷贝,还要删除记忆细胞中的这个细胞母体。
3)把获得肯定协调刺激的细胞送到记忆细胞集合,并删除它能匹配的隔离集合中的抗原。
4)把获得否定协调刺激的细胞删除,并把它能匹配的隔离集合中的抗原交给成熟细胞进行亲和力成熟过程:若该细胞是记忆细胞集合中某细胞的拷贝,还要删除记忆细胞中的这个细胞母体。
4. 基于克隆选择的入侵检测算法的实现
(1)系统层面分析
系统分为两个层面:一个层面是抗原处理流程,另一个为细胞进化过程。
第一个层面的抗原处理步骤为:
1)从实际网络数据流中,获取IP数据包,提取IP包的特征信息(如IP地址、端口号和协议等信息),构成长度为L的二进制串,作为抗原定量放入集合Ag中。
2)抗原抽样。从Ag中按一定的比例,随机选出抗原组成集合s Ag,用于每一代的检测。
3)记忆免疫细胞对s Ag集合元素进行检测。把被记忆免疫细胞分类为非自体的抗原删除,剩下被分类为自体的抗原被送到成熟免疫细胞集合进行检测。
4)成熟免疫细胞对s Ag集合元素进行亲和力训练。之后把自体抗原提交给未成熟细胞的自体耐受过程。
5)未成熟免疫细胞集合对s Ag集合元素进行耐受训练。
6)如果系统没有满足结束条件且对Ag的检测未达到指定的代数,返回2)。
7)如果系统没有满足结束条件且对Ag的检测完毕(已检测了指定的代数),返回1)。
第二个层面是细胞的进化步骤:
1)随机产生未成熟细胞,其意义为未成熟细胞与成熟细胞的数量总和等于一个常量。
2)自体耐受。未成熟细胞与通过免疫细胞检测的自体抗原进行耐受训练,在耐受期中,删除识别自体的未成熟细胞。这样,通过耐受期的未成熟细胞成长为成熟免疫细胞,并参加免疫循环。
3)成熟免疫细胞检测抗原。如果一个成熟细胞在某个年龄闽值兄(生命周期)之前匹配了个非自体抗原,则它被成功激活,并进入激活待协同刺激集合。相反,在其生命周期中没有匹配那么多的非自体抗原,则死亡。
4)记忆免疫细胞检测抗原。如果一个记忆免疫细胞检测出一个非自体抗原,则进入激活待协同刺激集合。把在指定时间内获得肯定的协同刺激的激活细胞加入记忆免疫细胞集合,把获得否定协同刺激或指定时间内没有获得协同刺激的细胞删除。
(2)实现步骤
具体步骤分为如下三个阶段:
第一阶段:要求定义初始的自体集合,Self和未成熟检测器集合G,后者经前者耐受后成为成熟检测器(未成熟检测器的自体耐受)。我们把在一段时间内收集到的所有正常的本地主机行为模式和网络通信模式,映射为长度是L的二进制串集合,并把这个集合当作初始的自体集合Self(可自定初始自体集,非收集),它是长度为L的全体正常二进制串的一个子集。最先把随机产生一个长度为L的二进制串当作随机生成的未成熟检测器,接着它自动进入耐受期a。在耐受期内,如果它与自体集中任何一个自体发生匹配,即被消除并重新产生一个新的未成熟检测器,并再次进入耐受期循环上述过程。如果未成熟检测器耐受成功,就变为成熟检测器。
第二阶段:从a+1时刻到记忆检测器产生的时刻,为自学习阶段。成熟检测器通过克隆选择,生成能识别大量不同非自体抗原的记忆检测器。经过记忆检测器检测剩下的抗原,要送与成熟检测器进行再检测,如被分类为非自体则立即被删除,最后是把分类为自体的抗原送给未成熟检测器进行耐受。一个成熟的检测器进入检测期后,能与未知的抗原进行匹配,如果在这个检验过程中(成熟检测器允许存活的最大年龄内),它的累积匹配数达到了其激活阈值,就会被成功激活,最后这个成熟检测器也就变成了一个记忆检测器。
第三阶段:从记忆检测器产生到系统终止,免疫系统各部件产生完毕后,进行实际环境中的检测:首先是让每个记忆检测器与每个抗原进行匹配,根据匹配结果和该抗原与当前自体集的关系,对记忆检测器集合和抗原集合分别进行相应的处理;接着把成熟检测器集合和剩下的抗原集合的每个元素一一进行匹配,采用为奎续位匹配规则,并根据匹配结果、该抗原与当前自体集的关系和成熟检测器的年龄、计数器的大小等条件,对抗原集合和成熟检测器集合作对应的处理;最后未成熟检测器以剩余抗原为自体进行耐受,把耐受不成功的检测器从未成熟检测器集合中删除,把耐受成功的检测器加入到成熟检测器集合。
根据三个工作阶段各自所做工作的分析,我们知道系统在对各个集合的元素进行检测和处理的过程中,可以使其中的未成熟检测器集合、成熟检测器集合、记忆检测器集合和抗原集合保持自动动态更新,从而确保系统具有良好的适应性和自学习性。在记忆检测模块成熟检测模块中,当记忆和成熟检测器与一个抗原匹配成功后,马上检查该抗原是否属于当前Self集合,如果属于则进行协同刺激,交给外部系统判断该抗原是自体还是非自体,并根据判断结果作进一步处理:如果是自体,则删除这个能检测出当前自体的检测器,否则删除该抗原,且删除已经不是当前自体的自体元素;如果不属于则把它视为非自体。在系统运行过程中,外部系统可以向Self添加当前认为是合法的自体元素。由于系统具有很好的自适应性,新添加的自体元素可以自动促使系统产生对它耐受的检测器。当更新抗原后,如果新产生的检测器所对应的抗原在其生命期内没有出现,这个检测器就会趋于死亡,并逐渐被系统新产生的检测器所取代。如果这个抗原(能最后变成新自体)经常出现,系统则不会产生对它的不耐受的检测器。这个依靠频率的性质正是真实环境中所需要的。
5. 结论
本文对基于克隆选择的入侵检测算法进行了详细的阐述,主要对动态自体模型,抗原演化模型,动态耐受模型,成熟细胞生命周期模型,动态免疫记忆模型进行了数学描述,从而在理论上对模型进行了可行性论证。接着,为了实现建立的模型,满足理论上对模型的要求,详细设计了整体模块以及耐受、记忆细胞检测、成熟细胞检测模块,对整个算法进行了梳理,并对算法的设计步骤做了介绍。
参考文献
[1]倪建成,李志蜀,陈黎,叶军.基于免疫原理的多代理网格入侵检测系统体系结构研究[J].计算机应用研究,2009,(02):705-708.
[2]姜南春.人工免疫系统中动态克隆选择算法的研究与设计[J].南京理工大学.2006,16-18.
克隆选择算法 篇6
启发式随机搜索在解决单目标的优化计算中取得了优异的成果, 这种方法不依赖于问题的连续性和可导性, 可以解决非线性、多峰函数的寻优计算, 且计算的难度也要远远小于传统方法。然而, 在工程实际中, 往往很难仅凭借单项指标来衡量某项决策的好坏, 因此即需引入多项指标来更为全面地评价相应决策。但是若使用多个性能泛函来评价一个事物时, 多个性能指标往往相互制约、且相互矛盾, 也就是一方的收益多会导致另一方的利益受损。我国以崔逊学、郑金华为代表的多目标进化算法学者, 于2006年先后发表了相关理论研究成果, 算法的进化方式则是依靠交叉和变异的有性生殖。随着免疫学的进步, 脊椎动物的免疫机理正逐步引入到进化计算的思想中, 本文即借鉴免疫机理, 模仿脊椎动物的免疫应答过程来实现多性能泛函的寻优计算。
1 多目标优化算法
1.1 多目标优化问题描述
多目标优化问题 (MOP) 可用如下数学表达式描述:
给定决策向量X= (x1, x2, …, xn) ∈Ω, 且满足下列约束:
设有r个优化目标, 但这r个优化目标却相互矛盾, 一方的增益会导致另一方的利益受损, 则该优化目标可以表示为:
寻求X*= (x1*, x2*, …, xn*) 使得F (X*) 最优, 且满足式 (1) 的两个约束条件。
1.2 生物免疫
免疫是复杂生物的一种生理机能, 生物通过这种机能来保护自己不受外来物 (细菌、病毒、致敏源) 或本身有害细胞 (肿瘤细胞) 的侵袭。1920年之后, 免疫学的理论研究进入到了免疫化学的研究阶段, 在这之后生物免疫系统诞生了两个重要学说。其中, 一个是1960年Burnet和Medawar的克隆选择学说, 这一学说解释了当抗原进入生物体后, 生物体如何对其进行识别, 并产生免疫应答和免疫记忆的过程;另一个则是Jerne提出的免疫网络学说[1]。这两种学说清晰阐明了免疫过程作用机理, 具体如图1所示。
图1即为免疫应答过程的简化流程示意图。当抗原被识别后, 效应T细胞和浆细胞进行克隆, 产生抗体并杀死抗原, 同时抗原数量又能反作用于抗体, 并且限制抗体的数量[1]。而在免疫应答过程中, 将会产生免疫B细胞, 这样就能在抗原再次刺激时快速发起杀死抗原的效应, 这一过程则称为免疫记忆。该过程也为算法提供了借鉴意义, 即对于一个多目标问题, 每一代进化均应保留一定数量的精英个体。
1.3 多目标人工免疫
人工免疫系统 (Artificial Immune Systems, AIS) 是一种模仿生物体免疫系统的智能方法, 这一过程主要包括免疫应答和免疫记忆[2]。AIS的研究最初起始于上世纪80年代, 并伴随着人们对生物免疫系统的深入研究而获得了稳步发展。近年来, 越来越多的学者团体投身免疫计算的研究, 所取得的异体检测与识别、未知异体学习与记忆、异体消除和系统修复等理论成果均已应用到了智能网络、故障诊断以及智能机器人等一众领域, 并获得了很好的效果。然而, 针对多目标优化的免疫算法和单目标情况却有着较大的区别, 这也是多目标优化算法的发展滞后于单目标优化算法的原因之一。我国针对多目标免疫算法的研究起步于2005年, 直至2010年焦李成、尚荣华等人发表了我国第一部拥有实际理论研究成果的多目标免疫算法著作。其算法的核心思想是对传统免疫算法理念的一个挪用或参照。区别于单目标免疫优化算法, 多目标免疫优化算法模仿的免疫过程及相关概念如下分别列示如下:
定义1抗体。同一抗原的表面有多个抗原表位, 每一个表位就相当于一个性能泛函, 只有多个表位被识别并产生免疫应答时才会产生抗体。因此, 抗体在多目标算法中就是根据每个性能泛函所产生的Pareto最优解。
定义2克隆。克隆是生物的无性增殖过程, 在算法中克隆是对抗体基因片段的简单复制, 在基因长度确定的情况下, 不允许基因位的横向扩展复制。
定义3变异。基因突变公认为是生物种群的进化方式之一, 由于抗体的克隆增殖过程不存在基因交叉, 因此, 高频变异是算法进化的主要动力。
定义4抗体—抗原亲和力。抗原和抗体是一种非共价的结合, 不形成共价键, 因此需要四种分子间的引力 (静电引力、范德华力、氢键结合力、疏水作用力) 来使其结合。在多目标优化中, 不同的结合力度对应着不同的支配等级, 所有非支配集合中的个体均认为是具备最强的结合力。
定义5选择与修剪。抗体不仅能够识别抗原, 还能相互识别, 这就使得抗体不会永远增殖, 算法通过计算抗体的聚集度来选择聚集度小的抗体并修剪抗体规模以保持种群良好的分布性。
2 算法的Matlab实现
染色体或基因片段的表达通常以矩阵的方式来描述, Matlab对矩阵计算具有较大优势, 而且以矩阵方式表述染色体更是降低了代码的复杂度。除此之外, Matlab自带的Simulink可以将仿真和优化计算相结合, 为工程实际问题的高效解决提供了更加便捷的方式。因此, 本文采用Matlab来实现免疫克隆选择多目标优化算法的编程, 算法步骤为:
Step1:根据抗原产生初始抗体群的基因片段, 为与其他进化算法的表述一致, 将这一基因片段当作是一条染色体;
Step2:根据免疫记忆原理, 对初始的抗体群进行小规模的克隆 (本文所用复制比为5) ;
Step3:高频变异 (本文采用0.9) 是本算法中种群的进化动力, 各个抗体的每一基因位均采用按概率变异的方式;
Step4:构造non-dominated set, 通过逐一比较的方式, 可将抗体划分为支配个体和非支配个体, 再将受支配的个体从进化种群中删除;
Step5:计算拥挤距离, 并判断种群规模是否超过预设值。若种群规模过大, 则删除聚集度大的个体, 以保持种群良好的分布特性;
Step6:克隆优异抗体;
Step7:判断是否达到预设的进化代数, 是则输出Parto最优解, 并绘制解的分布图, 否则跳转Step3。
算法的流程图如图2所示。根据算法流程图可以得到算法的主函数程序, 其主要内容如算法1所示。
算法1
2.1 变异算子
由于在二进制编码中存在着“Hamming”悬崖, 故本算法采用实数编码方式, 且实数编码方式省却了二进制数到十进制数的转换计算, 如此即能有效降低算法的时间复杂度。针对实数编码的变异方式有多种, 而每种变异方式对算法的局部搜索能力和全局搜索能力都会发生一定的影响, 尤其是进化过程中不存在交叉算子的情况下, 影响将更加突出。本文选取了常用的高斯变异方式, 其实现代码如算法2所示。算法中, chrom为抗体的基因片段, pm为变异概率 (本文取0.9) , bound则指明了每一基因位个体的变异取值范围。
设xk为变异点, 其取值范围是[xkmin, xkmax], 那么新的基因x'k为:
算法2
2.2 non-dominated set构造
非支配集的构造采用逐一比较的方式, 非支配集的构造即需遵循如下的定义6。
定义6:设X和X*是多目标优化问题候选解集中的任意两个非等值个体, 假定X*是非支配的 (Pareto-占优) , 则需要满足如下条件:
(1) 对于所有的子目标, X*不比X差, 即fk (X*) ≤fk (X) , (k=1, 2, …, r)
(2) 至少存在一个子目标, 使得X*比X好, 即q∈{1, 2, …, r}至少有一个子目标使fq (X*)
其中, r为子目标的数量, 此时可用“”表示两者的关系, 即。
算法设计时, 对受支配的个体, 将其赋值为Inf, 然后查找出种群中目标值为Inf个体, 删除对应的解和抗体, 具体实现如算法3所示。其中给出了部分代码, 输入的objv为候选解集, selch为对应的抗体 (变异后) , 相应的输出则为非支配集及其对应的解。
算法3
2.3 选择与种群修剪
随着迭代次数的增加, 非支配集中抗体数量会不断增殖, 为了保持种群良好的分布性, 避免局部抗体过于密集, 就需要对种群进行修剪, 选择出聚集度小的个体, 将其作为优秀抗体, 送入到下一代的进化过程中。本文在算法设计时, 首先对目标值进行排序, 然后分别计算每个目标值的拥挤距离, 对于两端的个体, 将其值取为Inf, 即无条件保留边界个体进入下一代。稍后, 按照原有抗体对应的目标值顺序将目标值相加并排序, 最后, 即按照种群的预设规模, 删除聚集度高的个体。拥挤距离的计算如公式 (4) 所示。
式中, aj-1, i表示第j-1位个体在第i个目标值的拥挤距离, sortdata为目标值矩阵, 分母中加上0.1是为了避免分母在特殊情况下为0状况的发生。
3 算法测试
为了验证仅依靠高频变异作为进化动力的免疫克隆选择多目标优化算法在解决多目标优化问题上的有效性, 本文选取了一个普通二维目标函数、一个经典kur测试函数以及三维目标测试函数MOP5和MOP7, 测试函数如下所示:
(1) test1测试函数
(2) kur测试函数
(3) MOP5测试函数
(4) MOP7测试函数
函数的测试结果如图3所示。
图3中, (a) 和 (b) 分别为二维目标函数的测试结果, 计算时设置最大进化次数Maxgen=100, 抗体规模nonex=80, 优异抗体克隆比例为20。 (c) 和 (d) 则为三维目标函数的测试结果, 计算时设置最大进化次数Maxgen=100, 抗体规模nonex=100, 优异抗体克隆比例为20。由计算结果可知, 解集分布均匀, 经典测试函数与标准结果相比较, 解集分布范围广阔且分布区域正确。
4 结束语
本文介绍了一种用于多目标优化的免疫克隆选择算法, 该算法通过模仿生物的免疫应答过程来实现多个目标函数的寻优计算。算法中, 抗体群的进化仅依靠变异算子来实现, 对优异抗体进行大比例的克隆, 且按概率进行免疫记忆, 保留精英抗体。通过算法的测试, 与文献[3]中所提供分布图的比较结果表明, 本文在Matlab环境下设计的算法计算效率高、Pareto解集分布广泛且均匀。本文算法可应用于经济中的多目标决策、最优控制器设计、路径优化、工程中的多目标优计算等诸多领域, 为解决实际问题提供了有效、可靠的计算方法。
参考文献
[1]焦李成, 尚荣华, 马文萍, 等.多目标优化免疫算法、理论和应用[M].北京:科学出版社, 2010.
[2]雷德明, 严新平.多目标智能优化算法及其应用[M].北京:科学出版社, 2009.
[3]郑金华.多目标进化算法及其应用[M].北京:科学出版社, 2007.
[4]JIAO L C, GONG M G, SHANG R H, et al.Clonal selection with immune dominance and anergy based multi-objective optimization[C]//Proceedings of 3rdInternational Conference on Evolutionary Multi-criterion Optimization.Berlin:Springer, 2005:474-489.
[5]SCHAFFER J D.Multiple objective optimization with vector evaluated genetic algorithms[C]//Proceedings of 1stInternational Conference on Genetic Algorithms and Their Applications.Hillsdale:Lawrence Erlbaum Associates, Inc., 1985:93-100.
[6]DEB K, PRATAB A, AGARWAL S, et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation, 2002, 6 (2) :182-197.
[7]COELLO C A, CRUZ C N.An approach to solve multiobjective optimization problems based on an artificial immune system[C]//Proceedings of 1stInternational Conference on Artificial Immune Systems, Canterbury, 2002:212-221.
[8]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社, 2006.
克隆选择算法 篇7
云计算(Cloud Computing)是一种通过互联网实现随时随地和按需访问的共享资源池的计算模式,共享资源池主要包括计算设施、存储设备和应用程序等[1]。
云计算作为一种新的并行计算技术,是在分布式计算、并行计算和网格计算的基础上发展起来的,其目标是使得资源以服务的形式呈现在用户面前,用户可以根据其需求快速申请或释放资源,并采用按需付费的方式使用资源,以降低资源使用成本和提高资源使用效率[2,3]。
云计算的特点可以归纳为:弹性化的服务规划、共享资源池化、按需服务、服务计费和泛在接入,这些特点使得用户可以通过互联网使用各种终端设备随时随地地接入云计算享受服务[4]。
云计算资源调度可以定义为在云计算环境下,根据一定的资源使用规则,在不同的用户任务之间进行资源分配的过程[5]。
云计算服务可以分为三个子层:基础设施服务(IaaS, infrastructure as a service)、平台即服务(PaaS, platform as a service)、软件即服务(SaaS, software as a service)。由于虚拟化技术的引入,使得云计算环境下的资源调度具有与网格计算不同的特点,资源调度目前已经成为云计算研究的一个重要课题[6]。
目前对云计算环境下的资源调度的主要工作有: 文献[7]设计了一种基于粒子群算法的资源调度方法,通过引入多种群协作和变异粒子,从而避免局部最优和实现全局最优。文献[8]基于虚拟机迁移技术,提出了一种虚拟机集群资源调度策略,当系统负载过大时,对节点上的虚拟机进行迁移以实现虚拟机集群的负载平衡和节能。文献[9]提出了一种基于模糊聚类算法和粒子群优化算法的资源调度方法,首先采用改进的聚类算法根据节点负载进行聚类,然后再对负载过大的节点上的虚拟机进行迁移,从而实现负载平衡。
上述工作均研究了云计算资源调度问题,具有重要的意义,但也存在着如粒子群算法易于陷入局部最优,所以,本文提出了一种基于改进克隆选择算法的资源调度方法,并通过实验证明了文中方法的优越性。
1云计算资源调度模型
云计算环境下的资源调度的目标为最小化任务执行时间跨度和资源负载均衡度。
定义1 资源调度模型
采用三元组G={R,T,E}表示云计算环境下的资源调度模型,其中,R={r1,r2,...,rm}表示由m个异构处理节点组成的资源集,T={t1,t2,...,tn}表示n个独立用户任务组成的任务集,E={e11,e12,...,enm}表示资源分配集,eij为1时表示任务ti在处理节点rj上执行,eij为0时表示任务ti不在处理节点rj上执行时。
定义2 资源负载
资源负载lj(1≤j≤m)参数主要包含CPU利用率、内存利用率、网络带宽、IO访问率和进程总数,分别采用Cj、Mj、Nj、IOj和Pj表示,资源负载可以表示为:
lj=Cjw1+Mjw2+Njw3+IOjw4+Pjw5 (1)
在式(1)中,w1、w2、w3、w4和w5为资源各负载参数所占权值,并满足:
资源负载因子ρ可以表示为:
式(3)中, m为资源总数,n为任务总数,
定义3 执行时间跨度
任务时间跨度(makespan)来表示任务集T在资源集R上执行的时间, 采用Sch={t,r,ts,te}表示任务t在资源r上执行的开始执行时间ts和任务结束时间te,所以任务跨度makespan可以表示为:
在式(5)中,max{tei}表示所有任务的最晚结束时间,min(tsj)表示所有任务的最早开始执行时间。
2基于改进克隆选择调度的资源调度
2.1克隆选择算法概述
克隆选择算法(Immune Clone Selection Algorism, ICSA)由Jerne提出[10],其依据免疫学中的克隆选择原理,通过引入克隆选择、克隆增值、免疫记忆等机制,最终求得最优解。
克隆选择算法针对所需要解决的问题进行分析,将问题看作抗原,从抗体中挑选出适应度较高即与抗原的亲和度较高的个体,并对其进行变异,使得寻优的范围增大,以增抗体种群的多样性,避免陷入局部最优,最终获得全局最优解。
2.2抗体编码
抗体表示所求问题的候选解,抗体对应了任务的资源调度方案,将资源分配集E中矩阵元素为1的列号作为抗体基因,其可以描述为:
式(6)中,n为任务总数,pi表示分配给任务ti的资源号,所以,1≤pi≤m。
2.3抗体与抗原之间的亲和度
抗体与抗原之间的亲和度反应了抗体与抗原的匹配程度,即候选解的优劣,因此,抗体与抗原之间的亲和度越大,则候选解越优。
云计算环境下的最优解需要同时考虑时间跨度和资源负载均衡,所以亲和度函数可以描述为:
式(7)中,资源负载因子ρ和任务时间跨度makespan分别可以由式(3)和式(5)获得。
2.4抗体与抗体之间的亲和度
为了保持多样性,避免算法陷入局部最优,需要对相似抗体进行抑制,采用信息熵理论进行计算,假设规模为K的抗体种群为A={P1,P2,...,PK},则抗体Pi第j位的信息熵可以表示为:
在式(8)中,Pi(k)表示抗体Pi的第j位基因相同的概率,当所有基因均相同时有 Hj(K)=0,则N个抗体的平均信息熵可以表示如下:
任意两个抗体的亲和度可以通过公式(10)获得。
当对任意两抗体根据公式(10)得到的抗体的亲和度值时,值越大则抗体之间的相似度越大,算法越易于陷入局部最优,所以需要对相似抗体进行抑制。
3云计算资源调度算法描述
初始化:采用任务总数n初始化抗体长度,抗体种群规模K,资源总数为m,交叉概率pc,变异概率pm,初始温度T0,当前迭代次数t=1,最大迭代次数tmax。
步骤1:采用资源总数m对抗体进行编码,抗体每个基因为1～m之间的自然数,随机产生规模为K的初始种群A={P1,P2,...,PK};
步骤2:根据公式(7)计算抗体与抗原的亲和度,并将所有抗体按亲和度从大到小排序得到的抗体集A′={P1,P2,...,PK};
步骤3 : 对排序得到的抗体集A′={P1,P2,...,PK}中的抗体Pi进行免疫克隆,克隆的数目为qi可以表示为:
经过免疫克隆后,新的抗体集可以表示为:Bk={P1q1,P2q2,...,PKqK};
步骤4: 对经过免疫克隆的抗体集Bk={P1q1,P2q2,...,PKqK}进行退火交叉,对于任意两个抗体Pi和Pj,当交叉概率为pc时,随机产生一个0到1之间的随机数rc,当rc≤pc根据式(12)得到交叉后的新抗体Pi′和Pj′:
根据式(12)获得新抗体Pi′和Pj′的亲和度,如果Fit(P′)>Fit(P),则将个体P′加入到下一代个体中,否则,计算选择概率:
式(13)中, Tt为温度序列。
如果p>rc,则将该抗体仍然加入下一代种群中,如果小于则抛弃;
抗体经过退火选择后得到新的抗体集
Ck=={P1cq1,P2cq2,...,PKcqK}。
步骤5:对经过退火选择的抗体集Ck={P1cq1,P2cq2,...,PKcqK}中的抗体进行高斯变异,对每个抗体Pi按照变异概率pm根据下式进行变异,得到新的抗体集Dk。
在式(14)中,N(0,1)为服从标准正态分布的随机变量。
步骤6:根据式(10)计算任意两个抗体之间的相似度,对相似抗体进行抑制,删除其中与抗原亲和度较小的个体,直到抗体的规模为K,得到新抗体集E={P1,P2,...,PK}。
步骤7:判断当前迭代次数t是否达到最大值tmax,如果达到最大值,则算法结束,否则t=t+1,并按下式更新温度序列:
4仿真实验
采用云计算仿真工具CloudSim对上述基于克隆选择算法的云资源调度算法进行仿真,实验环境如下:设有40个计算资源构成云计算资源池,对30—300个独立任务组成的任务集进行调度,并与文献[7]和文献[8]进行比较。
文中算法的参数设置如下:抗体长度30—300,抗体种群规模K=100,资源总数为m=40,交叉概率pc=0.5,变异概率pm=0.6,初始温度T0=40,当前迭代次数t=1,最大迭代次数tmax=200。
对三种算法获得的资源调度方案所对应的任务执行时间跨度和资源均衡因子进行仿真,得到的结果如图1和图2所示。
从图1中可以看出,文中方法得到的执行时间跨度最小,随着任务数的增加平稳增加,其平均值为549 s,具有较强的稳定性,而文献[7]和文献[8]所示的方法任务执行时间跨度平均值分别656 s和854 s,远大于文中方法,且在仿真中随着任务数的增加出现一些波动。
从图2中可以看出,文中方法对应的资源负载均衡因子最低,始终位于文献[7]和文献[8]方法较低,这表明文中方法具有较好的负载均衡能力,而文献[7]和文献[8]方法的负载均衡因子较高,且波动较大,具有不稳定性。这是因为文中采用改进的克隆选择算法通过对相似个体进行抑制,对亲和度较大的个体进行保留从而提高了全局寻优能力,能实现资源的负载均衡。
5结语
为了实现云计算环境下的集群资源调度,提出了一种基于克隆选择算法的云集群资源调度方法。首先,定义了云环境下以最小化执行时间跨度和负载均衡因子的集群资源调度模型,然后设计了抗体的编码方式,抗体与抗原之间的亲和度函数、抗体之间的亲和度函数、克隆算子、退火交叉算子和高斯变异算子,并定义了基于克隆选择算法的云计算集群资源调度方法。仿真实验证明文中方法能实现云计算环境下的集群资源调度,且与其它方法相比,具有较小的任务时间跨度和较好的负载均衡能力。
参考文献
[1] Mell P,Grance T.The NIST definition of cloud computing.NationalInstitute of Standards and Technology,2011
[2]罗军舟,金嘉晖,宋爱波,等.云计算:体系架构与关键技术.通信学报,2011;32(7):3—21
[3]李乔,郑啸.云计算研究现状综述.计算机科学,2011;38(4):32—37
[4]李莉,廖剑伟,欧灵.云计算初探.计算机应用研究,2010;12(27):4419—4426
[5] Izakian H,Ladani B T,Zamanifar K,et al.A continuous doubleauction method for resource allocation in computational grids.Proc ofIEEE Symposium on Computational Intelligence in Scheduling.[S.l.]:IEEE Press,2009:295—299
[6] Mell P,Grance T.The NIST definition of cloud computing.NationalInstitute of Standards and Technology,2011
[7]刘万军,张孟,郭文越.基于MPSO算法的云计算资源调度策略.计算机工程,2011;37(11):43—48
[8]周文熠,陈华平,杨寿保,等.基于虚拟机迁移的虚拟机集群资源调度.华中科技大学学报(自然科学版),2011;39(1):130—133
[9]姚婧,何聚厚.基于模糊聚类分析的云计算负载平衡策略.计算机应用,2012;32(1):213—217
【克隆选择算法】推荐阅读：
免疫记忆克隆选择算法07-17
克隆选择原理05-28
克隆·克隆羊·克隆人07-01
序列克隆论文06-27
克隆我自己08-04
克隆绿色作文07-12
中继选择算法06-10
区域选择算法07-05
网络选择算法07-05
算法选择器08-26