克隆算法范文

2024-08-27

克隆算法范文（精选10篇）

克隆算法第1篇

图像分割[1]是图像处理和分析的关键步骤,也是图像理解与模式识别的前提。阈值分割是图像分割最常用、最简单的方法,通过选取适当的阈值,将原图像中的目标与背景分离开来,为后续的分类、识别提供依据。如何选取最优阈值,保证最好的分割效果,一直是阈值分割的难点。人们对此已经提出了很多阈值选取方法,如1962年Doyle提出的P-title法,1966年Prewitt提出的mode法,即常用的双峰直方图谷底法,1979年Otsu[2]提出的最大类间方差法,该方法使得分割后图像的目标和背景差别最大,1985年Kapur[3]根据信息论中信息熵的概念提出了最大熵图像分割方法,1986年kitter等人提出的最小误差法。其中最大熵阈值分割方法是图像分割中分割效果较好的方法之一,它能更好地利用图像中包含的信息有效地进行图像分割。事实上图像阈值分割的问题就是对分割函数进行优化[4,5],这种函数优化的计算量相当大,收敛速度很慢,这就给图像阈值分割带来了很大的困难,因此,怎样减少函数计算量和提高函数收敛速度成为了图像阈值分割的关键性问题[6,7]。这里提出了一种克隆选择和粒子群相结合的算法,并将其用于最大熵阈值分割中。实验表明,该算法减少了图像阈值分割函数的计算量,加快了收敛速度,较快地求出了图像的最优阈值。

1 克隆选择和粒子群算法

1.1 克隆选择

克隆选择学说最早由澳大利亚免疫学家Burnet等人通过对人体免疫系统的研究在医学领域提出的。该学说认为抗体存在于细胞表面,当外来病毒(抗原)侵入时,抗体与抗原选择性地反应,只有与这种抗原匹配的抗体被激发,并使得抗体大量克隆增殖,得到成熟的抗体。成熟的抗体一部分分泌浆细胞清除抗原,一部分形成记忆细胞参加以后的二次免疫反应。即若再有同样或类似的病毒侵入时,记忆细胞立即被激活,迅速高效地清除病毒。在抗体迅速克隆增殖的过程中,抗体也会得到高频率的变异,得到一些更优秀的抗体。经过很多人对克隆选择的研究和改进,并通过在实际工程中的应用,人们针对克隆选择的机制,设计了克隆、变异、受体编辑、抑制删除等算子[8,9]来解决问题。

1.2 粒子群算法

粒子群优化算法(Particle Swarm Optimization,简称PSO算法),是由Kennedy和Eberhart于1995年首次提出的一种基于群智能的优化算法,是对鸟群觅食的社会行为模拟。本文使用改进了的异步粒子群优化算法。假设群体有m个粒子x1,x2,…,xm。第i个粒子在D维空间中的位置表示为

xi=(xi1,xi2,…,xiD)

其速度表示为:

vi=(vi1,vi2,…,viD)

其中,1≤i≤m

不同的粒子在D维空间中处于不同的位置时,所得到的目标函数的适应值不同。群体中所有粒子经过的最好位置表示为:

Pg=(Pg1,Pg2,…,PgD)

第i个粒子经过的最好位置表示为:

Pi=(Pi1,Pi2,…,PiD)

粒子群算法基本步骤如下:

①对粒子群中粒子的位置和速度随机初始化。

②计算每个粒子的适应值。

③更新群体的最好位置和每个粒子的最好位置。

④按下式更新粒子的位置和速度

vi(t+1)=wvit+c1r1(Pit-xit)+c2r2(Pgt-xit) (1)

xi(t+1)=xit+vi(t+1) (2)

其中,w表示惯性系数,c1,c2为学习速率,r1,r2为[0,1]之间的均匀随机数。

⑤判断终止条件,满足则结束,否则返回步骤②。

异步粒子群优化算法的不同之处在于每个粒子的适应值、个体极值、全局极值、位置和速度都是连续更新的,所以当前粒子的更新会考虑到之前所有粒子更新产生的新信息。而且在异步粒子群算法中,每一次迭代开始前,会根据每个粒子的适应值将所有的粒子排序,最优的适应值排在前面,差的适应值排在后面。这样在更新开始时,适应度越好的粒子就会越先更新,也会为以后粒子的更新提供更多有效的信息。

2 克隆选择和粒子群的结合

针对克隆选择和粒子群算法的特点,提出了克隆粒子群优化算法。克隆选择能够保留群体中最优个体,并保持群体多样性,粒子群算法在目标函数寻优中能够有效利用每次迭代的信息,实现整个群体迭代中的正反馈。在算法中,将整个群体分为若干个子群体,在子群体内部应用改进了的异步粒子群优化算法。以子群体作为抗体设计了克隆、变异和选择算子,对整个群体进行克隆选择算法。抗体的亲和力用子群体中全局最优粒子的适应值和子群体所有粒子的平均适应值表示;抗原定义为含有全局最优值的子群体;每个粒子的位置和速度定义为抗体中包含的染色体;抗体之间的距离定义为抗体的亲和力之差的绝对值,两个亲和力之差为零的抗体认为是相同的抗体;染色体之间的差别定义为代表粒子位置和速度的差别,如果粒子的位置和速度的欧氏距离同时为零,则认为染色体相同。

3 克隆粒子群最大熵图像分割

3.1 最大熵图像分割

最大熵法图像分割把信息论中“熵”的概念用于图像分割中,其原理如下:

设图像的灰度范围是0～(L-1)级,有阈值把图像分割为背景B和目标A两类。背景B的像素分布和目标A的像素分布分别是:

B: $\frac{f_{0}}{Ρ_{t}}, \frac{f_{1}}{Ρ_{t}}, \dots, \frac{f_{t}}{Ρ_{t}} (3)$

A: $\frac{f_{(t + 1)}}{1 - Ρ_{t}}, \frac{f_{(t + 2)}}{1 - Ρ_{t}}, \dots, \frac{f_{(l - 1)}}{1 - Ρ_{t}} (4)$

其中,fi是各灰度级出现的频率

$Ρ_{t} = \sum_{i = 0}^{t} Ρ_{i} (5)$

设图像背景和目标对应的熵分别为H(B),H(A),其表示如下:

$\begin{array}{l} Η (B) = \ln Ρ_{t} + \frac{Η_{t}}{Ρ_{t}} (6) \\ Η (A) = \ln (1 - Ρ_{t}) + \frac{Η - Η_{t}}{1 - Ρ_{t}} (7) \end{array}$

式中,Ht和H分别表示为

$\begin{array}{l} Η_{t} = - \sum_{i = 0}^{t} p_{i} \ln p_{i} (8) \\ Η = - \sum_{i = 0}^{l - 1} p_{i} \ln p_{i} (9) \end{array}$

图像的熵F(t)为H(B)和H(A)之和,即

$F (t) = \ln Ρ_{t} (1 - Ρ_{t}) + \frac{Η_{t}}{Ρ_{t}} + \frac{Η - Η t}{1 - Ρ_{t}} (10)$

图像分割的最佳阈值t就是使得图像的熵F(t)达到最大的阈值:

$t = \arg \max_{0 \leq t \leq l - 1} Η (t) (11)$

用最大熵法分割图像,不足之处在于计算量太大,需要对图像所有灰度进行迭代计算,计算其最大熵F(t),复杂度太大。故引入克隆粒子群算法来提高运算速度。为获得图像目标和背景最大信息量,信息熵越大越好,使得信息熵最大的灰度值t就是图像分割最好阈值。

3.2 克隆粒子群最大熵图像分割步骤

最大熵法求图像分割阈值的过程其实就是寻找式(10)最优解的过程,克隆粒子群算法作为一种新的全局优化搜索算法,具有记忆功能和良好的收敛性。所以完全可以把克隆粒子群算法用于图像分割中,通过寻找使得图像的熵为最大的阈值即为图像分割最佳阈值。

克隆粒子群最大熵图像分割步骤如下:

①初始化:随机产生n个初始子群体,每个子群体含有m个粒子,初始化粒子的速度和位置信息,并按式(10)计算各粒子的适应值。置迭代计数器gen=1,最大迭代数gen=20。

②在子群体内部进行粒子群优化R次。粒子的速度更新按(1)式进行,位置更新按(2)式进行。

③按下式计算各子群体的亲和力,并排序:

$a f f_{i} = \frac{(a v a f f_{i} + g b e s t_{i})}{2} i = (1, 2, \dots, n)$

其中,avaffi是子群体中粒子的平均适应值,gbest是子群体所有粒子最好的适应值。

④克隆:按子群体亲和力大小排序,对亲和力高的前50%子群体进行克隆。为增加子群体多样性,对其中一个子群体的各粒子施加一个很小的随机值,另一子群体不变。

⑤变异:对所有克隆后的子群体随机重组。

⑥选择:计算重组后抗体的亲和力,并按亲和力对抗体排序,选出m个子群体。

⑦判断是否达到最大迭代次数,达到则结束,否则,转步骤②。

⑧得到图像最优分割阈值并进行图像分割。

4 实验结果分析

为了验证克隆粒子群算法对图像阈值分割快速求解的有效性和稳定性,选用图像进行了实验。

相应的计算机配置如下:

处理器:Intel Pentium 4;

主频:2.6GHz;

内存:512M;

操作系统:Windows XP;

仿真软件:MATLAB7.0版本。

实验1:选取cameraman原始图像进行实验,图像大小256×256。实验结果如图1所示:(a)原始图像;(b)遗传算法分割结果;(c)粒子群算法分割结果;(d)克隆粒子群算法分割结果。

在实验中,对遗传算法、粒子群算法和克隆粒子群算法采用相同的迭代次数,最大迭代次数gen=20。在克隆粒子群算法中,种群规模n=8。子群体中进行相应的粒子群算法,粒子数m=3,迭代次数R=5,惯性系数W取值范围[0.9,0.4],学习速率c1=1.4,c2=1.6。

本文对这三种算法分别进行了5次独立实验,给出了5次独立实验的结果。从表1可以看出,本文提出的克隆粒子群算法能够克服局部最优,准确得到图像分割的最优阈值,在阈值计算时间上比遗传算法节省了大量时间,大大加快了阈值的求解速度。遗传算法求解的图像分割阈值最大为90,最小为84,图像阈值波动范围在6个像素之间,波动范围较大,而且不能够达到图像的最佳分割阈值。粒子群算法图像分割速度很快,但是其最大图像分割阈值为70,最小为66,图像阈值波动范围在4个像素之间,稳定性较差。而克隆粒子群算法求解的图像分割阈值很稳定,而且收敛速度也大大提高了。从图1可以看出图像分割效果较好,得到了图像的最优分割阈值。可见,克隆粒子群算法在求解图像阈值的稳定性和收敛速度上明显优于前两种算法。

实验2:选取westconcordorthophoto图像进行实验,图像大小为256×256。实验结果如图2所示:(a)原始图像,(b)遗传算法分割结果,(c)粒子群算法分割结果,(d)克隆粒子群算法分割结果。

在实验中,克隆粒子群算法种群规模n=8, 子群体中粒子数m=3,迭代次数R=5,惯性系数w取值范围[0.9,0.4],学习速率c1=1.4,c2=1.6。遗传算法、粒子群算法和克隆粒子群算法选用迭代次数均为gen=20。

对三种算法分别进行了5次独立实验。实验结果如表2所示,从表2可以看出,遗传算法求解图像分割阈值收敛速度最慢,而且图像阈值波动范围在5个像素之间,得到图像分割阈值结果不稳定,还不能达到图像分割的最优阈值。粒子群算法收敛速度很快,但是得到的图像分割阈值波动在3个像素之间,得到的阈值不稳定。克隆粒子群算法非常准确地得到了图像分割的最优阈值,并且分割速度也大大提高。通过比较克隆粒子群算法在图像分割阈值稳定性和收敛速度上明显优于前两种算法。

5 结束语

基于克隆选择原理和粒子群思想提出一种克隆粒子群算法的图像分割方法,该方法应用子群体内部的粒子群算法扩大了群体的搜索空间,利用克隆选择原理的克隆、变异、选择算子保证了群体的多样性,加快了搜索速度,实现了图像阈值的最佳分割。实验表明,该算法能够在保持群体多样性的同时加快收敛速度,能够准确地分割图像,取得了较好的分割效果。

参考文献

[1]贾永红.数字图像处理[M].武昌:武汉大学出版社,2003.

[2]OTSUN.A threshold selection method from gray level histogram[J].IEEE Trans on systems,man and cybemetics,1979,9(1):62-66.

[3]Kapur J N,Sahoo P K,Wong A K C.A new method of gray level picturethresholding using the entropy of the histogram.Computer Vision,Graphics,and Image Processing.1985,29(2):273-285.

[4]黄猛,唐琳,胡世安,等.一种改进的分裂合并图像分割算法[J].计算机应用技术,2009(22):102-105.

[5]Yi-tong LIU,Ming-yin FU,Hong-bin GAO.Multi-threshold in-frared image segmentation based on the modified particle swarm opti-mization algorithm.Proceedings of the 6th International Conferenceon Machine Learning and Cybernetics,2009,19(22):383-388.

[6]何宁,张朋.基于边缘和区域信息相结合的变分水平集图像分割方法[J].电子学报,2009,37(10):2215-2219.

[7]侯彪,刘凤,焦李成,等.基于自适应窗口固定及传播的多尺度纹理图像分割[J].电子学报,2009,37(7):1492-1500.

[8]王巧灵,高晓智,王常虹,等.基于克隆选择和粒子群思想的动态多群体优化算法[J].控制与决策,2008,23(9):1073-1076.

假如我会克隆，我要克隆作文第2篇

假如我会克隆，我要克隆许多的老师。因为在一些贫困的山村里，一些孩子家里没钱上学，所以我要克隆许多许多的老师，把他们分别送到那些山村里去，并让他们把知识输送给那些渴望读书的孩子们，让那些孩子像我们一样在知识的海洋里遨游。

假如我会克隆，我要克隆自己，因为，在自己孤独的时候，可以与克隆出来的人聊聊天、谈谈心。在学习上，我还可以与克隆出来的人一起竞争，共同进步。

克隆·克隆羊·克隆人第3篇

首先，究竟什么是“克隆”呢？，克隆，是英语clone的中文译音，意思是无性繁殖系。例如，将一个蒜瓣种到地里，可以长成一个大蒜头，这就是一个无性繁殖过程。因这个过程不需生殖细胞的产生与结合。一个大蒜头就是一个无性繁殖系，一个克隆。大蒜头中的每个蒜瓣就是组成一个克隆的小单位，称为“拷贝”，也就是“复制品”的意思。由于一个大蒜头中的每一个蒜瓣（拷贝）都是无性繁殖而来的，因此它们在遗传上都完全相同。当然，由于环境因素的差异，同一个大蒜头中的蒜瓣可能会有大小或其它差异，但它们都是在遗传上完全相同的复制品。由于许多植物都比较容易进行无性繁殖，因此，可以用插枝、压条、嫁接等方法人工形成克隆。

其次，克隆羊是怎么回事？科学研究发现，高等动物和人体的细胞，由于分化程度太高，不能自然进行无性繁殖。于是，科学家们就想出一个巧妙的办法来克隆高等动物。早在1938年，胚胎学家施佩曼就曾设想过一个“奇异的实验”，即从胚胎细胞中取出细胞核（此细胞称为“供体”），移植到一个去除了细胞核的卵细胞中（此细胞称为“受体”），让这个移植了供体核的卵细胞发育成一个完整的动物体。这个动物体由供体的细胞核“无性繁殖”而来，因而是克隆，并且几乎与供体一模一样，是供体动物的一个复制品——一个拷贝。

许多科学家多年来不断地进行着这方面的研究。英国的维尔莫特在经过了400多次实验之后，终于获得了一头由体细胞克隆的绵羊。这头世界上第一次由高等动物体细胞克隆的绵羊被命名为“多利”。克隆羊多利在各方面都非常正常。它浑身洁白，长着细长弯曲的羊毛，粉扑扑的鼻子，右耳上系着一红色的小身份牌。据报道，克隆羊多利已经做妈妈了。1998年4月13日当地时间凌晨，多利自然分娩产下了一头小母羊。这头小母羊（多利的女儿）被取名为“邦尼”。邦尼的出生，证明克隆羊多利完全能够正常交配、怀孕，并产下健康的后代。

最后，我们再来看看克隆人。其实，在人类正常的有性生殖过程中，自然产生出克隆人来，已经屡见不鲜：这就是同卵双胞胎。人的生命的第一个细胞——受精卵，分裂一次变成两个胚胎细胞。在少数情况下，这两个胚胎细胞会彼此分开，各自发育成一个胎儿，这就是同卵双胞胎。受精卵固然是有性生殖的产物，但同一个受精卵分裂成两个分开的细胞，这一步却是无性繁殖。因此，同卵双胞胎便组成了一个有两个拷贝的克隆。同卵双胞胎在遗传上几乎完全相同，外形也极为相似。那么，怎样来制造克隆人？克隆人的方法大体上与克隆羊相似：从某个人身上取得一小块组织进行体外培养，作为供体。从供体细胞取得细胞核，注入已经去核的受体卵细胞中。让这个接受了供体核的细胞在试管内发育一个短时期，然后移植到一个健康的、有生育能力的妇女子宫内，使后者怀孕，最终生下一个与供体相似（在遗传上几乎完全相同）的“克隆人”来。

用体细胞进行人类克隆，可以解决一个优生学的问题：对患有遗传病并有高风险遗传倾向的母体，可以从母体取得卵细胞，剔除其细胞核，再移植入一个正常的细胞核，孕育克隆人，就能有效地遏止遗传病遗传下去。克隆技术可以帮助那些患有无法治愈的不孕症的夫妇生儿育女。此外，利用克隆技术也可以克隆人的器官，例如心脏、肝脏、肠、五官、四肢等，以满足医疗上器官移植的需要。

一种基于引力的合作克隆选择算法第4篇

近年来,受生物免疫系统启发的人工免疫系统逐渐成为智能计算中的研究热点,出现了多种基于免疫原理的启发式算法。其中,模拟脊椎动物免疫系统克隆选择模型,人工克免疫克隆选择算法被设计出来。相比较遗传算法,人工克免疫克隆选择算法表现出许多好的特性,如提高了收敛速度;保持了种群多样性;较有效地克服早熟收敛、欺骗问题等遗传算法本身难以解决的问题。因此广泛应用在模式识别、优化等工程领域,近年来,也应用到数据挖掘,网络安全等领域。

本质上,克隆选择算法是以群体为基础的搜索算法。从不同的角度来看,一个以群体为基础的搜索算法,其个体在每次迭代中通过三个步骤来实现对搜索空间的探索和开发:自我适应(自我调整),合作和竞争。在自我调整的步骤中,每个个体提高其性能。在合作过程中,各个体通过信息传递相互协作。最后,在竞争这一步,个体竞争生存。这些步骤通常是随机的形式,并且可以用不同的方式来实现。这些步骤从自然界启发,是以群体为基础的启发式算法的原则思想,引导算法找到全局最优解。在克隆选择算法中,主要算子克隆、变异、选择完成对搜索空间的探索和开发,其中克隆与变异是个体的自我调整,选择就是竞争。

然而,并不是所有的以群体为基础的搜索算法对每个优化问题求解上都能提供了令人满意的结果,也没有一个启发式算法,在解决所有优化问题时,均可以比其他所有算法性能更优,换句话说,某个算法能解决一些问题性能更好,而解决其他一些问题比别的算法更差。因此,新的高性能启发式算法的研究会一直受到研究者的关注。

现有文献中,克隆选择算法自我适应方面的研究较多,比如按照抗体适应度,每个抗体克隆规模和变异概率有所不同,通常抗体的克隆规模和变异概率是其适应度的函数,克隆选择算法中,个体间的竞争体现在选择操作,每代中,克隆后的抗体群中适应度高的抗体会被选择进入下一代。抗体间的合作研究很少,一个个体,向着更好地适应度方向在运动,整体群体向着目标运动,要更多的挖掘群体中个体间的有关信息,让它们有助于整个抗体群更快速地向着目标运动,基于这一点,本文从牛顿万有引力定律入手,以抗体间的引力合作为基础,提出了基于引力的合作克隆选算法。

2 万有引力定律

牛顿万有引力,简称引力,是质体间的相互吸引力,它是自然界中的四个基本相互作用之一(其他是:电磁力、强相互作用、弱相互作用)。引力无处不在,引力的不可避免使得它不同于其他所有的自然力。两质体的引力大小与它们质量的乘积成正比与它们距离的平方成反比,与两物体的化学组成和其间介质种类无关。

其中F是万有引力大小,G是万有引力常数,M1和M2的分别代表第一个和第二个质点的质量,R是两个质点之间的距离。

牛顿第二运动定律:物体的加速度a跟物体所受的合外力F成正比,跟物体的质量M成反比。

3 基于引力的合作克隆选择算法

3.1相关概念

抗原:自然免疫学中指能刺激机体免疫系统产生抗体的物质。本文中指待求问题。例如函数优化问题(p)

这里, f (X) 为目标函数,变量X ={x1,x2,...,xm} ,xi( i = 1,2,⋯,m )为X第i个分量。函数f (X) 称为抗原。

抗体及抗体群:抗体中本文中指抗原可行解的一个代表。抗体A = x'1,x'2,...x'm是变量X的编码,记为A = e(X) ,而X称为抗体A的解码,记为X = e-1(A) 。 x'i( i = 1,2,...,m )称为抗体A的第i分量编码。编码方式有二进制,十进制,本文采用十进制。根据设定精度,分量xi∈[di,ui] i = 1,2,⋯,m的编码长度为l ,其编码形式为:x'i= 0.a1a2...al,式中,ai(i = 1,2...l)是0 至9的整数,这样就实现了分量在0~1 的实数编码。则分量译码方式为:

令I为抗体空间,则A ∈ I ,抗体种群A =[A1A2...An] ,Ai∈ I,1 ≤ i ≤ n ,整数n为抗体种群规模。

亲和度或适应度:自然免疫学中指抗体与抗原结合力大小。本文中指目标函数值。

3.2算法主要步骤

Step1:初始化:设置算法终止条件,设定抗体分量编码长度l ,随机产生初始抗体群A(0)=[A1(0)A2(0)...An(0)] (抗体Ai(0)={ai1(0),ai2(0),...,aim(0)},i = 1,2,...,n的各分量aij(0)j = 1,2,...,m),令k=0;置引力常G

Step2:对A(k) 进行克隆操作,得抗体群Y(k) 。

Step3: 对Y(k) 进行克隆变异操作:即依据概率对克隆后的群体Y(k) 进行变异,得抗体群Z(k)

Step4:计算适应度:计算Z(k)中各抗体适应度。

Step5:Z(k)及A(k)进行选择操作,得抗体群C(k)

Step6: 对C(k) 进行基于引力的合作操作。得抗体群A(k + 1)

Step7:算法终止测试:如果算法终止条件满足,则停止;否则,k = k + 1回到Step2。

3.2.1 基于引力的合作操作

基于引力的合作操作按以下方法设计:

1)计算第k代抗体i的质量Mi(k)

其中,fiti(k)代表k代第i个抗体的适应度值,worst(k)与best(k),在求解最小值问题中,如下计算:

2)计算第k代抗体i所受其他抗体的引力Fdi(k)。

设:抗体i与抗体j在第d个分量之间的引力Fdij(k)

其中,d∈[1,m] ,Mi(k)与Mj(k)分别代表第k代抗体i和j的质量。G(k)为第k代的引力常量,ε为一较小常量。Rij(k)为第k代抗体i与抗体j的欧几里得距离:

3)更新第k代抗体i的各分量

应用牛顿第二定律,设第k代抗体i在第d个分量的加速度为aid(k) :

第k代抗体i的各分量更新公式为:

为了保证算法初期的大范围搜索及算法后期的精细搜索,尽可能地避免限入局部极值,让适应度值更高的抗体移动更缓慢(合作时的更新更少,更有利于精细搜索),通常可采用以下方法:

1)引力常量G在算法开始时初始化,随着迭代次数增加逐步减小,以保证算法后期的精细搜索。因此G是初始值(G0)与迭代次数(k)的函数:

2)为了引入随机性,抗体i与其他抗体间在第d个分量间的引力Fid(k) 计算方法可更新如下:

其中randj代表[0,1] 区间内均匀分布的随机数,使算法在解空间搜索时更具有随机性。

3)抗体间的合作是基于引力的,可以取适应度值靠前的部分抗体Nbest作为合作抗体来影响其他抗体,Nbest是迭代次数的函数,在算法开始初始化,并随着迭代次数增加而减小,可以这样做,开始时,Nbest为全部抗体,全部抗体参加合作,随着迭代次数增加Nbest线性减小,到最后,只有一个抗体作为合作抗体,其引力来影响其他抗体。因此,公式(14)可进一步修改如下:

这里Nbest是前n个最高的适应度值及最大的质量。

3.2.3 函数优化应用

本部分将基于引力的合作克隆选择算法,应用于函数优化,并与标准的遗传算法(SGA)、克隆选择算法(CSA)、文献[1]中提出的进化算法以及文献[2]中提出的自适应混沌克隆进化规划算法(ACCA)进行对比。测试标准函数如下:

测试时,对于SGA和ACCA,设置交叉概率0.8,变异概率0.07,种群规模都为50;CSA、ACCA和本文算法的种群规模为50,克隆规模为25,保证各算法的总的函数计算次数相同;对于变异策略,ACCA采用“尺度收缩”[1],CSA和本文算法采用非均匀变异[2];ACCA算法,设置变异参数 α =2,β =0.2~10, γ =0.3。本文算法设置编码长度为10,引力常量G固定为0.1,合作抗体数Nbest固定为10 。对于二维测试函数优化,取算法的总进化代数为100;对于高维函数,取变量维数为10,算法总进化代数为300。表1是随机独立运行60次的统计结果(Visual studio 2010 C++编写)。

可以从表中看出,对于二维测试函数f1、f2和高维测试函数f3、f4,本文算法在求解性能上(主要是求解精度和稳定性)要优于其他三种算法。

4 结论

本文从牛顿万有引力定律入手,以抗体间的引力合作为基础,引入新的算子,充分利用了抗体群个体间的有关信息,让它们有助于整个抗体群更快速地向着目标运动。相比较其他一些克隆选择或其他算法,经过部分标准优化测试函数实验,本文提出的算法在求解性能上有较有效提高。

参考文献

[1]骆晨钟,邵惠鹤.采用混沌变异的进化算法[J].控制与决策,2000,15(5):557-560.

[2]杜海峰,公茂果,刘若辰,等.自适应混沌克隆进化规划算法[J].中国科学E辑,信息科学,2005,35(8):817-829.

[3]邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999.

克隆算法第5篇

假如我会克隆，我要克隆一个地球作文

。现在，克隆再也不是一件异想天开的事情了，克隆羊“多利”已经证明了人类科学技术的腾飞和美好的未来。

克隆技术有益处，也有害处。益处是：可以把我国的大熊猫、金丝猴、扬子鳄......的这些珍惜动物的基因、细胞提取出来，再去克隆，这样，动物就平等了，不分一级、二级保护动物。害处是：克隆一些对地球有害的东西。

假如我会克隆，我要克隆一个地球，因为在21世纪，世界的人口急剧上升，人类面临着一个大问题-无家可归，因为这样，人类乱砍乱伐的行为，使地球越来越憔悴，

小学生作文大全

克隆算法第6篇

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

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) 不考虑机器故障的情况。

克隆算法第7篇

众所周知, 码分多址 (CDMA) 技术产生的多址干扰 (MAI) 严重影响着系统的性能和容量。多用户检测技术 (MUD) 是有效解决多址干扰问题的方法之一。

1986年, Verdu提出了最佳多用户检测 (OMD) , 但是其运算复杂度随着用户数的增长成指数增长, 在实际应用中实现难度很大。为了使多用户检测能够实用化, 学者们将工作的重点集中在性能接近最佳多用户检测器而计算复杂度较低的次最佳多用户检测器上。

随着多用户检测器使用的普及, 现有的量子克隆遗传算法应用在多用户检测中也呈现出一些弊端。比如存在算法效率低、收敛速度较慢、易于陷入局部最优等缺陷, 文中针对这些缺陷进行改进, 提出一种改进的量子克隆遗传算法 (NQCGA) 。

(二) 多用户CDMA系统模型

考虑DS-CDMA通信系统, 假定小区有K个正在通信的用户, 则基站接收到的信号r (t) 为:

其中, P是每个用户的传递的码元数量;Tb为发射信号的码元间隔;Ak为第k个用户到达基站时的信号幅值;为第k个用户的第i个传输比特;τk∈[0, Tb) 为第k个用户的信号时延;n (t) 为功率谱密度为N0/2的高斯白噪声。第k个用户的扩频波形s k (t) 可表示为:

其中, 是一个持续时间为Tc的方波;Tc是扩频信号码片 (chip) 持续时间;aI (k) 是第k个用户的扩频序列的第l个比特值。将接收信号分别通过K个匹配滤波器进行相干处理, 获得对应于K个用户的观察数据y (i) =⎡⎣y1 (i) , y2 (i) , ..., yk (i) ⎤⎦T。

通常K个用户的匹配滤波器输出向量形式为:

其中, A是由信号幅度构成的PK×PK维的对角阵;b和n分别为PK维的信号列向量和噪声列向量;R是由R (v) , v∈{-1, 0, 1}构成的PK×PK维的块Toeplitz阵, R (v) 中的元素为:

其中, 1≤k, l≤K, ρkk (v) =1。在同步情况下, 对于任意的用户i, τi=0, P=1, R=R (0) 。

(三) 改进的量子克隆遗传算法

NQCGA的基本思想是在李阳阳给出的量子克隆遗传算法的基础上, 引入量子全干扰交叉, 在整个种群内进行信息传递, 避免陷入局部极值点, 加速算法收敛, 同时使用自适应量子旋转角更新策略, 加速最优解的搜索;为避免早熟和进化停滞, 采用量子灾变策略, 使用个体全干扰交叉, 使种群从各个不同方向搜索目标解, 从而提高了种群的多样性。

1. NQCGA算法基础

(1) 量子编码

量子编码是量子行为优化算法中一个主要的编码方法, 一般的遗传算法中主要包含三种编码方式, 即:二进制、十进制和符号编码。在NQCGA中, 采用了一种特殊的编码方式——量子比特编码, 即用一对复数来表示一个量子比特, 这也正是此算法高效性所在。因为一个量子比特一般通过一对复数来表示, 所以一个具有m个量子比特的系统 (即:一个量子个体) 可用公式表示为:

其中, 丨α2丨+丨β2丨=1, 即:丨α2丨和丨β2丨均表示基态在随机情况下出现的两个概率, 且它们满足归一化条件。

则系统的状态可以表示为:

式 (8) 表示的四种状态分别为:丨000〉, 丨001〉, 丨100〉, 丨101〉, 它们的概率分别为:。

(2) 量子交叉

量子交叉是通过量子力学的一些特性 (比如:量子的干涉和纠缠) 来设计的, 一旦量子交叉设计好了, 就可以通过它带来两个方面的好处:一是它可以产生新的个体, 并且能有效地促进算法的收敛速度。二是它能使种群内部所有信息进行交流和传递。

量子交叉的流程为:

1) 在种群Q (t) 中,

这里, 设种群的规模为N, 量子比特个体的数量为n, 基因段的大小为k, i=1, 2, L, n, j=1, 2, L, k, 且。

2) 交叉后代C1的第i个基因段的第一对概率副值为:

第j对概率副值为:

最后一对概率副值为:

c1 (βik) 的求法同上, 在j

3) 用2) 的方法重复上述操作, 直到取到N个后代交叉为止。

2. NQCGA算法操作策略

(1) 量子全干扰交叉策略

在NQCGA中, 利用量子叠加态的相干性构造了全干扰交叉。在这种交叉操作中, 可以随意选择参与交叉的个体数, 而参与交叉的每一个个体均进行交叉操作, 新形成的子代个体携带多个父代个体的信息, 实现了种群信息的充分融合, 可以有效地避免种群趋同现象的过早发生。

进行量子全干扰交叉时, 首先按照交叉率Pc从种群中选出一定数目的个体放入交叉池, 形成一个交叉阵列, 然后按对角线重新排列, 产生新个体。若交叉种群规模为4, 个体长为5, 全干扰交叉的具体操作如图1所示。按照对角线重新排列图1的交叉阵列, 新形成的四个个体分别为A1B2C3D4E1, A2B3C4D1E2, A3B4C1D2E3和A4B1C2D3E4。

量子全干扰交叉可以充分利用种群中的尽可能多的抗体的信息, 克服普通个体在进化后期的早熟现象。

(2) 量子旋转门自适应更新策略

文中采用一种改进的旋转角更新策略, 可以简单方便地得到旋转角, 大大减少计算量, 加快算法运算速度。改进的旋转角更新策略如下式所示

式中, θi为旋转角;sign为符号函数;xtji和ibt分别为解xtj与当前最优解bt的第i位;f (x tj) 和f (b t) 分别是它们的适应度值;为种群中第j个染色体的第i个基因对;Δθi为量子位旋转的角度, 其大小可以控制算法的收敛速度, 使用自适应量子旋转角更新策略, 按照公式 (14) 进行调整:

式中, maxt为进化终止代数, t为每次更新的循环次数。

(3) 优体全干扰交叉量子灾变策略

优体全干扰交叉量子灾变策略, 其具体操作为:只保留最优值, 重新按照优体全干扰交叉策略生成其余量子染色体。按概率从每个种群中选取一个或若干个适应度值大的个体, 对选出个体实施全干扰交叉操作, 生成新个体后按原比例分配到各种群, 从而给各种群注入新的活力。

3. NQCGA算法描述

(1) 初始化阶段

Step1:初始化进化代数t=0, 量子灾变计数器k=0, 设种群Q (t) =[q1, q2, L, qn]的规模为N;

Step2:对初始化量子种群中的量子个体实施一次测量, 得到一组状态R (t 0) ;

Step3:计算种群Q (t) 的每个量子个体的状态适应度;

Step 4:选择适应度高的N个个体, 记录其状态及其适应度, 保存到B (t0) , 并记录B (t0) 中适应度最高的个体的状态及其适应度, 保存到b (t0) 。

4. 迭代进化阶段

当种群不满足终止条件时, 进入迭代进化阶段, 随着迭代的进行, 种群的解逐渐向最优解收敛。

Step5:利用量子全干扰交叉对种群进行更新, 得到新一代种群Q1 (t) ;

Step6:对种群Q 1 (t) 实施一次测量, 得到一组状态R (t) , 并对各状态进行适应度评价;

Step7:如果Q1 (t) 和B (t-1) 中的最优个体优于b (t-1) , 则替代b (t-1) 得到b (t) ;

Step8:按照设定的克隆规模, 选择Q1 (t) 和B (t-1) 中适应度高的m个个体进行克隆操作, 组成临时克隆群体C;

Step9:对种群C中子群体内部采用自适应量子旋转门更新策略进行量子变异策略操作, 得到变异群体C1;

Step10:对1C进行免疫选择操作, 形成新的种群C2, 同时计算其适应度, 选择C2中适应度高的个体替代B (t-1) 中适应度较差的d个个体, 得到B (t) ;如果B (t) 的最优个体优于b (t) 则替代保存, 否则不变;

Step11:判断是否连续k代无进化, 如否转Step5, 令k=k+1;如果连续k代无进化, 令k=0, 进行个体全干扰量子灾变策略, 生成新的种群Q (t+1) , 同时计算其适应度, 选择Q (t) 中适应度高的个体替代B (t-1) 中适应度较差的d个个体, 得到B (t) ;如果B (t) 的最优个体优于b (t) , 则替代保存, 否则不变;

Step12:判断是否满足终止条件, 如果满足, 则输出b (t) ;如果否, 令t=t+1, 转Step 5重新执行。

NQCGA的流程图如图2所示:

(四) 基于改进量子克隆遗传算法的多用户检测器

NQCGA应用到多用户检测中, 是以适应度函数为判断依据的, 适应度函数的设计直接影响到NQCGA在多用户检测中应用的性能。

当用NQCGA解决多用户检测问题时, 能量函数可写为:

其中, x为待求变量, 适应度函数f (x) =-E (x) , 则NQCGA的适应度函数可写为:

在NQCGA中确定了适应度函数后, 就可以应用到多用户检测中解决多用户检测中的存在的问题。

基于NQCGA的多用户检测器的原理框图如图3所示。

(五) 仿真与分析

仿真在一个同步DS-CDMA系统下进行, 共有10个用户, 扩频码采用31位的Gold码, 种群规模均为50, 最大进化代数为300, 设置各参数为w=1, c1=c2=2, β=0.5, ρ=0.2。在整个仿真过程中, 选用的多用户检测器有:OMD、GA、QGA、QCGA和文章中所提的NQCGA的多用户检测器。

1. 误码率大小比较

在不同信噪比下, 分别使用OMD、GA、QGA、QCGA和NQCGA的多用户检测器进行接收, 它们的误码率如图4所示。

由图4可以看出, 五者的误码率都随着信噪比的提高而降低, 在信噪比低的情况下, 五者的误码率很接近, 但在高信噪比时, NQCGA的误码率明显低于GA、QGA和QCGA, 并且随着信噪比的提高, 这种趋势越来越明显。

图5为使用OMD、GA、QGA、QCGA和NQCGA五种不同多用户检测器时的收敛速度比较。由图可知, 五种检测器的误码ꣅ港率都是随着迭代次数的增加而逐渐降低, 直至完全收敛。NQCGA和QCGA的收敛速度明显比QGA和GA要快, 而NQCGA的收敛速度略高于QCGA。仿真得到较好的误码率和收敛速度。因此, NQCGA的确具有比QCGA更强的全局和局部搜索能力。

3. 抗多址干扰能力强弱比较

假设系统中有10个用户, 且各用户的信号能量相等, 用户1为期望用户, 其信噪比为4 dB, 其余9个用户为干扰用户 (设干扰用户信号能量与期望用户1信号能量之比为Ei E1) 。对各用户的信噪比进行改变, 就可得到不同强度的干扰。图6为各多用户检测器的误码率 (BER) 与抗多址干扰能力之间的曲线图。由图可知, 随着干扰用户信噪比的增大, NQCGA-MUD的抗多址干扰的能力明显优于GA-MUD、QGA-MUD和QCGA-MUD, 且与最优多用户检测器 (OMD) 很接近。

4.抗“远近”效应能力强弱比较

假设系统有10个用户, 用户1为期望用户, 其信噪比为4 dB, 其余9个用户为干扰用户 (设干扰用户信号能量与期望用户1信号能量之比为Ei E1) 。图7为误码率 (BER) 与抗“远近”效应之间的曲线图。由图可见, 随着干扰用户功率的增加, NQCGA-MUD的抗“远近”效应的能力明显优于GA-MUD、QGA-MUD和QCGA-MUD, 接近于OMD的性能。并且随着Ei/E1的增大, 这种趋势越来越明显。

(六) 结束语

文中在基于量子克隆遗传算法基础上, 引入量子全干扰交叉, 在整个种群内进行信息传递, 避免陷入局部极值点, 加速算法收敛, 同时使用自适应量子旋转角更新策略, 加速最优解的搜索;为避免早熟和进化停滞, 采用量子灾变策略, 增加种群的多样性。提出了一种改进的量子克隆遗传算法并将其应用到多用户检测中。仿真结果表明, 改进的量子克隆遗传算法的多用户检测器的误码率、收敛速度、抗多址干扰能力和抗“远近”效应能力均优于量子克隆遗传算法的多用户检测器和基于经典遗传算法的多用户检测器。

参考文献

[1]刘芳, 李阳阳.量子克隆进化算法[J].电子学报, 2003, Vol.31 (12A) .

[2]VerduS.Minimum probability of error for asynchronous Gaussian multiple-access channels.IEEE.Tran.On Info.Therory.1986, 32 (1) .

[3]Verdu S.Optimum multi-user asymptotic efficiency.IEEE Trans.on Commun.1986, 34 (9) .

[4]阎石, 吕振肃.基于进化算法的多用户检测器[J].电子与信息学报, 2006, 28 (2) .

克隆算法第8篇

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

自从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.

克隆算法第9篇

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

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.

克隆算法第10篇

船舶电力系统作为一种高阶、非线性、强耦合和多变量的复杂系统,是现代船舶的重要组成部分。它的安全性和抗扰性对于船舶,特别是船舶的生命力和战斗力意义重大。随着船舶电气化、自动化程度的日益提高,对船舶电力系统供电的可靠性和生命力提出了更高的要求,要求系统在出现故障时快速地重构系统,以最大限度地恢复供电。目前,对船舶电力系统的故障恢复的研究还处于起步阶段,文献[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.

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

【克隆算法】相关文章：

动态克隆选择算法论文06-19

克隆选择05-22

克隆生长07-30

克隆作文09-03

克隆一个我05-06

多克隆抗体09-02

克隆论文题目04-08

奇妙的克隆06-30

如果我会克隆作文06-06

逃出克隆岛影评06-23