改进的RD算法-盘古文库

改进的RD算法（精选9篇）

改进的RD算法第1篇

RSA公钥密码体制在密码学中占有重要的地位, 已经成为现在最流行的公钥加密算和数字签名算法之一。目前一般认为RSA需要1024位以上的字长才有安全保障。由于RSA所采用的模幂运算耗时太多, 这样大的数据量处理时速度很慢, 所以提高RSA的运算效率便成为非常重要的研究课题[1,2]。而模幂运算是RSA中的常用算法,因此提高模幂运算的运算效率可以极大地改进RSA的运算效率。在RSA的私钥端可以利用私钥来约减指数达到简化计算的目的,而公钥端由于没有私钥而不能进行指数约减。因此RSA存在公钥端和私钥端计算不均衡的现象。文献[3]中提出了一种基于因子分解的指数约减算法,但仅适用于已知私钥的计算,本文提出一种通用的指数约减算法。

在模算数计算中,我们常常要对大整数模m和n,计算bn(modm)。尽管在初等数论的原根与指数理论中有算法:如果b与m互素,先计算欧拉函数ϕ(m),再在ϕ(m)的因子中找b模m的阶d,从而化简运算, 但是,当ϕ(m)比较大时,找阶d的运算量比较大,所以计算bn(modm)常见的算法是模重复平方算法[4,5]。我们首先介绍模重复平方算法,再引入rho改进算法。

1模重复平方算法

若将n写成二进制:n=n0+n12++nk-12k-1,其中ni∈{0,1},i=0,1,,k-1,则bn(modm)的计算可归纳为:

bn≡bn0(b2)n1(b2k-2)nk-2(b2k-1)nk-1(modm)

使用模重复平方算法最多做2[log2n]次乘法。具体算法[4,5]如下:

(1) 令a=1,b0=b。

(2) 如果n0=1,则计算a0≡ab0(modm),否则取a0=a,即计算a0≡ab $_{0}^{n_{0}}$ (modm)再计算b1≡b $_{0}^{2}$ (modm)。

(3) 如果n1=1,则计算a1≡a0b1(modm),否则取a1=a0,即计算a1≡a0b $_{1}^{n_{1}}$ (modm)。再计算b2≡b $_{1}^{2}$ (modm)。

(4) 如果nk-2=1,则计算ak-2≡ak-3bk-2(modm),否则取ak-2=ak-3,即计算ak-2≡ak-3b $_{k - 2}^{n_{k - 2}}$ (modm)。再计算bk-1≡b $_{k - 2}^{2}$ (modm)。

(5) 如果nk-1=1,则计算ak-1≡ak-2bk-1(modm),否则取ak-1=ak-2,即计算ak-1≡ak-2b $_{k - 1}^{n_{k - 1}}$ (modm)。

最后,ak-1就是bn(modm)。

2rho改进算法

在模重复平方算法中,由于b0=b,bi+1≡b $_{i}^{2}$ (modm),(i=0,1,2,),而Zm是有限的,所以序列bi最终将产生重复。即存在j、ω,使得bj=bj+ω,则已经处在一个回路中,因为bj+1=bj+ω+1,bj+2=bj+ω+2,等等。序列b0,b1,b2,,bj-1可以画成一个rho(ρ)的“尾”,而回路bj,bj+1,,bj+ω-1可以看成rho的“体”[6]。bk叫做bk+1的前导,bk+1叫做bk的后继。把满足bj=bj+ω最小的j叫做序列bi的索引,记为λ,把满足bj=bj+ω最小的ω叫做序列bi的周期,记为μ,rho结构如图1所示。

使用Floyd循环查找算法,从数对(b1,b2)开始,由前一数对(bi-1,b2i-2)来迭代计算(bi,b2i),直到某个ω处,bω=b2ω。用“/”表示除以,“⎣」”表示向下取整,第一次bω=b2ω时,ω=μ(1+⎣λ/μ」)。注意,这里λ<ωλ+μ[7]。令θ=ω,如果bω=bω+θ/2,则θ除以2,循环这一过程,最终的θ就是所求的周期μ。令α=-1,β=ω,如果bα+⎣(β-α)/2」=bα+⎣(β-α)/2」+μ,令β=α+⎣(β-α)/2」,否则,令α=α+⎣(β-α)/2」,循环这一过程,直到β-α=1,β就是所求的索引λ。

下面我们研究rho“体”上元素的性质。

性质1 记号如上所示,令M=bjbj+1bj+2bj+ω-1。则对任意整数n>0,X有:

XM≡XMn(modm)

证明:由于:

bj+1≡b $_{j}^{2}$ (modm)

bj+2≡b $_{j + 1}^{2}$ (modm)

bj+ω-1≡b $_{j + ω - 2}^{2}$ (modm)

bj≡b $_{j + ω - 1}^{2}$ (modm)

记M=bjbj+1bj+2bj+ω-1,则M≡M2(modm),所以M3≡M2M≡MM≡M2≡M(modm),同理可证Mn+1≡MnM≡M(modm)。因此对于任意整数n>0,X有:

XM≡XMn(modm)

下面引出rho“体”上元素的另一条性质,在此之前先说明“循环二进位”的概念。向量(t0,t1,t2,,tn)(其中ti∈N)的循环二进位是指把t0,t1,t2,,tn看成二进制的低位到高位,从低位到高位满二进一,到最高位时满二向最低位进一位,循环这一过程直到t0,t1,t2,,tn全部为0或1。例如向量(3,4,6,4)的循环二进位过程为:(3,4,6,4)(1,4+1,6,4)(1,1,6+2,4)(1,1,0,4+4)(1+4,1,0,0)(1,1+2,0,0)(1,1,1,0),则向量(1,1,1,0)即为(3,4,6,4)的循环二进位的结果。

性质2 记号如上所示,对于ti∈N,有b $_{j}^{t_{j}}$ b $_{j + 1}^{t_{j + 1}}$ b $_{j + 2}^{t_{j + 2}}$ b $_{j + ω - 1}^{t_{i + ω - 1}}$ ≡b $_{j}^{n_{j}}$ b $_{j + 1}^{n_{j + 1}}$ b $_{j + 2}^{n_{j + 2}}$ b $_{j + ω - 1}^{n_{j + ω - 1}}$ (modm)。其中(nj,nj+1,nj+2,,nj+ω-1)是(tj,tj+1,tj+2,,tj+ω-1)的循环二进位。

证明:用“%2”表示模2取余,由于b $_{j}^{t_{j}}$ =b $_{j}^{2 ⌊ t_{j} / 2 ⌋ + t_{j} % 2}$ ,而bj+1≡b $_{j}^{2}$ (modm),所以:

b $_{j}^{t_{j}}$ b $_{j + 1}^{t_{j + 1}}$ b $_{j + 2}^{t_{j + 2}}$ b $_{j + ω - 1}^{t_{j + ω - 1}}$ ≡b $_{j}^{t_{j} % 2}$ b $_{j + 1}^{t_{j + 1} + ⌊ t_{j} / 2 ⌋}$ b $_{j + 2}^{t_{j + 2}}$ b $_{j + ω - 1}^{t_{j + ω - 1}}$ (modm)

由于b $_{j + 1}^{t_{j + 1} + ⌊ t_{j} / 2 ⌋}$ =b $_{j + 1}^{(t_{j + 1} + ⌊ t_{j} / 2 ⌋) % 2 + ⌊ (t_{j + 1} + ⌊ t_{j} / 2 ⌋) / 2 ⌋}$ ,而bj+2≡b $_{j + 1}^{2}$ (modm),因此:

b $_{j}^{t_{j} % 2}$ b $_{j + 1}^{t_{j + 1} + ⌊ t_{j} / 2 ⌋}$ b $_{j + 2}^{t_{j + 2}}$ b $_{j + ω - 1}^{t_{j + ω - 1}}$

≡b $_{j}^{t_{j} % 2}$ b(tj+1+⎣tj/2」)%2j+1b $_{j + 2}^{t_{j + 2} + ⌊ (t_{j + 1} + ⌊ t_{j} / 2 ⌋) / 2 ⌋}$ b $_{j + ω - 1}^{t_{j + ω - 1}}$ (modm)

同理bj,bj+1,bj+2,,bj+ω-1中其它前导和后继(bj+ω-1是bj的前导)也有相同性质。用(nj,nj+1,nj+2,,nj+ω-1)表示(tj,tj+1,tj+2,,tj+ω-1)的循环二进位,则:

b $_{j}^{t_{j}}$ b $_{j + 1}^{t_{j + 1}}$ b $_{j + 2}^{t_{j + 2}}$ b $_{j + ω - 1}^{t_{i + ω - 1}}$ ≡b $_{j}^{n_{j}}$ b $_{j + 1}^{n_{j + 1}}$ b $_{j + 2}^{n_{j + 2}}$ b $_{j + ω - 1}^{n_{j + ω - 1}}$ (modm)

下面利用性质1和性质2对模重复平方算法做出改进以适合大指数运算并把这种新方法叫做模重复平方算法的rho算法。

模重复平方算法的rho算法的具体步骤如下:

(1) 令a=1,b0=b,并将n写成二进制:n=n0+n12++nk-12k-1,其中ni∈{0,1},i=0,1,,k-1。

(2) 计算并存储bi,同时使用Floyd循环查找算法查找ω。如果找到ω则停止计算bi,并根据前面的算法计算出周期μ和索引λ;如果ω不存在则令μ=0。

(3) 如果μ为0,按照模重复平方算法的计算步骤从a0计算到ak-1,则bn≡ak-1(modm)。

(4) 如果μ为1,则M=bλ。由性质1,如果bλ=0,则bn≡0(modm);否则,令nλ=1,按照模重复平方算法的计算步骤从a0计算到aλ,则bn≡aλ(modm)。

(5) 如果μ>1,nλ,nλ+1,,nλ+μ-1及其后面的ni每隔μ为一个单位(不足μ位后面补零)平移叠加到一组初始值为0的临时变量tλ,tλ+1,,tλ+μ-1。由性质2,对叠加后的tλ,tλ+1,,tλ+μ-1进行循环二进位,并把tλ,tλ+1,,tλ+μ-1的值分别赋值给nλ,nλ+1,,nλ+μ-1。按照模重复平方算法的计算步骤从a0计算到aλ+μ-1,则bn≡aλ+μ-1(modm)。

3实例

计算320211(mod77)。

用模重复平方算法计算,计算迭代15次,计算如表1所示。

则最终结果为69,在计算中总共计算了24次模乘运算。

使用新方法计算则应该首先计算bi,计算到b8的时候发现b8=b4停止计算bi,进一步计算得到周期为4索引为1。bi的值如表2所示。

对n1,n2,n3,n4及其后面的ni进行平移叠加后得到的值为3,3,2,1,然后进行循环二进位,循环二进位的过程如表3所示。

令n1,n2,n3,n4分别为0,1,0,1 。然后按照模重复平方算法从a0计算到a4,计算过程如表4所示。所得最终结果为69。在计算中总共计算了11次模乘运算。与模重复平方算法相比减少了13次模乘运算。实质上是把320211(mod77)化简为计算321(mod77)。

4算法性能测试

图2显示的是3n(mod77),n在二进制位取全1的情况下新旧算法随着指数位数增加算法消耗时间的比较,所记录的时间是累计循环一百万次的时间。在指数位数很低时,由于模重复平方算法的rho算法中的指数约减运算并没有取得效果,使得效率低于模重复平方算法。但当指数位数增加到一定值后,模重复平方算法的rho算法中计算模幂运算的数量不再增加,所增加的运算量只有运算量很小的指数约减运算。所以最终模重复平方算法的rho算法效率会高于模重复平方算法,并且时间耗费增长率远小于模重复平方算法。rho算法的计算效率随指数位呈震荡现象,每次震荡便是表2中序列bi的一个周期。在一个周期中,指数的二进制位数每增加一位就会增加一次模乘运算,而到了下一个周期在上一个周期中增加的模乘运算又会被算法中的指数约减算法消掉,由于模乘算法在运算中的比重较大,所以在图2中可以看到rho算法的计算效率有随指数位震荡的明显现象。

5结语

新算法的实质是在原模重复平方算法的基础上增加了指数约减算法。模重复平方算法的rho算法更适合大指数运算。新算法在计算过程中会消耗更多的存储空间,所消耗的存储空间主要是用来存储bi序列,但是存储bi序列所消耗的单位存储空间个数不高于指数的二进制位数。该算法测试在软件环境下完成,算法本身有很高的可并行性,加上算法消耗的存储空间不高,使用硬件来设计应该可以取得更好的效果。该算法对底数、指数和模数并没有特殊要求,是一种通用算法。

参考文献

[1]刘晓星,胡畅霞,刘明生.公钥加密算法RSA的一种快速实现方法[J].微计算机信息,2006,22(18):118-119.

[2]郑焕,张彩环,黄勇.基于重复平方的重复二倍算法[J].计算机应用与软件,2007,24(6):154-155.

[3]谢琪.一种新的RSA的快速算法[J].计算机工程,2003,29(2):51-52.

[4]陈恭亮.信息安全数学基础[M].北京:清华大学出版社,2007.

[5]孙淑玲.应用密码学[M].北京:清华大学出版社,2004.

[6]Thomas HC,Charles EL,Ronald LR,et al.算法导论[M].潘金贵,顾铁成,李成法,等译.北京:机械工业出版社,2006.

[7]Alfred J Menezes,Paul C van Oorschot,Scott A Vanstone.应用密码学手册[M].胡磊,王鹏,译.北京:电子工业出版社,2005.

后进生的转化rd 文档第2篇

湍东三中李新强

人们说：转变一个差等生与培养一个优等生同样有价值。作为教师，我深知转化后进生的重要。因此，在工作中，我认真分析每一个差生的具体情况，找出后进的根源，引导其转变思想，改进学习方法，提高学习成绩。现做本学期差生转化计划如下：

一、本班学生分析：

我班现有学生24名，学习差异性较大，学习能力参差不齐。班内差生情况如下：陆某某、沈某某、吴某、元某某、侯某某智力较差的：李某某

纪律较差的：元某、王某某

后进生主要表现在学习不努力，对学习没有信心，基础知识掌握的较差，有的是差在基本技能及创造性发挥上。因此，我把转化后进生工作重点放在转化学生的自信心及创造性上。

二、转化目标：

通过本学期的转化，本班后进生能基本掌握学习的方法，能树立学习态度，对于掌握基本技能起到推动作用。

三、差生的原因

1、由于智力较差或纪律较差，很多问题老师讲数遍，他们照样记不住。

2、缺乏自觉学习的积极性，懒惰贪玩上课不注意听讲。

3、在家庭方面，学生家长有的是对子女溺爱，有的是父母离异，不在孩子身边，有的是学生家长自己没文化，对孩子的学习不能及时辅导，因此，个别学生家庭作业完不成，或完成质量较差，导致学习成绩一直上不来。

四、转化措施：

1、加强对后进生的课上管理，大多数后进生对学习不感兴趣而落下的，因此，教师要管理好后进生上课时经常提问他们。

2、加强对后进生的课后辅导工作，帮助学生对所学知识及时掌握。

3、通过各种方式调动后进生学习的积极性，大多数后进生厌烦学习，教师要改变学生的厌烦心理，必须调动起学生学习的兴趣，由要我学变成我要学。

4、对不同的差生用不同的改进方法，因材施教，把后进生的学习搞上去。

5、经常与学生谈心，教育他们端正学习态度，明确学习的重要性，利用课余时间加强基础知识的讲解和指导。

6、做好耐心细致的思想教育工作和家访工作。

改进的RD算法第3篇

关键词：万维网,信息检索,超链接,矩阵理论

1 引言

在超链接环境下, 最先把链接分析应用到web挖掘的是Dr.Jon.M.Kleinberg, 他提出了HITS算法, 该算法的直观思想非常简单:如果页面A有一个链接指向页面B, 那么页面A的创建者便认为页面B一定包含了一些有价值的信息资源。该算法的实现过程:首先由某一基于关键词查询得到一初始结果集, 然后对结果页面集构建一个包含该结果集合和它邻居页面的一个超链接子图, 该子图通过HITS算法反复的进行迭代计算, 最后收敛以得到每一节点的权威值。该思想后来在IBM Almadem实验室实现, 并把它命名为Clever Algorithm。在有些研究论文里也叫HITS算法

Clever Algorithm对每一页面计算两个非负权重值:权威权重值和h u b权重值, 结果输出具有较大权威权重值和hub权重值的页面, 那些具有较高权威权值的页面很有可能是内容相关的页面, 而那些具有较高权值的hub页面即可能是那些包含有指向内容相关页面超链接的页面。

Kleinberg证明向量a和h最终收敛, 并且它们和权重的初始值设置无关。最后的输出结果页面可以根据权值的不同进行分级。

但是Clever Algorithm存在这么一个问题, 下面我们给出一个简单的例子用来说明, 假定一个四个节点的子图如下:

很明显图中有三个链接P2到P1, P2到P3, P3到P4, 如果对图应用C l e v e r Algorithm, P4的权威权重和P3的hub权重都将收敛为0, 这是一个不正常的分值, 因为从直观上来看, P4的权威权重分值应该有P3来指向, 同样P3指向P4, 它的hub权重也不应该为0。

另外再仔细观察就会发现, 如果把P4从图中去掉, 应用Clever Algorithm算法P1, P2, P3得到的结果将和上面情况的结果是一样的, 因此P4的有无对C l e v e r Algorithm算法也就没有什么意义, 这种情况也是不能接受的。之所以会出现以上问题的重要原因是:权威值和hub值的相互加强只是通过单一的有向链接产生的, 而没有考虑到多重的连续链接情况.本文我们就是探讨如何有效的解决这个问题

1.1 相关的研究工作

自Clever Algorith提出以来, 该算法已成为计算web上权威权值和hub权值的主要方法, 也已有一些改进算法对它做出了新的应用, 但都没有涉及到算法执行过程的本身[1,2,3]。

Brin, 等人[5]考虑了文本内容的相似性, 提出了一个相似链接分析算法, 但该方法并没有对Clever算法本身的执行过程进行改进, 其思想基于文本的相似度比较。

Kumar, [8]提出了HITS-SW算法对它进行了改进, 但该方法只是为了弥补HITS算法的纯链接分析的不足, 把文本内容也考虑到该算法的权值计算当中去, 对解决HITS算法的主题漂移问题有一定的帮助。

文献[10]提出了一个对HITS算法很好的改进思想, 该算法首次提出了HITS算法的多重超链接的问题, 并提出了多重连续链接可行性矩阵概念。但是, 该方法的时间复杂度有待进一步改善, 本文主要是继承该算法的思想然后应用warshall算法对该算法的时间复杂度进行改进。

2 新算法

在新算法中, 主要要考虑如何能够解决链接图中多重连续链接的问题, 本文引入了一个新的矩阵用来代替C l e v e r Algorithm算法中的邻接矩阵, 为了考虑到多重连续链接, 也即从一个页面Pi到Pj, 其中可能经过的所有路径的可能性, 本文的方法是要能计算出这种可能性以更新计算的权威分值。因为新方法主要用到warshall算法, 下面首先介绍图论中的warshall算法。

2.1 warshall算法

warshall算法是用来判定有向图G中的两节点间是否存在道路, 或者判定它是否连通。

设A= (aij) n×n是G的邻接矩阵。由A的定义, aij=1表示 (vi, vj) ∈E (G) , 即vi可以通过某条边到达v, 或者说G中有道路从vi到达vj, 根据矩阵乘法, 设A2= (aij (2) ) , 有

aij (2) ≠0当且仅当存在k, 使αik=αkj=1, 也就是说, 如果G中存在节点vk, 满足 (vi, vk) , (vk, vj) ∈E (G) , 即经过两条边 (vi, vk) , (vk, vj) , vi可以到达vj时, aij (2) ≠0。同理, Al ( (l≤n) 中的元素aijl≠0表示了vi可以经过l条边到达vj。因此令

如果Pij=t, 说明vi有t条道路可以到达vj.若Pij=0, 即n步之内vi不能到达vj则在G中不存在vi到达vj的道路。否则, 若vi经过l (l>n) 步可达vj, 由抽屉原理, 该道路上一定存在重复出现的节点vk, 而vk之间的这段路一定是一个回路, 去除这段回路, vi仍然可以到达vj。由于G中存在n个不同的节点, 所以只要vi有道路到vj, 则一定有Pij=0.

在许多实际问题中, 往往只要求了解vi与vj之间是否存在道路。对此可以采用逻辑运算的方法, 即

相应的

就是图G的道路矩阵。

但是用上述方法求G的道路矩阵, 计算复杂性为O (n4) .以下介绍的Warshall算法是一个更好的方法, 其计算复杂性是O (n3) 。

Warshall算法

2.2 相关定义及新算法

定义1:设图G= (V, E) 是超链接图, V={P1, P2, …, Pn}, 这里的n>1, 设P为超链接图的可行性矩阵;矩阵P中的每一项 (i, j) 要么取值1要么为0, 如果从Pi到Pj存在有向链接, 则为1。否则为0。

定义矩阵H为多重连续链接可行性矩阵, H中每一项 (i, j) 表示从节点Pi到Pj的可行性。

定义2:多重连续链接可行性矩阵:

这里H计算的复杂度非常重要。如果按照传统的矩阵相乘的方法, 那么它的时间复杂度将是我们上面说的O (n4) .但是, 在这主要目的是要获得两节点之间是否存在着有向路经, 所以可以应用上面的Warshall算法来计算获得多重连续可行性矩阵H..复杂度将减少到O (n3) 。

本文改进的整个算法发现权威分值的过程如下:

首先由一初始集构建一连通的超链接图G= (V, E) , 其中的V={P1, P2, …, Pn}, 这里的n>1。

然后获得超链接可行性矩阵P, 再应用Warshall算法计算多重连续链接可行性矩阵H。对每一个V中的节点Pi, 设α[i]为它的权威值, h[i]为它的hub分值, V中所有节点的α[i]和h[i]初始值为1。反复计算如下向量α和h直至收敛:

3 主要的理论依据

下面进一步说明新方法在计算权威分值和h u b分值的理论可行性和结果唯一性。

定义3:超链接图G的权重分布定义为一有序向量对 (α*, h*) , 这里的α*是一个n维的向量元素为非负的列向量 (又叫做权威权值向量) , h*是另一个向量元素为非负的n维向量 (又叫h u b权值向量) , 且有α*=HTh*/||HTh*||和h*=Hα*/||Hα*||。

提示:||·||是向量范数, (α*, h*) 对实际上是权威分值和hub分值所期望的平衡值, 以上的两个等式是权威分值和hub分值得以相互加强的基本方法。

如果 (α*, h*) 是一个超链接图G的权重分布, 那么α*就是对应于矩阵HTH的一个非负特征值的一个特征向量, 因为对一个连通的超链接图都有一个确定的矩阵HTH, 应用矩阵理论原理很容易得知矩阵HTH的最大特征值也是很简单的, 它的一个特征向量正是我们要找的α*。

主要理论:任意一个连通的超链接图都有一个唯一的超链接权重分布, 本文算法的收敛性将以α→α*和h→h*得到保证。

4 例子和结论

下面用几个web试验例子对新的方法和Clever Algorithm进行了比较, 发现新算法得出了令人信服的结果, 这里仅仅给出两个简单的例子, 第二个例子是从一个实际的web搜索结果获得的。

例子1:以前面给出的四个节点图P1←P2→P3→P4为例。

例子2:另外一个4节点的图

一种改进的变异粒子群算法研究第4篇

粒子群优化算法PSO(Particle Swarm Optimization)是一类性能优越的寻优算法.但由于早熟问题,影响了算法性能的发挥.针对这一问题,引入粒子距离的概念,提出一种新的PSO改进方法(称为NA-PSO).通过求解组网雷达的系统偏差,表明了NA-PSO算法的`可行性,与对比方法相比较,能有效配准,且具有更好的收敛精度和更快的进化速度.

作者：王波李瑞涛王灿林朱丹 WANG Bo LI Rui-tao WANG Can-lin ZHU Dan 作者单位：王波,李瑞涛,王灿林,WANG Bo,LI Rui-tao,WANG Can-lin(海军航空工程学院,山东,烟台,624001)

朱丹,ZHU Dan(91550部队,辽宁,大连,116023)

改进的RD算法第5篇

支持向量机(Support vector machine, SVM)[1,2]是Vapnik等人于20世纪90年代提出的一种新的机器学习方法。它基于VC维理论和结构风险最小化原则,具有很强学习能力和泛化性能,解决了以往机器学习中存在的小样本、非线性、过学习、高维数等问题。由于这些优点,SVM已经在模式分类等领域取得了广泛的应用。

标准的SVM的训练算法涉及到求解线性约束的二次规划问题。二次规划问题求解受存储器容量和计算量的限制,当训练数集规模很大时,分类速度会受到很大影响,甚至无法完成。所以常规的高效的训练算法往往是将一个问题分解成若干个子问题,然后逐一求解优化。主要有Vapnik提出的chunking[2],Osuna提出的deposition[3]以及Platt提出的SMO[4]。这样做的的缺陷是结果可能得到的是一个次优解,而且可能需要多次分解才能达到为可解决的范畴。

混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)[5]是2000年由Eusuff和Lansey提出的一种基于群体智能的优化算法,根据全局信息交换和局部深度搜索的平衡策略来找到最优解[6,7]。用群体智能优化算法[8]训练SVM是一种全新的探索。Paquet等人首先提出将粒子群优化算法用于SVM训练[9],但结果并不理想。

本文提出用一种改进的混合蛙跳算法(ISFLA)训练SVM。该算法在SFLA基础上引入模拟退火思想,极易跳出局部最优解,改善了收敛精度和速度,且具有较强鲁棒性。并通过实验证明提出的算法具有良好的性能。

2 支持向量机简介

支持向量机最早应用于模式分类。不失一般性,以线性可分两分类问题为例。训练集包括L个训练样本:T={(x1, y1), , (xL, yL)} xi∈X=Rn, yi∈Y={1, -1}。其中X为输入,Y为输出。训练过程就是寻求一个平面wx+b=0,使两类数据点距离平面尽量远。这种最优分类面思想导致了对w和b的最优化问题:

$\min_{w, b} = \frac{1}{2} ∥ w ∥^{2}$

yi{(wxi)+b}≥i, i=1, , L (1)

根据最优化理论,原始问题可转化为对偶问题来求解。因此式(1)可转化为式(2)求解。

$\min_{a} = \frac{1}{2} \sum_{i = 1}^{L} \sum_{j = 1}^{L} y_{i} y_{j} a_{i} a_{j} (x_{i} x_{j}) - \sum_{j = 1}^{L} a_{j}$

st: $\sum_{i = 1}^{L} y_{i} a_{i} = 0 (2)$

ai≥0, i=1, , L

求解得到最优分类规则

$f (x) = sgn {\sum_{i = 1}^{L} y_{i} a_{i} (x_{i} x) + b} (3)$

在非线性可分问题中中,引入松弛变量ξ(ξi≥0),和惩罚系数C′,使式(1)优化问题转变为

$\min_{w, b, ξ} = \frac{1}{2} ∥ w ∥^{2} + C^{'} \sum_{i = 1}^{L} ξ_{i}$

st:yi{(wxi)+b}+ξi≥1 (4)

ξi≥0;i=1,,L

其对偶问题可转变为式(5)

得到最优分类规则

$f (x) = sgn {\sum_{i = 1}^{L} y_{i} a_{i} Κ (x_{i} x) + b} (6)$

在式(6)中不为零的ai即为支持向量。SVM利用核函数方法将低维数据非线性映射到高维,使其线性可分,并由支持向量及其系数构造最优分类面。

3 改进的混合蛙跳算法训练SVM

3.1 SFLA算法

在一个D维的目标搜索空间中,随机生成P只青蛙(解)组成初始群体,第i只青蛙表示问题的解为Xi=(xi1,xi2,,xiD)。青蛙个体按适应度值从优到劣排列,将整个群体分为M个子群体。其中排名第1的青蛙分入第1子群体,排名第2的青蛙分入第2子群体,第M只青蛙分入第M子群体,第M+1只青蛙分入第1子群体,第M+2只青蛙分入第2子群体,依次类推,直到全部青蛙划分完毕。

每个子群体进行局部深度搜索,即在子群体的每次迭代中,首先确定当前迭代中子群体的最差个体xw、最好个体Xb和全局最好个体Xg,只对该子群体当前最差的个体Xw进行更新,更新策略为:

Di=rand()*(Xb-Xw)(-DmaxDiDmax) (7)

newXw=Xw+Di (8)

其中,rand()是均匀分布在[0,1]之间的随机数;Dmax表示青蛙所允许更新步长的最大值。如果newXw的适应度值优于原来的Xw,则取代原来种群中的解。如果没有改进,则用Xg取代Xb重复执行更新策略(7)(8)。如果仍没有改进,则随机产生一个新的解取代原来的Xw。重复这种更新操作,直至满足子群体的更新代数。当所有子群体的局部深度搜索完成以后,将所有的青蛙个体重新混合排序并再次划分子群体,然后再进行局部深度搜索,如此反复直到满足混合迭代次数。

3.2 模拟退火算法

SA算法的思想是由Metropolis在1953年提出的[10,11,12],它是一个全局最优算法,具有并行性,并且以概率1接近最优值[13]。SA来源于固体退火过程,当固体的温度充分高时,内部粒子变为无序状,内能较大,随着固体缓慢冷却,其内部粒子渐趋有序,内能逐渐减小;在每个温度都会达到平衡态,最后在常温时达到基态,内能减为最小[14,15]。此算法将优化问题比拟成一个物理系统,将优化问题的目标函数比拟为物理系统的能量,通过模拟物理系统逐步降温以达到最低能量状态的退火过程而获得优化问题的全局最优解[16,17,18]。具体步骤如下:

(1) 初始退火温度Tk(k=0),产生随机初始解X。

(2) 在温度Tk下重复执行如下操作,直至达到温度Tk的平衡状态:

在解X的领域中产生新的可行解X′;计算X′的目标函数f(X′)和X的目标函数f(X)的差值Δf;依照概率min{1,exp(-Δf/Tk)}>rand()接收X′,其中rand()表示[0,1]内的随机数。

(3) 退火操作:Tk+1=C*Tk,k←k+1,其中C∈(0,1)。若满足收敛判据,则退火过程结束;否则,转(2)。

本文利用公式x′=x+ηξ产生新解,式中η为扰动幅值参数,ξ为随机变量,一般服从正态分布。SA通过退火机制所得的子代,即随着温度的下降,接受劣解的概率逐渐减小,从而提高算法的性能。

3.3 改进的SFLA算法在SVM训练中的应用

SVM训练的数学本质即为求解支持向量系数,适应度函数为

$f (a_{i}) = \frac{1}{2} \sum_{j = 1}^{L} a_{i} a_{j} y_{i} y_{j} Κ (x_{i}, x_{j}) - \sum_{i = 1}^{L} a_{i} (9)$

用改进的SFLA算法训练SVM基本流程如下:

(1) 初始化蛙群,个体初始位置为[0,C′]间的随意数,种群个体总数N,个体的维数m,子种群个数M,子群局部搜索迭代次数cyc,退火的初始温度T,温度冷却系数C,扰动幅值η。

(2) 计算每个个体的适应度值,规定若某个个体位置不满足 $\sum_{i = 1}^{L} a_{i} y_{i} = 0$ ,则定义该个体的适应度值为1e8,否则保持适应度值不变。

(3) 将当前所有个体的适应度值从优到劣排序,依次将个体划分到各子种群。

(4) 利用SFLA的更新策略,对子种群的最差个体进行更新,获得一个较优解X。

(5) 利用SA算法,产生新解X′,利用退火机制比较X和X′的质量,获得较优解。

(6) 对该子种群适应度值排序,然后转步骤(4),重复该更新策略,直至子种群内的迭代次数满足事先给定的要求cyc。

(7) 当所有子种群完成了更新操作后,若当前最优个体满足收敛条件,则进化过程成功结束,返回全局最优解;否则修改种群的退火温度,即令T=C*T,转步骤(3)。

4 实验结果与分析

在此给出3组实验结果。第1组数据来自Breast-cancer数据集,第2组来自Iris数据集,第3组来自Heartstatlog数据集。这3个数据集均来自UCI数据库。

试验中SVM核函数采用高斯核函数:

$Κ (x, y) = \exp (- \frac{∥ x - y ∥^{2}}{2 σ^{2}}) (10)$

改进的SFLA的参数如下:种群大小100,子群内个体数量20,子群体内迭代次数30,退火的初始温度10,基态温度1,降温系数0.8,扰动幅值η为5。

(1) Breast-cancer数据集分类实验。本数据集中训练样本100个,测试样本100个。由经验取C′=10,σ=4。分别用st_svm(标准SVM)、sfla_svm和imsfla_svm三种方法得到分类结果如表1所示。

(2) Iris数据集分类实验。本数据集中训练样本50个,测试样本50个。由经验取C′=100,σ=2。分别用st_svm(标准SVM)、sfla_svm和imsfla_svm三种方法得到分类结果如表2所示。

(3) Heartstatlog数据集分类实验。本数据集中训练样本50个,测试样本100个。由经验取C′=100,σ=50。分别用st_svm(标准SVM)、sfla_svm和imsfla_svm三种方法得到分类结果如表3所示。

以Heartstatlog数据集分类实验为例,图1表现了标准sfla和改进的sfla在分类中的演化过程。

由表1-3看出,本文提出的基于改进的SFLA算法训练获得的识别率和标准SVM训练方法相当,比SFLA算法训练的性能有较大提高。由图1可以看出,改进的SFLA算法能够快速收敛,得到很高的识别率,而标准SFLA算法在第二步后就陷入局部极值,无法继续跳动,从而识别率较低。因为模拟退火方法以某种概率接收较差的个体,所以具有跳出局部最优解的能力,在一定条件下能以概率1收敛到全局最优值。

5 结束语

本文提出将混合蛙跳算法引入到SVM训练中,并提出一种改进的混合蛙跳算法,提出了加入模拟退火的蛙跳算法。以不同的概率接受较好的和较差的个体,使蛙跳具有跳出局部最优的能力,同时也加快了收敛速度,使训练算法的性能获得很大提升。通过实验,也证明了用群体优化算法作为SVM的算法作为一种新的方向具有良好的效果。

摘要：支持向量机的训练需要求解一个带约束的二次规划问题,但在数据规模很大情况下,经典训练方法将变得很困难。本文提出一种基于改进的混合蛙跳算法的SVM训练算法。针对混合蛙跳算法搜索速度慢且容易陷入局部极值的缺陷,将模拟退火思想引入到混合蛙跳算法中,提出一种改进的混合蛙跳算法。该算法保持了混合蛙跳算法参数少和容易实现的特点,同时通过模拟退火的降温过程来提高算法的进化速度和精度。实验结果表明,该算法能显著提高收敛速度,并能有效克服局部极值,在SVM训练中具有良好效果。

改进的RD算法第6篇

云计算概念自2007 年提出后产生了巨大的影响, 全世界都把云计算作为重点新兴战略产业, 为抢占云计算制高点, 很多国家都研制并且出台了云计算的战略规划, 加快部署并推动国家级的云计算相关应用和云计算基础设施, 同时也成为工业界和学术界的研究热点[1,2]。

云计算的关键技术是资源调度技术, 由于虚拟化技术[3]的引入, 云资源调度以虚拟机为单位进行, 将物理资源分配给用户任务对应的虚拟机。由于系统规模增大导致系统具有复杂性、多样性、异构性和动态性等特征, 使得云数据中心基于虚拟机的资源调度充满挑战性, 同时也决定了虚拟机放置问题是一个NP-hard问题[4]。在云环境中, 虚拟机放置时间比调度算法所需的时间长得多, 因此云资源调度需要考虑的主要是虚拟机如何放置的问题。

数据中心服务器的负载是影响系统性能的瓶颈, 由于CPU时间分片和网络等影响, 服务器负载较高时运行任务具有较长的平均完成时间[5], 因此保证数据中心的负载均衡很重要。现有一些算法[6,7,8]往往只关注成本控制和云资源使用率, 忽略了负载均衡对系统性能的影响, 虽然在一定程度上缓解了云资源与用户需求的矛盾, 但云数据中心的资源规模大、资源间差异大、组成复杂等问题直接导致数据中心资源的浪费, 现如今还没有很好的虚拟机放置算法快速实现数据中心的负载均衡, 因此研究先进的虚拟机放置算法具有重要的现实和学术意义。

1 问题描述

1.1 云资源调度模型

根据云计算的特点, 建立云资源调度三层结构二级调度模型如图1 所示。三层结构分别为用户层、虚拟层和物理层。二级调度为任务调度和虚拟机调度, 任务调度为第一级调度, 发生在在用户层和虚拟层之间;虚拟机调度为第二级调度, 发生在虚拟层和物理层之间。虚拟资源的调度和分配策略是云计算的核心问题[9], 本文主要研究云环境下二级调度过程中的虚拟机资源分配, 即将虚拟机放置到满足条件的服务器上。

1.2 基本定义

定义1:云环境中的虚拟机资源调度是将M个虚拟机部署到N个物理机上, 映射模型相当于将M个不同元素放到N个不同元素的集合, 共有NM种解决方案, 该问题属于装箱问题, 即给定集合PM{P1, P2, ……, PN}和集合VM{V1, V2, ……, VM}, 把VM中的M个元素放到PM的N个元素中, 保证使用的PM中元素数量最少。

定义2:N为云数据中心物理机的数量, Nuse为数据中心中已经占用的物理机的数量;Uuse为数据中心物理机CPU的平均利用率, Uiuse为物理机i中CPU的利用率;Muse为数据中心物理机的内存平均利用率, Miuse为物理机i中内存的利用率;Suse为数据中心物理机总存储的平均利用率, Siuse为物理机i中硬盘的利用率。

物理机部署的虚拟机会占用一定数量的CPU、内存和硬盘空间, 因此在定义1中的集合PM中的元素要满足几个约束条件:Nuse≤N, 0≤Uiuse≤1, 0≤Miuse≤1, 0≤Siuse≤1。

定义3:为了衡量云计算数据中心的负载均衡率, 定义E为云计算平台中负载不均衡度, 。可以看出负载不均衡度E的值越小, 表示系统负载越均衡。

定义4:需要定义物理机负载的两个阈值, 本文以物理机的CPU利用率来定义阈值, 即物理机负载最低阈值Tmin和负载最高阈值Tmax, 分别为20%和80%, 物理机负载率在Tmin~Tmax之间的状态称为平衡状态。

1.3 目标函数

为避免数据中心的资源浪费, 达到负载均衡, 根据上小节基本定义, 定义目标函数如下:

(1) f1= Min (Nuse) , f1 表示将虚拟机分配到物理机后, 保证使用的物理机数量最少;

(2) , f2表示将虚拟机分配到物理机后, 保证物理机资源利用率最大化;

(3) f3= Min (E) , f3表示将虚拟机分配到物理机后数据中心的负载不均衡度函数, 其中E即上文1.2 定义的负载不均衡度, 该函数表示E值越小表示系统越平衡。

2 基于改进粒子群算法的虚拟机放置算法

2.1 粒子群优化算法介绍

1995 年由美国博士Kennedy和Eberhart[10]通过研究鸟群觅食行为提出粒子群算法 (Particle Swarm Optimization, PSO) 。设想场景:一群鸟在随机搜寻食物, 区域内仅有一块食物, 所有鸟都不知道食物在哪里, 但它们知道当前位置离食物多远, 那么找到食物最有效的策略就是搜寻目前离食物最近鸟的周围区域。PSO算法是一种基于群体的自适应搜索优化算法。算法中每个优化问题的潜在可能解都称其为“粒子” (Particle) , 每个粒子都有一个被目标函数所决定的适应值 (Fitness Value) , 还有一个速度决定飞翔的方向和距离。每个粒子均受局部最优信息和全局最优信息影响, 以一定速度在整个解空间飞行, 飞行速度和位置由个体飞行经验和群体飞行经验动态调整, 以便用于信息交换。通过大量实验研究, 证实了群体中个体之间的社会协作和信息共享有助于整体进化[11], 用公式表示如下:

其中, 1≤d≤D, 1≤i≤N, D为搜索空间的总维数, N是粒子群内粒子的个数;xi= (xi1, xi2, …, xi D) t表示粒子i的当前位置;vi= (vi1, vi2, …, vi D) t表示粒子i的当前速度;pt id = (pi1, pi2, …, pi D) t是第t时刻粒子i本身的最优位置的第d维变量, 即它经历过的最好位置;pt gd = (Pg1, Pg2, …, Pg D) t是第t时刻粒子群全局最优位置的第d维变量, 即在群体所有微粒经历过的最好位置;ω 是惯性权重;c1、c2是学习因子;r1、r2是均匀分布在[0, 1]区间的随机数。

虽然标准PSO算法优点很多, 但是随机性很大, 多样性比较差, 很容易陷入局部最优现象, 因此需要完善, 下面将介绍本文改进的粒子群算法。

2.2 基于改进粒子群算法的虚拟机放置算法

2.2.1 算法设计

1.粒子群算法编码

首先对n个待部署虚拟机进行编码形成队列, 然后通过虚拟机放置算法得到虚拟机与数据中心m个物理机的映射关系, 最后按照映射关系将虚拟机放置到对应物理机上, 从而实现优化目标。种群中的每个粒子的位置和速度分别用公式 (3) 和公式 (4) 表示, 如下所示:

公式 (3) 中xij表示第i个粒子代表的第j个虚拟机在第t次迭代时放置的物理机节点编号。公式 (4) 中vij代表第i个粒子在第t次迭代的第j维速度。为了避免粒子产生过度偏移现象, 用vmax来限制粒子飞行范围。所有粒子的速度和位置每次迭代通过公式 (1) 、 (2) 更新。

2.分析与设计惯性权重 ω

影响算法搜索结果和收敛速度的关键参数就是ω, 经过先前的大量实验研究, ω 过大有利于全局寻优, ω 过小有利于局部寻优。根据 ω 取值对搜索结果的影响, 可以采用经典的线性递减方式设定 ω 的值如公式 (5) 所示。

其中, ωmax一般取0.9;ωmin一般取0.4;num为最大迭代次数;t为当前迭代次数。ω 随着迭代次数的增加而减小, 且递减速率在变缓, 有利于从全局搜索转变为局部搜索, 并保证算法不会过快收敛。

3.确定算法的适应度函数

根据1.3 提出的算法目标, 通过对目标优化要求的不同设定相应的权值, 实现多目标优化。本算法的目标是在迭代次数范围内找到使适应度函数值最小的资源分配方案, 即最终的虚拟机放置方案。适应度函数可以定义如下公式:

4.种群初始化引入按资源需求和实时负载分配的思想

根据虚拟机对资源的需求情况选择能够满足其要求的物理机, 即所选的物理机一定要满足虚拟机对资源的需求, 同时根据1.2 的定义4 物理机部署虚拟机后不至于过载。

5.引入分组思想

首先将种群随机分成若干份等量的小粒子群, 然后在每一个子群里随机设置参数, 进行粒子群优化算法寻优, 最后再对全部最优解取最小值为最终最分配方案。

2.2.2 算法步骤

Step1:按照初始种群方案生成有M个粒子的种群, 每个粒子编号为1 到M, 将M个粒子随机分成N个独立的子群空间, 每个子群的粒子个数为m =M/N;

Step2:在每一个子群中执行标准PSO, 初始化各参数, 其中xi= (xi1, xi2…xij…xin) 0, n为待放置虚拟机数量, i=1, 2, …, m, vi= (vi1, vi2…vi j…vin) 0;pibest= (xi1, xi2…xij…xin) 0, pqbest=min (p1best, p2best, …, pqbest, …, pmbest) ;

Step3:根据适应度函数公式 (6) 依次计算每个子群中每个粒子的适应值F;

Step4:对于每个粒子, 比较个体当前适应值和历史最优位置pibest, 如果当前适应值较好, 则将此粒子当前的位置作为当前最优的位置并更新pibest, 否则保持pibest不变;

Step5:对于每个粒子, 比较当前最优位置pibest和子群体中整体的最优位置pqgbest, 如果当前最优位置较好, 则将其作为当前群体最优位置并更新pqgbest, 否则pqgbest不变 (q=1, 2...N) ;

Step6:根据公式 (1) 和公式 (2) 更新每个粒子的速度和位置信息;

Step7:判断迭代次数num是否达到最大值, 若达到则结束循环, 再比较所有子群的最优位置的适应度值, 取最小值得到整个粒子群的最优位置, 即pgbest= min (p1gbest, p2gbest, …, pqgbest, …, pNgbest) ;否则转至第三步继续。

3 仿真实验

3.1 实验环境和参数设置

为了验证基于分组的粒子群优化算法GPSO在云环境下虚拟机资源分配问题上的可行性, 本文扩展了Cloud Sim平台进行仿真实验, 并与轮询算法Round Robin和标准的PSO算法进行了比较。参数设置如表1、表2 所示。

3.2 结果与分析

3.2.1 负载不均衡度E的比较

系统的负载不均衡度随着虚拟机数量的增加而减小。图2 表示三种算法分别在不同虚拟机规模时系统的负载不均衡度。由图2 可知GPSO算法的负载不均衡度E小于其他两个算法, 说明GPSO算法在负载平衡方面的性能优于其他两个算法。这是因为PSO算法初始种群是随机生成的, 而GPSO算法的初始种群是根据系统的实时负载随机生成, 并将负载不均衡度作为目标函数进行搜索。轮询算法没有考虑物理机实时负载, 也没有优化目标策略。

3.2.2 资源利用率比较

如图3 所示, GPSO算法比其它两种算法的资源利用率更高, 这是因为目标函数包含了对系统资源利用率的优化策略, 从而一定程度上避免了系统资源的浪费。

4 结论

本文针对现有虚拟机资源放置算法只考虑云资源的能耗和使用率, 忽略负载均衡对系统性能影响的问题, 提出了基于分组的改进粒子群算法 (Grouped Particle Swarm Optimization:GPSO) , 通过最小化云数据中心的负载不均衡度达到系统的负载平衡。与标准粒子群算法中随机生成初始种群的方式不同, 本文根据系统的实时负载来随机生成初始种群, 在算法中引入分组的思想, 将该种群进行随机分组, 通过比较各组的全局最优解得到最终分配方案。通过Cloud Sim平台仿真实验表明, 改进算法生成的资源分配方案较原算法能有更好的负载均衡、更高的资源利用率, 证实了该算法的有效性。

摘要：云计算通过使用虚拟机技术提高了数据中心的资源利用率。虚拟机放置算法作为云计算的关键技术, 具有重要研究意义。现有虚拟机放置算法往往只关注成本控制和云资源使用率, 忽略了负载均衡对系统性能的影响。针对该问题, 本文在标准的粒子群优化算法基础上进行改进, 首先设计多目标函数时引入负载不均衡度概念, 然后通过系统实时负载随机生成初始化种群, 并在算法中引入分组思想, 通过对初始种群进行随机分组, 避免算法陷入早熟现象。通过Cloud Sim模拟平台进行仿真实验, 表明改进后的算法更利于云数据中心进入负载均衡状态, 并有较高的资源利用率。

关键词：云计算,虚拟机放置,负载均衡,多目标优化,粒子优化群算法

参考文献

[1]钱琼芬, 李春林, 张小庆, 等.云数据中心虚拟资源管理研究综述[J].计算机应用研究, 2012, 29 (7) :2411-2415.

[2]王倩, 曹彦.云计算研究[J].软件, 2013, 34 (5) :116-118.

[3]丁养志.浅析虚拟化技术在云计算中的运用[J].软件, 2014, 35 (3) :176-177.

[4]Garey Michael R, Johnson David S.Computers and intractability-a guide to the theory of np-completeness[J].W H Freeman co, 1979, 25-31.

[5]李建锋, 彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用, 2011, 31 (1) :65-69.

[6]米海波, 王怀民, 尹刚, 等.一种面向虚拟化数字中心资源按需重配置方法[J].Journal of Software, 2011, 22 (9) .

[7]林伟伟, 齐德星.一种基于动态重配置虚拟资源的云计算资源调度方法[P].中国201010268105.7, 2001.01.05.

[8]华夏渝, 郑骏, 胡文心.基于云计算环境的蚁群优化计算资源分配算法[J].华东师范大学学报, 2010, 1 (1) :127.

[9]张栋梁, 谭永杰.云计算中负载均衡优化模型及算法研究[J].软件, 2013, 34 (8) :52-55.

[10]KENNEDY J, EBERHART R C.Particle swarm optimization[C]//Proceedings of International Conference on Neural Networks.New York:IEEE, 1995, 1942–1948.

RSA算法的改进第7篇

公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲(Diffie)和赫尔曼(Hellman)两人首先发明的,但目前最流行的RSA是由分别取自三位发明此算法的数学家Ronald Rivest、Adi Shamir和Len Adleman的名字的第一个字母来构成的。[1]

RSA已被国际上一些标准化组织如ISO、ITU等作为标准采用,现在流行的PGP也采用RSA算法作为其解密和数字签名算法。它是第一个既能用于数据加密也能用于数字签名的算法。

但RSA的安全性一直未能得到理论上的证明。RSA的安全性依赖于大数难于分解这一特点。据猜测,从一个密钥和密文推断出明文的难度等同于分解两个大素数的积,并且RSA的加密算法速度与对称加密算法相比,其速度非常缓慢的。因此,研究快速的RSA算法是十分有意义的。

至今,人们在此方面已经作了很多的研究,提出了许多快速的RSA算法。其中分块模幂算法[2],幂等价代换的改进[3]及SMM算法[4]等都极大地提高了RSA加密算法的速度。

2. RSA算法的基本原理

RSA体制用户i的公开加密变换Ei和保密的解密变换Di的产生:

(1)随机选取素数pi和qi;

(2)计算ni=piqi,Ф(ni)=(pi-1)(qi-1);

(3)随机选取整数ei满足(ei,Ф(ni))=1;

(4)利用欧几里得算法计算di,满足eidi≡1MODФ(ni);

(5)公开ni,ei作为Ei,记为Ei=,保密pi,qi,di,Ф(ni)作为Di,记为Di=。

加密算法:c=Ei(m)=mei(MOD ni);

解密算法:m=Di(c)=cdi(MOD ni)。

在RSA算法中,包含两个密钥:加密密钥PK和解密密钥SK,加密密钥公开。[5]

3. RSA算法的举例

要对2运用RSA算法进行加密,因为RSA的原则是被加密的信息应该小于p和q的较小者,因此取p=5,q=3,求得n=p*q=5*3=15,m=(p-1)*(q-1)=(5-1)*(3-1)=8,然后生成较小的数e,使e与8互质,2不对,3是最小的,于是e=3,最后生成d,使d*e MOD m=1,d*3 MOD8=1,d*3除以8余数为1,于是算出d=3,所以求出公钥e=3,n=15,私钥d=3,n=15,密钥计算完毕。

加密:c=pe%n=23%15=8%15=8,于是密文为8,把8传出去。同时应把公钥也传出去,好在收到时知道对应的是那个私钥。

解密过程:接收者收到密文和公钥,找到对应的私钥:p=cd%n=83%15,经过运算,余数为2。

4. RSA算法的改进

4.1 RSA改进算法的三重性

由于RSA算法是基于大数分解的理论,应用了费尔马小定理[123123123],在两个素数qi和pi的乘积n被分解是最主要的攻击方法,因此提出了三重RSA算法:用户j的公开加密变换Ej和保密的解密变换Dj的产生:

(1)随机选取三个素数pj、qj和rj;

(2)计算nj=pj*qj*rj,Ф(nj)=(pj-1)(qj-1)(rj-1);

(3)随机选取整数ej满足(ej,Ф(nj))=1;

(4)利用欧几里得算法计算dj,满足ei*di≡1 MODФ(nj);

(5)公开nj,ej作为Ej,记为Ej=,保密pj,qj,rj,dj,Ф(nj)作为Dj,记为Dj=。

加密算法:c=Ej(m)=mej(MOD nj);

解密算法:m=Dj(c)=cdj(MOD nj)。

在RSA算法中,包含两个密钥:加密密钥PK和解密密钥SK,加密密钥公开。

由于三重的RSA算法成立,原来的RSA算法也成立,因此推断N重RSA算法即:用户x的公开加密变换Ex和保密的解密变换Dx的产生:

(1)随机选取N个素数p1、p2pn;

(2)计算nx=p1*p2*pn,Ф(nx)=(p1-1)*(p2-1)**(rj-1);

(3)随机选取整数ex满足(ex,Ф(nx))=1;

(4)利用欧几里得算法计算dx,满足ex*dx≡1 MODФ(nx);

(5)公开nx,ex作为Ex,记为Ex=,保密p1,p2,,pn,Ф(nx)作为Dx,记为Dx=。

加密算法:c=Ex(m)=mex(MOD nx);

解密算法:m=Dx(c)=cdx(MOD nx)。

在N重RSA算法中,同样也包含两个密钥:加密密钥PK和解密密钥SK,加密密钥公开。

下面对N重RSA算法给与证明。

应用2.2中提出的定理1:

若p,q是相异质数,d*e==1MOD(p-1)(q-1),a是任意一个正整数b==ae MOD p*q,c==bd MOD p*q,则c==a MOD p*q。

可以得出推论1:

若p1,p2,,pn是相异质数,d*e==1MOD(p1-1)*(p2-1)**(pn-1),a是任意一个正整数b==ae MOD p1*p2**pn,c==bd MOD p1*p2**pn,则c==a MODp1*p2**pn。

证明推论1的过程中过程如下:

由n(n>=2)个质数时,推论1成立。

当n+1时d’*e’==1 MOD(p1-1)*(p2-1)**pn*(p(n+1)-1)a’是任意一个正整数

因此通过(1)(2)式可以得到方程组

由于里面的a’、b’、p1,p2,,pn,p(n+1)都是已知数,就c’是未知数,所以可以求得c’==b’d’MOD p1*p2**pn*p(n+1)因此可以知道推论1成立。

可以证明N重RSA算法的正确性,因为N重RSA算法是正确的所以三重的RSA算法想当然是正确的。

4.2 RSA改进算法的性能

RSA算法使用方便,尤其是公开密钥的特征使得用户在数据传输之前无需交换密钥,就算是和多个用户进行秘密通信,也没有必要记住所有的密钥,N个用户通信,要有N对密钥,每个用户只需记住自己的密钥,并到公共存储区去取得其他公钥就可以了。

但是,由于RSA算法的实现是以大素数来为基础,依赖于计算机的速度和容量,效率比较低。根据统计,对相同数据块的加密,对称算法比RSA算法的效率要高几十倍。

改进的N重RSA算法中,由于所取得素数比较多,取多少个也是有应用N重RSA算法的用户决定的,所以就可以把所取得素数的大小取得小一点,这样就提高了计算机的运算速度,加快了RSA算法的运算效率。由于N重RSA算法根本没有违背RSA算法,所以其安全性也是毋庸置疑的。

4.3 RSA改进算法举例

要对2运用N=3的N重RSA算法进行加密,取p1=5,p2=3,p3=7,求得n=p1*p2*p3=105,m=(p1-1)*(p2-1)*(p3-1)=(5-1)*(3-1)*(7-1)=48,然后生成较小的数e,使e与48互质,2不对,5是最小的,于是e=5最后生成d,使d*e MOD m=1,d*5 MOD 48=1,d*3除以48余数为1,于是,算出d=29,所以,求出公钥e=5,n=105,私钥d=29,n=105,密钥计算完毕。

加密:c=pe%n=25%105=8%105=8,于是密文为8,把8传出去。同时应把公钥也传出去,好在收到时知道对应的是那个私钥。解密过程:接收者收到密文和公钥,找到对应的私钥:p=cd%n=829%105,经过运算,余数为2。

上面运用了N=3时的N重RSA算法,在这种非对称的RSA加密算法中,充分利用了大数分解的思想,这样在改进的N重RSA算法中加进了多个是相乘,由于这样每次都有可能有不同多个数得出的结论来完成的加密密钥和公钥的计算,所以在更大程度上也保证的算法的安全性和保密性。

5. 总结

本文是在对传统的RSA算法的充分研究和深刻理解上,对RSA算法效率低的问题进行了改进得到了基于原有算法的N重RSA算法。在增加了素数的情况下降低了所选素数的个数,以达到小数相乘运算速度比大数相乘效率高的特点。

由于N重RSA算法还是在原有的RSA算法的基础上,因此它的安全性和保密性都和原来的RSA算法是一样的,因此在应用上还是和原有的RSA算法是相同的,所以N重RSA算法是否等同于大数分解依然不能得到理论上的证明。

在N重RSA算法中,传送保密信息的主要工作密钥参数p1,p2pn,ex,dx,都具有一次使用的特征,即每次通信使用到的这些工作密钥参数都在随机变化。

在某种意义上,它接近于一次一密的密码体制[6],显然它的保密性要远优于工作密钥在一个较长时间内固定不变的原有的RSA算法,并且减少了每一个随机产生素数的位数,因此也在一定义以上加快了RSA算法计算机实现的效率问题。

但是,由于在几个小素数相乘后得到的还是一个较大的数,所以还是没有从根本上解决RSA算法基本只用于较少的数字加密,例如数字签名上的问题。

参考文献

[1]Don Slice.专业IP网络规划与设计[M].北京:希望电子出版社,2000.2.

[2]Yin Zhang,Matthew Roughan,Carsten Lund,et al.An informa-tion-theeoretic approach to traffic matrix estimation[C].SIG-COMM’03,2003.

[3]Yin Zhang,Matthew Roughan,Nick Duffield,et al.Fast accuratecomputation of large-scale IP traffic matrices from link loads[C].SIGMETRICS’03,2003.

[4]Matthew Roughan,Mikkel Thorup,Yin Zhang.Traffic enginee-ring with estimated traffic matrices[C].IMC’03,2003.

[5]曹建国,王丹,王威.基于RSA公钥密码安全性的研究[J].计算机技术与发展.2007,1(17):172-176.

过河问题的算法改进第8篇

在操作系统课程中, 进程管理是其中一个主要内容。其中如何有效地使用信号量机制来实现并发进程的互斥与同步是进程管理的难点。信号量机制是荷兰学者Dijkstra提出的一种卓有成效的进程同步工具, 它主要是通过P、V两个操作原语的使用, 来保证进程之间的同步与互斥。过河问题是进程同步与互斥的一个典型问题, 传统的解决方案避免了死锁现象, 但却有可能使某些进程长期得不到服务, 产生"饿死"现象。本文提出了一种改进算法, 避免该现象的发生, 使所有进程能公平使用资源。

1、问题的描述

过河问题是指:假设有一条南北走向的河, 河中有N块石块搭起的便桥 (N≥2) , 如图1所示, 石块编号依次为1, 2, …, N, 两个相邻石块间距恰好为一步, 每个石块上只允许站一人, 东面过河者要依次经过石块N, N-1, …, 2, 1到达西岸, 西面过河者要依次经过1, 2, …, N-1, N到达东岸, 当东面过河者踏上第N块石头, 西面过河者踏上第1块石块时, 将发生死锁。为防止死锁发生, 规定同一方向的人可连续过河, 某方向有人过河时另一方向的人等待。

2、传统的解决方案

为实现东西方过河者的互斥, 设置了一个互斥信号量mutex。另外, 再设置两个整型变量EastCount和WestCount分别表示东西方过河者数目。由于只要东面有一个过河者在过河, 便不允许西面过河, 因此, 仅当EastCount=0, 表示尚无东面过河者时, 东面过河者进程才需要执行P (mutex) 操作。若P (mutex) 操作成功, 东面过河者便可过河, 相应地, 做EastCount加1操作。同理, 仅当东面过河者进程在执行了EastCount减1操作后其值为0时, 才须执行V (mutex) 操作, 以便让西面过河者进程过河。又因为EastCount是一个可被多个东面过河者进程访问的临界资源, 因此, 也应该为它设置一个互斥信号量ECmutex。同理, 应设置互斥信号量WCmutex。

算法描述如下:

算法分析:假设有河东过河者E1、E2、E3…及河西过河者W1、W2、W3…都要过河, 若到达次序如表1所示。当河东过河者E1正过河时 (执行到pass the river) , 又有诸多过河者到来, 因第1个河西过河者W1过河前要执行P (mutex) 操作, 故会阻塞。而河东过河者E2、E3则会直接过河。随后到达的W2、W3会等待在信号量WCmutex上。故最终的过河次序为:E1、E2、E3、W1、W2、W3。

在这种算法中, 只要河东有过河者不断到来, 后续的河西过河者就会被随后而来的河东过河者插队而长时间等待, 直到所有的河东过河者都过完且没有新的河东过河者到来时河西过河者才能过河, 这样就会造成河西过河者被"饿死"的现象。反之亦然。

3、双方公平竞争方案

为了防止"饿死"现象的产生, 对原先的算法进行了改进。在该方案中, 每面的过河者完全按照到达的先后顺序过河, 即河西有过河者到达时, 后续的河东过河者都必须等待, 不允许后来者超越先来的等待资源者。这样两个方向的过河者就公平竞争使用资源。为了实现双方公平竞争, 在传统算法基础上, 引入新的互斥信号量IDmutex作为已经有对方过河者处于等待状态的标记。每个过河者在过河之前都要先执行P (IDmutex) , 若对方已有人在等待, 即对方也执行了P (IDmutex) , 则会阻塞;若对方无人等待, 则可以过河。

算法描述如下:

算法分析:假设有若干过河者到达次序如表1所示。当河东过河者E1正过河时 (执行到pass the river) , 第1个河西过河者W1到来, 会等待在信号量mutex上, 此时IDmutex的值减为0。河东过河者E2、E3到来时, 要执行P (IDmutex) , 会等待在信号量IDmutex上。随后到达的W2、W3也会等待在信号量IDmutex上。当E1完成V (mutex) 时, 会优先唤醒W1。当W1完成后, 会依次唤醒E2、E3。最后唤醒W2、W3。故最终的过河次序为:E1、W1、E2、E3、W2、W3。

在该算法中, 过河者不仅要考虑有没有对方过河者正在过河, 同时也要考虑有没有对方过河者正在等待过河, 完成了双方公平竞争使用资源。

4、结束语

进程同步是操作系统中非常重要的一部分内容, 过河问题是进程同步问题中的经典实例, 若能熟练掌握, 对于常见的进程同步问题必能起到举一反三的作用。

摘要：过河问题是操作系统进程同步中的一个经典例题。分析了原有算法中存在的问题, 提出了一种改进的算法, 通过实例比较了两种算法的结果。

关键词：进程,同步,互斥,信号量

参考文献

[1].张尧学, 史美林.计算机操作系统教程[M].第3版.北京:清华大学出版社, 2006.

[2].汤小丹, 梁红兵, 哲凤屏等.计算机操作系统[M].第3版.西安:西安电子科技大学出版社, 2007.

改进的RD算法第9篇

图像分割是数字图像处理中的一个非常重要领域,是进行模式识别的首要问题和基本问题[1]。图像分割就是要把图像中具有特定性质的目标区域提取出来,从而有利于进行进一步的分析。长期以来,随着各学科的不断发展和各种新技术的应用,人们不断对这一课题进行研究,涌现出了大量的新算法。同时,各种分割算法不断改进,以期寻求更为高效、满意的分割效果。目前,最为流行的分割算法有:

(1) 基于阈值的分割方法。主要就是先确定一个处于图像灰度取值范围之内的阈值,然后将图像中各个像素的灰度值都与这个阈值相比较,并根据比较之后的结果将对应的像素分为两类,从而达到分割的目的。很容易看出,确定一个最优阈值是分割的关键,严学强等人提出了基于量化直方图的最大熵阈值处理算法[2],使计算量大大地减小;薛景浩、章毓晋等人提出基于最大类间后验交叉熵的阈值化分割算法[3],取得了很好的通用性和有效性;任明武等人提出的一种基于边缘模式的直方图构造新方法[4],使分割阈值受噪声和边缘的影响减少到最小。ZikuanChen[5]等人提出的基于小波的自适应阈值分割方法把小波引入图像分割,利用小波分析取得阈值,得到了很好的分割效果。诸如此类的分割算法还有很多,其基本思想一致,都是寻求最佳阈值。

(2) 基于边缘的分割方法。利用图像一阶导数的极值或二阶导数过零点信息来提供判断边缘点的基本依据,构造对图像灰度阶跃变化敏感的差分算子来进行图像的分割。如宋焕生[6]等人提出了多尺度脊边缘及其在图像目标分割中的应用,最后通过脊边缘跟踪、滤波和小波反变换,得到分割结果。张静[7]等人提出了行扫描空间带通滤波法,在总结前人理论和实验结果的基础上提出的一种边缘提取新方法,对视频图像的跟踪识别有很好的效果。

(3) 基于区域的分割方法。区域分割的实质就是把具有某种相似性质的像素连通起来,从而构成最终的分割区域,利用了图像的空间信息,但它常常会造成图像的过度分割现象。最近出现了很多新方法,比如王广君等人提出的基于四叉树结构的图像分割方法[8],将区域增长和人工智能结合起来,使分割速度大大提高。刘宁宁等提出的基于代理机模型的交互式图像分割方法[9],通过控制界面和汇报界面实现与操作者的交互。

图像分割迄今为止采用了多种理论工具相结合,比如基于数学形态学的分割算法[10]、基于模糊数学的图像分割算法[11]、基于人工神经网络技术的图像分割算法[12]、基于小波分析和变换的图像分割算法[13]等。灰度图像的分割技术可以被用在彩色图像每一个分量的分割上,其中最关键的问题之一就是如何选取颜色空间,其次就是对每一个像素如何将各个分量上的彩色信息进行整合而得以利用。为此,本文在与人类视觉感知特性最相似的HSI颜色空间下,提出了一种权衡彩色图像上的三个分量对整幅彩色图像影响的基于遗传算法的彩色图像分割改进算法。

1预备知识

1.1HSI颜色空间

为了便于颜色处理和人眼识别,人们通常采用HSI颜色空间模型,它比RGB颜色空间模型更符合人的视觉感知特性。在图像处理和计算机视觉中大量的算法都是基于HSI颜色空间模型的,因为模型的三个分量可以分开处理而且是相互独立的。所以,利用HSI颜色空间可以大大简化图像分析和处理的工作量。

HSI颜色空间模型和RGB颜色空间模型只是同一物理量的不同表示法,因而,它们之间也存在着转换关系。

(1) 色调信息

$Η = {\begin{cases} θ B G \\ 360 - θ B \geq G \end{cases} Η \in [0 ‚ 2 π]$

其中 $θ = \arccos \frac{\frac{1}{2} [(R - G) + (R - B)]}{[(R - G)^{2} + (R - G) (R - B)]^{\frac{1}{2}}}$

(2) 饱和度信息

$S = 1 - \frac{\min (R, G, B)}{Ι} S \in [0, 1]$

(3) 亮度信息

$Ι = \frac{R + G + B}{3} Ι \in [0, 255]$

1.2遗传算法

遗传算法[14]简称GA,是1962年由美国Michigan大学的Holland教授提出的模拟自然界生物进化过程而形成的一种并行随机搜索优化算法。它将“优胜劣汰,适者生存”的生物进化原则引入到优化问题中,让群体中适应度高的个体保留下来,通过不断地遗传进化,直到满足一定的终止条件为止,从而得到全局最优解。

遗传算法是一种随机概率搜索算法,其基本思想是模拟生物群体进化的过程,整个过程如图1所示。

1.3熵

对于一幅图像而言,人眼对其中每一个区域的敏感程度是不同的,从而导致了对图像各个部分的注意力不均匀且没有规律,而这就决定了人对图像视觉信息的理解。如果不考虑图像表达的意义,不把图像内容与编码方法结合起来,对整个图像一概而论的话显然是不合理的。为了衡量图像信息量的大小以及人类视觉系统对图像的敏感程度,人们提出了视觉熵VE(Visual Entropy)的概念。

在信息论中,信源X中目标xi(i=1,,n)的信息量I(xi)被定义为:

I(xi)=ln(1/pi)=-lnpi

其中pi为xi(i=1,,n)出现的概率。

信息熵[15](Entropy) $Η (X) = - \sum_{i = 1}^{n} p_{i} \ln p_{i}$ 就是信源X中所有目标的平均信息量,即:

$Η (X) = E (Ι (x_{i})) = - \sum_{i = 1}^{n} p_{i} \ln p_{i}$

熵是一种对不确定问题的度量准则。一幅图像的熵值H(X)是它的平均信息量的量度。

2基于遗传算法的最佳熵阈值求解

由于在遗传算法中适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。因此,适应度函数设计应尽可能简单,这样可以减少计算时间上和空间上的复杂性,降低计算的成本;并且适应度函数针对某类具体问题而言,应尽可能通用。在下面的算法中我们将信息熵的概念应用到图像分割当中,反映了全局图像的先验信息,并且对适应度函数的定义作了进一步的改进,从而使算法在计算上的时空开销更小。遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。

基于遗传算法的彩色图像最佳熵阈值的求解步骤如下:

Step1 颜色空间转换

将彩色图像从RGB颜色空间转换到HSI颜色空间。值得注意的是:我们需要一个量度的转换,将这三个分量的值都统一映射到[0,255]区间上,为遗传操作编码提供便利。

Step2 初始化编码

对彩色图像的三个颜色分量H、S、I分别进行编码,将每个像素用8位二进制表示。

Step3 适应度函数的计算

根据信息熵的定义,选择适应度函数H(t)如下:

$Η (t) = \ln [\sum_{i = 0}^{t} p_{i}] + \ln [\sum_{i = t + 1}^{m} p_{i}] - \frac{\sum_{i = 0}^{t} p_{i} \ln p_{i}}{\sum_{i = 0}^{t} p_{i}} - \frac{\sum_{i = t + 1}^{m} p_{i} \ln p_{i}}{\sum_{i = t + 1}^{m} p_{i}}$

其中m表示像素最大值,一般取255。当H(t)取最大值时,t值作为阈值来分割图像,可以取得更好的效果,更能够反映图像的信息。

Step4 遗传操作

选择算子采用轮盘赌选择法;交叉算子采用二进制交叉中的单点交叉法,随机产生的交叉点位于第4位,交叉概率为0.7;变异算子采用二进制变异中的基本位变异法,变异概率为0.04。

Step5 算法终止

经过50次的迭代运算,取最高适应度的个体解码后得最佳熵阈值。在三个颜色分量H、S、I中分别产生三个最佳熵阈值μ1、 μ2、 μ3。

3一种改进的彩色图像分割方法

对于彩色图像的分割,传统的方法是先将彩色图像转换成对应的灰度图像,利用灰度图像的分割方法进行阈值分割,最后得到彩色图像的分割图像。

在HSI颜色空间模型中,I表示彩色图像的亮度信息,也可以用该分量来近似地表示彩色图像对应的灰度图像信息。因此,人们往往利用HSI颜色空间模型中I分量来对彩色图像进行分割。但是,事实上仅用一个I分量是不能够代表图像上每一个点所要突出反映的内容的,因为彩色图像中有的点强调H(色调)信息,有的点强调S(饱和度)信息,还有的点I(亮度)信息更为重要,所以,不能够单独用I这个分量来计算彩色图像中所有点的分割阈值。

为此,我们提出了一种新的彩色图像分割方法,权衡了三个分量对整幅彩色图像的影响,将H、S、I三个分量分别作为权值,权值越大,那么该分量对整幅彩色图像的影响就越大;反之,权值越小,那么该分量对整幅彩色图像的影响就越小。利用一个计算式子Y=UTf,其中f表示彩色图像上的一个点,U表示通过遗传算法求得的最佳熵阈值。通过公式转换,将HSI颜色空间中的三个分量统一映射到一个分量当中,再利用遗传算法进行图像的阈值分割。这样既考虑了H、S、I三个分量对每个像素点的影响,而且又从宏观上把握了图像的信息。

该方法的具体实施步骤如下:

Step1 首先,计算出彩色图像HSI颜色空间模型中各个分量的最佳熵阈值μ1、 μ2、 μ3作为特征向量U。

Step2 然后,我们将彩色图像中的每一点 $f (Η, S, Ι)$ 映射到上述特征向量U中去,得到一个向量Y。

Y=UTf 其中 $U = (μ_{1}, μ_{2}, μ_{3})$

Step3 向量Y是彩色图像上的每一个点 $f (Η, S, Ι)$ 在特征向量 $U = (μ_{1}, μ_{2}, μ_{3})$ 上投影的值,也权衡了各个分量对整幅图像的影响后得出的值。根据向量Y的值,再利用上面提到的遗传算法对图像进行分割,从而得到了彩色图像的分割结果。

这种分割方法综合考虑了颜色空间模型中三个分量对整幅图像的影响,利用一个映射公式,将彩色图像上的三个颜色分量统一转换到一个分量当中。这样不仅便于彩色图像的分割计算,更重要的是还能够权衡各个分量对整幅彩色图像的影响,在分割阈值的计算当中利用了基于并行随机概率搜索的遗传算法,体现了图像并行处理的能力,有利于实时图像的处理。

4实验

针对24位的真彩色图像,本文选择了两幅典型图像进行分析。

首先对lena图像进行分割实验,如图2所示。图2(a)是原始图像,图2(b)是采用传统方法分割后的结果,即先将彩色图像转换成灰度图像,然后对其进行分割,此处采用迭代阈值法,其分割阈值为61。图2(c)是利用前面描述的改进的彩色图像分割方法进行分割,其分割阈值为99,分割结果如图所示。

其次对couple图像进行分割实验,如图3所示。图3(a)是原始图像,图3(b)是采用传统分割方法分割后的结果,即先将彩色图像转换成灰度图像,然后对其灰度图像进行分割,此处采用最优阈值法进行分割,分割阈值为56。图3(c)是利用前面所描述的改进的彩色图像分割方法进行分割,其分割阈值为45,分割结果如图所示。

经过大量的实验表明,使用这种改进的彩色图像分割方法对于分割目标区域和背景区域相差比较大的彩色图像来说,具有很好的分割效果。因此,在处理目标物体比较明显的彩色图像的时候,我们就利用改进的彩色图像的分割方法来满足用户的需要,同时也达到了实时处理图像的目的。

5结论

本文在HSI颜色空间模型中对彩色图像进行分割处理,提出了一种可以权衡各颜色分量对彩色图像影响的基于遗传算法的彩色图像分割改进算法。

首先,在HSI颜色空间模型中对图像进行分割,使人们对于彩色图像的理解更加直观、更加符合人的视觉特性。其次,所利用的遗传算法对图像进行分割,体现了图像处理的并行能力,有利于进行实时图像的处理,并且,基于最佳熵阈值的方法容易理解,在设计适应度函数时用到了图像的先验信息,更能够反映一幅图像信息量给人类视觉系统带来的影响。在适应度函数的定义上还考虑到了时空开销更小的要求,只有适应度函数设计好了,遗传算法才可以得到最优的解。另外,在求得了三个颜色分量的最佳熵阈值以后,我们权衡了这三个分量对整幅彩色图像的影响,最终计算得到了一个最佳熵阈值来对图像进行分割处理。

改进了的彩色图像分割算法,能基本满足实时应用的要求,是一种较为理想的、针对目标和背景区域相差比较大的彩色图像的分割方法。

改进的RD算法

改进的RD算法第1篇

后进生的转化rd 文档第2篇

改进的RD算法第3篇

一种改进的变异粒子群算法研究第4篇

改进的RD算法第5篇

改进的RD算法第6篇

RSA算法的改进第7篇

过河问题的算法改进第8篇

改进的RD算法第9篇

改进的RD算法

猜你喜欢

栏目

最近更新

热门标签

改进的RD算法

改进的RD算法 第1篇

后进生的转化rd 文档 第2篇

改进的RD算法 第3篇

一种改进的变异粒子群算法研究 第4篇

改进的RD算法 第5篇

改进的RD算法 第6篇

RSA算法的改进 第7篇

过河问题的算法改进 第8篇

改进的RD算法 第9篇

改进的RD算法

猜你喜欢

栏目

最近更新

热门标签

改进的RD算法第1篇

后进生的转化rd 文档第2篇

改进的RD算法第3篇

一种改进的变异粒子群算法研究第4篇

改进的RD算法第5篇

改进的RD算法第6篇

RSA算法的改进第7篇

过河问题的算法改进第8篇

改进的RD算法第9篇