混合算法

2024-12-28

混合算法（精选12篇）

混合算法篇1

0 引言

最优化问题[1]存在于人类日常生活中的方方面面,人类从事任何活动的实质归结为认识世界和建设世界,认识世界就是为了更好地建设世界,然而建设世界的本质就是依靠优化决策。最优化问题是一个古老的课题,早在在古代战国时期,就有了孙膑为田忌赛马献策赢了齐威王这一经典事件[2];在第二次世界大战期间,英国成立了专门的作战研究小组,目的是为了最有效地利用有限的战备资源去赢取最大的胜利[1]等。随着科学技术日新月异的发展和应用领域的不断扩展,常规的优化方法[2,3,4](例如牛顿法,拉格朗日乘数法,共轭梯度法等)已经无法满足越来越复杂的优化问题的求解需要,因此寻找更为有效的优化方法显得越来越重要。

一些学者提出模拟自然界生态系统机制的新型智能优化算法,并用来解决复杂优化问题,取得了一定的效果。群体智能优化算法正是基于此基础上产生的。群体智能优化算法[5,6]自20世纪90年代提出以来受到广泛的关注,通过对自然界中社会性生物的群体行为进行模拟和建模,研究其内在的原理,并以此为基础解决许多工程应用,科学计算,社会经济等领域的实际问题。由于其求解能力强,计算结构简单,吸引了众多演化计算领域专家的注意,形成了许多新的研究热点并取得显著的成就。目前群体智能优化算法广泛应用于农业、通讯、交通、金融、材料、化工、能源及国防等领域中。

混合蛙跳算法[5,6,7](Shuffled frog leaping algorithm,SFLA)是近几年兴起的一种新型的后启发式群体智能优化算法,它继承其他优化算法的优点同时,还具有寻优能力更强,参数更少的优点,目前已广泛应用于模式识别[8],函数的优化[9,10,11,12],信号与信息处理[13,14]等领域中并取得了成功。由于混合蛙跳算法提出的时间不长,无论在理论研究还是实践应用方面都处于起步阶段。

1 混合蛙跳算法

1.1 SFLA算法的数学模型

混合蛙跳算法是2003年由Eusuff和Lansey提出的一种新的群体智能优化算法,它概念简单,参数少,计算速度快,全局寻优能力强。

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

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

蛙跳步长更新公式

青蛙个体的位置更新公式

其中,Ωi表示青蛙个体的更新步长,i=1,2,…,N;rand()为均匀分布在[0,1]之间的随机数;||Ωmax||表示所允许更新的最大蛙跳步长;||Ωmin||表示所允许更新的最小蛙跳步长。执行更新策略(1)(2)。如果newXw的适应度值优于原来Xw的适应度值,则用更新后的个体的位置(解)取代原来群体中的当前最差个体的位置(解)。如果没有改进,则更新策略变为如下过程。

蛙跳步长更新公式:

青蛙个体的位置更新公式:

执行更新策略(3)(4)。如果newXw的适应度值仍然没有改进,则随机产生一个新的Xw。

当所有子群体的局部深度搜索完成以后,将所有的青蛙个体重新混合排序并再次划分子群体,然后再进行局部深度搜索,如此反复直到满足混合迭代次数。

1.2 SFLA算法的实现流程

第1步:随机初始化青蛙种群,设置SFLA算法中的参数:种群中的青蛙个体总数N,青蛙个体(解)的维数d,每个子群体中的个体数m,子群体的个数n,子群体内的局部迭代次数cyc,全局混合迭代次数cyc,允许更新的最大蛙跳步长Ωmax和最小蛙跳步长Ωmin。

第2步:计算每只青蛙个体的适应度值。

第3步:将当前所有的N只青蛙个体按照适应度值从优到劣进行排序。

第4步:将每只青蛙个体依次划分到各个子群体中,共划分为n个子群体。

第5步:对每一个子群体,重复执行以下步骤cyc次:

(1)根据适应度值更新当前迭代中子群体的最好个体的位置Xb和全局最好个体的位置Xg,并确定当前迭代中子群体的最差个体的位置Xw;

(2)按照1.1节中所描述的更新策略对Xw进行更新。

第6步:当所有子群体都完成了局部深度搜索后,若满足全局混合迭代次数cyc,进化过程结束,输出全局最优值;否则,将全部的青蛙个体重新混合,转至第3步重新计算。

以上算法实现流程如图1所示。

2 混合蛙跳算法的研究现状

2003年,Eusuff和Lansey首次提出混合蛙跳算法,由于其结构简单、参数少、运行速度快、易于实现的优点,得到了国内外学者的广泛关注。然而混合蛙跳算法存在算法迭代后期容易陷入局部极值点,出现早熟收敛现象,同时收敛速度变慢,寻优时间变长,无法搜索到精度更高的最优点等缺陷。因此,目前对混合蛙跳算法的研究主要集中在算法改进和算法应用方面。

混合蛙跳算法由于提出的时间不长,无论在理论研究还是实践应用方面都处于起步阶段。群体智能优化算法不是一门理论严谨的学科,主要是以实验为主,因此关于算法的理论研究主要集中在算法收敛性证明上。骆剑平等人[15]通过求解差分方程分析了混合蛙跳算法的运动轨迹并证明了算法的全局收敛性;Elbeltagi等人[16]对比研究了遗传算法、粒子群优化算法、蚁群算法和混合蛙跳算法的数学模型和优化性能;

目前,针对混合蛙跳算法存在的缺陷,为了提高算法的优化性能,国内外学者从各个方面对算法提出了改进。罗雪晖等人[17]将调整序思想引入到混合蛙跳算法的局部搜索阶段,将变异操作引入到全局信息交换阶段,从而提出一种改进的混合蛙跳算法并将其应用于求解旅行商问题(Travelling salesman problem,TSP),实验结果表明该算法在求解旅行商问题上具有更好的搜索性能和顽健性;骆剑平等人[15]把具有极强局部搜索能力的幂律极值动力学优化融合在混合蛙跳算法中,从而拓展了算法的搜索精度和空间;郑仕链等人[18]提出新的蛙跳移动步长公式,每次蛙跳移动步长中引入上一次的移动距离,包含了对过去经验的记忆,因此具有更强的寻优能力;Alireza等人[7]提出一种混合多目标蛙跳算法,并将其应用于流水线平衡装配线排序问题中;Elbeltagi等人[19]提出一种新的参数用来加速算法的搜索范围,并分析了该参数对算法优化性能的影响,最后将所提算法用来求解离散和连续两类问题,结果表明改进算法十分有效并且可行;文献[9]通过适当地延长蛙跳步长并且加入惯性部分,提出一种改进的蛙跳步长更新公式,同时为了进一步改进混合蛙跳算法的局部深度搜索能力和加速收敛,将进化算法引入到混合蛙跳算法的局部深度搜索阶段,从而提出一种改进的混合蛙跳算法;文献[20]将模拟退火算法和混合蛙跳算法相结合,从而改进了算法迭代后期陷入局部极值的缺点,并将其应用于求解最优潮流问题(Optimal power flow,OPF);文献[21]提出一种求解多目标柔性作业车间调度问题的改进混合蛙跳算法,该算法通过几种策略来构成初始种群,并依据一种新的准则来划分子群体,同时在全局信息交换阶段引入两种变异因子,在局部深度搜索阶段嵌入一些不同的局部搜索方法,从而提高算法的求解性能。

与其他群体智能优化算法一样,混合蛙跳算法由于其独特的优势被广泛应用于实际优化问题中。例如,旅行商问题[22]、电力系统优化[23]、作业车间调度问题[24,25]、函数优化[10,11,12]、财务调度问题[26]、水资源分配[27]、图像处理[13]、背包问题[28]、聚类问题[29]等方面,文献[30]提出一种多目标优化的改进混合蛙跳算法,并用来求解配电馈线重组问题;文献[31]中将一种改进的混合蛙跳算法应用于工业CSTR反应器的醋酸乙烯聚合中;文献[32]中将混合蛙跳算法应用求解离散优化问题中。

3 结束语

混合蛙跳算法在提出的短短几年时间里得到了国内外学者的广泛关注,成为人工智能领域中的研究热点。虽然混合蛙跳算法被成功用于求解实际优化问题,但是由于其提出的时间不长,无论是在理论研究还是实际应用都处于起步阶段。目前关于混合蛙跳算法并没有一套完整的理论体系,未来的工作应当注重算法收敛速度证明并总结出一套完整的理论模型;由于现实生活中需要解决的优化问题各式各样,如何突破原有混合蛙跳算法模型的束缚,设计出更为有效的群体智能优化算法将在未来工作中继续研究。

混合算法篇2

教学内容：教科书第93―94页，练习二十的第；一10题。

教学目的：

1．使学生掌握加法和乘法的运算定律。能够比较熟练地运用这些运算定律进行简便计算。

2．使学生掌握四则运算的运算顺序．能正确计算四则混合运算。

教学过程（）：

一、运算定律

教师：“我们在学习四则运算时．学过哪些运算定律?”指名用自己的话说出运算定律，并举例说明。然后用字母表示出来：教师根据学生的回答，整理成教科书第93页的表。

如果学生只举整数的例子，教师可以引导学生想一想：运算定律除了对整数加法和乘法适用以外，对小数和分数的加法、乘法适用吗?让学生再举几个有关小数、分数加法和乘法的例子。

下面的式子有没有错误?把错的地方改正过来。

(4．3十2．5)×4＝4．3×4×2．5×4

(700十1)×68＝700×68十68

153×(220十57)＝153×220十57

63×8十37×8；(63十37)×(8十8)

还可以做练习二十的第8题。

教师：“在我们学过的知识里哪些地方应用丁运算定律?”可以多让几个学生说一说。如果学生掌握得比较好，还可以让学生用运算定律解释―下积、商的变化规律：如：在乘法里。如果一个因数扩大10倍，另一个因数不变，那么积就扩大10倍：可

以用下面的式子说明：

(a×10)×b＝a×10×b＝a×b×10＝(a×b)×10

这里应用了乘法的交换律和结合律。

二、简便算法

教师：“应用运算定律可以使―些计算简便。谁能举个例子?”

接着出示教科书第93页的例1、先让学生观察题目中的数有什么特点。然后让学生说一说应该用什么运算定律。说完后，让学生独立完成计算。

集体订正时．教师再提问：这道题是怎样应用运算定律的?应用了哪些运算定律?使学生明确：在计算时．不仅计算的开始有时可以用简便方法进行计算，在计算的过程中有时也可以用简便方法进行计算。

教师：“在计算时，要随时注意用简便方法进行计算、”

做教科书第93页“做一做”中的题目。

教师说明题目要求后。让学生独立计算。教师巡视，对学习有困难的学生进行个别辅导。集体订正时．让学生说一说每道题是怎样用简便方法计算的。特别是下面二道题，是怎样进行简便计算的?

567十98 1 ― ― 21 ÷7

教师要提醒学生：有的`算式可能存在几种不同的算法，所以。在运算前要认真审题．看清算式中各个数的特点、选用―种比较简便的算法，使计算又对又快。

三、四则混合运算

引导学生回忆四则混合运算的有关概念和运算顺序。

“什么叫做第一级运算?什么叫做第―级运算：”

“在一个算式中如果只含有同―级运算、运算顺序是怎样的：”

“在一个算式中如果含有第―级和第二级两级运算。应该先算什么?”

“在含有括号的算式中。应该先算什么?再算什么?”

出示教科书第94页中间的算式．让学生标明运算顺序。

教师：“在计算混合运算的式题时．首先要认真审题，看清题中有哪些运算符号．确定运算的顺序。”

出示教科书第94页的例2。先让学生认真审题。想一想运算顺序。然而让学生独立计算。教师巡视。了解学生掌握的情况、对个别学生进行辅导，集体订正时，指名说一说运算的顺序。同时，还要注意强调书写的格式。

做练习二十的第9题。学生独立计算。集体订正。

四、小结(略)

混合互补问题的光滑算法及收敛性篇3

关键词混合互补问题;Jacobian光滑算法;信赖域方法;梯度步;全局收敛;二阶收敛

中图分类号 O178 文献标识码:A

1 引言

互补问题是运筹学与数学的一个交叉研究领域,许多经济、金融、控制等方面的问题都可以转化为互补问题来求解,其中混合互补问题MCP(a,b,F)是求x*∈[a,b],使得对任意x∈[a,b]满足

F(x*)T(x-x*)≥0,MCP(a,b,F),

式中,a,b∈Rn,F为连续可微的向量函数.这类问题也称作箱形约束的变分不等式问题(BVI).引入松弛变量后,MCP(a,b,F)系统的解x*满足KKT系统

F(x)+y-z=0,x-a≥0,z≥0,(x-a)Tz=0,

b-x≥0,y≥0,(b-x)Ty=0.(1)

文献[1]中采用了将信赖域方法和线搜索技巧相结合的光滑化方法来求解非线性互补问题,该方法推广了Yang和Qi的方法^[2].Ma和Kang在^[3]中也采用两种下降方向相结合的方法求解变分不等式.

基于这种思想,本文推广文^[2]的算法,针对混合互补问题,采用将信赖域和梯度方法相结合的方法,提出了逐次逼近光滑近似算法.

2 辅助函数及性质

问题(1)等价于系统

x-a≥0,F(x)+y≥0,(x-a)T(F(x)+y)=0,b-x≥0,y≥0,(b-x)Ty=0.(2)

由NCP函数φ(a,b)=a2+b2-a-b的性质知,问题(2)等价于求解非线性方程组

H(x,y):=φ(x1-a1,F1(x)+y1)φ(xn-an,Fn(x)+yn)φ(b1-x1,y1)φ(bn-xn,yn)=0.(3)

相应于方程组(3)的效益函数定义为Ψ(x,y)=12‖H(x,y)‖2.形如问题(3)的非光滑方程组,研究得最多的是构造光滑逼近函数的方法,这些方法基本上每迭代一次,需求解广义牛顿方程,增加运算量.第2节我们将通过引入光滑函数,并介绍光滑逼近函数.

构造带参数的光滑函数

φμ(a,b)=φ(a,b),a2+b2>μ,

a(a-2μ)2μ+b(b-2μ)2μ+μ2,a2+b2≤μ,

式中,μ>0为光滑因子.可以证明,φμ:R2→R是光滑函数,而且是以Fischer-Burmeister函数为极限函数,即lim μ→0φμ(a,b)=φ(a,b),则问题(3)的光滑逼近方程组为

Hμ(x,y):=φμ(x1-a1,F1(x)+y1)φμ(xn-an,Fn(x)+yn)φμ(b1-x1,y1)φμ(bn-xn,yn)=0.(4)

对应于方程组(4)的效益函数为Ψμ(x,y)=12‖Hμ(x,y)‖2.经济数学第 27 卷

第3期何郁波等:混合互补问题的光滑算法及收敛性

3 算法与基本假设

记z=xy∈R2n,则本文所针对的目标函数为

H(z)=0min z∈R2nΨ(z).(5)

根据所引进的光滑函数,将利用下面光滑非线性方程组来逼近问题(5),

Hμ(z)=0min z∈R2nΨμ(z),μ↓0.(6)

给出关于问题(6)的信赖域法和梯度方向相结合的光滑化方法.令

Qk(d):=12‖Hμk(zk)+H′μk(zk)Td‖2

=Ψμk(zk)+Hμk(zk)TH′μk(zk)Td+12dTH′μk(zk)TH′μk(zk)Td.

算法2.1 (光滑逼近算法)

步0 选取初始点z0=(x0)T,(y0)TT∈R2n,Δ0,Δmin ,λ,η,α,ε,ρ∈(0,1),γ>0,σ∈(0,12(1-α)),0

步1 若 ‖

步2 求解信赖域子问题得解dk∈R2n

min ‖d‖≤ΔkQk(d),(7)

步3 若

Hμk(zk)TH′μk(zk)Td<-max {ρ‖dk‖Ψμk(zk),ρ‖dk‖2},(8)

则转步5;

步4 令

dk:=-

在{0,1,2,...}中求满足

Ψ(zk+λmkdk)≤Ψ(zk)-σλmk‖dk‖2(10)

的最小非负整数mk,令tk=λmk,zk+1=zk+tkdk,Δk+1=Δk,转步6;

步5 令

rk=Ψμk(zk)-Ψμk(zk+dk)Ψμk(zk)-Qk(dk),(11)

zk+1=zk+dk,rk>c2zk,rk≤c2(12)

Δk+1=c3Δk,rk≤c2,max {Δmin ,Δk},c2

步6 若

‖H(zk+1)‖≤max {η βk,α-1‖H(zk+1)-Hμk(zk+1)‖},(14)

则令βk+1=‖H(zk+1)‖,并取μk+1满足

0<μk+1≤min {α2nβk+1,μk2,μ-(zk+1,γβk+1)};(15)

若式(14)不成立,dk由式(9)确定,则令βk+1=βk,取μk+1满足

0<μk+1≤min {α2n‖H(zk+1)‖,μk2,‖H(zk)‖-‖H(zk+1)‖2n};(16)

否则,令βk+1=βk,μk+1=μk;

步7 令k:=k+1,转步1.

记K={0}∪{k∈N|‖H(zk)‖≤max {ηβk-1,α-1‖H(zk)-Hμk-1(zk)‖}}.

由于在算法2.1的梯度步中,使用了标准Armijo搜索准则,而在信赖域步中根据信赖域算法的特点可知算法2.1是适定的.

假设2.1 令{zk=(xk)T,(yk)TT}R2n是算法2.1产生的序列,假设

{zk}L0:={z∈R2n|Ψ(zk)≤(1+α)2Ψ(z0)}.(17)

4 收敛性分析

本节将证明算法2.1的全局和局部收敛性.下面引理来自文献[4].

引理3.1 令zk是算法2.1产生的序列,假定zk的聚点z*是问题(4)的解,则K是无限集且{μk}↓0^[4].

引理3.2 设zk由算法2.1产生的序列,假定指标集K是无限集,则序列zk的每个聚点是方程组(4)的一个解^[4].

引理3.3 设序列zk由算法2.1产生,zkL是收敛于z*的子序列,若对于所有k∈L,都有dk=-

定理3.1 设zk由算法2.1产生的序列,则zk的每个聚点都是Ψ(z)的一个稳定点.

证明若K是无限集,则由引理3.2可知,zk的每个聚点都是Ψ(z)的一个稳定点.下面假设K是有限集.若zk中有无限多步由梯度步产生,则由引理3.3知,zk的聚点z*是Ψ(z)的稳定点.因此下面考虑梯度步有限的情形.

设是K中最大整数,则对所有k>,有,

μk≤μ,βk≤β

及

‖H(zk+1)‖>ηβk=η‖H(z)‖>0.

由于μk单调递减且有下界,因此收敛.设{μk}→μ*.下面证明μ*=0.若不然,假设μ*>0,则k充分大时,μk=μ*且k∈:={k|Hμk(zk)TH′μk(zk)Tdk<-max {ρ‖dk‖Ψμk(zk),ρ‖dk‖2}}.假设zk的任何聚点都不是Ψ(z)的稳定点,则有lim k

令K1:=k|k∈,rk>c2,由Ψμ*(zk)单调递减有下界,且当k充分大时k∈,由式(11),式(12)及式(18)得∑k∈K1‖

从而Hμ*(z*)=0,根据文献[4]的引理3.1可得H(z*)=0,即z*是混合互补问题的解.由引理3.1知,这与K是有限集的假设矛盾.

若Hμ*(z*)≠0,则

Hμk(zk)TH′μk(zk)Tdk<-max {ρ‖dk‖Ψμk(zk),ρ‖dk‖2}<-ρ‖dk‖Ψμk(zk).

而

-‖

TH′μ*(zk)Tdk<-ρ‖dk‖Ψμk(zk),

即‖

0,这与式(19)矛盾.

综合以上可知μ*=0,即由梯度步dk=-

3.2,引理3.3立即得本定理.

证毕

定理3.2 设序列zk由算法2.1产生且收敛于方程组(4)的解,若J(z*)=H′μ(z*)非奇异且在z*点附近Lipchitz连续,则当k充分大时,问题(7)的信赖域半径有正下界,牛顿步dkN=-J-1kHμk(zk)为其最优解,其中Jk=H′μk(zk),从而算法是局部二阶收敛的.

根据牛顿收敛定理即可证明本定理.

5 数值试验

本节就低维混合互补问题进行数值试验,比较文中算法2.1与文献[6]中的算法.算法中,终止准则为ε=10-6,参数选取为ρ=10-10,α=0.4,η=0.5,λ=0.8,γ=0.6,σ=0.01,Δmin =0.01.用Matlab程序实现.

算例1 考虑下面非线性互补问题

F(x)=3x21+2x1x2+2x22+x3+3x4-62x21+x1+x22+10x3+2x4-23x21+x1x2+2x22+2x3+9x4-9x21+3x22+2x3+3x4-3.,

考虑约束集Ω=[a,b],其中a=(0,0,0,0)T.b=(105,105,105,105)T,这个问题在区间[0,+

算例2 考虑下面混合互补问题

F(x)=400x31+2x1-400x1x2-2-200x21+220.2x2+19.8x4-40360x21+2x3-360x3x4-219.8x2-180x23+220x4-40.,

考虑约束集Ω=[a,b],其中a=(-10,-10,-10,-10)T.b=(10,10,10,10)T.这个问题在区间(-

根据上面2个算例的两种算法比较,对于算例1,文献[6]中算法具有一定的优势,主要是迭代次数较少.对于算例2,目标函数非线性程度较高,本文算法具有较为明显的优势,主要表现在迭代次数较少.但是笔者在试验过程中发现文中算法2.1稳定性受初始点的影响较大,如何改进算法的稳定性将是我们今后的任务.同时,如何利用混合互补问题本身的特性来构造算法将是以后更加深入研究的方向.

参考文献

[1] 陈为民. 求解非线性互补问题的光滑化方法[D]. 长沙:湖南大学,2004.

[2] YANG Yu-fei,QILi-qun. Smoothing trust region methods for nonlinear complementarity problems with P0-functions [J]. Annals of Operations Research, 2005,133(1):99-117.

[3] MA Chang-feng, KANG Tong. A Jacobian smoothing method for box constrained variational inequality problems [J]. ApplMathand Comput, 2005, 162(3):1397-1429.

[4] 何郁波. 混合互补问题的光滑化方法[D].桂林:桂林电子科技大学计算科学与数学学院,2006.

[5] POWELLM J D. Convergence properties of a class of minimization algorithms, in: Nonlinear programming [M]. New York: Academic Press, 1975.

[6] MA Chang-feng. Quadratic convergence of damped newton’s method for bi-obstacle problems[J], Mathematics in Economics, 1998,15(1):88-94.

The Convergence of a Smoothing Method

for the Mixed Complementarity Problem

HE Yu-bo1,MA Chang-feng2,DONG Xiao-liang3

(1.Department of Mathematics and applied mathematics, Huaihua University,Huaihua,Huna 418008,China;

2. School of mathematics and computer science, Fujian Normal University, Fuzhou,Fujia 350007,China;

3. School of Information and computation science, the North University

for Ethnics, Yinchuan,Ningxia 750021,China)

Abstract We convertedthe mixed complementarity problem into a system of nonsmooth nonlinear equations by using Fischer-Burmeister function,and we used a smooth function to approximate the Fischer-Burmeister function. By combining trust region method with gradient method, a Jacobian smoothing method was proposed. Under some conditions, we provedthe global convergence and local convergence of the algorithm. Numerical result indicates that the algorithm is quite promising.

混合算法篇4

关键词：遗传算法,启发式算法,车间作业调度

1 引言

作业车间调度问题(Job—shop Secheduling Problem,JSP)是一类满足任务配置和顺序约束要求的资源分配问题,是最困难的组合优化问题之一[1],由于该问题计算复杂性过高,因此在工程实践中,大多采用启发式算法求其近优解.随着人工智能和计算机技术的发展,一些较复杂的优化方法得到了迅速发展,如神经网络、模拟退火和遗传算法等,并已成为调度理论的研究热点。

本文提出应用混合遗传算法即:在遗传算法中融入启发式算法的方法来解决生产调度的排序问题。遗传算法作为一种群体优化算法,通过选择、变异、交叉等操作,使解集性能不断得到进化,最终以较快的速度进行搜索,但其存在早熟和收敛性难以控制的问题。而传统的启发式算法结构简单,搜索速度快,但全局搜索能力差,容易陷入局部最优。因此把传统的启发式算法嵌入到遗传算法中构造一个能力更强的遗传算法对于解决复杂的优化问题是很有意义的。该算法将遗传计算的并行性、记忆功能和启发式算法的快速搜索能力相结合,提高了求解质量。

2 混合遗传算法

本文将传统的启发式算法和遗传算法结合起来,应用该混合遗传算法解决作业计划排序问题。针对遗传算法的早熟和收敛性的问题,加入启发式算法的一些规则,同时对遗传算法的一些关键参数(如交叉概率、变异概率)设置了自适应功能,使得算法在车间作业调度方面得到改进。

我们主要通过以下方式实现遗传算法的改进:

(1)把启发式嵌入到初始化中,产生一个适应性好的初始解群。按这种方式,混合式遗传算法能够优于启发式算法。

(2)将启发式嵌入到评估函数中,将染色体解码为作业调度。

(3)自适应设计个体的交叉率与变异率。

其中,遗传算法被用于个体中的全局搜索,而启发式算法在染色体中施行局部探寻。由于遗传算法和启发式算法的互补性能,混合遗传算法将优于两种单独的算法。

3 生产调度问题描述

所谓调度,就是为了实现某一目的而对共同使用的资源进行时间分配。本文所说的生产调度问题,是指用一组机床加工一组零件,如何安排每台机器上的工件加工顺序,使得某种指标(比如,总的加工时间、总的加工费用或者相对加工时间等)最优。

一般零件的加工过程由若干工序组成,且应满足一定的约束关系,车间作业调度约束条件的数目和内容会随作业需求和作业环境的不同而不同,如零件生产的工艺需求、设备条件等。

本文定义P={P1,P2,…,Pn}代表n个工件的集合,M={M1,M2,…,Mm}代表m台机床的集合,工件Pi的工序数目为Ki,工件Pi的加工工序为Pi1(Ji1),Pi2(Ji2),…,Pi Ki(Ji Ki)(Ki∈Z+,i=1,2,…,n),其中Z+表示正整数,Ji Ki表示工件Pi第Ki道工序在某台机床上加工,(Ji Ki∈M)。STi Ki表示工件Pi第Ki工序的加工起始时间,ETi Ki表示工件Pi第Ki工序的加工终止时间。用Ti Ki表示工件Pi第Ki工序的加工时间。

基于以上的定义,作业调度要满足以下几个约束:

1.每个工件包含一个由多道工序组成的工序集合,工件的工序顺序是预先给定的。

2.一台机床仅能同时加工一个工件的一道工序。

3.不同工件的工序之间没有先后的约束。相同工件工序满足先后约束关系。

4.工序Pi Ki(Ji Ki)与Pi Ki+1(Ji Ki+1)之间的时间间隔为零,即STi Ki+1-ETi Ki=0。

5.STi Ki≥0,即每个工件的每道工序的开工时间一定大于或等于零。

6.∑Ti Ki=Ti(Ti为工件Pi的总加工时间),即要求所有工件在交工期前加工完毕。

4 混合遗传算法求解作业调度

⑴.参数编码

应用遗传算法,必须将问题空间的参数转换成遗传空间的、由基因按一定结构组成的染色体或个体,这一转换操作就是编码。编码有基于工序的表达方法、基于工件的表达方法、基于位置“列表”的表达方法、基于机床的表达方法等。这里采用基于机床的表达方法。染色体编码为机床的序列,基于该机床序列,具体编码如下:

工件编号0 1,0 2,…n,每个工件的工序编号0 1,02,…k,机床编号01,02,…m。那么符号01.01.01表示工件01的01工序在设备01上完成。以3(工件)×3(机床)为例。假设工件中工序最多为4,机床对应不存在的加工工序则定义为00.00.00,工件工序加工必须满足工序先后关系的约束。则如表1所示,表示了工件、工序与机床的关系。

⑵.初始种群的生成和适应度函数的设计

初始种群的产生采取随机产生的方式,这样容易达到解空间所有状态的遍历。通过约束条件检验判断其是否为可行解,若是,将其加入初始种群;否则淘汰。但是初始群体的随机产生加大了进化的代数,大大增加遗传算法的计算时间,这里加入了启发式算法,运用启发式算法的局部搜索能力强的特性,加快优良个体的产生。

个体的适应函数应该是工件总的加工时间单调递减函数,即总工时越小,个体适应度函数值越大;总工时越大,个体适应度函数值越小。个体i的适应函数定义为:

式中Cmax为f(x)的最大值估计。初始种群的生成流程图如图1所示。

⑶.选择操作:采用了轮盘赌选择方法。若某个个体i,

其适应度为fi,则选择概率为:选择适应度最优的Pop Size个个体作为新一代种群。

⑷.交叉操作:交叉算子采用一点交叉运算,对参与交叉运算的两个个体母体M和父体F依据自适应交叉概率Pc进行交叉运算。记参与交叉运算的两个个体母体M和父体F,M与F经交叉运算后产生的子代个体记为D和S,染色体长度为L。随机地生成整数p,1

式中,fmax—群体中最大的适应度值;favg—每代群体的平均适应度值;f'—要交叉的两个个体中较大的适应度值。

自适应调整与算法的收敛程度成反向,从而有效地防止了算法收敛于局部最优,并使好的进化结果得以保存。

⑸.变异操作:变异操作采取互换变异,即先随机生成整数m,m取值范围为机器数量。在本机器上随机选择某一位,将此道工序与相临的工序互换。变异时要注意相临加工工序是否是同一工件的加工,如果是,变异后的染色体非法。自适应变异概率P?m定义如下:

式中,fmax—群体中最大的适应度值;favg—每代群体的平均适应度值;f—要变异个体的适应度值;

⑹.目标函数:本文将工件完工时间最小化作为目标,其目标函数为:

惩罚技术是用遗传算法解约束优化问题中最常用的技术[2]。本质上它是通过惩罚不可行解将约束问题转化为无约束问题。在遗传算法中,惩罚技术用来在每代的种群中保持部分不可行解,使遗传搜索可以从可行域和不可行域两边来达到最优解。

惩罚策略的主要问题是设计一个惩罚函数p(x),从而能有效地引导遗传搜索达到解空间的最好区域。对于本文研究的作业调度问题,根据上面的目标函数,相应的惩罚函数定义为所有工件的超期时间之和。设wai为工件i的超期时间段,则相应的惩罚函数表示则带有惩罚项的调度的目标函数表示为:

5 调度算法应用

为了检验的合理性,现采用文献[3]中的例2。该例由4台机器和8个工件组成,每个工件分别在4台机器上各加工一次,每个工件的加工路线与每道工序的加工时间按照文献[3]所示,如表2。

采用混合遗传算法进行作业计划排序,基本参数设置为:初始种群数=20,遗传代数=200代,经遗传算法重组运算后,作业计划的排序结果GANTT图如图2和3。由图中可见,最长加工路径为33,整个系统的设备空闲等待时间为2。

文献[3]中的例2的任务在文献[4]中用神经网络方法排序,最长加工路径为36;在文献[3]中采用基于效率函数方法经调度后,最长加工路径为33,但是设备的空闲等待时间为3。采用本文混合遗传算法经调度后,最长加工路径为33,设备的空闲等待时间为2。因此,根据例2的执行结果,采用本文研究的混合遗传算法进行作业计划排序,不仅所得的最长加工路径最短,而且设备利用率也是最高的。

6 结束语

车间调度问题已经证明为N P问题,难以找到能够求得最优解的确定性调度算法。又由于遗传算法的优良特性,因此,采用遗传算法对车间调度问题进行求解已成为求解该类问题的趋势。本文提出的基于混合遗传算法的调度算法,融入启发式规则,充分发挥遗传算法优势的同时,又加入启发式算法的快速搜索等优点,提高了分配效果。实例表明该算法能够取得较优的调度结果。

参考文献

[1]GERVEY M R,JOHSON D S,SOTHI R.The com-plexity of flowshop and jobshop scheduling[J].Mathematics and Operations Research1976(1):117-129.

[2][日]玄光男,程润伟著,汪定伟,康加福,黄敏译,遗传算法与工程设计[M].北京:科学出版社,2000.

[3]常会友,刘丕娥,张淑丽,王凤儒,基于效率函数求解的单件车间调度问题的算法[J].CIMS计算机集成制造系统.1998,(4):5-6

混合算法篇5

基于混合禁忌搜索算法的供应链排序问题

摘要：分析非标准件加工企业供应链的特点,提出协同优化订单分配、生产调度和批量运输调度的多工厂多客户供应链排序问题.以工件的.最长订货提前期与总成本加权之和最小化为目标,构建问题的数学模型.在分析解的最优性条件基础上,设计一种基于矢量组编码方法的混合禁忌搜索算法.算法对可行域进行分区,通过基于插入、交换两种邻域操作的禁忌搜索算法选择子区域,采用基于块结构邻域操作的禁忌搜索算法搜索子区域中的优良解.采用所提混合禁忌搜索算法对算例进行优化求解,并对采用不同编码方法、不同启发式算法的算例结果进行比较,结果表明所提出算法的有效性. 作者：蒋大奎李波 Author： JIANG DakuiLI Bo 作者单位：天津大学管理与经济学部天津300072 期刊：机械工程学报 ISTICEIPKU Journal： JOURNAL OF MECHANICAL ENGINEERING 年，卷(期)： ,47(20) 分类号： N945 TP29 关键词：供应链排序多工厂批量运输禁忌搜索机标分类号： N94 TP3 机标关键词：混合禁忌搜索算法企业供应链排序问题Search AlgorithmHybrid编码方法子区域最优性条件启发式算法订货提前期运输调度优化求解协同优化算法选择数学模型生产调度邻域结果构建问题基金项目：教育部新世纪优秀人才支持计划，高等学校博士学科点专项科研基金基于混合禁忌搜索算法的供应链排序问题[期刊论文]机械工程学报 --2011,47(20)蒋大奎李波分析非标准件加工企业供应链的特点,提出协同优化订单分配、生产调度和批量运输调度的多工厂多客户供应链排序问题.以工件的最长订货提前期与总成本加权之和最小化为目标,构建问题的数学模型.在分析解的最优性条件基础上...

求解排课问题的遗传蚁群混合算法篇6

针对排课问题，本文将遗传算法和蚁群优化算法融合，提出了一种遗传蚁群混合的优化算法。首先利用遗传算法产生初始信息素的分布，在运用蚁群算法求精确解。实验表明该算法取得了良好的适应度值和时间性能。

排课问题涉及到教师、教室、班级、课程、时间等诸多因素，是一个处理起来相当复杂的优化决策问题。排课问题已被证明是一个NP完全问题，也是一个很有研究价值的实际问题。

文献提出了一种新型的解决排课问题的离散粒子群算法，在三维空间中建立模型，并引入了冲突检测及变异等操作。文献提出了自适应遗传算法，该算法采用三维编码方案，并在交叉概率和变异概率、适应度函数、初始种群的生成等方面都进行了设计和优化。文献应用蚁群遗传算法进行排课研究。在本文将遗传算法与蚁群算法融合来研究排课问题。

排课问题描述

问题描述

排课问题实际上是一个五维空间上的组合优化求解问题。五维是指教室、教师、班级、课程、时间，要实现的目标是上述五元素的最优化配置，对于这一类组合优化问题要寻求一种合理的近似最优解。

约束条件

排课方案必须满足两大类约束：硬约束是衡量一个排课方案是否可行的标准，软约束是衡量一个排课方案优劣的标准，而反映一个排课方案优劣的标准有多种情况。

硬约束是指在排课过程中必须遵守的规则，一般包含以下几个方面：同一时间段内，一位教师不能排一门以上的课程，不能占有一个以上的教室；同一时间段内，一个班级不能上一门以上的课程；同一时间段内，一个实验室不能排一门以上的课程；教室能够容纳上课班级的学生人数。

软约束条件是指在排课方案中可以满足但又可以不完全满足的条件，根据各学院情况不同而有所差别，包含以下几个方面：专业相关的重要课程尽量安排在较好的教学时间段；多学时的课程每周的安排要错开（学时大于等于4课时，能够尽量隔天排一次课）；一周内每天课时尽量平均；教室利用率高，上课班级人数尽量接近教室可容纳人数。

遗传蚁群算法

算法基本思想

遗传算法在搜索初期具有较高向最优解的收敛速度，但是达到一定时刻后不能有效利用系统中的反馈信息，使搜索具有盲目性，导致求解速度会明显降低。由于信息素匮乏，蚁群算法在初期搜索速度缓慢，当信息素累积到一定程度之后，蚁群算法求解效率会迅速提高。而遗传蚁群混合算法的基本思想是，首先采用遗传算法产生初始信息素的分布，当遗传算法达到一定迭代次数或群体中向最优解的进化速率低于一定程度时结束遗传算法，应用蚁群算进行最优解的求解。如图1所示。

遗传算法

编码。针对排课问题的特点，使用三维数组对排课信息进行保存，具有编码和解码都很直观，方便冲突检测，算法的复杂度低等优点。

混合算法篇7

目前,在云计算环境下基于遗传算法的资源调度问题已经进行了大量研究工作。文献[2]提出一种双适应度的遗传算法,通过两个适应度函数来选择种群,从而保证较短的总任务执行时间和任务平均执行时间。由于云计算的中心思想,是实现廉价高效的运算,对整个系统进行负载均衡研究是十分重要的。文献[3]通过自适应的变异概率,对任务响应时间和资源损耗代价同时进行优化。不但最短化任务执行时间,而且使虚拟机群的资源利用率最高。但未解决传统遗传算法局部搜索能力差以及早熟现象等问题。因此从改变染色体的编码方式出发,文献[4]采用组方式和三空间分割方法分别对染色体进行编码和译码,并根据不同染色体长度的变化设计交叉和变异遗传算子,算法对解空间内的多个区域同时搜索,具有群体和自我进化的优势,优化一次即可获得对不同目标的权值运算多次才能得到的最优解,提高了获得最优解的速度。文献[5]基于负载均衡度和最优跨度准则,改进了染色体编码方式,这种编码方式所形成的基因串的总数小于系统资源池内的总数,所以在计算过程中可以达到最优的资源调度,从而达到提高计算速度和计算准确度的目的。从初始化种群出发,文献[6]通过染色体匹配率将种群个体均匀分布在解空间上,有效地避免了早熟问题; 并通过对作业运行时间、费用、系统带宽以及服务质量的子适应度函数加权获得总适应度函数,并通过调节权值系数来满足不同用户需求。从混合遗传算法出发,文献[7]使用了多Agent与遗传算法相结合的混合遗传算法,通过个体之间的交互、协作和自学习,在解决负载均衡问题的同时具有更好的算法收敛性能。文献[8]提出了将贪婪和遗传算法相结合的混合遗传算法,对每个染色体都通过贪婪算法进行处理,达到内存使用量最小,同时能够在较短的时间内找到问题的优化解。但这种使得内存使用量最小的方法依然会出现局部最优解的可能。文献[9]同样采用了贪婪与遗传算法相结合的方式,这里贪婪算法只对无效染色体进行处理,将物理机使用数量引入总适应度函数,可降低局部最优解的出现。并分别从物理机使用数量、负载均衡度和迁移次数3 个方面进行加权组合,对资源利用率、能源节约和迁移代价多目标问题进行联合优化。但负载均衡度和迁移次数的适应度函数在不同染色体间的差异度不足,限制了算法的收敛速度; 同时只通过物理机数量来衡量内存使用量是不完善的。

针对文献[9]的不足,本文提出了以下两个改进方法: 一是对其适应度函数进行改进,从遗传算法染色体选择性出发,通过提高染色体间的优选概率,进而提升遗传算法的收敛速度; 二是提出了内存适应度函数,将其与物理机数量适应度函数相结合,增加相同物理机数量染色体间内存使用量的差异度,进一步提高内存使用率的同时,也提高了选择算子中的择优性能。仿真结果表明,该方法能够有效提高遗传算法的收敛速度。

1 总体架构调度系统模型

任务上传到云端的数据中心,数据中心的调度器响应该任务,将其随机分配给物理机PM,并在PM上建立相应的虚拟机VM来执行该任务。由于应用程序信息的不确定性以及PM处理能力的差异性,导致了PM负载不均衡,因此需要实施高效的调度策略,通过迁移VM技术来协调不同PM上的负载,提高资源利用率,同时也降低系统能耗。调度系统模型示意图,如图1 所示［10］。

通过云端的检测模块,检测初始负载信息和VM的配置信息。然后执行调度策略,得到新的配置方案。将其与原配置方案进行比较,是否提高资源利用率。具体通过以下指标进行判断: PM的使用数量和使用的PM负载均衡度。由于通过迁移VM技术来执行调度策略的结果,所以还需要考虑VM迁移成本。若迁移成本太高,则不执行调度算法; 反之执行调度算法。

2 混合遗传算法

为了解决云端资源优化问题,可采用基于多维混合遗传算法的资源调度策略［9］。算法考虑了3 个评价指标,包括PM使用数量、负载差异度和VM迁移次数。并将其进行加权组合,实现了权值可调的多目标优化。

2. 1 混合遗传算法

混合遗传算法执行过程如图2 所示。

1) 选取种群数目P,种群中的个体称为染色体。每个染色体代表着一种VM配置方案,即将所有VM分配在哪些PM上。

2) 计算种群中每个个体的适应度函数值。

3) 选择: 通过适应度函数值得到累积概率,进行染色体的选择。

4) 交叉: 采用单点交叉法,即随机设置一个交叉点,在该点相互交换部分染色体。

5) 修正无效因子: 由于每个PM内存是有限的,这样经过交叉后的染色体,可能会产生无效因子,此时通过贪婪算法对无效因子进行修正。

6) 变异: 依据变异概率将染色体中的某个基因值用其他值替换,从而形成一个新的个体。

7) 修正无效因子: 同步骤5) 。

8) 是否达到最大进化代数,如果已是最大代数,则产生最优个体,算法结束。反之,则返回到步骤2) 。

注意,为了确保当前种群中最好的个体不被交叉或变异操作破坏,将其直接保留至下一代,覆盖下一代种群中最差的个体。

2. 2 适应度函数

适应度函数由3 种子适应度函数组合而成,表示染色体被选择的概率。适应度函数值越高,染色体被选中的概率越大,反之,则被选中的概率越小。3 种子适应度函数代表着3种评价指标,分别是对物理机使用数量、负载差异度和VM迁移次数的评价。下面进行具体描述。

1) 子适应度函数Ei1

物理机数量的评价函数Ei1为

式中: pm表示云端的物理机数量; counti表示第i条染色体占用的物理机数量; p表示种群中含有的染色体数量。

2) 子适应度函数Ei2

云端负载主要是3 种负载: CPU负载、网络吞吐量和I/O负载。假设第k个PM含有n个VM,3 种负载分别用a,b,c表示。这样n个VM的3 种负载的大小是: [ak1,ak2,…,akn],[bk1,bk2,…,bkn]和[ck1,ck2,…,ckn]。为了方便处理,将3 种负载的值都归一化,即值的范围在[0,1]之间。每种负载的平均值分别为:。

则第k个物理机的负载差异度为

则第i个染色体负载差异度为

因此,负载差异度的评价函数Ei2可表示为

式中: Si表示第i条染色体的负载差异度; ∑S表示种群中所有染色体的负载差异度之和,即。

3) 子适应度函数Ei3

迁移次数的评价函数Ei3可表示为

式中: Mi表示第i条染色体需要迁移VM的次数; ∑M表示所有染色体需要迁移VM的总次数,即。

4) 子适应度函数Ei

Ei为总适应度函数,其将3 个子适应度函数进行加权求和

式中: x,y和z分别为Ei1,Ei2和Ei3的权重系数,且x + y + z =1。通过改变这3 个系数的值来调节评价指标所占的权重。

2. 3 评价函数的差异度

以负载差异度的评价函数式( 4 ) 为例,,其分母是对适应度函数进行归一化,而分子决定了不同染色体间的差异度。假设两个染色体的评价函数值分别为E12和E22,其比值为,若比值接近1 说明两个染色体的评价函数值差异度小,反之差异度大。从上式可以看出,差异度受到∑S的影响。因此随着p的增大,的值将会接近1,即两个染色体的评价函数值的差异度将会缩小。而评价函数值差异度的缩小,会导致染色体在选择时的择优性能下降,影响到算法的收敛速度。

3 改进的评价函数

3. 1 改进的适应度函数

1) 子适应度函数E'i2

因此,将子适应度函数Ei2中的评价指标总量用其最大值进行替换,即式( 4) 中的∑S改为Si的最大值,得到改进后负载均衡度的适应度函数E'i2,可表示为

其中,Smax表示种群中最大的负载差异度。

可将E'i2和Ei2的选择概率简化为

式中:为染色体协方差的归一化值;为所有染色体的归一化协方差和。由于中至少有一个 Smax项，且ni≤1,故1≤N < p。

从式( 8) 和式( 9) 可以看出,E'i2和Ei2均是负斜率的一次函数,其斜率分别为

由于N≥1,所以,即︱k'i2︱≥︱ ki2︱。这表明当ni取值区间为[0,1]时,E'i2的函数值范围将大于Ei2的范围。因此不同染色体的负载差异度对应的选择概率将比原有的选择概率更加稀疏,这意味着改进后的评价函数增加了不同染色体间优劣的区分度。

当负载差异度取最小值,即Si= 0,此时ni= 0,Ei1和E'i1都取得最大值且分别为

当负载差异度取最大值,即Si= Smax,此时ni= 1,Ei1和E'i1都取得最小值且分别为

由于N≥1,,所以E'i2max≥Ei2max。且仅当种群的染色体个数为1,负载差异度为Smax时,等号才成立。同理可得E'i2min≤Ei2min。则E'i2和Ei2随ni的变化如图3所示。

从图3 可以看出,当ni取较大值时,E'i2≤Ei2,这意味着差异度大的染色体以E'i2作为评价函数时,该染色体被选中的概率小于以Ei2作为评价函数时该染色体被选中的概率; 同理,当ni取较小值时,E'i2≥Ei2,这意味着差异度小的染色体以E'i2作为评价函数时,被选中的概率大于以Ei2作为评价函数时的概率。所以改进后的适应度函数提高了好的染色体被选择的概率,降低了差的染色体被选择的概率,即增加了不同负载差异度染色体的选择概率的区分度,从而提高了遗传算法的收敛速度。

2) 子适应度函数E'i3

与E'i2原理相同,由于虚拟机最大迁移次数为虚拟机的总个数。因此可将Ei3改为E'i3

式中: Mi表示第i条染色体需要迁移虚拟机的次数; vm表示总虚拟机的个数。

而对于物理机数量的评价函数Ei1,其使用物理机数量的最大值即为物理机的总数量pm,因此不需要进行改动。

3. 2 内存适应度函数

PM内存利用率对衡量资源利用率是一个很重要的指标。虽然贪婪算法是以内存最小化为目标修正无效因子,但是在选择最优染色体的时候,评价函数并不会因此选择内存空闲率低的染色体。图4 所示为更新迭代150 次后,物理机数量达到最小染色体的内存使用量。从图中可以看出,具有物理机数量最小的染色体方案不止一种,但每种方案物理机的内存空闲量是不同的,这表明评价函数不仅要考虑物理机数量,同时也应该考虑到内存使用量。所以需要选取恰当的物理机以便满足虚拟机的需求,同时还不浪费物理机的内存资源。

1) 内存利用率评价指标

式( 17) 为物理机内存利用率评价函数。其中,sum_ pm表示云端所有物理机的内存和; Ri表示第i个染色体的闲置内存量,闲置内存量为染色体中所使用PM的总容量与所有虚拟机的内存容量之差。

2) 适应度函数E'i

总的适应度函数需要综合所有子适应度函数,原有的方法是将子适应度函数进行加权求和得到总的适应度函数Ei。但在一些情况下,这样直接进行加权求和存在一定的问题,如物理机数量越小内存空闲率就会越小,这样内存空闲率与物理机数量具有一定的相关度,如果直接进行加权,会使得总的适应度函数值偏向物理机数量和内存空闲率这两个评价指标,会造成对其他评价指标的不公平性。

将Ei1与Ei4的和平均得到E'i1

从式( 18) 可以看出,相同物理机数量的Ei1具有相同的值,Ei4的引入将增加具有相同Ei1染色体的区分度。这样有利于增加物理机数量的择优性,从而提高算法的收敛性。并且在选择染色体时,E'i1不仅兼顾了内存空闲率,同时还不会影响到其他不相关的评价指标在总评价函数中的权重,保证了评价指标之间的公平性。总的评价函数如下

式中: x,y和z分别是E'i1,E'i2和E'i3的权重系数,且x + y + z =1。可通过改变这3 个系数的值来调节评价指标所占的比重,满足不同的优化需求。

4 仿真结果及分析

4. 1 遗传算法收敛性

仿真参数如表1 所示。

为了更好地分析物理机负载均衡度和虚拟机迁移度的收敛性能,分别取负载均衡加权系数为0. 9 和迁移度加权系数为0. 9,对原始算法与改进算法的收敛曲线进行对比,如图5、图6 所示。物理机数量变化率为最优方案与原始方案的物理机数量之比; 负载均衡变化率为最优方案与原始方案的协方差之比; 迁移次数变化率为最优方案的迁移次数与总的VM数量之比。

从图5、图6 可以看出,随着遗传迭代次数的增加,负载均衡变化率和迁移次数变化率逐渐降低。但改进后的负载均衡度和迁移次数变化率曲线整体要低于原始的收敛性曲线,说明在相同的遗传迭代次数下,改进后的遗传算法的收敛速度比原始方法的收敛速度快,这与理论分析一致。

图7、图8 所示迭代150 次后,负载均衡度和迁移度随权值变化曲线。

从图7 中可以看出,随着负载加权系数y的逐步增大,负载均衡度在Ei中的比重就会增大,所以负载均衡变化率会逐步降低。同时,从图8 可以看出,随着迁移度权重z的增大,迁移次数变化率也逐步降低。但是经过改进后得到的负载均衡度曲线和迁移次数变化率曲线整体均低于改进前的负载均衡度和迁移次数变化率曲线。这表明改进后的方法在不同的加权系数下均具有更好的收敛速度。

4. 2 内存使用率的收敛性

图9、图10 所示为E'i的加权系数x = 0. 9 时,内存空闲率与物理机使用率的收敛性对比图。其中,实线表示添加了内存使用量评价函数的内存收敛曲线; 虚线表示原始未添加时的内存使用量收敛曲线。内存空闲率为当前最优方案中物理机的空闲内存与物理机总内存之比。

从图9、图10 中可以看出,对E'i添加了内存使用量的评价函数后,其内存空闲率曲线和物理机数量曲线整体低于未添加内存使用量的收敛曲线。这表明添加了内存使用量评价函数,有利于提高内存空闲率和物理机数量的收敛性能。

图11 所示为各指标随E'i1的权值变化曲线。其中内存空闲率与物理机数量变化率曲线均低于改进前,同时迁移次数和负载均衡度曲线在改进前后基本保持不变。这表明在不同加权系数下,内存使用量评价指标的引入,有利于提高内存空闲率与物理机数量变化率的收敛性。同时,这种引入新评价函数的方法,并不会对负载均衡度曲线和迁移次数变化率产生影响。

5 小结

本文基于混合遗传算法在云计算资源调度中的应用,对其收敛性能进行了分析,并通过改进其评价函数,增加了适应度函数值在不同染色体间的差异度,提高了染色体的择优性。同时提出了内存使用率的评价函数,通过将物理机数量与内存使用量适应度值相结合,提升了内存的优化效率。最后通过仿真对比,表明算法的收敛速度得到了有效的提高。

摘要：在云计算中,系统规模和虚拟机迁移数量都是十分庞大的,需要高效的调度策略对其进行优化。将云计算的任务分配抽象为背包求解问题,可通过遗传算法进行求解。传统的遗传算法具有局部搜索能力差以及早熟现象的缺点,采用遗传和贪婪相结合的混合遗传算法。针对混合遗传算法在资源利用率与能源消耗的收敛速度较慢问题,通过改进适应度函数,改变了适应度函数在不同染色体间的差异度,从而提高了染色体在选择算子中的择优性能。仿真结果表明,该方法能够有效提高混合遗传算法在云计算资源优化中的收敛速度。

基于特征进化的混合遗传算法篇8

遗传算法GA (Genetic Algorithms) 是近年来发展起来的一种具有普适性的进化算法, 对多种工程应用问题显示出较强的求解能力, 被成功地应用于诸多领域[1], 但GA仍存在收敛速度慢和早熟性收敛两方面问题。许多研究结果表明, 将GA与启发式算法结合能有效提高求解旅行商问题 (TSP) 的质量[2,3,4]。文献[5]认为, 早熟性收敛主要是由有效等位基因的缺失造成的, 而有效等位基因与种群多样性密切相关。种群多样性越好则有效等位基因越丰富, 可保证遗传算子产生更多的新个体, 这些新个体是维持丰富有效等位基因的有效手段之一。

由此, 提出了基于特征进化的混合遗传算法, 该算法一方面结合高效的启发式算法, 加快算法的收敛速度;另一方面采用新的基于特征进化算子对有效等位基因进行保护, 保持算法在进化过程中产生更多高适应度的新个体补充到种群中, 更好地抑制算法早熟性收敛, 并能收敛于规模小于2 000的TSP全局最优解。

1改进的遗传算法

1.1启发式算法的选择与优化

在TSP研究领域, 常用的启发式算法主要包括2-Opt、3-Opt和Lin-Kernighan (LK) 算法。大量的实验和研究成果表明, 虽然LK算法具有较2-Opt和3-Opt更高的复杂度, 但表现了更好的优化质量, 以Concorde[6]提供的链式LK (CLK) 算法为蓝本进行研究。CLK算法的主要参数包括:重复次数、参照优化边集、Kicks类型等。如何选择上述参数, 是提高CLK算法运行效率和求解质量的关键。其中, 重复次数和Kicks类型可通过重复随机实验建立, 而参照优化边集建立的方法较多, 难以对某种具体的建立方法进行评价。文献[10]指出, 建立更合理的参照优化边集 (ROE) , 在提高对任意给定一条路径的优化质量的同时, 与其它ROE初始化方法相比, 在其它参数相同的情况下前者运行时间得到明显缩短, 为此采用前期研究结果建立ROE[12]:随机初始化50条环路, 利用CLK算法进行优化得到优化后的50条环路, 取这些环路所有边的并集, 该并集高概率包含全局最优解的所有边。

1.2特征进化遗传算子的设计

根据GA的最小诱导模式机理, 最小诱导模式普遍存在于个体之中, 对这些诱导模式的保护, 有助于加速算法的收敛速度。同时, 对于个体中已包含的属于算法收敛优化解或全局最优解中的基因块——有效基因块, 由于遗传算子随机性过强, 不能充分利用个体中的有效信息进行重组, 对有效基因块不具有判断能力。如果交叉点或变异点选择在这些有效基因块中的某个基因座时, 有效基因块将遭到破坏, 这势必影响算法的收敛速度和效果, 这种情况在GA收敛后期尤为明显。因此, 保护最小诱导模式和有效基因块, 对加速GA的收敛起到很大作用。

设任意两条路径p1和p2, 两者之间的相似距离为:

d (p1, p2) =|E (p1) ∩E (p2) |/N

设p*为全局最优解, 由于:[E (p1) ∩E (p2) ]∩E (p*) =[E (p1) ∩E (p*) ]∩[E (p2) ∩E (p*) ], 则有:[E (p1) ∩E (p2) ]∩E (p*) ≤min (E (p1) ∩E (p*) , E (p2) ∩E (p*) ) 成立。根据鸽巢原理, 若d (p1, p*) >0.5且d (p2, p*) >0.5同时成立, 则有:

$\frac{| [E (p_{1}) \cap E (p_{2})] \cap E (p^{*}) |}{Ν} \geq \min [d (p_{1}, p^{*}), d (p_{2}, p^{*})] - 0.5$

成立。由此有下式成立:

${\begin{cases} \frac{| [E (p_{1}) \cap E (p_{2})] \cap E (p^{*}) |}{Ν} \geq \min [d (p_{1}, p^{*}), d (p_{2}, p^{*})] - 0.5 \\ \frac{| [E (p_{1}) \cap E (p_{2})] \cap E (p^{*}) |}{Ν} \leq \min [d (p_{1}, p^{*}), d (p_{2}, p^{*})] \end{cases}$

根据文献[3]结论:CLK算法解质量平均达到0.8, 即 $\bar{d} = 0.8$ , 表明 $[E (p_{1}) \cap E (p_{2})] \cap E (p^{*}) \neq ϕ$ , 又由于:

${[E (p_{1}) \cap E (p_{2})] \cap E (p^{*})} \subset E (p^{*})$

恒成立, 可得以下结论:

结论1 对于两条与全局最优解相似距离超过0.5的路径, 二者边的交集中包含全局最优解部分边。两条路径与全局最优解之间的相似距离越大, 交集中包含的属于全局最优解的边数量越多。

当两个个体执行交叉或变异时, 两个个体的边交集中包含有效基因块的概率将随着GA进化过程的推进逐渐升高, 这是由于个体逐步接近收敛优化解或全局最优解, 与优化解或全局最优解之间的海明距离逐渐缩小, 其距离越小两个个体中相同的有效基因块数量越多, 则得到保护的概率越大。同样, 对最小诱导模式具有相同的效果。文献[10]也得到如下结论:经过CLK算法优化的环路与全局最优解的相似度平均达到80%。由此建立以下基于特征的两点交叉算子 (CTCO) 和单点变异算法 (CSMO) 。

算法1CTCO

输入:父代个体X1和X2

输出:交叉操作后的新个体X1′和X2′

Begin

1) 初始化 (建立一个空的边集合, 记为A) ;

2) 取A为X1与X2的边集的差集;

3) 若A中边的数量少于两个 , 则:

(1) 从所有的基因座中随机选择两个交叉点;

否则

(1) 随机从A中选取两条边;

(2) 根据所选取的边确定两个交叉点;

(3) 执行交叉, 形成两个新个体X1′和X2′

End

算法2CSMO

输入:父代的一个个体X1和参照变异个体X2

输出:变异操作后的一个新个体X1′

Begin

1) 初始化 (建立一个空的等位基因集合, 记为A) ;

2) 取A为X1的边集与和X2边集的差集;

3) 若A中的边数为0, 则:

(1) 从所有的基因座中随机选择一个变异点;

否则

(1) 随机从A中选取一条边;

(2) 根据所选取的边确定变异点;

(3) 执行变异, 形成新个体X1′

End

算法二中参照变异个体X2的选择可根据具体情况进行选择, 如果希望种群更快向最小诱导模式进化, 则可以选择种群中适应度最高个体;如果希望扩大种群的多样性, 可随机选择一个个体或选择种群中适应度最低的个体。

2基于特征进化的混合遗传算法

由于采用文献[12]方法建立的问题初始边集, 需要产生50条随机路径, 而GA中的种群初始化亦采取相同过程, 本文设计的GA的种群规模设置为50, 可用一个功能模块完成CLK参照优化边集的建立和GA种群初始化。

算法3 基于特征进化的混合遗传算法

输入:TSP数据集

输出:TSP的优化解

Begin

1) 初始化

(1) 建立一个空的边集合, 记为A; //CLK参照优化边集

(2) 申请种群空间Population;

2) 种群初始化

(1) repeater←1; //CLK参照优化边集使用的重复次数

(2) KickType←随机类型; //Kicks类型

(3) 建立问题的最近3近邻边集Ne;

(4) 循环K=50次, 做:

① 随机初始化一条环路p;

② p′←CLK (repeater, KickType, Ne, p) ;

③ 将p′中所有的边合并到A;

④ 将p′加入到Population;

3) 计算Population中每个个体的适应度;

4) repeater←N/2; //GA优化使用的重复次数

5) 循环直到达到终止条件, 执行:

(1) 执行选择算子选择两个体X1和X2;

(2) X1′, X2′←两点CTCO (X1, X2) ;

(3) X1′←单点CSMO (X1′, X2′) , ←单点CSMO (X2′, X11′) ;

(4) X1′←CLK (repeater, KickType, A, X1′)

(5) X2′←CLK (repeater, KickType, A, X2′) ;

(6) 计算X1′和X2′适应度;

(7) 替换种群中较X1′和X2′适应度更低的个体;

6) 返回种群中适应度最高的个体X*;

End

3实验情况及分析

下述实验环境均为Intel Core2 E6300 1.86GHz CPU, 1GB内存, 操作系统为Windows XP。数据集均采自TSPLIB95[11]。GA中交叉概率为0.615, 变异概率为0.15, 进化50代, 当算法搜索到全局最优解即行停止, 距离按取整方式计算。每个数据集重复求解30次, 并给出了平均解距离全局最优解的偏差值, 其中:

偏差= (平均环路长度-全局最优解环路长度) /全局最优解环路长度×100%

实验对比算法如下:

算法1 GA使用3-Opt局部优化算法;

算法2 GA使用重复N/2次且采用Quadrand 3近邻域参照优化边集初始化的CLK算法;

算法3 GA使用重复N/2次且采用先期研究成果文献[12]中方法进行边集初始化的CLK算法;

算法4 本文算法三——基于特征进化的混合遗传算法。

对比情况如表1, 表中标记下划线数据为该数据集上仅重复一次, 原因是算法单次不能收敛于全局最优解或收敛时间过长。

由于3-Opt算法较CLK算法的优化质量相差很大, 本文仅给出算法2、3、4的收敛对比曲线, 数据集为pr1002, 如图1所示。

从上述实验结果可见, 算法2、3、4均能收敛到问题的全局最优解。从图1的收敛曲线上看, 三种算法的收敛趋势差异很小, 但从表1的收敛时间上看, 算法2收敛时间约为算法3的2倍左右, 表明文献[12]提出算法的有效性。算法4在算法3基础上引入了特征进化算子, 在大规模数据求解上表现了良好的收敛时间, 在规模为1 889个城市问题的求解中, 仅花费了相当于算法2的1/9时间、算法3的1/3时间收敛到全局最优解, 验证了提出的算子的有效性。

4结束语

通过分析及论证, 本文建立了用于求解中小规模TSP的GA, 通过在GA中引入CLK作为启发式算法, 加快了GA的收敛速度, 同时提出了CTCO和CSMO两个特征遗传算子, 在高概率性保护种群中最小诱导模式和问题优化解的前提下, 为父代个体中非有效基因块基因座上的基因提供了更多进化机会, 较好地抑制了GA的早熟现象, 有效地提高了算法收敛速度和全局寻优能力。通过大量覆盖实验表明, 本文提出的GA算法, 将GA的全局寻优能力和CLK的局部寻优能力进行了较好的结合, 在本文规定遗传代数内能收敛到规模在2 000以内问题的全局最优解。

参考文献

[1] Xi Y G, Cai T Y, Yun W M.Survey on genetic algorithms [J].Control Theory, Application, 1996, 13 (61) :696-704.

[2]Baraglia R, Hidalgo J I, Perego R.A hybrid heuristic for the travelingsalesman problem[J].IEEE Transactions on Evolutionary Computa-tion, 2001, 5 (6) :613-622.

[3] Merz P, Freisleben B.Genetic local search for the TSP:New results [C].In:Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, 1997:159-164.

[4] Merz P, Freisleben B.Memetic algorithms for the traveling salesman problem [J].Complex System, 2001, 13 (4) :297-345.

[5] Potts J C, Terri D G, Surya B Y.The development and evolution of an improved genetic algorithm based on migration an artificial selection [J].IEEE Transactions on Systems, Man and Cybernetics, 1994, 24 (1) :73-86.

[6] David A, Robert B, VASEK C.Concorde network optimization package [CP/OL].http://www.tsp.gatech.edu/concorde/downloads/ codes/src/co031219.tgz.1997-08-08/2006-11-07.

[7]Jones T, Forrest S.Fitness Distance Correlation as a Measure of Prob-lem Difficulty for Genetic Algorithms[C].//ESHFILMANL.Proceed-ing of the 6th International Conference on Genetic Algorithms.San Ma-teo, CA:Morgan Kauffrnan, 1995:184-192.

[8] Lin S, Kernighan B W.An effective heuristic algorithm for the traveling-salesman problem [J].Operations Research, 1973, 31:498-516.

[9] Boese K.Cost versus distance in the traveling salesman problem[R].Technical Report, TR-950018, CS Department, UCLA, 1995.

[10] Lin S, Kernighan B W.An effective heuristic algorithm for the traveling-salesman problem [J].Operations Research, 1973, 31:498-516.

[11] University of Heidelberg.Traveling Salesman Problems Library [CP/OL].http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.1997-08-08/2006-11-07.

软件安全中混合加密算法的设计篇9

目前, 根据不同软件系统所应用的领域, 比较常见的加密算法有DES加密算法、RSA加密算法、Base64加密算法和维热纳尔加密算法等。针对不同算法的各自特点, 本文首先自定义一种简单的初始加密算法, 再对维热纳尔加密算法进行了优化改进, 最后结合Base64加密算法共同组成混合加密算法, 在很大程度上提高了加密算法的安全性。

2 基础加密算法

2.1 初始加密算法

初始加密算法是根据明文信息中的字符组成, 再借助字符的ASCII码, 进行相应的变换运算, 从而使原有的真实信息进行伪装, 避免被轻易的破解, 提高了系统加密保护的安全系数。

在一般的软件系统加密过程中, 组成明文信息的字符一般可以分为大写英文字母、小写英文字母、阿拉伯数字和其他特殊字符等四部分。因此, 在定义初始加密算法时, 需要根据不同种类的字符进行一定的变换运算处理。

具体如下:第一类变换:明文信息的字符是英文字母时, 明文在[A, M]范围内, 密文为明文的ASCII码值加45;明文在[N, Z]范围内, 密文为其ASCII码值加19;明文在[a, m]范围内, 密文为其ASCII码值减19;明文在[n, z]范围内, 密文为其ASCII码值减45。第二类变换:明文信息的字符是阿拉伯数字时, 明文在[0, 4]范围内, 密文等于明文乘以2再加1;明文在[5, 9]范围内, 密文等于明文乘以2再减10。第三类:当明文信息是其他特殊字符时, 密文与明文相同。

2.2 Base64加密算法

Base64加密算法主要的考虑了三个问题, 第一为是否加密;第二为加密算法复杂程度和效率;第三为如何处理传输。加密是必须的, 但是加密的主要目的不是让用户发送非常安全的Email。而是要达到一眼望去完全看不出内容就行。基于这个目的加密算法, 其复杂程度和效率也就不能太大或太低。

2.3 改进的维热纳尔加密算法

维热纳尔密码是一个非常著名的多码加密法, 主要是通过采用定义好的维热纳尔方阵, 以及自定义的密钥对明文信息进行加密。以前对于维热纳尔方阵的定义, 是通过以二十六个大写英文字母为依据, 依次循环不断改变排列顺序, 组成26×26级的方阵。为了提高此算法的复杂度, 同时提高保密性能, 本文在二十六个大写英文字母的基础之上, 再将十位阿拉伯数字随机插入到英文字母序列中, 最终构建成36×36级的改进维热纳尔方阵。

在维热纳尔加密算法中, 除了维热纳尔方阵之外, 还需要明文字符集和密钥。明文字符集主要是用来记录组成维热纳尔方阵所需要的字符。密钥是用来在对明文信息加密过程中, 指定字符所对应的加密字符。因此, 在改进的维热纳尔加密算法中, 改进维热纳尔方阵、明文字符集和密钥, 分别记为A、M和K。

改进微热纳尔方阵的明文字符集M定义为:

密钥K定义为:

因此, 针对上述定义的密钥K, 对明文信息字符串“H I S E N S E 2 011”进行加密变换, 得到的密文是“ILY4UD7K49G”。

3 混合加密算法的设计

混合加密算法是在上述基础加密算法的基础上, 由初始加密算法、改进优化的维热纳尔加密算法以及Base64加密算法共同组成的, 并且其实现的过程必须按照固定的顺序依次进行, 即先使用自己定义的初始加密算法, 再使用改进优化的维热纳尔加密算法, 最后使用Base64加密算法。以明文信息字符串“chongq”为例, 应用混合加密算法进行加密处理, 具体的实现步骤如下:

第一步:字符串“chongq”经过初始加密算法之后, 得到的加密字符串为“PUBATD”。

第二步:将改进优化的维热纳尔加密算法中的所使用的密钥K设定为:K={9, D, 7, F, 6, I}。

利用密钥K对字符串“PUBATD”继续进行加密处理, 得出的加密信息字符串为“QZF7B3”。

第三步:使用Base64加密算法继续对字符串“QZF7B3”进行加密换算, 得到加密字符串为“UVpGN0Iz”。

在计算机网络信息飞速发展的时代, 信息加密算法已经成为研究软件安全的一个重要领域, 取得了大量的研究成果。本文中所设计的混合加密算法, 是由三种加密算法组成的, 也可以在此基础之上, 再增加几种著名的加密算法或自己设计的新算法, 只有跟随时代发展而同步进步的技术才有更广阔的的应用空间和更长的生命周期。

摘要：随着计算机技术的飞速发展和Internet的广泛普及, 人们的生活正在发生着巨大变化。但是怎样才能达到使信息系统的机密信息不能够被泄漏, 或者即使被窃取了也很难被识别, 以及即使被识别了也极难修改, 这一系列的要求已经成为IT业界的热点研究课题。加密技术就是目前电子商务采取的基本安全技术手段。采用信息加密技术不仅可以满足信息保密性的安全需求, 而且还可以避免重要信息泄漏的安全威胁。因此, 加密技术是认证技术以及其它许多安全技术的基础, 也是信息安全的核心技术。

关键词：软件安全,混合加密算法

参考文献

[1]何茗.加密解密算法的实现及改进[J].西南民族大学学报 (自然科学版) .2010.1.

[2]徐荣峰.加密算法及其应用研究[D].西北工业大学.2006.

[3]刘玉珍, 王丽娜, 傅建明, 等, 译.密码编码学与网络安全原理与实践[M].第三版, 北京:电子出版社.2004.

混合算法篇10

在云计算时代, 数据中心的整合趋势进一步发展, 从早期的业务大集中到目前基于虚拟化技术的服务器整合, 从业务分布处理到可快速分发、快速迁移的计算资源整合, 从私有网络集中处理业务向云段延伸等, 这种趋势使得数据中心的规模呈现快速增长的趋势, 对网络安全提出更高的要求。

2 HADOOP平台

Hadoop是Apache软件基金会旗下的一个开源分布式计算平台。以分布式文件系统 (Hadoop Distributed File System, HDFS) 和Map Reduce (Google Map Reduce的开源实现) 为核心的Hadoop为用户提供了系统底层细节透明的分布式基础结构。HDFS的高容错性、高伸缩性等优点允许用户将Hadoop部署在廉价的硬件上, 形成分布式系统;Map Reduce分布式编程模型允许用户在不了解分布式系统底层细节的情况下开发并行应用程序。HDFS采取了主从 (Master/Slave) 结构模型, 一个HDFS集群是由一个Name Node和若干个Data Node组成的。其中Name Node作为主服务器, 管理文件系统的命名空间和客户端对文件的访问操作;集群中的Data Node管理存储的数据。HDFS允许用户以文件的形式存储数据。从内部来看, 文件被分为若干个数据块, 而且这若干个数据块存放在一组Data Node上。Name Node执行文件系统的命名空间操作, 比如打开、关闭、重命名文件和目录等, 它也负责数据块到具体Data Node的映射。Data Node负责处理文件系统客户端的文件读写请求, 并在Name Node的统一调度下进行数据块的创建、删除和复制工作。

3 基于AES和ECC的混合加密

在对称加密算法中, 也称为秘密密钥算法或单密钥算法加密密钥和解密密钥是相同的。常见的对成加密算法有DES、AES、RC5等。AES可以有效的抵御蛮力攻击和分析攻击, 其分组大小为128位, 支持的密钥长度为128位, 192位和256位, 相应的加密轮数10、12和14。公钥加密也称为非对称密钥, 是指一对加密密钥与解密密钥, 这两个密钥是数学相关, 用某用户密钥加密后所得的信息, 只能用该用户的解密密钥才能解密。常见的公钥加密有RSA、ECC等。RSA算法基于大整数因式分解的难度, 即单项函数问题。而ECC则是通过使用椭圆函数曲线构建对数问题, 这是一个NP问题, 时间复杂度为指数级别。

由于对称加密算法运行速度快, 但是密钥容易泄漏, 管理较为困难;而公钥加密算法密钥管理简单方便, 加密强度高, 但是算法运算量大导致运行速度慢。因此文中采用对称加密算法AES加密文件级别的大批量数据, 而用公钥加密算法ECC来加密AES密钥。这种混合加密算法既提供良好的加密速度, 又保证数据的安全性。具体步骤如下:

(1) 明文经过AES密钥加密, 形成密文。调用API上传密文至HDFS。 (2) AES密钥经过ECC公钥加密, 形成加密密钥。 (3) 通过ECC公钥计算出ECC私钥。

4 ECC的私钥管理

如果私钥被偷, 用户数据会被破解。如果私钥丢失了, 回不去了, 这将无法将加密过的数据解密。由于私钥的重要性, 需要建立一种方案管理私钥。为了安全的管理私钥, 可以将其通过指纹识别技术加密存储在云端。具体步骤如下:

(1) 用户向服务器提出上传私钥的请求。 (2) 服务器准备接收用户指纹信息。 (3) 用户将指纹信息连同密钥一起上传到服务器。 (4) 服务器在接收到该数据后, 将数据存储在HDFS。

其解密过程集体步骤如下:

(1) 用户请求下载私钥。 (2) 服务器接收用户的指纹信息, 并在HDFS中查找是否有匹配的记录。 (3) 若存在返回指纹信息对应的私钥给用户, 若不存在返回信息错误。

5 实验以及分析

我们进行完全分布式的集群场景 (复制=3) 来测试三重加密方案性能, 本文实验中搭建的Hadoop集群由1台namenode和2台datanode共3台服务器组成, 客户通过namenode来提交数据。3台服务器的配置为:intel i7-2600@3.40GHZ CPU;Hadoop版本为Hadoop2.0.5;Linux版本为ubuntu 14.04;JDK采用1.7.0.45使用6个不同大小的文件, 每个文件进行10次实验, 测试其加密性能, 其实验结果如表1所示。

本文的三重加密算法以AES加密为基础, 对密钥进行加密, 然后通过指纹信息进行保存。AES算法具有良好的抗差分和线性攻击攻击, 也能抵抗穷举攻击, 另外加上密钥的管理, 可以保证数据的安全性。加密数据的性能保持在4M/s, 考虑到云计算的集群能力, 可以提供较强的计算力, 故本算法在Hadoop下具有良好的适应性。

6 结语

本文所提出的三重加密方案, 在云计算的环境下具有良好的适应性。在接下来的日子里, 将对数据的传输过程进行研究, 达到既要保证其完整性, 又保证数据安全的目的。

摘要：云计算由于可以为用户提供按需分配的、可靠的、低成本的服务, 在近几年蓬勃发展起来。用户对云计算的安全性提出了越来越高的要求, 安全已经成为重要问题。单一的加密算法无法保证安全性, 本文将提出一种三重加密方案, 使用AES加密HDFS, 然后通过RSA加密密钥, 最后使用指纹识别技术将RSA的私钥存储在云端。我们在Hadoop平台下实验, 以研究其适应性。

关键词：云计算,混合加密,Hadoop

参考文献

[1]冯登国, 等.云计算安全研究[J].软件学报, 2011 (1) .

[2]Christof Paar, Jan Pelzl.深入浅出密码学.马小婷[M].北京:清华大学出版社, 2012 (9) .

混合算法篇11

关键词：混合算法；梯度优化法；神经网络

中图分类号：TP18 文献标识码：A 文章编号：1674-1161（2014）04-0025-02

人工神经网络技术的应用，为发动机故障诊断和状态监控提供了一个非常有效的工具。神经网络系统具有容错、联想、推测、记忆、自学习、自适应、多模式处理等功能，利用神经网络算法进行发动机振动故障诊断，不但能使发动机故障诊断系统应用于多种不同状态下的故障模式诊断，而且其噪声抑制力强、诊断准确。然而，在实际应用中常存在收敛速度慢、出现振荡等问题，网络训练经常出现瘫痪现象。在网络算法的改进方面，已有许多人做了研究。现提出人工神经网络权值和阈值的混合算法，并应用到发动机的故障诊断中。

1 人工神经网络理论

BP算法是一种有导师的训练算法，它在给定输出目标的情况下，通过调节权值和阈值使总体平均误差达到最小值。BP算法每步的搜索方向是沿负梯度方向并以固定步长迭代，实际上并没有搜索到该梯度方向上的最小点，所以该算法实质上并不等价于优化方法中的梯度法。BP法搜索原理图如图1所示，图中虚线和实心点表示每次迭代时梯度法应达到的位置，实线和箭头表示BP算法每步到达的位置。由图1可知，对构成的目标函数采用梯度法优化将会比BP算法好得多。

2 人工神经网络混合算法原理

通过上述2种方法的原理分析可知，BP算法沿负梯度方向以定步长迭代，迭代初期速度较快，但接近目标点时往往经多次迭代，总体平均误差下降得很小，即出现振荡现象；梯度优化法采用最优步长迭代，迭代时避免出现振荡现象并且可获得较高目标函数精度及较少的迭代次数，但每次迭代都要进行步长优化计算，造成整体训练时间较长。为了获得较快的训练速度，综合两种方法的优点（即迭代前期采用BP算法，迭代后期采用梯度优化法）可以避免BP算法迭代后期的振荡现象，加快梯度优化法的迭代速度。这2种方法的转折点可以采取4次函数值比较法，如图2所示。

3 混合算法在发动机故障诊断中的仿真分析

4 结论

1）将BP算法和梯度优化法相结合的混合算法应用到多层人工神经网络权值和阈值的计算，实现了网络权值和阈值的快速运算。

2）发动机的实例计算分析表明：BP算法计算网络参数很不理想（迭代次数较多）；梯度优化法对BP算法实现了改进，但迭代时间较长；混合算法能快速收敛到目标函数极小值并获得准确的神经网络权值和阈值。

参考文献

[1] 李秋玲，贾敏智.基于改进ABC算法优化SVM的汽车发动机故障诊断[J].制造业自动化，2014（5）：57-60.

[2] 周亨，彭涛，邓维敏.基于差分进化算法优化的RBF神经网络的发动机故障诊断研究[J].农业装备与车辆工程，2014（2）：22-26.

[3] 崔华林.机械优化设计方法与应用[M].沈阳：东工出版社，1989.

Abstract： This paper presents a kind of engine vibration fault diagnosis method based on hybrid neural network， namely the early iteration using BP algorithm iterative later using a gradient optimization method. The calculation o network weights and threshold value byBP algorithm and hybrid algorithm shows that the proposed hybrid algorithm is effective and practical.

基于混合算法的冲压回弹模拟研究篇12

随着现代科学技术的发展,模具设计制造技术也在不断发展。人们针对过去利用试错法进行模具设计制造带来了巨大的成本浪费和理论计算不能解决复杂型面的问题,逐步发展了有限元模拟技术。板料冲压中,经常遇到的产品缺陷是板料成形后产生回弹。由于回弹本身的复杂性致使在设计模具时很难预测其回弹情况,导致废品增多及模具设计中型面补偿难以实现。利用有限元模拟能够很好地预测板料的回弹情况,并能及时指导模具设计者进行改进模具结构,有效地提高了模具设计效率,减少了不必要的设计时间。本文利用混合动力算法对板料冲压成形及回弹进行模拟计算,讨论了有限元模拟技术中的关键技术,对多角弯曲件冲压成形及回弹进行模拟,并通过验证凸模运动速度的合理性证明了模拟的可靠性,对实际模具设计具有很好的指导和参考价值。

2 板料冲压中常用的数值模拟算法:

2.1 静态隐式积分算法

静态隐式积分算法是由虚功原理建立一个高阶非线性方程组,采用牛曼法求解方程组。然后通过有限元离散后形成矩阵方程。而静态模拟过程就是解一系列矩阵方程的过程。由于这种算法是由方程组成,符合理论计算公式,所以静态隐式积分算法具有无条件稳定性。但其计算过程需要构造和求解刚度矩阵,联立求解非线性方程组,而且每一步迭代都要进行接触判断,对于薄板冲压成形这种包含接触、摩擦高度非线性的过程分析,往往会出现迭代不收敛的情况,即使收敛,计算时间也很长,所以静力隐式算法在模拟模型较大和接触条件复杂的冲压成形时效率较低。然而,冲压件在成形后的卸载过程中,由于工件的非线性成分不明显,故在进行薄板的冲压回弹模拟时静力隐式算法更接近冲压件回弹的本质。

2.2 动态显式积分算法

动态显式算法基于动态平衡方程,对求解域空间进行有限元离散化,对时间域采用中心差分法,使有限元方程的计算显式化,避免了因迭代计算和非线性引起的收敛问题。虽然动态显式算法是条件稳定的,受最小时间步长的限制,但由于冲压成形本身的非线性特性,要求必须采用较小的时间积分步长,才能获得精确解,故冲压成形本身要求在很小的时间步进行成形,这基本上弥补了动态显式算法的不足。因此,薄板冲压成形过程的模拟一般采用动态显示模拟算法。

2.3 混合模拟算法

混合模拟算法是指成形过程使用动态显式模拟算法,而回弹过程采用静态隐式模拟算法来分析。通过上面的分析,动态显式模拟算法适合于模拟冲压件的冲压成形过程,而冲压件的回弹过程更适合使用静态模拟算法,即使用混合模拟算法。

3 利用动态显式算法模拟成形时的关键技术

3.1 网格划分技术

板料成形模拟分析中的单元常采用基于薄膜理论的薄膜单元、基于板壳理论的薄壳单元以及基于连续介质理论的实体单元[1]。这三种单元中,基于板壳理论的壳单元既不会像薄膜单元那样忽略弯曲效应,又不像实体单元那样需要很长的计算时间,而且板壳理论本身就是研究薄板三维变形行为的理论工具,故基于板壳理论的薄壳单元被广泛用于板料成形回弹分析中。

在冲压成形回弹分析中的单元划分,要根据实际情况来划分单元。在本文中,主要研究的是板料的成形与回弹过程,而模具相对于板料来说,其硬度、刚度和强度远远大于板料。故在划分网格时,把模具作为刚体,即在成形过程中认为模具不变形,在划分网格时,网格可以稀疏一些,同时考虑到模具在圆角处曲率变化较大,为了提高计算精度,此处的网格比模具其他平滑处的网格要密一些。板料将在成形和回弹过程中产生很大的变形,在冲压过程中将产生复杂的应力和应变,所以板料的网格划分要密一些。一般情况下,为了兼顾计算效率和计算精度,板料的网格单元数为模具单元数的2倍左右,但在圆角处或曲率变化比较大的型面处,网格依然要密一些,本文中此处的网格与板料的网格数相同。

3.2 凸模虚拟速度设置

对于实际的板料冲压过程,其冲压速度比较慢,如果使用实际冲压速度进行模拟,需要耗费的时间很大,甚至使模拟失去了其本身的意义,故通常要将模拟中的速度进行放大,即为凸模虚拟速度。但是,由于冲压过程实际为一个准静态过程,而动态显式模拟会带来系统的动态效应,必须将这种动态效应控制在一定的范围内才能保证动态显式模拟的结果接近准静态模拟。通常用系统动能与内能的比值r作为评价指标,当r<5%时显式算法的求解结果与准静态过程的结果最接近。本文中由于板料比较薄,凸模虚拟速度不能过大,通过模拟实验,本文中选择凸模虚拟速度为1-2m/s时,r<5%,适合本次模拟。

4 多角弯曲件冲压成形数值模拟

板料的冲压成形和回弹过程受材料非线性、几何非线性和边界非线性的综合影响。在模拟中需要设置合理的参数和选择适当的求解器才能得到比较精确的模拟结果。本文对多角弯曲件弯曲回弹进行模拟,采用ABAQUS软件中的动态显式算法模拟板料的成型过程,然后以成形后的数据导入静态隐式求解器中,进行回弹模拟计算。

4.1 几何模型建立

制件的几何模型是多角弯曲件,图1所示为中性面尺寸为:α=β=90°,R1=R2=2.15,板料的原始长度为56.4mm,宽度20mm,板料厚度t=0.3mm,有限元几何模型如图2所示。

4.2 材料模型

对于冲压成形模拟中的材料需要设置密度、弹性模量、泊松比、屈服强度和真实的应力应变曲线数据。本实验中使用锡磷青铜QSn6.5-0.1材料,通过实验得到参数如表1,锡磷青铜QSn6.5-0.1材料的真实应力应变曲线如图3所示。

4.3 壳单元及积分点选择

考虑到厚向积分点等因素,选用通用壳单元S4R壳单元,在厚度方向上取5个积分点。

5 弯曲成形分析

根据图2建立有限元模型,成型过程的模拟在ABAQUS/Explicit实现。由于板料较薄,故设置虚拟冲压速度为v=1m/s,模具单边间隙为板厚,接触摩擦系数为u=0.1,从图4中应变数据可以看出,板料的内表面板厚方向主要以拉伸应变为主,即板料在厚度方向发生了增厚,这主要是内侧金属受压应力造成的结果;从图5可以看出,板料外表面在板厚方向主要以压缩应变为主,即板料在厚度方向发生了减薄,这主要是外侧材料受拉应力造成的结果。此外从云纹图中直观地看出,等效塑性应变较大的区域主要发生在弯曲变形的圆角部分。这证明了数值模拟的结果与理论受力分析结果是一致的。

6 板料冲压回弹有限元分析

6.1 板料冲压回弹有限元模型建立

通常在模拟板料回弹时,采用无模法进行模拟,即不考虑模具的因素,以冲压结束时的状态为回弹的初始状态开始计算,当计算至所有外力趋于零时,即得到回弹的结果。在ABAQUS中进行模拟时,基于上述冲压成形有限元模型,有限元模拟方法建立是在成形分析过程完成的基础上,建立多曲率件回弹分析有限元模型,步骤如下:

(1)建立模型Model-2,将[PART]中导入成形模型分析得到的*.odb文件。

(2)定义装配件。

(3)定义回弹分析步,使用ABAQUS/Standard模块定义为Static、General,并确定相应的时间步长。

(4)在初始部中添加新的场变量约束,即成形过程文件;对弯曲件建立边界条件,以便模拟确定弯曲件的回弹情况。

(5)建立回弹分析工作文件,提交回弹分析工作文件计算。

6.2 回弹分析

弯曲成型模拟的结果从ABAQUS Explicit的模拟结果输入到ABAQUS Standard中,利用静态分析来模拟计算回弹。如图6为0.3mm厚板回弹前板材应力分布情况,从图中的云纹图和Mises应力分布都可以看出,成形后的应力分布情况,应力大的部位比较多,应力分布也不均匀,这种应力在板厚上的不均匀分布正是弯曲的特点。当外力去除后,模拟结果如图7所示,从Mises应力分布可以看出,最大应力相对于成形时变小了,从云纹图也不难看出应力减小了,且回弹后应力分布相比成形而言均匀了很多,这是因为回弹后成形件的内部应力得到释放的结果。通过成形和回弹模拟分析,印证了弯曲件的回弹是由于在板厚上的应力和应变分布不均匀而引起的理论推断。

7 结语

(1)本文针对板料冲压讨论了适合本次研究的求解模拟方法,使用动态显式求解器进行冲压成型模拟,而使用静态隐式法进行冲压后回弹模拟比较合适,即采用混合分析法进行模拟冲压回弹问题。

(2)对所研究的零件在模拟软件中的几何模型建立、材料模型建立、单元选择等进行了分析选择;针对实际冲压时间和模拟中凸模速度的差别,研究了适合本模拟中使用的凸模虚拟速度,证明使用凸模虚拟速度为1m/s~2m/s比较合适。

(3)在讨论了混合算法基础上,研究了具体的多角弯曲件冲压成形和回弹模拟的实际实现方法。

(4)经过上面的讨论可知有限元对冲压回弹模拟是比较可靠的,在接下来的工作中,可以通过输出数据分析具体的回弹数据(如回弹角度、曲率及厚向回弹大小),对模拟设计有很好的参考价值,同时节省了大量的模具设计时间,提高了生产率。

摘要：文中对数值模拟算法进行分析,得出对于板料冲压成形问题使用动态显式算法进行模拟比较合适,而对于成形后回弹问题使用静态隐式算法进行模拟更适用,即利用混合算法对冲压回弹问题进行模拟;讨论了有限元模拟中的单元选择、网格技术和凸模虚拟速度的关键技术。利用混合算法在ABAQUS软件中对多角弯曲件冲压成形及回弹进行模拟,对实际模具设计具有很好的指导和参考价值。

关键词：混合算法,数值模拟,ABAQUS,弯曲,回弹

参考文献

[1]解可新,韩立兴,等.最优化方法[M].天津:天津大学出版社,1997:8-11.

[2]庄茁,张帆,岑松,等.ABAQUS非线性有限元分析与实例[M].北京:科学出版社,2005:129-130.

[3]柴海啸.基于几何和工艺补偿的冲压回弹控制方法研究[D].2006.

[4]龚寿鹏.现代锡磷青铜带材生产线的建设及其工艺与装备的选择[J].上海有色金属,2004(4):60-65.

[5]邰振中,等.铈对锡磷青铜铸造与变形组织的影响[J].铸造,2001(8):23-26.

【混合算法】推荐阅读：

混合优化算法01-20

混合智能算法10-24

混合蛙跳算法10-29

混合遗传算法10-31