抗独特型克隆选择算法_张立宁
ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.sodocs.net/doc/da6618075.html,
Journal of Software, Vol.20, No.5, May 2009, pp.1269?1281 https://www.sodocs.net/doc/da6618075.html, doi: 10.3724/SP.J.1001.2009.03266 Tel/Fax: +86-10-62562563
? by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
?
抗独特型克隆选择算法
张立宁1,2+, 公茂果1,2, 焦李成1,2, 马文萍1,2
1(西安电子科技大学智能信息处理研究所,陕西西安 710071)
2(西安电子科技大学智能感知与图像理解教育部重点实验室,陕西西安 710071)
Clonal Selection Algorithm Based on Anti-Idiotype
ZHANG Li-Ning1,2+, GONG Mao-Guo1,2, JIAO Li-Cheng1,2, MA Wen-Ping1,2
1(Institute of Intelligent Information Processing, Xidian University, Xi’an 710071, China)
2(Key Laboratory of Intelligent Perception and Image Understanding of the Ministry of Education, Xidian University, Xi’an 710071,
China)
+ Corresponding author: E-mail: liningzh@https://www.sodocs.net/doc/da6618075.html,
Zhang LN, Gong MG, Jiao LC, Ma WP. Clonal selection algorithm based on anti-idiotype. Journal of
Software, 2009,20(5):1269?1281. https://www.sodocs.net/doc/da6618075.html,/1000-9825/3266.htm
Abstract: Based on the antibody clonal selection theory of immunology, an artificial immune system algorithm,
clonal selection algorithm based on anti-idiotype (AICSA), is proposed to deal with complex multi-modal
optimization problems by introducing the anti-idiotype. This algorithm evolves and improves the antibody
population through clonal proliferation, anti-idiotype mutation, anti-idiotype recombination and clonal selection
operation, which can perform global search and local search in many directions rather than one direction around the
identical antibody simultaneously. Theoretical analysis proves that AICSA can converge to the global optimum. By
introducing the anti-idiotype, AICSA can make the most of the structure information of antibodies, accelerate the
convergence, and obtain the global optimization quickly. In experiments, AICSA is tested on four different types of
functions and compared with the clonal selection algorithm and other optimization methods. Theoretical analysis
and experimental results indicate that AICSA achieves a good performance, and is also an effective and robust
technique for optimization.
Key words: clonal selection; anti-idiotype; evolutionary algorithm; artificial immune system; numerical
optimization
摘要: 基于免疫学中的抗体克隆选择学说,通过引入抗独特型结构,提出了一种用于求解复杂多峰函数优化问
题人工免疫系统算法——抗独特型克隆选择算法.该算法通过克隆增殖操作、抗独特型变异操作、抗独特型重组操
? Supported by the National Natural Science Foundation of China under Grant No.60703107 (国家自然科学基金); the National
High-Tech Research and Development Plan of China under Grant No.2009AA12Z210 (国家高技术研究发展计划(863)); the National
Basic Research Program of China under Grant No.2006CB705700 (国家重点基础研究发展计划(973)); the Program for New Century
Excellent Talents in University under Grant No.NCET-08-0811 (新世纪优秀人才支持计划); the Program for Cheung Kong Scholars and
Innovative Research Team in University of China under Grant No.IRT0645 (长江学者和创新团队发展计划)
Received 2007-09-04; Accepted 2008-01-29
1270 Journal of Software软件学报 V ol.20, No.5, May 2009
作和克隆选择操作这4个操作算子来实现抗体种群的进化,能够同时在同一抗体周围的多个方向进行全局搜索和
局部搜索,具有较强的搜索能力.理论分析表明,抗独特型克隆选择算法具有全局收敛性.抗独特型结构的引入充分
利用了优势抗体的结构信息,加快了抗体种群的收敛速度,从而以更快的速度获得全局最优解,同时降低了算法陷入
局部极值点的几率.实验部分采用4组不同类型的函数对算法性能进行测试.理论分析及实验结果表明,与克隆选择
算法等已有算法相比,该算法性能好,求解精度高,鲁棒性强.
关键词: 克隆选择;抗独特型;进化算法;人工免疫系统;数值优化
中图法分类号: TP18文献标识码: A
从20世纪以来,优化问题吸引了越来越多不同背景研究人员的注意力,成为科学研究中的一个热点领域.
同时,真实世界中处理的问题变得越来越复杂,常规算法已经不能很好地解决这些复杂的研究问题,这时就需要
能够解决这些复杂问题的新算法.通常,非约束优化问题可以用以下D维最小化函数来表示:
Min f(x),x=[x1,x2,…,x D] (1) 其中,D表示优化参数的维数.上面的表达式给出了常规优化问题的统一数学模型.
人工免疫系统借鉴脊椎动物免疫系统的作用机理,特别是高级脊椎动物(主要是人)免疫系统的信息处理模
式,以免疫学术语和基本原理构造新的智能算法,为问题的求解提供了新颖的方法.人工免疫系统提供噪声忍
耐、无教师学习、自组织、记忆等进化学习机理,结合分类器、神经网络和机器推理等系统的一些优点,其研
究成果涉及到控制、数据处理、优化学习和故障诊断等许多领域,已成为继神经网络、模糊逻辑和进化计算后
人工智能的又一研究热点[1,2].在人工免疫系统中,克隆选择机理已经引起了研究者的兴趣,一些基于克隆选择
学说的算法[3?5]相继被提出来,但是这些研究大多集中在对生物免疫功能的简单模拟上,对于抗体细胞独特型
结构[6]并没有过多的考虑,因此,现有的人工免疫系统算法并没有完全模拟生物免疫系统的功能.
本文通过将抗独特型结构引入克隆选择算法,构造了一种人工免疫系统算法——抗独特型克隆选择算法
(clonal selection algorithm based on anti-idiotype,简称AICSA).具体来说,该算法通过抗独特型变异和重组算子
来模拟抗体的独特型结构,从而实现对生物免疫功能的模拟.仿真实验结果表明,相对于de Castro等人的克隆选
择算法及其他已有的优化算法,抗独特型克隆选择算法在处理复杂函数优化问题时具有更高的求解精度和更
强的鲁棒性.
本文第1节介绍有关人工免疫系统的一些基本知识.第2节详细描述抗独特型克隆选择算法,并对其收敛
性进行分析.第3节首先介绍测试函数的形式,并对抗独特型克隆选择算法的参数进行分析,同时给出对测试函
数的仿真实验和分析.最后一节是本文的结论和进一步的研究工作.
1 人工免疫系统
1.1 克隆选择学说
1958年,Burnet等人提出了克隆选择学说[7],其中心思想为:抗体是天然产物,以受体的形式存在于细胞表
面,抗原可与之选择性地反应.抗原与相应抗体受体的反应可导致细胞克隆性增殖.该群体具有相同的抗体特异
性,其中某些细胞克隆分化为抗体生成细胞,另一些形成免疫记忆细胞以参加以后的二次免疫反应.在此过程
中,主要借助克隆使其激活、分化和增殖,以增加抗体的数量,通过进行免疫应答最终清除抗原.因此,克隆选择是
生物免疫系统自适应抗原刺激的动态过程,在这一过程中所体现出的学习、记忆、抗体多样性等生物特性[5],
正是人工免疫系统所借鉴的.
1.2 克隆选择算法
根据Burnet的抗体克隆选择学说,de Castro以及Kim等人从不同的角度模拟上述生物学抗体克隆选择机
理,相继提出了不同的克隆选择算法[3?5].本文重点描述文献[3]的克隆选择算法,并给出de Castro提出的克隆选
择算法的流程.
张立宁等:抗独特型克隆选择算法1271
克隆选择算法(clonal selection algorithm).
Step 1. 生成初始种群(P),(P)由一组记忆单元(M)和保留种群(P r)构成,即(P=P r+M).
Step 2. 依据抗体-抗原亲和度,从中选择n个抗体细胞组成抗体种群(P n).
Step 3. 针对抗体种群(P n)执行克隆操作,得到临时种群(C),克隆规模与抗体-抗原亲和度成正比.
Step 4. 对克隆临时种群进行高频超变异,变异概率与亲和度成正比.变异操作之后获得的抗体种群为(C*).
Step 5. 从(C*)重新选择改进的个体组成记忆单元M,P中的一些个体也被(C*)其他一些改进个体替代.
Step 6. 利用新产生的抗体代替d个旧抗体,亲和度低的抗体更容易被替代.
上述de Castro的克隆选择算法正是对抗体克隆选择机理的简单模拟.它是最早的对生物免疫系统的简单模拟,也是最典型的人工免疫系统算法,后续的许多人工免疫系统算法都是在该算法基础上加以改进而得到的.
1.3 抗独特型结构
通过生物免疫学机理,我们了解到抗体是B细胞识别抗原后克隆增殖分化为浆细胞所产生的一种蛋白质分子,也称为免疫球蛋白分子.抗体结合由外界入侵的感染微组织或者有毒物等抗原,然后依靠自己或者借助免疫系统其他元素(T细胞、MHC分子等)帮助破坏这些抗原,消除对人体的威胁.抗体具有两种截然不同的功能区:一部分是保持相对静态的稳定区(constant),称为稳定区,简称C区;而另一部分则是负责与不同的多种感染抗原结合的分子变化区(variable),称为可变区,简称V区.可变区基本上只关心抗原结合.稳定区与宿主组织上的受体相互作用.C区变化有限,V区的变化使得免疫系统在自适应处理中具有一定的能力和速度.对免疫应答期间产生的抗体多样性的研究表明,V区的(细胞分子物质)体细胞(somatic)变异随时间增加,正是可变区为免疫系统提供了大部分鲁棒性和自适应能力.抗体的结构如图1所示.
Fig.1 Structure of the antibody
图1 抗体的结构
从图1可以看出,抗体部分是由抗体决定基和独特型(idiotype)组成.由生物免疫学机理可知,抗体与抗原之间的匹配程度越接近,分子结合强度越大,识别效果越好.抗体也能与其他抗体结合,因为它们既含有抗体决定基,也含有抗原决定基,即独特型抗原决定基(简称独特型).不同的特异性抗体又具有不同的独特型抗原决定基,它不仅能够激发不同物种或者同种异体产生相应的抗体,也能在自身体内刺激其他克隆的细胞产生抗独特型抗体[6].因此,抗体独特型在免疫系统中起着识别抗原、产生抗体、消灭抗原的作用,抗体独特型结构在生物免疫系统中的作用不容忽视.本文正是基于免疫学中的这一现象而设计出一种人工免疫系统算法.
2 抗独特型克隆选择算法
2.1 抗独特型克隆选择操作算子
本文根据Burnet的抗体克隆选择学说,并结合生物免疫学中抗体的独特型结构,提出了一种人工免疫算法——抗独特型克隆选择算法(简称AICSA).它模拟了生物免疫系统的作用机理,其状态转移图形式如下
:
1272 Journal of Software 软件学报 V ol.20, No.5, May 2009
(1) 克隆增殖算子C c T
在人工免疫系统中,克隆增殖算子按如下方式进行定义:
12(())[(()) (())...(())]C C C C T c c c c NP T A k T a k T a k T a k = (2)
其中,(())(),1,2,...,,C c i i i T a k I a k i NP =×=I i 为元素为1的q i 维行向量,称为a i 的q i 克隆.
q i (k )=g (N c ,f (a i (k ))) (3)
一般取
1(())()Int ,1,2,...,(())i
i c j j f a k q k N j NP f a k =?
?=×=????????
∑ (4)
N c >NP 是与克隆规模有关的设定值,Int(x )表示大于x 的最小整数.由此可见,对于单一抗体而言,其克隆规模
是根据抗体-抗原亲和度而自适应调整的.在本文后面的实验中,为简便起见,文章中选取固定的克隆规模,即
q i (k )为一个固定整数nc .克隆增殖过后,种群变为
12(){(),(),...,()}NP A k a k a k a k ′′′′= (5)
其中,
12(){(),(),...,()},()(),1,2,...,i i i inc ij i a k a k a k a k a k a k j nc ′=== (6)
(2) 抗独特型变异算子C
m T
在人工免疫系统中,B 细胞与抗原结合后会被激活,激活后即以极高的频率分裂,该过程为体细胞的高频变异,是克隆扩增期间重要的变异方式.根据抗体的独特型结构,抗体可变区为免疫系统提供了大部分的鲁棒性和自适应能力,当抗原决定基发现匹配时,它不仅可以激发个体产生相应的抗体,也能在自身体内刺激其他克隆的B 细胞产生抗独特型抗体,从而消灭抗原.de Castro 提出的CSA 中的变异算子通过超变异来实现[3],这种变异方
式通过在抗体空间中进行随机搜索来实现.显然,这种方式的效率是很低的.本文中的抗独特型变异操作结合了抗体自身独特型结构信息,有指导地进行变异.下面对抗独特型变异算子进行简单的介绍.
首先依据概率i m P 对克隆增殖后的群体进行抗独特型变异操作,()(())C m A k T A k ′′′=.具体地,针对任一抗体
a ij (k ),i =1,2,…,NP ,j =1,2,…,nc 按如下操作进行变异(其中,NP 表示抗体种群规模,nc 表示抗体克隆规模):
12()()(()())ij
ij r j r j a k a k v a k a k ′=+×? (7) 其中,i ,r 1,r 2∈{1,2,…,NP }为互不相等的整数.因此,必须满足NP ≥3的条件.v ∈[0,1]为功能系数,表示抗独特型结构在产生新抗体时的作用.图2给出了一个二维向量个体a ij (k )抗独特型变异操作的示意图.
图2采用二维函数等值线图来表示测试函数的函数值,×和ο表示了抗体在空间中的分布.抗体采用与原点连接的向量表示,3条实线向量表示变异前抗体,点划线表示变异生成抗体.显然,抗独特型变异操作通过利用抗体信息,采用差值获得抗体的独特型结构信息,从而指导抗体的变异.图2中采用×表示当代抗体,采用ο表示变异生成抗体.可以看出,抗独特型变异操作使变异生成的抗体更加靠近空间中的最优极值点.因此,抗体独特型结构信息的引入,为抗体的进化提供了有效的路径,从而实现了抗体种群的快速、有效变异.
(3) 抗独特型重组算子C x T
de Castro 等人的克隆选择算法仅仅通过抗体变异操作来实现抗体亲和度成熟.与此不同,本文的抗
Fig.2 Illustration of the anti-idiotype mutation operator
图2 抗独特型变异算子示意图
张立宁 等:抗独特型克隆选择算法
1273
独特型克隆选择算法引入了抗独特型重组算子C x T ,这一重组算子的引入可以增加抗体种群的多样性.抗独特
型重组操作作用在原始抗体a i (k )和抗独特型变异抗体()ij
a k ′之上.给定重组概率C R ,重组操作为()(())C x A k T A k ′′′′′=.通过抗独特型重组操作,新生成的抗体可以更好地遗传父代抗体的模式,从而保证了抗体优 势模式的保留.具体地,图3给出了一个8维向量抗独特型重组操作示意图.
图3表示抗体a i (k )与变异抗体()ij
a k ′抗独特型重组操作,其中Mask 表示一维0,1数组M (j ),且
0,if (
) or ()(), 1,2,...,1,if () and ()rand j CR j d i M j j D rand j CR j d i <=?==?>≠?
(8)
其中,D 表示测试问题的维数,rand ( j )表示[0,1]之间的随机数,CR 为重组概率,d (i )为[1,D ]之间的随机整数.
从图3中可以看出,本文提出的抗独特型重组操作与遗传操作中的一致交叉(uniform crossover)[8]从形式上
很相似.但是,本文的操作又有所不同:一致交叉作用在两个父代个体上,生成两个子代个体;而抗独特型重组操作作用在父代抗体和对应的变异个体上.因此,本文的抗独特型重组操作更加有利于保持抗体自身的优势模式,保证抗体种群的多样性.
(4) 克隆选择操作C s T
de Castro 提出的CSA 在进行选择操作时采用了(μ,λ)选择策略[9,10],即在生成的子代种群中选择与父代个体数目相同的个体组成下一代种群.本文中的抗独特型克隆选择算法采取了(μ+λ)选择策略[9,10],这是由于抗独特型克隆选择算法在变异和重组操作上与CSA 存在很大的差别,高频率的变异和重组容易导致优势模式的丢失.为使优势模式在子代抗体基因中得以保留,我们采用了(μ+λ)选择策略,以使优秀个体得以生存.具体来说,算法在生成的子代抗体种群和父代抗体种群中,根据适应度大小,选择与父代个体数目相同的个体组成下 一代抗体种群,可以表示为(1)(()())C s A k T A k A k ′′′+=+. 2.2 抗独特型克隆选择算法(AICSA )
在人工免疫系统算法中,抗体种群的进化都是通过各种各样的操作算子来实现的.通过上述对算法的描述我们可以看出,抗独特型克隆选择算法通过抗体克隆增殖操作、抗独特型变异操作、抗独特型重组操作和克隆选择操作这4个操作算子完成对种群的更新和进化.
针对AICSA 测试问题及问题的所有约束条件记作抗原F (*),初始抗体种群随机生成.在本文的算法中,我们采用了实数编码方式,抗体种群记作A ={a 1,a 2,…,a NP }.抗独特型克隆选择算法的流程如下:
抗独特型克隆选择算法(clonal selection algorithm based on anti -idiotype ).
Step 1. 初始化算法参数:抗体种群规模NP ,抗体克隆规模nc ,抗独特型变异概率MR ,抗独特型重组概率
CR ,功能系数v ;随机产生初始抗体种群A (0)={a 1(0),a 2(0),…,a NP (0)};设定亲和度成熟条件;设定当前迭代次数k =0.
Step 2. 若抗体种群A (k )满足亲和度成熟条件,则输出A (k )中抗体-抗原亲和度最高的抗体,算法停止;否则,
转Step 3.
Step 3. 对抗体种群A (k )执行克隆增殖操作:(())C c T A k ,获得抗体种群A ′(k ).
Step 4. 对抗体种群A ′(k )执行抗独特型变异操作:(())C
m
T A k ′,获得抗体种群A ″(k ). Step 5. 对抗体种群A ″(k )执行抗独特型重组操作:(())C x T A k ′′,获得抗体种群A ″(k ). Step 6. 计算抗体A ″(k )的亲和度:():{(())}A k A k Φ′′′′′′.
Step 7. 根据亲和度大小,针对抗体种群A ″(k )和抗体种群A (k )执行克隆选择操作:(()())C s T A k A k ′′′+,生成下
()ij
a k ′a i (k
)
()ij
a k ′′Fig.3 Illustration of the anti-idiotype
recombination operation 图3 抗独特型重组操作示意图
1274 Journal of Software 软件学报 V ol.20, No.5, May 2009
一代抗体种群A (k +1);k :=k +1,转Step 2.
2.3 算法的收敛性分析
定义1. 函数最小化问题的最优抗体集合为
****{:,()()}f f ??≠> A a a a a a (9)
对于抗体种群A ,令*()||?∩ A A A 表示抗体种群A 中包含最优抗体的个数. 定义2. 如果对于任意的初始状态A 0,均有
**00lim {()|(0)}lim {()|(0)}1k k p A k A A A p A k I A A →∞
→∞
∩≠?==∈== (10)
也就是说,
0lim {(())1|(0)}1k p k ?→∞
≥==A A A (11)
则称算法以概率1收敛到最优种群集.
定理1. 抗独特型克隆选择算法以概率1收敛.
证明:记0(){(())0}{()*}P k P k P k A ?===∩=?A A ,由贝叶斯条件概率公式[11]有
0(1){((1))0}{((1))0|(())0}{(())0} {((1))0|(())0}{(())0}
P k P k P k k P k P k k P k ???????+=+==+=≠×≠++==×=A A A A A A A (12)
由克隆选择的性质可知,克隆选择获得的最优解至少比克隆前要好,因此 {((1))0|(())0}0P k k ??+=≠=A A (13) 所以 00(1){((1))0|(())0}()P k P k k P k ??+=+==×A A (14)
又
min {((1))1|(())0}0P k k ??+==>A A (15)
记min min {((1))1|(())0},0,1,2,...k
P k k k ζ??=+===A A ,因此
{((1))1|(())0}0P k k ??ζ+==≥>A A (16)
所以
{}
{((1))0|(())0}1((1))0|(())01{((1))1|(())0}
1{((1))1|(())0}11
P A k A k P A k A k P A k A k P A k A k ????????ζ+===?+≠==?+≥=≤?+==≤?< (17)
因此
2100000(1)(1)()(1)(1)...(1)(0)k P k P k P k P ζζζ+≤+≤?×≤?×?≤≤?× (18)
因为
1lim(1)0k k ζ+→∞
?=,1≥P 0(0)≥0 (19)
所以
1000lim ()lim(1)(0)0k k k p k P ζ+→∞
→∞
≤≤?= (20)
故 0lim ()0k p k →∞
= (21)
因此
00lim {()*|(0)}1lim ()1k k P k A P k →∞
→∞
∩≠?==?=A A A (22)
即0lim {(())1|(0)}1k p k ?→∞
≥==A A A .
于是可以证明抗独特型克隆选择算法是以概率1收敛的.
□
张立宁 等:抗独特型克隆选择算法 1275
3 实验分析
为了评价本文提出的抗独特型克隆选择算法(AICSA)在对函数优化时的求解性能,将该算法与克隆选择算法(CSA)[3]和微分进化算法(DEA)[12]以及广泛学习粒子群算法(CLPSO)[13]进行了对比. 3.1 实验测试函数
在实验部分,本文首先采用了文献[13]中所使用的16个不同类型的问题对算法性能进行测试.这16个测试问题按其性质分为4组,分别为单峰测试函数、多峰测试函数、旋转多峰测试函数及复合函数.
表1~表4给出了4组测试函数的具体表达形式.有关函数的构造方式和函数的特性参见文献[13].为了更好地测试AICSA 解决复杂函数的特性,本文还针对近期Liang 等人提出来的几种其他形式的复合函数[14]进行了测试.实验中,我们取维数D =10(记作10-D )进行测试,表4中的两个测试函数正是其中的CF1和CF5.
复合函数是Liang,Suganthan 和Deb 等人于2005年提出的一组新的复杂多峰测试函数[14].由于进化算法在求解已有的基准测试函数,如Sphere,Weierstrass 和Rastrigin’s 等函数时,往往通过利用这些基准函数已知的特性来设计与之具有针对性的操作算子,例如,已有的基准函数的局部极值点多沿着平行的坐标轴,而全局最优点中很多维的坐标值都相同,或最优点位于空间中原点位置等等,这些特点往往会被学者用来设计算法,因此已有的基准函数就往往不能很好地检验算法在未知空间的寻优能力,而现实世界问题往往是未知结构的问题.正是基于以上原因,Liang 等人通过对一组已有的基准测试函数进行平移、旋转、组合等操作构造了一组复合测试函数.这些复合函数形状复杂,局部极值点极多,而且位置不固定,最优值点位置随机分布于空间中,常规算法都难以很好地解决这类复杂问题.基于以上考虑,本文采用了这组测试函数来检验AICSA 解决复杂多峰函数优化问题的能力.有关函数的构造方法、表达形式及具体特性均可从https://www.sodocs.net/doc/da6618075.html,.sg/home/EPNSugan/处获得.
Table 1 Unimodal and simple multimodal functions
表1 单峰测试函数及简单多峰测试函数
Groups
f Test functions Optimization
f 1
211
()D
i i f x x ==∑
0 Group A
f 2
1222211
()(100()(1))
D i i i i f x x x x ?+==?+?∑0
Table 2 Unrotated multimodal functions
表2 未旋转多峰测试函数
1276 Journal of Software软件学报 V ol.20, No.5, May 2009
Table 3 Rotated multimodal functions
表3旋转多峰测试函数
Table 4 Composition functions
表4复合测试函数
Groups f Test functions Optimization
f15CF1 0
Group D
f16CF5 0
3.2 实验对比算法
针对本文提出的抗独特型克隆选择算法,我们通过与以下几种算法进行对比来验证算法的有效性:
(1) 克隆选择算法(CSA)[3].de Castro的CSA是基于克隆选择机理最早的人工免疫系统算法,也是最经典
的人工免疫系统算法;
(2) 微分进化算法(DEA)[12].DEA是一种有效的解决全局优化问题的启发式算法,近些年引起了广泛的
关注;
(3) 广泛学习粒子群算法(CLPSO)[13].CLPSO是一种新提出来的粒子群算法,文献[13]将其与其他几种经
典的粒子群算法进行了对比,并且取得了良好的效果.因此,本文将AICSA与CLPSO进行了比较,
CLPSO的结果引自文献[13].
3.3 仿真实验结果
3.3.1 参数敏感性分析
本节我们选择两个有代表性的复杂复合多峰函数f15和f16来分析参数对抗独特型克隆选择算法所产生的影响.为使经过克隆增殖后生成的抗体均能利用抗体独特型结构信息,算法设置抗独特型变异概率MR=1.为获得最优参数设置,本节针对抗独特型克隆选择算法参数NP,nc,CR和v进行了敏感性分析,分析策略如下:
(1) 抗体种群规模NP与克隆规模nc的敏感性分析
对参数NP在区间[5,50]以步长5采样,参数nc在区间[2,20]以步长2采样,于是获得了10×10=100组参数.实验停止条件为|f best|<ε,针对每组参数进行30次独立实验,然后计算该参数设置条件下函数值平均计算次数.图4给出了实验结果,算法的其他参数设置为CR=0.8,v=0.8,最大函数值计算次数设定为50 000次.
如图4所示,两个函数的函数值计算次数随NP和nc变化趋势相似.当NP和nc较小或NP和nc都很大时,函数f15,f16计算次数已达到50 000的最大限制条件,而算法却陷入了局部极值点,未能收敛到指定精度.而抗体种群规模的增加可以增加抗体密度,抗体克隆规模的增加可以扩大搜索空间.从图4可以看出,当NP和nc合适时,可以在较少的计算次数条件下获得指定精度.通过对参数的实验数据分析我们认识到,当NP取值为25~35
张立宁 等:抗独特型克隆选择算法
1277
和nc 取值为3~6时,算法在获得同样计算精度的情况下所需的计算次数较小.因此,实验中设置NP =30,nc =5.
(a) f 15 (b) f 16
Fig.4 AICSA sensitivity in relation to NP and nc
图4 AICSA 对NP 和nc 的敏感性
(2) 抗体重组概率CR 和功能系数v 的敏感性分析
与上面的测试方法相同,参数CR 在[0.1,1]以步长0.1采样,参数v 在[0.1,1]以步长0.1采样,于是同样获得了
10×10=100组参数.实验停止条件为|f best |<ε,其余参数设置NP =30,nc =5,最大计算次数设定为50 000次,图5给出的是针对每组参数30次随机实验的统计平均结果.
(a) f 15 (b) f 16
Fig.5 AICSA sensitivity in relation to CR and v
图5 AICSA 对CR 和v 的敏感性分析
与参数NP 和nc 分析相似,从图5的结果可以看出,重组概率CR 和功能系数v 对于算法的性能也有很大影响,当CR 和v 取值较小时,算法陷入了局部极值点,在规定计算次数内不能收敛到指定的精度.当CR 和v 同时增大时,算法的性能获得了改善.同样,CR 和v 也存在最优的参数设置,这时,算法可以在获得同样精度的结果条件下,函数值计算次数最小.通过对参数的实验数据分析我们认为,CR 取值在0.7~0.9,v 取值在0.7~0.9时,算法可以在较小代价条件下获得同等结果.下面的实验中,我们取CR =0.8和v =0.8.
3.3.2 实验结果与分析
通过上面对算法参数的实验分析,我们获得了最佳参数模型,即NP =30,nc =5,CR =0.8及v =0.8.在下面的实验中,我们按照上面获得的参数设置对测试函数进行实验仿真.实验分为3个部分:首先针对16个测试函数的10-D 问题进行实验仿真,同时对比了4种算法的30次实验的均值、方差;接下来针对16个测试问题的30-D 实验函数进行仿真,同时给出对于结果的分析;实验最后部分给出了算法针对6个10-D 复杂复合函数的测试结果.
(1) 10-D 测试问题实验结果.实验中针对10-D 测试问题,设定停止条件为最大函数值计算次数达到30 000次.表5给出了4种算法针对4组测试问题的30次随机独立实验的结果.4种算法中最优的结果加粗显示.
E v a l u a t i o n s
E v a l u a t i o n s
20
E v a l u a t i o n s
E v a l u a t i o n s
1278 Journal of Software软件学报 V ol.20, No.5, May 2009
Table 5 Statistical results for 10-D functions
表5 10-D测试函数统计结果
CSA DEA CLPSO AICSA Groups
Mean Std Mean Std Mean Std Mean Std
f1 3.54e+000 1.53e+000 9.55e?013 1.32e?012 5.15e?29 2.16e?028 1.50e?024 2.67e?024 A
f2 1.69e+000 0.63e+000 1.02e?0028.60e?003 2.46e+000 1.70e+000 4.86e+000 1.64e+000
f3 1.83e+000 0.36e+000 4.80e?007 3.58e?007 4.32e?014 2.55e?014 3.33e?013 3.68e?013
f40.91e+000 0.10e+000 4.30e?0017.19e?002 4.56e?003 4.81e?003 2.72e?002 3.90e?002
f5 1.17e+000 0.13e+000 7.31e?004 2.87e?0040000 B
f6 1.92e+000 0.55e+000 2.20e+001 4.60e+0000000
f7 1.90e+000 0.61e+000 1.37e+001 2.08e+0000000
f87.66e+000 3.82e+000 1.28e?002 4.45e?0020000
f9 2.45e+000 0.36e+000 5.98e?007 3.66e?007 3.56e?005 1.57e?004 4.85e?013 5.35e?013
f100.90e+000 0.11e+000 5.37e?0019.71e?002 4.50e?002 3.08e?002 1.93e?001 1.22e?001
f11 2.71e+000 0.57e+000 1.10e?002 4.50e?003 3.72e?010 4.40e?010 3.09e?013 1.05e?013 C
f12 1.61e+001 3.66e+001 3.62e+001 5.49e+001 5.97e+000 2.88e+000 1.41e+001 6.43e+000
f13 1.05e+001 2.99e+000 2.10e+001 4.24e+001 5.44e+000 1.39e+00011.0e+001 4.53e+000
f14 4.81e+002 1.43e+002 9.00e+002 4.47e+002 1.14e+002 1.28e+002 5.52e+002 2.44e+002
f15 6.05e+000 3.51e+000 1.73e?012 2.55e?012 1.64e+001 3.63e+0017.63e?021 1.22e?020 D
f16 3.20e+000 9.64e+000 1.20e+001 2.99e+001 1.98e+001 2.93e+001 2.26e+000 1.39e+000从上面的测试结果可以看出,针对Group A中的单峰测试函数,AICSA并不是4种算法中最优的测试结果.
这是由于AICSA引入了抗独特型变异算子,使得算法扩大了解的搜索空间,但同时也导致了算法针对简单单峰
测试函数在相同计算次数条件下并没有取得最好的结果.针对其余3组多峰测试函数,AICSA则在函数f9,f11,
f15,f16上取得了最佳结果.针对函数f9算法所得解的平均值为4.85e?013,与其他3种算法相比,无论从解的精度
函数稳定性上都有很大的提升.同样,针对函数f15,算法解的平均值为7.63e?021,而性能一直很好的CLPSO为1.64e+001,因此,AICSA在解决更加复杂的函数时,比CLPSO具有更好的特性.同样,在解决函数f5~f8等时,AICSA和CLPSO取得了同样最优的结果.而CLPSO算法在解决函数f3,f4,f10,f12~f14上面取得了最优的结果,
但与AICSA相比,它们在解的精度和稳定性上很相近,可以认为它们的结果是统计相同的.由上面的分析可以
看出,CLPSO在解决更加复杂的函数时却容易陷入局部最优值,函数f15恰好说明了这一点.因此,AICSA在解决
低维多峰函数、旋转多峰函数和复杂函数等问题时,与CSA,DEA和CLPSO相比均表现出了良好的性能,尤其
是针对复杂函数,AICSA更是可以获得高质量的解,同时表现出了更强的鲁棒性.
(2) 30-D测试问题实验结果.实验中针对30-D测试问题,设定停止条件为最大函数值计算次数达到200 000次.表6给出了4种算法针对4组测试问题的30次随机统计独立实验结果.4种算法中最优的结果加粗显示.
Table 6 Statistical results for 30-D functions
表6 30-D测试问题统计结果
CSA DEA CLPSO AICSA Groups
Mean Std Mean Std Mean Std Mean Std
f1 3.71e+000 0.72e+000 1.46e?009 2.40e?009 1.16e?113 2.92e?113 5.90e?035 3.23e?034 A
f2 4.97e+000 1.91e+000 1.21e+0010.93e?001 2.10e+001 2.98e+000 2.32e+001 2.01e+000
f3 1.04e+000 0.12e+000 1.16e?005 5.71e?00600 4.44e?015 4.44e?015
f4 1.03e+000 0.01e+000 1.10e?003 3.40e?003 3.14e?010 4.64e?01000
f5 2.36e+000 0.15e+000 1.12e?002 3.80e?0037.82e?0158.50e?01500 B
f6 2.08e+000 0.41e+000 1.03e+002 2.44e+0010000
f7 2.29e+000 0.54e+000 8.88e+001 2.98e+001 4.36e?010 2.44e?01000
f8 1.11e+000 2.34e+000 5.13e+003 1.25e+003 1.27e?0128.79e?01300
f9 2.21e+000 0.22e+000 1.54e?0059.49e?006 3.43e?004 1.91e?004 4.44e?015 1.25e?015
f10 1.03e+000 0.01e+000 1.30e?003 4.10e?0037.04e?010 1.25e?011 1.24e?009 1.58e?009
f11 1.26e+001 1.31e+000 1.54e?001 6.05e?002 3.07e+000 1.61e+000 3.81e+000 2.06e+000 C
f12 6.68e+001 1.17e+001 2.17e+002 1.13e+001 3.46e+001 4.59e+000 4.44e+001 1.20e+001
f13 4.00e+001 7.45e+000 1.93e+002 1.51e+001 3.77e+001 5.56e+000 3.72e+001 1.06e+001
f14 2.38e+003 3.96e+002 7.66e+003 2.99e+002 1.70e+003 1.86e+002 2.73e+003 6.09e+002
f150.69e?001 0.19e?001 3.80e?010 6.03e?0107.50e?005 1.85e?004 1.29e?0309.78e?031 D
f16 5.34e+001 0.66e?001 8.76e+001 5.70e+0007.86e+000 3.64e+000 3.86e+000 1.07e+000
张立宁等:抗独特型克隆选择算法1279
表6给出了AICSA针对16个测试函数的30-D问题的测试结果.与10-D的测试结果相似,算法针对函数f4,f5,f7~f9,f15的结果无论在解的精度还是稳定性上与其他几种算法相比都有了很大提高,而针对函数f4,f5,f7和f8在同样的计算代价下,30次随机实验均获得了函数的最优结果0,体现出了算法极强的寻优能力.同样与上面10-D的结果相似,针对函数f9,算法获得了4.44e?015的最优结果.与其他几种算法相比,从解的精度提升了10个数量级不等.同样,针对更加复杂的复合函数f15,与其他几种算法相比,AICSA同样在解的精度和稳定性上取得了质的提升.但是我们依然可以看出,并不是对于所有的函数AICSA均具有最好的特性,针对函数f1,f3和f10,CLPSO取得了最好的结果,并且精度和稳定性都要优于AICSA.对于函数f6,f12~f14和f16,AICSA和CLPSO解的精度和稳定性相近,函数f2,f11最优结果分别为CSA和DEA取得.
从上面两组的结果可以看出,虽然AICSA并不是在所有问题上都有最优的结果,但总体而言,对于多峰复杂函数,AICSA表现出了良好的性能,一方面能够找到高质量的解,另一方面方差小、算法性能稳定,具有很强的鲁棒性.
(3) 复合函数测试结果
为了进一步验证算法解决复杂多峰函数的有效性,本文针对其余几个多峰复合函数进行了测试.由文献[14]可知,CF1~CF6为10-D测试函数,最优值均为0.表7给出了7种算法的实验测试结果,其中最优的结果加粗显示.表中AICSA的结果是100次随机实验的平均,其余几种算法的结果均是20次随机独立实验的平均.在本次实验中,我们增大了抗体种群规模,参数设置为NP=40,nc=5,CR=0.8,v=0.8,实验停止条件为函数值最大计算次数为50 000.对比算法的实验结果取自文献[14].
Table 7Comparison results achieved by seven algorithms on six composition functions
表76个复合函数的7种算法对比结果
CF1 CF2 CF3
Mean Std Mean Std Mean Std
PSO 1.00e+002 8.17e+001 1.56e+002 1.31e+002 1.7203e+002 3.2869e+001
CPSO 1.56e+002 1.34e+002 2.42e+002 1.49e+002 3.6264e+002 1.9631e+002
CLPSO 5.73e?008 1.04e?007 1.92e+001 1.48e+001 1.33e+002 2.00e+001
CMA-ES 1.00e+002 1.89e+002 1.62e+002 1.51e+002 2.14e+002 7.41e+001
G3-PCX 6.00e+001 6.99e+0019.27e+0019.91e+001 3.20e+002 1.25e+002
DEA 6.75e?002 1.11e?001 2.88e+0018.63e+000 1.44e+002 1.94e+001
AICSA 3.12e?019 4.11e?019 5.21e+000 6.29e+000 1.32e+002 4.48e+001
CF4 CF5 CF6
Mean Std Mean Std Mean Std
PSO 3.14e+002 2.01e+0018.34e+001 1.01e+0028.61e+002 1.26e+002
CPSO 5.22e+002 1.22e+002 2.56e+002 1.76e+0028.53e+002 1.28e+002
CLPSO 3.22e+002 2.75e+001 5.37e+000 2.61e+000 5.01e+002 7.78e?001
CMA-ES 6.16e+002 6.71e+002 3.59e+002 1.68e+0029.00e+002 8.32e?002
G3-PCX 4.93e+002 1.42e+002 2.60e+001 4.16e+0017.72e+002 1.89e+002
DEA 3.25e+002 1.48e+001 1.08e+001 2.60e+000 4.91e+002 3.95e+001
AICSA 2.85e+002 4.01e+0010.16e?0010.54e?001 5.11e+002 7.67e+001 为了更清楚地描述AICSA的结果,图6给出了6个函数100次实验所得解的分布图,其中横坐标为函数值,纵坐标为实验次数.
从表7及图6的结果可以看出,AICSA在解决复合函数时,与其他几种算法相比表现出了良好的性能,尤其是针对CF1,AICSA在100次随机独立实验中均获得了10?018数量级的解.同时,针对函数CF5,AICSA在100次随机独立实验中有90次解,均为函数的全局最优解,而只有10次算法求解结果大于1,表现出了算法很好的求解特性.同时,针对函数CF2~CF4,几种算法都未获得函数的最优解,这是由于函数结构非常复杂,表7中所列7种算法在多次运行中均未能寻找到最优解区域,同时也体现出了复合函数空间结构的复杂和对进化算法性能测试的效果.但是,AICSA获得的结果依然是7种算法中最优的结果.当然,AICSA对于CF6的求解结果与其余几种算法相似,均陷入了局部最优值,未能取得很好的效果.但是,上述实验结果同样表明了AICSA很好的求解特性和良好的鲁棒性.
需要说明的是,在前面的实验中,Group D中的CF1和CF5由于算法参数和评价次数设置不同,测试结果也
1280 Journal of Software 软件学报 V ol.20, No.5, May 2009
有所不同.在本次实验中,我们增大了抗体种群规模和最大函数值的计算次数,这样同样会导致两个方面的作用:一方面,增大抗体规模会增加每一代种群函数值的评价次数,从而导致算法在同样评价次数条件下算法未能收敛到最优结果;但另一方面,这样会增加抗体种群的密度,减少陷入局部极值区域的几率.因此,CF1的结果质量相对于上面略有降低,而CF5的结果则相对于上面有所提高.
总而言之,通过以上分析可知,AICSA 算法是一种受参数影响很大的人工免疫系统算法,通过设置合适的实验参数,AICSA 在解决复杂函数优化问题时可以获得高质量的解,同时,算法的性能较为稳定,鲁棒性较强.
(a) CF1
(b) CF2
(c) CF3
(d) CF4
(e) CF5
(f) CF6
Fig.6 Distribution of the results of the six composition functions
图6 6个复合函数解的分布情况
4 结论与展望
基于免疫学中的抗体克隆选择学说,通过引入抗独特型结构,本文提出了一种用于解决复杂多峰函数优化问题的人工免疫系统算法——抗独特型克隆选择算法.AICSA 通过克隆增殖操作,使得算法可以在同一父代抗体周围的多个方向进行全局和局部搜索.
抗独特型变异算子的引入充分利用了抗体结构信息,指导了算法有效变异,加快了收敛速度;抗独特型重组算子则使得优势抗体模式信息得以保留,降低了抗体进化后期的早熟现象;克隆选择操作则使生成的优势种群得以保留,保证了算法以概率1收敛于最优解.
理论分析和实验结果表明,与de Castro 等人的CSA,Storn 等人的DEA 及Liang 等人提出的CLPSO 相比,该算法从求解的精度和稳定性上都显示出了良好的特性.尤其是针对复杂的复合函数,与其他算法相比,该算法更是从精度上有了更加明显的提升,体现了AICSA 在解决复杂函数优化问题时的优势.而针对6个复合函数的求解结果则更显示了AICSA 很好的寻优特性和良好的鲁棒性.
本文的结果表明,抗独特型克隆选择算法在数值优化问题上取得了很好的效果,说明该算法是非常有潜力的.因此,下一步我们将用该算法解决其他优化问题,如多目标优化、组合优化等. References :
[1] Dasgupta D, Forrest S. Artificial immune systems in industrial applications. In: Meech JA, Veiga MM, Smith MH, LeClair SR, eds.
Proc. of the 2nd Int’l Conf. on Intelligent Processing and Manufacturing of Materials. Piscataway: IEEE Press, 1999. 257?267.
0 1 2 3 ×10?18
Function values
T e s t t i m e s
0 1 2 3 ×10?18
1612840
20Function values
T e s t t i m e s
1086420
12Function values
T e s t t i m e s
8642
10Function values
T e s t t i m e s
Function values
T e s t t i m e s
400 600 800 1000
Function values
T e s t t i m e s
张立宁等:抗独特型克隆选择算法1281
[2] Jiao LC, Du HF. Development and prospect of the artificial immune system. Acta Electronica Sinica, 2003,31(10):1540?1548 (in
Chinese with English abstract).
[3] de Castro LN, von Zuben FJ. The clonal selection algorithm with engineering applications. In: Langdon WB, Cantu-Paz E, Mathias
KE, Roy R, Davis D, eds. Proc. of the 2002 GECCO, Workshop on Artificial Immune Systems and Their Applications. San Francisco: Morgan Kaufmann Publishers, 2000. 36?37.
[4] Kim J, Bentley PJ. Towards an artificial immune system for network intrusion detection: An investigation of clonal selection with
a negative selection operator. In: Kim JH, Zhang BT, Fogel G, Kuscu I, eds. Proc. of the 2001 Congress on Evolutionary
Computation. Piscataway: IEEE Press, 2001. 1244?1252.
[5] Jiao LC, Du HF, Liu F, Gong MG. Immunological Computation for Optimization, Learning and Recognition. Beijing: Science
Press, 2006 (in Chinese).
[6] Mo HW. The Principles and Applications of Artificial Immune System. Harbin: Harbin Institute of Technology Press, 2003 (in
Chinese).
[7] Gong MG, Du HF, Jiao LC. Optimal approximation of linear systems by artificial immune response. Science in China (Series F—
Information Sciences), 2006,49(1):63?79.
[8] Chen GL, Wang XF, Zhuang ZQ, Wang DS. Genetic Algorithm and its Applications. Beijing: Posts & Telecom Press, 1996 (in
Chinese).
[9] Yao X, Liu Y, Lin GM. Evolutionary programming made faster. IEEE Trans. on Evolutionary Computation, 1999,3(2):82?102.
[10] Beyer HG, Schwefel HP. Evolution strategies—A comprehensive introduction. Natural Computing, 2002,1(2):3?52.
[11] Sheng Q, Xie SQ, Pan CY.Probability Theory and Mathematical Statistics. 2nd ed., Beijing: Higher Education Press, 2003 (in
Chinese).
[12] Storn R, Price K. Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces. Journal
of Global Optimization, 1997,11(4):341?359.
[13] Liang JJ, Qin AK, Suganthan PN, Baskar S. Comprehensive learning particle swarm optimizer for global optimization of
multimodal functions. IEEE Trans. on Evolutionary Computation, 2006,10(2):281?295.
[14] Liang JJ, Suganthan PN, Deb K. Novel composition test functions for numerical global optimization. In: Arabshahi P, Martinoli A,
eds. Proc. of the 2005 Swarm Intelligence Symp. Piscataway: IEEE Press, 2005. 68?75.
附中文参考文献:
[2] 焦李成,杜海峰.人工免疫系统进展与展望.电子学报,2003,31(10):1540?1548.
[5] 焦李成,杜海峰,刘芳,公茂果.免疫优化计算、学习与识别.北京:科学出版社,2006.
[6] 莫宏伟.人工免疫系统原理及应用.哈尔滨:哈尔滨工业大学出版社,2003.
[8] 陈国良,王煦法,庄镇泉,王东生.遗传算法及其应用.北京:人民邮电出版社,1996.
[11] 盛骤,谢式千,潘承毅.概率论与数理统计.第2版,北京:高等教育出版社,2003.
张立宁(1981－),男,河北晋州人,硕士生,主要研究领域为自然计算,人工免疫系统,数据挖掘.
焦李成(1959－),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为自然计算,数据挖掘,图像处理,智能信息处理
.
公茂果(1979－),男,博士,副教授,主要研
究领域为人工免疫系统,进化计算,数据挖
掘,多目标优化.
马文萍(1981－),女,博士,讲师,主要研究
领域为进化计算,图像处理.
免疫算法的克隆选择过程
免疫算法的克隆选择过程 % 二维人工免疫优化算法 % m--抗体规模 % n--每个抗体二进制字符串长度 % mn--从抗体集合里选择n个具有较高亲和度的最佳个体进行克隆操作 % A--抗体集合(m×n),抗体的个数为m,每个抗体用n个二进制编码(代表参数) % T--临时存放克隆群体的集合,克隆规模是抗原亲和度度量的单调递增函数% FM--每代最大适应度值集合 % FMN--每代平均适应度值集合 % AAS--每个克隆的最终下标位置 % BBS--每代最优克隆的下标位置 % Fit--每代适应度值集合 % tnum--迭代代数 % xymin--自变量下限 % xymax--自变量上限 % pMutate--高频变异概率 % cfactor--克隆(复制)因子 % Affinity--亲和度值大小顺序 %% clear all clc tic; m=65; n=22; mn=60; xmin=0; xmax=8; tnum=100; pMutate=0.2; cfactor=0.1; A=InitializeFun(m,n); %生成抗体集合A,抗体数目为m,每个抗体基因长度为n F='X+10*sin(X.*5)+9*cos(X.*4)'; %目标函数 FM=[]; %存放各代最优值的集合 FMN=[]; %存放各代平均值的集合 t=0; %% while t 常用分子克隆实验方法I 一、植物总DNA的小量提取 方法1：提取吸附法。无须巯基乙醇、氯仿等有毒物质，产物无须Rnase处理。 (1)充分研磨。称取约0.2克植物组织，加入液氮充分研磨3-5min，稍后加约1ml溶液 A，继续研磨至略粘稠的组织匀浆，用大口1ml吸头将所有溶液移至1.5ml离心管 中，55℃水浴30min； (2) 高速离心去杂质。10,000rpm离心5min，取约600ul上清至新1.5ml离心管； (3) 核酸吸附。往上清液中加入1倍的异丙醇，轻轻混匀，再加入总体积1/4已混匀的 溶液B，静置3min; (4) 低速离心沉淀。5000rpm离心1min，轻轻倒掉上清，并用吸水纸轻吸离心管口， 再用移液枪吸走大部分残余液体； (5) 75%乙醇清洗。加入1ml75%乙醇，5000rpm离心30s，轻轻倒掉上清，用吸水纸稍 吸离心管口。重复该步骤一次，再5000rpm离心30s，然后用移液枪吸走管底的残 液，晾干5min； (6) 核酸洗脱。加入约55ul TE（PH8.0）至管底，轻轻重悬硅土，静置3min，10,000rpm 离心1min，用小枪头轻轻吸取出50ul管底溶液，冷藏。 方法2：CTAB法，此为在经典方法基础上，经过摸索改进，提高了得率，减少了污染。 (1)充分研磨。称取约0.2克植物组织，加入液氮充分研磨3-5min，稍后加约1ml CTAB 提取液，继续研磨至略粘稠的组织匀浆，用大口1ml吸头移至1.5ml离心管，65℃ 水浴30-60min。 (2) 氯仿抽提。10,000rpm离心3min，取约600ul上清。加入1倍的氯仿，轻轻混匀， 10,000rpm离心3min，取上清再抽提1遍。 (3) 核酸沉淀。加入预冷的1倍异丙醇或2倍乙醇，轻混匀，6000rpm离心3min，弃 上清。 (4) 清洗沉淀。轻加入1ml 75%乙醇，再吸掉上清，重复一次，倒置于吸水纸或横放于 离心管架上晾干5min。 (5) 溶解DNA。加50ul含Rnase A（约10ug/ml）的TE，常温下放置30min。取约3-5ul 电泳检测后，低温冷藏。 对基于克隆选择和小种群粒子群算法的混杂算法的实证研究 Pinaki Mitra, 学生会员, IEEE, Ganesh K. Venayagamoorthy, 资深会员, IEEE 摘要—本文提出了一种混合算法，基于对克隆选择算法（CSA）和小种群中的粒子群优化（SPPSO）于对克隆选择算法（CSA）和引入小种群粒子群算法，本文 CS P SO）是观察四家已知的基准函数。提出了一种混合算法。演出这种新算法（22 该SPPSO是一个传统PSO的变种（CPSO），是由本文的第二作者提出，初始粒子选择极小数目，经过几次迭代，最好是保留，而且其余颗粒取而代之的是相同的再生粒子数。另一方面，克隆选择算法属于人工免疫系统（AIS）家庭。它是一种进化算法，其中，在进化过程中的抗体能够识别通过克隆增殖的抗原。通过两种算法的混杂，CPSO优化能力得到大幅提升。用较少的内存需求和CSA的概念提高寻优能力和减少收敛到局部最小的可能性使SPPSO概念有助于找到最优解，试CS P SO表现比CPSO和SPPSO在求解Rosenbrock's，Rastrigin's 验结果表明：22 和Griewank's函数时表现更好。 1.引言 粒子群优化（PSO）已被证明有解决单一和多目标的忧化问题巨大潜力 [1]。这是一个简单，灵活和平衡算法为了进行局部和全局搜索过程。在这里，一组的粒子，称为群，在多维空间移动搜索，以找出全局最优解。随着粒子数的大群增加，到一个全局最优解越来越得到更多的保障。原因是越大的搜索空间的探索需要更高的粒子数。但是，正如粒子数的增加，为了运算内存要求也增加了，随着该算法在现实世界实时数字信号处理器或微控制器等应用这常常是不允许的，同样地，如果在首次的几个迭代，一粒子动作非常接近局部极小和没有一个是接近全全局最优解，那儿有一个可能，整个群是被误导收敛到本地极小。 投稿日期2008年6月15日。这项工作是支持的一部分美国国家科学基金会，美国国家科学基金会就业资助下＃ECCS的0348221。 Pinaki Mitra是实时的电源与智能系统实验室，欧洲经委会系，美国密苏里大学和科学技术，罗拉，莫65401，美国（电话：609-384-1302，电子邮件：pm33d@https://www.sodocs.net/doc/da6618075.html,）。 Ganesh K. Venayagamoorthy与实时功率和智能系统实验室，欧洲经委会系，美国密苏里大学和科学技术，罗拉，莫65401，美国（电子邮件：gkumar@https://www.sodocs.net/doc/da6618075.html,）。 这种情况经常发生在有大量局部极小值的功能函数。为了摆脱这两个问题，SPPSO算法提出了在[2]和[3]。该SPPSO概念是开始几次迭代后用少量的粒子数更换所有的粒子除了全球最佳相同数的再生粒子。在这种方法以来，PSO算法的运 分子克隆技术 一、填空题 1.PCR反应中加入矿物油的作用是___________________________。 2.分子克隆实验中外源DNA和载体片段连接之前，要对载体进行去磷酸化处理，我 们在本次试验中去磷酸化使用的碱性磷酸酶是___________________________。它 的目的是___________________________。 3.用α互补筛选转化子是，带有外源片段的菌落显___________________________色。 4.Southern杂交中进行与杂交的目的是___________________________。 5.凝胶糖凝胶电泳时加入loading buffer作用是___________________________和 ___________________________。 6.影响琼脂糖凝胶电泳的因素主要有___________________________、 ___________________________、___________________________、 ___________________________、___________________________。 二、简答题 1.简述PCR反应体系中都有哪些成分及各成分的作用。 2.为得到质量较好的水稻RNA，抽提前应做如何准备？RNA抽提过程中、RNA的 保存及以后对RNA的操作过程中应特别注意什么？ 3.简述为防止放射性同位素外照射及内照射对人体造成伤害，在操作放射性同位素 时，我们可以采取哪些措施进行防护？ 4.简述影响电转化感受态细胞转化效率的因素有哪些？ 5.质粒抽提时用到的SolutionI，SolutionII，SolutionIII及异丙醇分别起什么作用？操 作时应注意什么？ 三、分析问答题 1.描述并图示pUC19载体DNA及其在HindIII位点克隆了外源DNA片段的质粒DNA 和水稻总DNA及它们的HindIII和BamH1酶切产物在琼脂糖凝胶电泳时的带型。 2.利用质粒载体克隆外源DNA片段主要包括哪些步骤？涉及到哪些工具酶？要获得 理想的结果，各步骤操作中应主要注意哪些事项？ 3.在Southern杂交实验中，同一根杂交管内的膜曝光的····（原卷此处不清晰）冲 洗后，有些组X光片信号很强，有些组信号很弱，有的样品点样孔附近有较强的 信号，但是有的地方信号较弱，请分析造成这种结果的可能原因。 4.下面是本次课生物技术班某组β-active基因RT-PCR（反转录前没有对总RNA进 行去除DNA 的处理）试验的琼脂糖凝胶电泳图，凝胶上共点了6个样，PCR使用 的模板从左至右分别是：该组提取的水稻总DNA，该组提取的水稻总RNA，该组 的4个反转录产物。（原卷本题图不清晰） 请问： 提取的RNA的质量如何？ RT-PCR是否成功？为什么会出现这样的结果？ 有哪些地方需要改进？ ISSN 1000-9825, CODEN RUXUEW E-mail: jos@https://www.sodocs.net/doc/da6618075.html, Journal of Software, Vol.20, No.5, May 2009, pp.1269?1281 https://www.sodocs.net/doc/da6618075.html, doi: 10.3724/SP.J.1001.2009.03266 Tel/Fax: +86-10-62562563 ? by Institute of Software, the Chinese Academy of Sciences. All rights reserved. ? 抗独特型克隆选择算法 张立宁1,2+, 公茂果1,2, 焦李成1,2, 马文萍1,2 1(西安电子科技大学智能信息处理研究所,陕西西安 710071) 2(西安电子科技大学智能感知与图像理解教育部重点实验室,陕西西安 710071) Clonal Selection Algorithm Based on Anti-Idiotype ZHANG Li-Ning1,2+, GONG Mao-Guo1,2, JIAO Li-Cheng1,2, MA Wen-Ping1,2 1(Institute of Intelligent Information Processing, Xidian University, Xi’an 710071, China) 2(Key Laboratory of Intelligent Perception and Image Understanding of the Ministry of Education, Xidian University, Xi’an 710071, China) + Corresponding author: E-mail: liningzh@https://www.sodocs.net/doc/da6618075.html, Zhang LN, Gong MG, Jiao LC, Ma WP. Clonal selection algorithm based on anti-idiotype. Journal of Software, 2009,20(5):1269?1281. https://www.sodocs.net/doc/da6618075.html,/1000-9825/3266.htm Abstract: Based on the antibody clonal selection theory of immunology, an artificial immune system algorithm, clonal selection algorithm based on anti-idiotype (AICSA), is proposed to deal with complex multi-modal optimization problems by introducing the anti-idiotype. This algorithm evolves and improves the antibody population through clonal proliferation, anti-idiotype mutation, anti-idiotype recombination and clonal selection operation, which can perform global search and local search in many directions rather than one direction around the identical antibody simultaneously. Theoretical analysis proves that AICSA can converge to the global optimum. By introducing the anti-idiotype, AICSA can make the most of the structure information of antibodies, accelerate the convergence, and obtain the global optimization quickly. In experiments, AICSA is tested on four different types of functions and compared with the clonal selection algorithm and other optimization methods. Theoretical analysis and experimental results indicate that AICSA achieves a good performance, and is also an effective and robust technique for optimization. Key words: clonal selection; anti-idiotype; evolutionary algorithm; artificial immune system; numerical optimization 摘要: 基于免疫学中的抗体克隆选择学说,通过引入抗独特型结构,提出了一种用于求解复杂多峰函数优化问 题人工免疫系统算法——抗独特型克隆选择算法.该算法通过克隆增殖操作、抗独特型变异操作、抗独特型重组操 ? Supported by the National Natural Science Foundation of China under Grant No.60703107 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2009AA12Z210 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant No.2006CB705700 (国家重点基础研究发展计划(973)); the Program for New Century Excellent Talents in University under Grant No.NCET-08-0811 (新世纪优秀人才支持计划); the Program for Cheung Kong Scholars and Innovative Research Team in University of China under Grant No.IRT0645 (长江学者和创新团队发展计划) Received 2007-09-04; Accepted 2008-01-29 Computer Engineering and Applications 计算机工程与应用 2018，54（21）1引言基于免疫机制的进化算法因其对复杂问题具有强大的处理能力，已被广泛地应用于智能优化、数据挖掘、模式识别、机器学习、故障诊断、入侵检测等[1-2]诸多领域，deCastro 和Von Zubon 等人在2000年提出了克隆选择算法（Clonal Selection Algorithm ，CSA ）[3]，它应用于检测器的训练过程，但是其易陷入局部最优，收敛速度慢等缺点也显露无疑。为了解决传统克隆选择算法的不足，更好地兼顾进化过程中全局和局部的搜索，胡江强等在克隆选择过程中采用分级变异的方式[4]，该算法根据抗体的亲和度合理地将整个种群分为3个不同的子种群，在每个子种群 中分配不同的搜索任务，并使用不同的变异策略，还在进化过程中实时地改变种群的规模大小、克隆的规模大小和变异参数。为了能够自适应地调整变异的尺度，陶新民等提出了一种定向多尺度变异克隆选择算法[5]，该算法采用多尺度高斯变异的机制，在算法的开始阶段利用较大尺度的变异，伴随着适应度值的不断提升，小尺度的变异会随之减低，使得算法在后期阶段能够有效使 用小尺度的变异实现局部的精确搜索。Hong 和Liao 提出了自适应动态克隆选择算法[6]，根据亲和度大小自适应调整克隆规模，根据抗体浓度选择变异尺度的大小。自适应混合变异克隆选择算法研究 巫东凯，张凤斌，席亮 WU Dongkai,ZHANG Fengbin,XI Liang 哈尔滨理工大学计算机科学与技术学院，哈尔滨150080 School of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China WU Dongkai,ZHANG Fengbin,XI Liang.Research on clonal selection algorithm of adaptive hybrid https://www.sodocs.net/doc/da6618075.html,puter Engineering and Applications,2018,54（21）：78-83. Abstract ：Clonal selection algorithm is the core of the detectors ’evolution in immune invasion theory.In traditional im-mune clonal selection algorithm,it is difficult to take into account the global and local search with a single mutation,which leads to the disadvantage of easy to fall into local optimization or slow convergence.By introducing cultural algorithm,this paper realizes the evolution of population space and belief space.This paper proposes clonal selection algorithm of adaptive hybrid mutation,which combines the strong global search ability of cauchy mutation with the strong local search ability of chaos mutation in the mutation.And it utilizes the knowledge of belief space to adaptively determine the time and the proportion of the two kinds of mutations.The algorithm is tested in KDDCUP99data set.The result shows that the algorithm has good convergence and robustness. Key words ：immune intrusion detection;cultural algorithm;cauchy mutation;chaos mutation;clonal selection 摘要：克隆选择算法是免疫入侵理论中检测器进化的核心。传统免疫克隆选择算法中通过单一的变异很难同时兼顾全局和局部搜索，从而导致容易陷入局部最优或者收敛速度慢等弊端，通过引入文化算法，实现种群空间和信仰空间双层进化，在变异时将全局搜索能力强的柯西变异和局部搜索能力强的混沌变异相结合，提出了自适应混合变异克隆选择算法，利用信仰空间的知识来自适应地确定两种变异的作用时间和作用比例，通过KDDCUP99数据集进行测试，结果显示该算法有较好的收敛性和鲁棒性。 关键词：免疫入侵检测；文化算法；柯西变异；混沌变异；克隆选择 文献标志码：A 中图分类号：TP393.08doi ：10.3778/j.issn.1002-8331.1707-0499 基金项目：国家自然科学基金（No.61172168）；黑龙江省教育厅科学技术研究项目（No.12541130）。 作者简介：巫东凯（1992―），男，硕士研究生，研究领域为网络与信息安全，E-mail ：122041275@https://www.sodocs.net/doc/da6618075.html, ；张凤斌（1965―），男，博士， 教授，研究领域为网络与信息安全；席亮（1983―），男，博士，副教授，研究领域为网络与信息安全。 收稿日期：2017-08-01修回日期：2017-09-20文章编号：1002-8331（2018）21-0078-06 CNKI 网络出版：2018-03-01,http∶//https://www.sodocs.net/doc/da6618075.html,/kcms/detail/11.2127.TP.20180301.1539.012.html 78万方数据 量子克隆进化算法 刘 芳,李阳阳 (西安电子科技大学计算机学院,陕西西安710071) 摘 要: 本文在量子进化算法的基础上结合基于克隆选择学说的克隆算子,提出了改进的进化算法———量子克 隆进化策略算法(QCES ).它既借鉴了量子进化算法的高效并行性又利用克隆算子来代替其中的变异和选择操作,以增加种群的多样性,避免了早熟,且收敛速度快.本文不仅从理论上证明了该算法的收敛,而且通过仿真实验表明了此算法的优越性. 关键词: 克隆算子;进化算法;量子克隆进化策略中图分类号: T N957 文献标识码: A 文章编号: 037222112(2003)12A 22066205 Quantum Clonal Evolutionary Algorithms LI U Fang ,LI Y ang 2yang (Institute o f Computer ,Xidian University ,Xi ’an ,Shaanxi 710071,China ) Abstract : Based on the combining of the quantum ev olutionary alg orithms (QE A )with the main mechanisms of clone ,an im 2proved ev olutionary alg orithm —quantum clonal ev olutionary strategies (QCES )was proposed in this paper.By adopting the high 2effec 2tive parallelism of QE A and replacing clone operator by mutation and selection of the classical ev olutionary alg orithms (CE A ),it has better diversity and the converging speed than CE A and av oided prematurity.The convergence of the QCES is proved and its superiori 2ty is shown by experiments in this paper. K ey words : clone operator ;ev olutionary alg orithm ;quantum clonal ev olutionary strategies 1 引言 计算是人类思维能力的最重要的方面之一,计算能力的提高与人类文明进步息息相关.从古老的算盘到现代的超级计算机,人类的计算技术实现了革命性的突破.综观当今,计算机的广泛应用已经并且仍在继续改变着我们的世界.一方面,人们为计算机的神奇能力所倾倒.另一方面,人们也为它无力完全满足实际的需要而烦恼.因此,加速计算机的运算速度以提高计算机的运算能力成为计算机科学的中心任务之一. 如何加快计算机的运算能力呢?这一问题大体可以从两个方面着手解决.一是制造更为先进的计算机硬件,另一则是设计恰当的计算机运算流程,后者可以称之为“算法”.一类模拟生物进化过程与机制来求解问题的自组织、自适应人工智能技术即进化计算(包括用于机器学习问题的遗传算法,优化模型系统的进化规划和用于数值优化问题的进化策略)的出现为我们寻找快速算法提供了新思路.进化计算是一种仿生计算,依照达尔文的自然选择和孟德尔的遗传变异理论,生物的进化是通过繁殖、变异、竞争、选择来实现的,进化算法就是建立在上述生物模型基础上的随机搜索技术.我们所熟悉的 遗传算法(G enetic alg orithms )[1],它通过模拟达尔文的“优胜劣汰,适者生存”的原理鼓励好的个体,通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体,同时寻找更好的个体,由此来模仿一切生命与智能的产生与进化过程.理论上已经证明:进化算法能从概率的意义上以随机的方式寻求到问题的最优解;但在实际应用当中随着问题的复杂和海量的数据量,也出现了一些不尽人意的情况,主要表现在:计算后期解的多样性差即易造成早熟,收敛速度慢等缺点.因此,为克服上述缺点关键是构造性能良好的进化算法. 在改进的进化算法中,有些是将传统寻优算法与遗传算法相结合提出了混合遗传算法[2,3],有些则另辟蹊径提出了新颖的学习算法———量子进化算法[4]和免疫进化算法[5],量子力学是20世纪物理学最惊心动魄的发现之一,量子计算是物理理论与计算机的成功结合,在量子体系中,一位的信息位不在是经典的1比特,而是由两个本征态的任意叠加态所构成即称之为量子比特位(qubit ),例如一个n 位二进制的串在量子体系中就可同时表示2n 个信息,而量子计算机对每个叠加分量(本征态)实现的变换相当于一种经典计算,所有这些经典计算同时完成,并按一定的概率振幅叠加起来,给出量子计算的结果,这种计算称之为量子并行计算[6].正是量子的 收稿日期:2003209210;修回日期:2003212210 基金项目:国家自然科学基金(N o.60133010);国家高技术研究发展计划(863计划)(N o.2002AA135080) 第12A 期2003年12月 电 子 学 报 ACT A E LECTRONICA SINICA V ol.31 N o.12A Dec. 2003 —22— 量子密钥分发误码协调算法分析 赵 峰，王发强，郑力明，路轶群，刘颂豪 (华南师范大学信息光电子科技学院光子信息技术广东省高校重点实验室，广州 510006) 摘 要：误码消除是量子密钥分发过程的关键技术之一。分析了奇偶-汉明单向函数纠错算法的原理，给出了对原始量子密钥进行误码协调的步骤及表达式，对这种算法的纠错能力进行了理论和实验分析。结果显示，当原始密钥误码率为11%时，利用该纠错技术能够完全消除误码，且最终密钥生成效率与密钥的原始误码率直接相关。 关键词：误码协调；奇偶比较；汉明码；量子密钥分发 Error Reconciliation Algorithm for Quantum Key Distribution ZHAO Feng, WANG Faqiang, ZHENG Liming, LU Yiqun, LIU Songhao (Lab of Photonic Information Technology, School of Information and Optoelectronic Science and Engineering, South China Normal University, Guangzhou 510006) 【Abstract 】Error reconciliation is a necessary step for quantum key distribution process. The efficiency and the correction ability of error reconciliation procedures are analyzed and estimated, and it gives some expressions about it. The experiment results indicate that it can easily eliminate all errors when the error rate is at 11%. 【Key words 】Error reconciliation; Parity comparison; Hamming codes; Quantum key distribution 计 算 机 工 程Computer Engineering 第33卷 第12期 Vol.33 No.12 2007年6月 June 2007 ·博士论文· 文章编号：1000—3428(2007)12—0022—03 文献标识码：A 中图分类号：TP391 量子密钥分发使得合法通信双方Alice 和Bob 在异地可 以随时建立起秘密的随机序列，通常称为密钥，其安全性由海森堡的不确定性原理和量子不可克隆定理保证。然而，由于实际量子信道存在不可避免的噪声，以及非法窃听者干扰，使得合法双方生成的密钥中存在一定的误码。因此，当密钥分发完成后，若其误码率在一定范围内，则通信双方通常利 用保密纠错技术来消除误码[1~4]。 量子密钥分发过程一般需要4个步骤：量子传输，数据筛选，保密数据纠错和信息保密增强。经典通信中的误码消除技术常常会伴随通信信息的泄漏。实际量子保密通信误码消除过程需要极少的泄漏密钥的信息，并且泄漏的信息可以通过保密增强技术来消除[5,6]。 数据纠错技术是通信系统中不可缺少的部分，在量子保密通信中通常利用奇偶比较方法来构造各种纠错协议[7,8]，通常双方按照协议将生成的密钥分成段，并计算其奇偶性，然后在经典信道中进行奇偶比较。为了消除窃听者获得的信息，在每次比较结束双方丢掉一位。利用奇偶比较完全消除误码，需要多次在经典信道上进行通信。由于通信的次数会随着密钥长度增加而增加，通常n 位的序列需要2log n 次通信[7]，并且，为了安全起见每次通信前需要身份认证[9] ，这样完全消除密钥误码过程需要的时间随着密钥增加而增加。 二元汉明码的纠错能力为1=t ，利用汉明码的校验矩阵h 来构造校验码，Alice 和Bob 双方通过比较校验码来验证共享密钥的完整性，在文献[10]中用于量子密钥分发误码协 调[10]。本文对奇偶-汉明纠错算法在量子密钥分发过程中的应用进行分析。 1 奇偶-汉明纠错算法 奇偶-汉明纠错算法利用了奇偶比较来检误，比较汉明校验码进行纠错。由于二元汉明码的纠错能力为1，当某段的误码多于一个时利用汉明算法可能会引入误码。因此，汉明算法仅仅当密钥误码率很低，每段含一个误码以上可能很小时是很有效的。Alice, Bob 首先利用奇偶比较方法对误码进行一次比较，若奇偶性一致，则表示该段中没有误码或含有偶数个误码；若奇偶不一致，则表示含有奇数个误码，当误码率较低而且服从二相分布，则存在一个误码的概率远远大于奇数多个。然后利用汉明纠错方法对奇偶性不一致的进行纠错。通常为了减少泄漏的信息，在奇偶比较结束时丢掉最后一位。而利用汉明纠错算法则需丢掉m 位，其位置为{}{}2(0,...,1)i i m ∈?。 二元汉明校验矩阵()(3)m h m ≥，表述为 ) 2](mod 2[1 )(,?=i m j i j h (1) 例如当3≡m 时，其矩阵表示为 ? ?????????=000111101100111010101)3(h (2) 利用校验矩阵构造校验码{}1,...,i S S i m ==，，则i S 为 {}m j m j i j i m h X S 1,0)2(mod 121)(,∈??? ?????=∑?= (3) 其中，1 1,...,2m j X j ?=（）为合法通信双方（Alice,Bob ）含有误码的一段密钥序列。双方进行纠错过程中在经典信道上发送 {}i S S =，而不发送j X 本身。 利用奇偶-汉明纠错算法过程如下：Alice 和Bob 选择相 基金项目：国家“973”计划基金资助项目(G2001039302) 作者简介：赵 峰(1979－)，男，博士生，主研方向：量子信息技术；王发强、郑力明，副教授；路轶群，研究员；刘颂豪，院士 收稿日期：2006-08-10 E-mail ：qkd@https://www.sodocs.net/doc/da6618075.html, 人工免疫系统是基于生物免疫系统特性而发展的新兴智能系统。利用免疫系统的克隆选择机制，提出一种用于函数优化的改进免疫算法。其主要特点是采用克隆和自适应变异等操作，提高收敛速度和种群的多样性。仿真程序表明，该算法能以较快速度完成给定范围的搜索和全局优化任务。 在工程实际中，很多问题都可转化为函数优化问题，而对于高维、非凸、且有多个局部极值点的函数优化问题，传统的基于梯度的算法通常不能求得理想解。免疫系统作为一种分布式自学习系统，能自适应地维持群体多样性及具有自我调节功能，导致基于免疫机制的算法具有整体、局部搜索能力强的特点，使得这类算法在函数优化、组合优化、模式识别、数据挖掘及机器学习等方面得到了有效应用。 1 免疫算法原理 免疫算法的灵感来自生物获得性免疫的克隆选择原理。根据该原理，在生物免疫系统中，一旦病原体侵入肌体就被分解为抗原片段，B淋巴细胞能够为产生相应的抗体与抗原结合，同时活化、增殖和分化，产生浆细胞，通过中和、溶解和调理等作用，最终使抗原从体内清除。另有一些B细胞变成了长期存活的记忆细胞，它通过血液、淋巴和组织液循环，为下一次快速、高效的消除相同或者类似抗原引起的感染奠定了基础。 免疫算法采用高变异克隆的单性繁殖搜索方式，避免了遗传算法中的交叉操作引起的模式干扰，同时具有未被激发的细胞消亡及记忆细胞的产生等过程又保证了抗体的多样性。 2 算法描述 克隆选择算法模拟生物免疫系统的克隆选择原理，一般将待优化的目标函数及其约束条件视为抗原，其算法步骤如下： (1)初始化：随机产生N个二进制编码的抗体对应问题的可能解。 (2)评价和选择1：将N个抗体分解成由m和r个抗体组成的两部分Am，Ar，分别表示进入记忆集的抗体和剩下的部分，其中进入记忆集的都是亲和度较高的抗体。 (3)克隆：在亲和度最高的抗体中选择k个进行克隆，克隆的数量与其亲和度成正比。 (4)变异：模拟生物克隆选择中的超变异过程，对克隆后的抗体执行变异操作，变异按某一变异概率以一定规模随机进行。 (5)评价和选择2：重新计算变异后的抗体的亲和度，若克隆变异后的抗体中亲和度最高的抗体比父代抗体的亲和度还要高，就用该抗体替换原抗体，形成薪的记忆集。 (6)消亡：模拟生物克隆选择中5％的B细胞自然消亡的过程，在Ar中选择d个亲和度最低的抗体重新初始化，以保证抗体的多样性。 分子克隆实验标准步骤 一、 常规分子克隆实验流程： 二、 分子克隆实验标准步骤（含实验编号）： 1. PCR 扩增目的基因（编号Clone SOP-1） 以本实验室常用酶KOD-Plus-Neo （TOYOBO ）为例 体系（50ul ）： 10×KOD buf 5ul dNTP(2mM) 5ul Mg 2+ 3ul Primer1 1ul Primer2 1ul Template50-200ng KOD0.5ul ddH 2O up to 50ul 程序： 95℃2min 98℃10s 58℃30s 35cycle 68℃2kb/min 68℃7min 12℃∞ 2.PCR产物的琼脂糖凝胶电泳琼脂糖凝胶的制备（编号Clone SOP-2） 琼脂糖溶液的制备：称取琼脂糖，置于三角瓶中，按1%-1.5%的浓度加入相应体积的TBE或TAE缓液，将该三角瓶置于微波炉加热至琼脂糖溶解。 胶板的制备：①取有机玻璃内槽，洗净、晾干；②将有机玻璃内槽置于一水平位置模具上，安好挡板，放好梳子。在距离底板上放置梳子，以便加入琼脂糖后可以形成完好的加样孔。 ③将温热琼脂糖溶液倒入胶膜中，使胶液缓慢地展开，直到在整个有机玻璃板表面形成均匀 的胶层。④室温下静置30min左右，待凝固完全后，轻轻拔出梳子，在胶板上即形成相互隔开的上样孔。制好胶后将铺胶的有机玻璃内槽放在含有0.5～1×TAE（Tris-乙酸）或TBE（Tris-硼酸）工作液的电泳槽中使用，没过胶面1mm以上。 3.试剂盒回收DNA片段（编号Clone SOP-3） 以本实验室常用DNA凝胶回收试剂盒（天根）为例 使用前请先在漂洗液PW中加入无水乙醇，加入体积请参照瓶上的标签。 ①柱平衡步骤：向吸附柱CA2中（吸附柱放入收集管中）加入500μl平衡液BL， 12,000rpm(~13,400×g)离心1min，倒掉收集管中的废液，将吸附柱重新放回收集管中。（请使用当天处理过的柱子） ②将单一的目的DNA条带从琼脂糖凝胶中切下（尽量切除多余部分）放入干净的离心管中， 称取重量。 ③向胶块中加入等倍体积溶液PN（如果凝胶重为0.1g，其体积可视为100μl，则加入100μlPN 溶液），60℃水浴放置，其间不断温和地上下翻转离心管，以确保胶块充分溶解。如果还有未溶的胶块，可继续放置几分钟或再补加一些溶胶液，直至胶块完全溶解(若胶块的体积过大，可事先将胶块切成碎块)。 注意：对于回收<300bp的小片段可在加入PN完全溶胶后再加入1/2胶块体积的异丙醇以提高回收率；胶块完全溶解后最好将溶液温度降至室温再上柱，因为吸附柱在室温时结合DNA 的能力较强。 ④将上一步所得溶液加入一个吸附柱CA2中（吸附柱放入收集管中），室温放置2min， 12,000rpm(~13,400×g)离心30-60sec，倒掉收集管中的废液，将吸附柱CA2放入收集管中。 ⑤向吸附柱CA2中加入600μl漂洗液PW（使用前请先检查是否已加入无水乙醇）， 12,000rpm(~13,400×g)离心30-60sec，倒掉收集管中的废液，将吸附柱CA2放入收集管中。 ⑥重复操作步骤⑤。 ⑦将吸附柱CA2放回收集管中，12,000rpm(~13,400×g)离心2min，尽量除尽漂洗液。将吸附 柱CA2置于室温放置数分钟，彻底地晾干，以防止残留的漂洗液影响下一步的实验。 ⑧将吸附柱CA2放到一个干净离心管中，向吸附膜中间位置悬空滴加适量洗脱缓冲液EB或 ddH2O，室温放置2min。12,000rpm(~13,400×g)离心2min收集DNA溶液。 4.酶切反应（编号Clone SOP-4） 以本实验室常用酶FastDigest restriction enzymes（Thermo）为例 双酶切体系（若是单酶切则只用加一种酶）： 10×FastDigest? buffer or 10×FastDigest? Green buffer 5ul FastDigest restriction enzyme 1 0.5-1ul FastDigest restriction enzyme 2 0.5-1ul DNAN ddH2Oupto50ul 酶切体系混合均匀后置于37℃条件下反应，反应时间应大于30min，若是载体（2-3ug）至少酶切2小时。 5.酶切产物的回收（编号Clone SOP-5） 以本实验室常用Axygen?AxyPrep?PCRClean-UpKit（Axygen）为例 ①在PCR、酶切、酶标、或测序反应液中，加入3个体积的BufferPCR-A（若BufferPCR-A https://www.sodocs.net/doc/da6618075.html, 量子克隆遗传算法1 李阳阳1，焦李成1 1西安电子科技大学电子工程学院，西安(710071) E-mail: lyy_111@https://www.sodocs.net/doc/da6618075.html, 摘要：遗传算法是解决优化问题的一种有效方法。但在实际应用中也存在着收敛速度慢，早熟等问题，使得其结果极不稳定。本文将遗传算法和量子理论相结合并利用免疫系统中所特有的克隆算子，针对0/1背包问题，提出了一种改进的进化算法——量子克隆遗传算法(QCA)。它能有效的避免早熟，且具有收敛速度快的特点。 关键词：遗传算法量子克隆遗传算法 0/1背包 中图分类号：TN957 1.引言 进化计算是一种仿生计算，依照达尔文的自然选择和孟德尔的遗传变异理论，生物的进化是通过繁殖、变异、竞争、选择来实现的，进化算法就是建立在上述生物模型基础上的随机搜索技术。我们所熟悉的遗传算法(Genetic Algorithms)[1]，它通过模拟达尔文的“优胜劣汰，适者生存”的原理鼓励好的个体，通过模拟孟德尔的遗传变异理论在进化过程中保持好的个体，同时寻找更好的个体，由此来模仿一切生命与智能的产生与进化过程[2][3]。理论上已经证明：进化算法能从概率的意义上以随机的方式寻求到问题的最优解；但在实际应用当中随着问题的复杂和海量的数据量，也出现了一些不尽人意的情况，主要表现在：计算后期解的多样性差即易造成早熟，收敛速度慢等缺点。因此，为克服上述缺点关键是构造性能良好的进化算法。 量子力学是20世纪物理学最惊心动魄的发现之一，量子计算是物理理论与计算机的成功结合，在量子体系中，一位的信息位不在是经典的1比特，而是由两个本征态的任意叠加态所构成即称之为量子比特位(qubit)，例如一个n位二进制的串在量子体系中就可同时表示n 2个信息,而量子计算机对每个叠加分量(本征态)实现的变换相当于一种经典计算,所有这些经典计算同时完成,并按一定的概率振幅叠加起来,给出量子计算的结果,这种计算称之为量子并行计算[4]。正是量子的并行性使得原来传统计算机无法解决的复杂问题以惊人的速度得以解决,但在量子计算机尚未构成的情况下，为了充分利用量子计算的高效并行性，本文借用了量子计算中的量子编码，继承了免疫克隆策略[5]中的克隆算子将二者相结合，提出了量子克隆遗传算法，并将其应用于0/1被包问题上，与传统进化算法相比较,它具有收敛速度快、寻优能力强的特点。 1本课题得到高等学校博士学科点专项科研基金（项目编号：20030701013）资助。 - 1 -常用分子克隆实验方法
对基于克隆选择和小种群粒子群算法的混杂算法的实证研究【精品文档】(完整版)
分子克隆技术试卷
抗独特型克隆选择算法_张立宁
自适应混合变异克隆选择算法研究
量子克隆进化算法
量子密钥分发误码协调算法分析
基于克隆选择机制的函数优化免疫算法
分子克隆实验标准步骤
量子克隆遗传算法