混沌DNA遗传算法

2024-09-19

混沌DNA遗传算法（共5篇）

混沌DNA遗传算法篇1

引言

当今的网络由于其协议、系统方面的缺陷, 一些有特定意义的图像 (如医疗图像、法庭证据等) 易受到非法者的篡改、盗取, 图像加密算法能有效保护图像拥有者的利益。

混沌系统广泛应用在图像加密系统中[1,2,3], 但文献[4]表明单一的混沌映射图像加密算法安全性较差。

Adleman通过生物实验成功求解7个顶点的有向汉密尔顿路径问题[5], DNA计算诞生。Catherine等人[6]提出一种以DNA为载体来隐藏信息的方法。Gehani等人[7]提出一种基于DNA序列特性的一次一密加密算法。此类方法需要复杂的生物实验来实现, DNA密码学多停留在理论层面。Kang Ning等人[8]提出一种伪DNA计算的加密方法, 不需要复杂的生物实验, 还具有很好的加密效果, 自此提出了诸多基于DNA特性的加密算法[9,10,11]。

本文算法, Chebyshev混沌对原图进行基于位平面的像素置乱[1], 利用天然DNA序列作为密钥, 根据DNA的互补配对原则, 自定义DNA矩阵的加、减运算, 再结合PWLCM混沌映射进行像素替代。

1. 相关理论

1.1DNA编码规则

天然DNA序列由4种碱基A、T、C、G组成。根据碱基互补的原则, 定义8种DNA编码规则, 如表1。

8bit的灰度图像, 一个像素点可由4个碱基来表示灰度值。

1.2DNA矩阵运算

表2、表3示例采用表1中第一种DNA编码规则定义一种DNA序列的加、减运算:

1.3混沌映射

Chebyshev混沌映射:

α>2, xn∈[-1, 1], 初始值变化为1*10-16时可产生两个截然不同的混沌序列。

PWLCM混沌映射:

xn∈[0, 1) , p∈ (0, 0.5) , 该混沌具有均匀的不变分布以及更高的遍历性、混合性和确定性。

1.4混沌映射初始值获取算法

首先将原图每个像素点转换为8位的2进制序列, 再划分为4个坐标对, 定义集合{A}、{B}一一对应存储坐标对的值。例如图像像素点为54、92……, 集合{A}、{B}对应值如图1。再计算得到新的集合{a}、{b}, 其中a0=b0=0.5。

最后计算得到混沌映射的初始值x0和y0, 其中m、n是图像的行列维数。

算法中通过PWLCM混沌映射的序列对得到的DNA序列进行碱基互补, 混沌映射的初始值是由天然DNA序列根据上述原理获得, 使得算法的像素替代敏感于天然DNA密钥。

2. 算法流程

加密算法流程如图2所示。

1) 读取灰度图像, m、n是图像I的行列, 根据1.4节的方法得到Chebyshev映射的初始值x0和y0。

2) Chebyshev映射采用初始值x0迭代m次, 得到序列{X}, 然后对序列{X}进行升序排列得到{X'}, 将图像I扩展后的位平面的行根据序列{X}各元素在{X'}中的位置进行排序。

Chebyshev映射采用初始值y0迭代n*8次, 得到序列{Y}, 然后对序列{Y}进行升序排列得到{Y'}, 将图像I扩展后的位平面的列根据序列{Y}各元素在{Y'}中的位置进行排序。

最后得到置乱后的图像A (m, n) 。

3) 置乱图像A (m, n) 扩展为8个位平面, 两个相邻位平面为一组, 每一组按照1.1节定义的原则分别采用1~4种规则进行DNA编码, 得到4个DNA矩阵A1 (m, n) , A2 (m, n) , A3 (m, n) , A4 (m, n) 。

4) 天然DNA序列, 生成4个天然DNA矩阵NM1 (m, n) , NM2 (m, n) , NM3 (m, n) , NM4 (m, n) 。

5) 根据1.2节定义的DNA序列加法, 矩阵A1, A2, A3, A4和NM1, NM2, NM3, NM4各自对应相加得到矩阵C1, C2, C3, C4。

6) 矩阵NM1与NM2拼接得到矩阵N1 (m, n*2) , 矩阵NM3与NM4拼接得到矩阵N2 (m, n*2) , 矩阵M1和M2按照1.1节的第一种编码规则进行解码得到二进制矩阵M1 (m, n*4) 和M2 (m, n*4) , 然后M1和M2按照1.4节的原理得到初始值a0, b0, c0, d0。

7) PWLCM映射, 采用初始值a0, b0, c0, d0, 分别迭代m*n次, 得到4个序列{P1}, {P2}, {P3}, {P4}, 然后将4个序列转为二值序列, 当pij=1, i∈[1, 2, 3, 4], j∈[1…mn]时, DNA矩阵Ci对应位置的碱基取补, 否则不变。得到矩阵C1’, C1’, C1’, C1’。

8) 最后将C1’, C1’, C1’, C1’按照1.1节定义的原则分别采用5~8种规则进行DNA解码, 再将解码得到的二进制矩阵依次按照8个位平面组合, 最终得到加密的灰度图像EI (m, n) 。

解密算法是加密算法的逆操作, 步骤5的加法采用减法。

3. 实验结果及分析

在matlab7环境下, 对3幅128*128像素的灰度图像“Lena”、“Babara”、“Peppers”进行仿真实验。密钥key={AL031432, 1, 4, 0.35}, 天然DNA序列Gene ID是AL031432, 从第1位碱基截取128*128*4的DNA序列, 4是Chebyshev混沌映射参数α, 0.35是PWLCM混沌映射参数p。图3是加密图像。

3.1置乱程度分析

1) 不动点比

原图I (m, n) , 加密图I' (m, n) , 公式:

2) 灰度平均值

原图I (m, n) 和加密图I' (m, n) , 灰度平均值计算公式如下:

灰度平均值产生均匀变化时, 安全性高, 置乱效果好。

3) 信息熵

信息熵是测试图像灰度值分布的一个参数, 公式如下:

256灰度级的灰度图像, 如果每一个灰度值出现概率都相同, 信息熵H (m) =8, 即该图完全随机。为了抵御基于熵的攻击, 加密图像信息熵越接近8越好。

进行仿真实验, 表4给出了置乱程度定量分析的结果, 结果表明该算法置乱效果非常好。

3.2相关性分析

一个有效的加密算法能降低相邻像素点的相关性。随机选取4000对相邻像素点 (横向、纵向、对角线) 进行相关性分析。分析函数:

表5是图像加密前后的相关性信息。本文的算法能有效抵御基于相关性分析的攻击。

3.3差分攻击分析

NPCR (像素变化率) 和UACI (归一化平均变化强度) 这两个标准来衡量加密算法是否能有效抵御差分攻击, 公式:

原图改变一个像素点Lena:T (1, 1) =255、Babara:T (3, 3) =10、Peppers:T (2, 2) =250, 加密后进行分析, 表7, 由结果可知, 本文提出的算法能有效抵御差分攻击。

3.4密钥空间及敏感性分析

一个好的加密算法必须有极大的密钥空间才能有效抵御穷举攻击, 随着首个完整基因组测序工程的完成, DNA序列数据呈现指数级的增长, 且对同一个DNA序列, 截取起始位置不同, 获取的序列完全不一样。

加密算法对密钥敏感性越高该算法的安全性越高。仿真测试分别改变密钥DNA矩阵的第一位碱基、第一百位碱基、第二百位碱基为其互补的碱基, 然后对各图进行错误密钥解密, 图4展示了错误密钥解密后的图, 与原图完全不同, 表示本算法对密钥有极高的敏感性。

4. 总结

本文提出的基于DNA序列和混沌映射的图像加密算法, 通过原图获取Chebyshev混沌初始值, 加密算法敏感于原图, 基于位平面置乱图像像素点, 实验结果表明置乱程度高;天然DNA序列作为密钥, 密钥空间大, 能模拟一次一密的加密效果, 且密钥的存储、传输更为便捷;置乱后图按位平面划分生成DNA矩阵与天然DNA矩阵运算, 且各平面的编码规则各不相同, 算法加密性能好;最后通过PWLCM混沌序列, 对得到的DNA序列进行碱基互补配对, 配对操作敏感于天然DNA序列, 算法安全性高。实验结果表明, 本文提出的加密算法, 置乱程度高, 安全性高, 密钥空间大, 能有效的抵御穷举攻击、统计攻击、差分攻击。

参考文献

[1]Fu C, Lin B, Miao Y, et al.A novel chaos-based bitlevel permutation scheme for digital image encryption[J].Optics Communications, 2011, 284 (23) :5415-5423.

[2]Awad A, Awad D.Efficient image chaotic encryption algorithm with no propagation error[J].ETRI journal, 2010, 32 (5) :774-783.

[3]Zhu C.A novel image encryption scheme based on improved hyperchaotic sequences[J].Optics communications, 2012, 285 (1) :29-37.

[4]Solak E, Rhouma R, Belghith S.Cryptanalysis of a multichaotic systems based image cryptosystem[J].Optics Communicatio ns, 2010, 283 (2) :232-236.

[5]Adleman L M.Molecular computation of solutions to combinatorial problems[J].SCIENCE, 1994:1021-1021.

[6]Clelland C T, Risca V, Bancroft C.Hiding messages in DNA microdots[J].Nature, 1999, 399 (6736) :533-534.

[7]Gehani A, La Bean T, Reif J.DNA-based cryptography[M].In Aspects of Molecular Computing.Springer Berlin Heidelberg, 2004:167-188.

[8]Kang Ning.A pseudo DNA cryptography method[J].DBLP:journals/corr/abs-0903-2693, 2009.

[9]Zhang Q, Guo L, Xue X, et al.An image encryption algorithm based on DNA sequence addition operation[C]//Bio-Inspired Computing, 2009.BIC-TA'09.Fourth International Conference on.Ieee, 2009:1-5.

[10]Zhou Shihua.The Research of Image Encryption Based on DNA Sequences and Self-assembly[D].Dalian University of Technology, 2013.

[11]Awad A, Miri A.A new image encryption algorithm based on a chaotic DNA substitution method[C].Communications (ICC) , 2012 IEEE International Conference on.IEEE, 2012:1011-1015.

混沌DNA遗传算法篇2

关键词：云遗传算法,混沌,粒子群算法,混合算法

Kennedy和Eberhart受到鸟群觅食行为的启发,提出一种模仿鸟群觅食行为的多元搜索优化算法,即粒子群(particle swarm optimization,PSO)算法[1,2,3,4]。PSO算法因其自身良好的局部收敛效果、快速的收敛速度、易于实现以及控制参数少等优点[5,6],在提出后得到了广泛应用。但是PSO算法种群随机初始化遍历性差、易陷入早熟收敛和不具备全局收敛性的缺点[7,8],极大地限制了PSO算法的性能。为了提高PSO算法的性能,文献[9]通过自适应策略,动态地调整PSO算法的惯性权重参数,来提高PSO算法的全局收敛性能;文献[10]提出一种遗传算法和PSO算法相结合的混合路径规划方法,避免了PSO算法陷入早熟收敛;文献[11]通过在PSO算法初始化阶段引入Logistics混沌映射,利用Logistics混沌映射的遍历性和随机性,提高了初始粒子的质量。

为了解决PSO算法存在的不足,本文提出一种基于云遗传的混合混沌粒子群算法(cloud genetic hybrid PSO,CGHP),使用均匀性更优的无限折叠混沌映射实现粒子的初始化,通过自适应云算子、改进的Metropolis接受准则以及动态调整粒子集规模等策略,实现了云遗传算法和PSO算法的协同,并进行了全局收敛性证明、时间复杂度分析和实验分析。

1 算法介绍

1.1 PSO算法

在一个涉及到h维解空间的问题中,假设粒子群的规模为m,第i个粒子为Zi=(zi1,zi2,…,zih),粒子i的速度为Vi=(vi1,vi2,…,vih)。依据不同粒子的适应度值来判定不同粒子的优劣,粒子i适应度最佳的个体最优解为Pi=(pi1,pi2,…,pih),而种群中具有最佳适应度值的种群全局最优解为Pg=(pg1,pg2,…,pgh)。粒子群算法在运算过程中,根据速度更新公式和位置更新公式来实现粒子的进化,速度更新和位置更新的公式[6]如下

其中,i表示粒子数,t为迭代次数,T为最大迭代次数。c1与c2为加速常数,r1和r2是两个随机数,ω为惯性权重[11]。图1为二维空间内粒子位移示意图。粒子群根据更新公式不断向最优粒子靠拢,但当最优粒子为局部最优时,算法将会陷入早熟收敛[7]。

1.2 云遗传算法

1995年李德毅教授在概率论、数理统计和模糊数学基础上首次提出云模型理论[12]。云模型是一种用自然语言描述定性概念与定量概念的双向认知转换模型[13]。云模型具有三个典型数字特征,即Ex,En和He。其中,Ex是云的期望,集中体现云的定性概念,最能代表样本空间中最优个体的特征;熵En用来表征不确定性的带宽,亦代表随机性和模糊性的范围;He是熵的熵,衡量熵的不确定性和模糊性,通常,采用这三个数字特征共同反映一朵云的定性概念。

云模型发生器是指被软件模块化或硬件固化了的云模型生成算法[14],现采用Y条件云发生器进行交叉操作,由正态云发生器进行变异操作,如图2。

云遗传算法在传统的遗传算法思想中集合了云模型理论[15],借助云模型的随机性和稳定倾向性的特点,采用云模型更新个体,保证了给个体的多样性和全局最佳定位,从而有效克服了传统遗传算法的早熟收敛和易陷入局部最优等缺点。

2 CGHP算法

2.1 初始化

标准的PSO算法初始化过程是随机的,往往使初始粒子分布不均匀,出现大量粒子远离最优解的现象[6]。为了克服这一缺陷,文献[16]和文献[17]利用混沌模型来对PSO算法进行初始化。混沌(Chaos)是确定性系统在长期演进中表现出来的一种从有序到无序的伪随机自组织过程,具有规律性、遍历性等特点[18]。Logistic映射是一种常用的一维迭代混沌模型,其函数映射式为

当μ=2时,映射处于满射混沌状态,其在(0,1)上概率密度函数为:

Logistic映射在(0,1)区间上的概率密度曲线如下

从图3中可以看出,Logistics映射存在着边缘骤变,中间平缓,区间两端处概率大于区间中部概率的特点[19],映射的均匀分布特性较差。文献[20]提出一类无限折叠混沌映射,并通过实验证明了在区间(0,1)内较Logistics映射具有更佳的均匀分布特性,其函数映射式为

为避免搜索的盲目性,提高搜索效率及遍历程度,采用均匀性更优的无限折叠混沌映射产生随机数序列randi对初始种群进行赋值,种群中粒子不同维度取值范围为[zmin,zmax],则采用下式对种群粒子的各个维度进行初始化:

2.2 自适应云算子

在云模型的三个数字特征中,He与En成正比,En一方面反映云模型中元素在论域空间中的范围,即云模型的水平宽度,另一方面其又是随机性的度量,反映了云滴的离散程度[18]。在执行云遗传算法时,对于适应度低的粒子,需要产生方差较大、离散程度髙的云滴,以增强搜索能力,提高产生更高适应度后代的概率;对于适应度髙的粒子,则产生方差小、离散度低的云滴,以保证算法的收敛效果。因此,本文提出一种自适应于粒子适应度的云交叉算子和云变异算子,对云遗传算法进行改进。

自适应En定义如下:

式(7)中Fmax为父代最大适应度,Fmin为父代最小适应度,m=t(D1),t(D1)为区间(0,5)上服从t分布的随机数,D1的表达式如下

在自适应条件下,适应度低的粒子,D1较小,t分布产生较大随机数的概率髙,易产生较大En值,可以产生离散程度高的云滴,提高产生更高适应度后代的概率;适应度髙的粒子,D1较大,t分布产生较小随机数的概率较髙,易产生较小的En值,可以产生离散程度低的云滴,可以保证算法的收敛性。

定义云交叉算子如下

式(9)中Ex为两个父代个体的适应度均值,He=n1En,E'n是以En为期望值,以He为标准差生成的一个正态随机数。

定义云变异算子如下

式(10)中Ex为单个父代个体的适应度值,He=n2Ee,E'n是以En为期望值,以He为标准差生成的一个正态随机数。

2.3 基于云遗传的混合粒子群算法

在传统的PSO算法中,随着算法的进行和迭代次数的增加,粒子群种群多样性不断损失,直到算法陷入早熟收敛[7]。因此,定义种群密度(population density,PD)来衡量粒子群种群多样性水平,作为判断是否进入早熟收敛的依据,其表达式为:

式(11)中zij为第i个粒子的当前第j维值,pgj为群体当前最优粒子的第j维值。当种群密度小于预设值时,表示粒子群算法陷入早熟收敛。

为了解决PSO算法的早熟收敛问题,提出改进Metropolis接受准则更新全局最优解和动态减少PSO算法粒子数两种策略,实现PSO算法和云遗传算法的协同。

改进的Metropolis接受准则:若云遗传算法种群最优粒子Pgc的适应度fc大于PSO算法的种群最优粒子Pgp的适应度fp,则将Pgc作为共同的全局最优粒子Pgt存储于全局最优数据库中,并令Pgp=Pgt;否则,若Er=exp[-(fc-fp)/A]大于随机数R,则仍接受Pgc为全局最优粒子存储于全局最优数据库中,若Er小于R,则接受Pgp为全局最优粒子存储于全局最优数据库中,并令Pgc=Pgt。其中A=a/lg(t+T),a为一个趋近于1的常数,T为协同算法最大迭代次数,t为算法当前迭代次数,R=t(D2)/5,t(D2)为区间[0,5]上由t分布产生的随机数,D2公式如下:

当种群密度小于预设值,PSO算法陷入局部收敛时,依据式(11),保留PSO算法当前粒子数mt中前mt+1个粒子,将其他粒子加入云遗传算法中。

CGHP算法流程如下。

Step1:利用无限折叠映射对种群进行初始化,产生两个规模为m的粒子集A、B。

Step2:判断是否达到结束条件,若达到,终止运算,并输出全局最优数据库中适应度值最大的粒子;否则执行Step3。

Step3:根据种群密度,判断PSO算法是否进入早熟收敛,若进入早熟收敛,动态增减数据集A、B的粒子数,然后执行Step4;否则,直接执行Step4。

Step4:对数据集A、B分别进行PSO算法和云遗传算法,将PSO算法和云遗传算法产生的各自的全局最优解Pgp和Pgc利用改进的Metropolis接受准则进行筛选,将接受的最优解赋值给协同算法全局最优解Pgt存入全局最优数据库中,并令Pgp=Pgt、Pgc=Pgt,然后执行Step2。

CGHP算法流程图如图4。

其中执行云遗传算法的流程图5所示。

3 收敛性和时间复杂度

3.1 收敛性分析

对于云遗传算法,虽然相较于传统的遗传算法,其采用云模型进行选择、交叉和变异操作,但是由于“交叉-变异-选择”操作和进化代数无关,云遗传算法构成了一个有限状态齐次马尔科夫链[15],且CGHP算法中的云遗传部分采用保留最优个体的精英选择方法。文献[21]应用齐次有限马尔科夫链分析并证明了保留最优个体的遗传算法以概率1全局收敛,云遗传算法构成有限齐次马尔科夫链并保留最优个体,虽然在遗传算法的基础上引入了云模型,但仍然具有全局收敛性。

Solis和Wets[22]给出的一般随机搜索算法收敛性判定准则及相关定理,文献[5]利用收敛判定准则证明了协同算法的收敛性。根据收敛性判定准则及相关定理,并参考文献[5],给出CGHP算法全局收敛性的证明。

一般最优化问题可记为<A,f>,对于随机搜索算法D,其第k次寻优结果为Xk,下一次迭代寻优结果为Xk+1=D(Xk,ζk)。其中,A为Rn上某个子集的σ-域,f为适应度函数,ζk为算法D寻优过程中找到的解。

判定准则1:算法D满足f(D(x,ζ))≤f(x),若ζ∈A,则f(D(x,ζ))≤f(ζ)。

准则1要求随机搜索算法D是广义单调非递增的,从而保证适应度值f(x)是非递增的。

判定准则2:对于A的任意Borel子集P,若满足v(P)>0,则有

式(15)中,μk(P)为算法D在第k次迭代中搜索到的解在集合P上的概率测度。准则2说明,只要是可行解空间A中概率测度大于零的子集P,算法D连续无穷次搜索不到集合P中解的概率为0。

引理(随机算法全局收敛的充要条件):若函数f可测,可测空间A是Rn上可测子集,且算法D满足条件1和条件2,{xk}∞k=1是算法D产生的解序列,则

式(16)中,P(xk∈Rε,M)是算法D第k步搜索到的解xk在最优区域Rε,M中的概率测度。

文献[8]指出PSO算法不能以概率1收敛于最优解,文献[23]证明种群初始分布不会直接影响算法收敛性,因此证明CGHP算法的全局收敛性,仅需证明PSO算法和云遗传算法的协同过程的全局收敛性。

定理设CGHP算法优化的目标函数f是一个可测函数,其解空间S为Rn上可测子集,并且CGHP算法满足随机搜索算法全局收敛的准则1和准则2,设{xk}k∞=0是CGHP算法所产生的解序列,则

式(17)中,P(xk∈Rε,M)是CGHP算法第k步搜索到的解xk在最优区域Rε,M中的概率测度。

证明:

依据CGHP算法协同部分的流程,迭代函数F可定义为

因为CGHP算法利用全局最优数据库保留种群最优解,即采用适应度值非递增的精英保留策略,可知算法满足准则1。

如果CGHP算法满足准则件2,则规模为n的混合种群样本采样空间的并集一定包含目标函数f的解向量空间S,即

式(19)中,Mi,k为第k次迭代种群中粒子i的样本空间支撑,即概率测度为1的最小闭子集。

令Yk为云遗传算法在第k次迭代时搜索到的解。因为单独执行云遗传算法算法得到的解序列{Yk}以概率l全局收敛于最优区域Rε,M。因此,在CGHP算法中,对于有限个满足f(Yk)>f(Pg,k)的解Yk,可令其下一状态为Pg,k,并将其存储于全局最优数据库中,而且该机制对云遗传算法全局收敛性没有影响,即在CGHP算法中恒有公式(20)成立,也就是说,当f(Yk)<f(Pg,k)时,存在一个粒子i0,其支撑集Mi0,k=S。

而对于其他粒子i,

式(20)中,0≤φ1≤c1,0≤φ2≤c2,可知Mi,k为一个顶点为(φ1,φ2)=(0,0),另一个顶点为(φ1,φ2)=(c1,c2)的超矩形。

当max{c1|Pi-X(t-1)|,c2|Pg-X(t-1)|}<0.5diameterj(S)时,有:v(Mi,k∩S)<v(S),其中,diameterj(S)表示解向量空间S在第j维分量的长度。因xi收敛到平衡点(φ1Pi+φ2Pg)/(φ1+φ2),所以Mi,k长度趋于0。随着迭代次数k增加,v((Mi,k∩S))和v(∪i≠i0(Mi,k∩S))逐渐减少,从而存在整数k1,当k>k1时,v(∪i≠i0(Mi,k∩S))<v(S)),但是因为有支撑集Mi0,k=S,所以∪ni=1Mi,k=S。令S的Borel子集A=Mi,k,则v(A)>0,且(22)式成立,从而CGHP算法满足准则2。

综上所述,CGHP算法的PSO算法和云遗传算法的协同部分,满足随机搜索算法全局收敛的判定准则1和判定准则2。因此CGHP算法的搜索序列以概率1收敛于全局最优解,即CGHP算法具有全局收敛性。

3.2 时间复杂度分析

算法时间复杂度[24]是衡量算法性能优劣的标准之一,CGHP算法的时间复杂度主要由四部分构成:无限折叠混沌映射初始化、PSO算法和云遗传算法并行协作全局搜索、种群密度判定和改进Metropolis接受准则进行最优解筛选。

设种群规模为2m,粒子维数为h,T为最大迭代次数。初始化的时间复杂度为O(h·m)。设PSO算法和云遗传算法的粒子数分别为mtp和mtc,t为迭代次数,则在PSO算法中,初始化粒子群的速度、适应度值的复杂度均为O(h·mtp),个体最优和种群全局最优选取也均为O(h·mtp);在一次迭代寻优过程中,所有粒子速度、位置更新及适应度评价的复杂度均为O(h·mtp);对于云遗传算法在一次交叉、变异和计算适应度的复杂度均为O(h·mtc),选择和评价优劣等操作复杂度均为常数O(C)。因此协同部分的时间复杂度为O[h·(mtp+mtc)·T],又因为mtp+mtc=2m,PSO算法和云遗传算法协同部分的复杂度为O(h·m·T)。种群密度判定和改进Metropolis接受准则进行最优解筛选的时间复杂度均为O(T)。综上,CGHP算法的时间复杂度为O(h·m·T),且与PSO算法的复杂度[[25,26]]在同一数量级上。

4 实验分析

4.1 测试函数

为测试CGHP算法性能,选取4个典型benchmark测试函数[[27,28]]对算法性能进行验证,并对测试结果进行分析,测试函数如表1所示。

测试函数的三维视图如图6所示。

其中,Quadric noise具有一个广阔的平坦区域;Rosenbrock是一个非凸且变量间具有高度相关性的函数,其全局最优位置在狭长的抛物面状谷底内,搜索方向极难辨别;Griewanks是一个变量间相互独立的多峰值函数;Rastrigin是一个具有大量正弦波动特性局部最优位置的多峰值函数,其变量间相互独立。本文采用的多峰函数均为非线性复杂函数,大量局部极值点的存在特别适合测试改进算法全局寻优特性和避免过早收敛等方面的性能。

4.2 实验结果和分析

所有算法实现的编译环境均为MATLAB R2014a。实验参数设置如下:初始种群规模为40,两个子种群规模各为20,为进一步优化CGHP算法在进化过程中的开发和开采性能,惯性权重ω从0.9线性递减至0.4,学习因子c1、c2均为1.494,最大迭代次数为1 000,种群密度阈值为0.05。同于对比的PSO算法[29]和CSPSO算法[30]的参数设置与原始文献中设置保持一致。

实验对维数为30的测试函数(f1~f4)分别进行30次独立实验,算法性能测试的最终结果如表2所示。

为便于验证分析,表2中实验结果均以“寻优平均值+标准差”形式表示每个解,同时,在表2中的0.05显著水平下双侧t-检验结果符号标记及相应释义如表3所示。

从表3中的实验结果可以看出,对于单峰函数f1和f2而言,CGHP算法与标准PSO算法、CSPSO算法相比,在提高寻优精度的同时,解的标准差为0,解的稳定性显著提高;三种算法都可以找到全局最优解,CGHP算法的全局最优解质量最高,标准PSO算法和CSPSO算法均可收敛到相应容忍度下限,且CSPSO算法优于标准PSO算法。多峰函数f3和f4具有众多的局部极值点,CGHP算法相较于其他两种算法,同样可以显著提高解的质量,并且获得了测试函数f3的全局最优解;对于测试函数f4而言,CGHP算法虽未获得全局最优解,但是子PSO算法和云遗传算法的协同以及全局最优数据库保存全局最优的策略仍然能够使CGHP算法得到精度更高的解。在0.05显著水平下的双侧t-检验结果也验证了CGHP算法在寻优精度和稳定性方面的优势。

为进一步说明CGHP算法的收敛性能,图7(a)~图7(d)展示了三种算法在迭代1 000次过程中对于四种测试函数的收敛情况。

从图7可以看出,CGHP算法的收敛性明显优于PSO算法和CSPSO算法,在算法迭代前期,CGHP算法的适应度值迅速减小,收敛速度快于PSO算法和CSPSO算法;在迭代后期,CGHP算法的适应度值维持在极小的水平,算法寻优精度较好。

图7(a)显示30维f1函数的实验结果,CGHP算法在迭代初期适应度值迅速减小,表明算法定位到最优解区域,CGHP算法具有优于其他两种算法的全局搜索性能;在迭代中后期,CGHP算法的适应度值维持在极小的水平,表明算法具有良好的寻优精度,优于PSO算法和CSPSO算法的全局搜索能力和寻优精度,体现PSO算法和云遗传算法协同策略的优势。对于f2函数的优化问题,如图7(b)所示,当传统PSO算法获得的最优粒子为局部最优时,算法将会陷入早熟收敛而难以迅速寻找到全局最优解,而CGHP算法采用并行协同机制,借助动态调整粒子集规模和改进的Metropolis接受准则策略,使算法能够有效地跳出早熟收敛,实现最优解区域的准确定位,在短时间内实现算法的快速收敛。f3和f4函数是典型的用来测试算法全局搜索性能的函数,如图7(c)和图7(d)所示,CGHP算法在开始阶段即能找到全局最优解所在的区域,并且可以有效跳出早熟收敛并找到全局最优解,虽然迭代后期收敛速度放缓,但相对于PSO算法和CSPSO算法仍然具有良好的寻优精度,表明CGHP算法的搜索能力要优于其他两种算法。

5 结论

混沌DNA遗传算法篇3

数据预测在金融投资领域占有重要地位,而股票指数预测具有变换幅度大,变化因素多,变化不稳定等特性,是金融数据中最复杂的数据类型之一,其研究一直是金融理论的研究热点。股票指数具有明显的混沌特征,许多学者对其混沌特性进行了深入研究,建立了多种基于混沌理论的股票指数(价格)预测模型,如BP神经网络模型[1,2]、RBF神经网络模型[3]、小波神经网络[4]等。其中,BP神经网络模型是比较成功的预测模型。但该模型有两个明显的缺点:一是容易于陷入局部极小值;二是收敛速度慢。为克服上述缺点,本文从非线性混沌时间序列角度出发,采用遗传算法(Genetic Algorithm,GA)优化的BP神经网络预测模型,用于沪深股票指数预测。

一、相空间重构

相空间重构理论是混沌时间序列预测的基础,Packard[5]等人提出了用延迟坐标法对混沌时间序列x1,x2,…,xn进行相空间重构,则在状态空间中重构的某一点状态矢量可以表示为:

Xi=(xi,xi+τ,…,xi+(m-1)τ)T, i=1,2,…,M (1)

式中M=n-(m-1)τ是重构相空间中相点的个数,τ是延迟时间,m是嵌入维数,即重构相空间的维数。

Takens定理证明了如果嵌入维m≥2d+1,d为系统动力学维数,则系统原始状态变量构成的相空间和一维观测值重构相空间里的动力学行为等价,两个相空间中的混沌吸引子微分同胚,即一维观测值中包含有系统所有状态变量演化的全部信息。由此演化规律可得系统下一时刻的状态,从而得到时间序列下一时刻的预测值。这为混沌时间序列的预测提供了依据。

二、BP神经网络预测模型

混沌时间序列预测的实质是一个动力系统的逆问题,即通过动力系统的状态来重构系统的动力学模型F(g),即:

F(Xi)=xi+T (T>0) (2)

式中T为前向预测步长。

构造一个非线性函数f(g)去逼近F(g)的方法有很多,BP神经网络就是一种构造混沌时间序列非线性预测模型F(g)的很好方法。

若一个非线性离散动力系统的输入为Xi=(xi,xi+τ,…,xi+(m-1)τ)T,输出为yi=xi+1,选择典型的三层BP神经网络,由于用BP神经网络来预测混沌时间序列,神经网络输入层的神经元数等于混沌时间序列重构相空间的嵌入维数m时,预测效果比较好[6],故本文取BP神经网络的输入个数为m、隐层为p、输出个数为1,则BP神经网络完成映射f:Rm→R1,其隐层各节点的输入为:

$S_{j} = \sum_{i = 1}^{m} w_{i j} x_{i} - θ_{j}, j = 1, 2, \dots, p (3)$

式中wij为输入层至隐层的连接权值,θj为隐层节点的阈值。

BP神经网络转移函数采用Sigmoid 函数f(x)=1/(1+e-x),则隐层节点的输出为:

$\begin{array}{l} b_{j} = \frac{1}{1 + \exp (- \sum_{i = 1}^{m} w_{i j} x_{i} + θ_{j})} \\ j = 1, 2, \dots, p \end{array} (4)$

同理,输出层节点的输入、输出分别为:

$L = \sum_{j = 1}^{p} v_{j} b_{j} - γ (5)$

$x_{i + 1} = \frac{1}{1 + \exp (- \sum_{j = 1}^{p} v_{j} b_{j} + γ)} (6)$

式中vj为隐层至输出层的连接权值,γ为输出层的阈值。

BP神经网络的连接权重wij、vj和阈值θj、γ可以通过BP神经网络训练求得,故xi+1是可预测的。式(6)即为BP神经网络的预测模型。

BP神经网络在开始训练前将各层的连接权值及阈值随机初始化为[0,1]之间的值,这种未经优化的随机初始化往往会使BP神经网络的收敛速度慢,且容易使最终结果为非最优解。采用遗传算法可以对初始权值以及阈值分布进行优化,优化的初始权值和阈值能使BP神经网络具有更高的精度。

三、遗传算法优化BP神经网络预测模型

(一)基本思路

GA算法是一种全局搜索算法,把BP神经网络和GA算法有机融合,利用GA算法来弥补BP神经网络连接权值和阈值选择上的随机性缺陷,不仅能发挥BP神经网络泛化的映射能力,而且使BP神经网络具有很快的收敛性以及较强的学习能力。本文将遗传算法和BP神经网络相结合,形成一个改进的遗传算法优化BP神经网络的预测模型。模型算法基本思路为:(1)对负荷时间序列进行相空间重构,根据其相空间重构参数确定BP神经网络拓扑结构;(2)随机生成一个遗传算法种群个体作为BP神经网络的初始权值和阈值,用遗传算法对BP神经网络进行优化;(3)以遗传算法优化BP神经网络得到的最优个体作为BP神经网络的初始权值和阈值,然后用BP神经网络预测模型进行局部寻优,从而得到具有全局最优解的BP神经网络预测值。下面结合预测算法介绍具体操作。

(二)GA算法优化混沌BP神经网络预测算法

算法基本步骤如下。

Step1:设种群规模为P。随机生成P个个体的初始种群W=(W1,W2,…,WP)T,给定一个数据选定范围,由于初始群体的确定对GA的全局寻优有很大影响,所以采用线性插值函数生成种群中个体Wi的一个实数向量w1,w2,…,wS,作为遗传算法的一个染色体。染色体的长度为:

S=RS1+S1S2+S1+S2 (7)

式中R为输入层结点数,S1为隐层结点数,S2为输出层结点数。确定好的种群中的每个个体Wi=(w1,w2,…,wS),(i=1,2,…,P)代表一个BP神经网络的初始值,个体Wi中的一个基因值wj表示神经网络的一个连接权值或阈值。为了得到高精度的权值、缩短染色体的串长,采用浮点数编码方法。

Step2:确定个体的评价函数。给定一个BP神经网络进化参数,将Step1中得到的染色体对BP神经网络权值和阈值进行赋值,输入训练样本进行神经网络训练,达到设定的精度得到一个网络训练输出值 $\hat{y}$ i,则种群W中个体Wi的适应度值fitnessi和平均适应度值 $\bar{f}$ 分别定义为:

$f i t n e s s_{i} = \sum_{j = 1}^{Μ - 1} (\hat{y}_{j} - y_{j})^{2}, i = 1, 2, \dots, Ρ (8)$

$\bar{f} = \frac{\sum_{i = 1}^{Ρ} f i t n e s s_{i}}{Ρ} (9)$

式中 $\hat{y}$ j为训练输出值,yj为训练输出期望值;M为重构相空间中相点数;P为种群规模。

Step3:采用轮盘赌法选择算子,即基于适应度比例的选择策略对每一代种群中的染色体进行选择,则选择概率pi为:

$p_{i} = \frac{f_{i}}{\sum_{i = 1}^{Ρ} f_{i}} ‚ i = 1, 2, \dots, Ρ (10)$

式中fi=1/fitnessi, P为种群规模。

Step4:由于个体采用实数编码,所以交叉操作方法采用实数交叉法。第k个基因wk和第l个基因wl在j位的交叉操作为:

${\begin{cases} w_{k j} = w_{k j} (1 - b) + w_{l j} b \\ w_{l j} = w_{l j} (1 - b) + w_{k j} b \end{cases} (11)$

式中b为[0,1]间的随机数。

Step5:变异操作选取第i个个体的第j个基因进行变异操作:

$w_{i j} = {\begin{cases} w_{i j} + (w_{i j} - w_{\max}) f (g), r \geq 0.5 \\ w_{i j} + (w_{\min} - w_{i j}) f (g), r < 0.5 \end{cases}} (12)$

f(g)=r2(1-g/Gmax) (13)

式中wmax和wmin分别为基因wij取值的上下界,r为[0,1]间的随机数,r2为一个随机数,g为当前迭代次数,Gmax为最大进化代数。

Step6:将遗传算法得到的最优个体分解为BP神经网络的连接权值和阈值,以此作为BP神经网络预测模型的初始权值和阈值对其进行赋值,BP神经网络预测模型经训练后,混沌时间序列预测最优解输出。

四、仿真实验

(一)仿真条件

为了说明本文算法的有效性,本文Matlab2009b环境下,采用Matlab语言编写算法计算程序,并应用Matlab神经网络工具箱构建了两种预测模型:遗传算法优化混沌BP神经网络预测模型(GABP模型)模型和一般的混沌BP神经网络预测模型(BP模型)。对于同一上海股票指数时间序列,进行预测对比实验。

实验中的股票指数时间序列数据按式(14)处理成均值为0、振幅为1的归一化时间序列:

$y_{i} = \frac{x_{i} - \frac{1}{n} \sum_{i = 1}^{n} x_{i}}{\max (x_{i}) - \min (x_{i})} (14)$

式中{xi}为原时间序列,{yi}为归一化的时间序列。

实验的误差评价体系采用绝对误差err、平均绝对误差MAE和相对误差perr,即:

$e r r = x_{i} - \hat{x}_{i} (15)$

$Μ A E = \frac{1}{Ν_{Ρ}} \sum_{i = 1}^{Ν_{Ρ}} | x_{i} - \hat{x}_{i} | (16)$

$p e r r = \frac{\sum_{i = 1}^{Ν_{Ρ}} (x_{i} - \hat{x}_{i})^{2}}{\sum_{n = 1}^{Ν_{Ρ}} x_{i}^{2}} (17)$

式中xi和 $\hat{x}$ i分别为真实值和预测值,NP为预测样本数。

实验采用三层BP神经网络结构,输入层结点数为m,隐层节点数为2m+1,输出层节点数为1;BP神经网络参数设置为:训练次数取100,训练目标取0.00001,学习率取0.01;遗传算法参数设置:种群规模取10,进化代数取100次,交叉概率取0.4,变异概率取0.1。

(二)上证综指时间序列的实证分析

实验中的数据为上海证券交易所2005年3月1日-2010年7月20日上证综指的每日收盘指数,共产生1 314个数据,如图1所示。分别用C-C 算法和Cao方法求得该指数流时间序列的延迟时间τ=1、嵌入维数m=6,根据最大Lyapunav 指数小数据量的改进计算方法,得其最大Lyapunav 指数为0.0403,说明该上证综指时间序列为混沌时间序列。

实验中,用文中的两种预测模型对该股指时间序列进行单步预测,为测试预测方法的准确性,预测取不同数量的训练样本。图2给出了训练样本为1 200,预测样本为30时两种预测模型的预测结果。从图2可以看出两种预测模型的预测结果都能够很好地反映上证综合指数变化的趋势和规律,GABP模型平均绝对误差MAE比BP模型降低5.21%,相对误差perr降低10.37%,预测效果令人满意。

为进一步说明本文预测算法的有效性,表1给出了两种预测模型在不同数量训练样本条件的平均绝对误差MAE相对误差perr。从表1的结果可以看出,文中的GABP预测算法对不同数量训练样本条件下的上证综合指数的预测是有效的。

五、结论

针对BP神经网络预测存在局部极小缺陷和收敛速度慢的问题,提出了一种遗传算法优化混沌BP神经网络的时间序列预测方法。将其应用于上证综合指数的预测,并与BP模型进行了比较。结果表明:该方法降低了BP神经网络预测模型陷入局部极小值的可能、提高了模型收敛速度。相对于BP预测模型,该方法对上证综合指数具有更好的非线性拟合能力和更高的预测精度。

参考文献

[1]郁俊莉.基于混沌时间序列的非线性动态系统神经网络建模与预测[J].武汉大学学报(理学版),2005,51(3):286-290.

[2]陈敏,叶晓舟.混沌理论在股票价格预测中的应用[J].系统仿真技术,2008,4(4):228-232.

[3]张中华,丁华福.基于混沌神经网络的股票分析及其预测[J].计算机技术与发展,2009,19(3):185-188.

[4]牛国鹏.小波网络与混沌时间序列预测[D].兰州大学,2009.

[5]Takens F.Determining strange attractors in tur-bulence[J].Lecture Notes in Math,1981(898):361-381.

混沌DNA遗传算法篇4

1 建立数学模型

1.1 模型描述

假设学校有N个班, N={ni|i=1, 2, 3, …, N}, 各个班级人数为{i|=1, 2, 3, …, N};班级集合有T个教师, T={t1, t2, …, tT};课程总数为S, S={s1, s2, …, sS;教室个数为R, R={r1, r2, …, rR}, 各教室可容纳人数为{x1, x2, …, xR};时间段数为M个, M={m1, m2, …, mR}。

1.2 模型中的约束条件

1.2.1 软约束条件

(1) 满足教师所提出的上课时间和地点的特殊要求。 (2) 多学时课程的周安排要错开, 一般对于每周多学时的课程应该能够尽量将其隔1天以上安排才能保证有较好的教学效果。 (3) 在排课过程中较难的课程最大程度地安排在授课效果较好的节次中, 比如上午上课效果要比下午效果好。

1.2.2 硬约束条件

(1) 同一时间, 同一班级不能同时有两门以上的课程。 (2) 同一时间, 同一个教师不能同时有两门以上的课程。 (3) 同一时间, 同一个教室不能同时有两门以上的课程。 (4) 分配的教室可容纳人数应该大于等于上课的班级的学生人数。

1.3 建立的数学模型

排课问题的数学模型是一个组合优化问题, 其中f为目标函数。目标函数值为4时最为理想, 从此可看出排课问题是一个求最大值问题。其中R1表示老师对课程有没有特殊要求, 若有则R1=1, 否则R1=0。R2表示周学时的大小, 若周学时大则R2=1, 否则R2=0。R3表示课程的级别, 若为必修课则R3=1, 否则R3=0。R4表示可是课程难度级别, 若课程难度大的安排在上午或课程难度小的安排在下午则R4=1, 否则R4=0。Ki表示以上的权重, 其中由以上各自的优先级可令K1≥K2≥K3≥K4≥0, 教师tt在时间mm、教室rr中给班级nn讲授课程ss, 表示nnttssrrmm=1, 反之为nnttssrrmm=0。

2 混沌遗传算法

混沌遗传算法是在遗传算法的过程中加一混沌扰动, 从而提高了收敛速度, 找到全局最优解。

2.1 步骤

(1) 编码。二进制编码不能很好地反映排课问题的特点, 且交叉和变异较难操作。本文采用浮点数编码, 因为其自然直观、交叉和变异操作较容易、解码操作也非常容易、节省时空开销、计算效率高。

(2) 生成初始群体。混沌遗传算法利用混沌的遍历性进行粗粒度全局搜索获得比随机搜索有更好的效果, 从而提高初始种群个体的质量和计算效率。

(3) 确定个体适应度函数。确定个体适应度真正目的是确定个体在群体中的优劣。适应度越大个体越好, 反之适应度越小则个体越差。根据适应度的大小对个体进行选择, 以保证适应性能好的个体有更多的机会繁衍后代, 使优良特性得以遗传。因此适应度函数设定的好坏直接影响到混沌遗传算法的收敛速度和能否找到最优解。由于排课问题的软约束条件有多个, 因此本文采用多目标化的个体适应度函数。

(4) 确定交叉概率Pc, 并执行交叉操作。在混沌遗传算法的整个进化过程中交叉操作要进行成千上万次。遗传算法中的交叉算子主要采用单点、对称、大片断基因保留、小片断基因保序的交叉方法。而在混沌遗传算法中, 利用混沌序列来控制交叉操作, 从而提高交叉的效率。 (1) 混沌序列控制交叉频率:交叉概率在很大程度上影响着算法的收敛速度和解的质量。混沌遗传算法利用混沌序列对目标基因进行混沌扰动, 从而加快了算法的收敛速度和解的质量。其中0.25≤Pc≤1.0比较理想。 (2) 混沌序列控制交叉点位置的选择:由产生的一个混沌序列映射到该目标个体的基因空间, 则在相应的位置进行交叉操作。

(5) 确定变异概率Pm, 并执行变异操作。在混沌遗传算法中, 产生的混沌序列来控制变异算子。从而提高变异的效率。 (1) 混沌序列控制变异频率:混沌遗传算法利用混沌序列对目标基因进行混沌扰动, 从而提高了解的质量。其中0.001≤Pm≤0.1比较理想。 (2) 混沌序列控制变异点位置的选择:由产生的一个混沌序列映射到该目标个体的基因空间, 则在相应的位置进行变异操作。

(6) 适应度较低个体的混沌优化。混沌遗传算法利用混沌进行细粒度局部搜索, 提高解的精度。对当前代群体中适应度较小的90%的基因加混沌扰动。这种变异可能产生比剩下10%较高适应度基因更好的基因, 从而有效地避免单纯的遗传算法陷入局部最优解与早熟的问题。

(7) 判断该算法收敛准则是否满足终止条件, 若满足则输出搜索结果, 否则返回 (4) , 直到满足终止条件。

2.2 混沌遗传算法流程图 (图1)

3 实验结果及分析

为了验证本文算法在排课问题上优先于遗传算法。选择玉林师范学院2015-2016学年上学期排课任务为测试范例, 其中种群数1000。对算法性能的考察指标包括平均运行时间、出现较优解的次数。

3.1 实验结果

基于两种算法的高校排课方案, 迭代次数分别设定为50、100、150、200、250、270、290, 每次迭代50次进行测试, 运行并记录结果。如图2、图3所示。

3.2 实验结果分析

我们从两个方面来分析混沌遗传算法的有效性。首先从出现较优解的次数方面, 随着迭代次数的增加, 混沌遗传算法和遗传算法出现较优解的次数都趋于稳定, 但是当迭代次数一定时, 混沌遗传算法出现较优解的次数明显比遗传算法出现较优解的次数多出2倍。其次从收敛速度方面, 实验表明, 出现较优解的次数趋于稳定时, 混沌遗传算法收敛速度比遗传算法的收敛速度快3倍。以上分析表明, 本文采用的混沌遗传算法具有收敛速度快, 易趋于全局最优解等特点, 故该算法应用到排课问题上是有效可行的。

摘要：排课问题有很多制约因素, 其目的是要找出各因素间的最佳对应关系, 因此高校排课问题就是一个非线性组合优化问题。遗传算法是解决非线性组合优化问题的有效智能算法, 但是遗传算法可能会陷入局部最优的局面, 并且收敛速度比较慢。为了弥补这些缺陷, 本文利用混沌的遍历性、随机性、内在规律性和遗传算法的反演性, 采用混沌遗传算法来解决高校排课问题。实验结果表明:当运行趋于稳定状态时, 该混沌遗传算法比遗传算法收敛速度快、能更有效地求得全局最优解。

关键词：排课,混沌优化,混沌遗传算法

参考文献

[1]李兵, 蒋慰孙.混沌优化方法及其应用[J].控制理论与应用, 1997.14 (4) :613-615.

[2]王东升, 曹磊.混沌、分形及其应用[M].合肥:中国科学技术大学出版社, 1995.

混沌DNA遗传算法篇5

网格工作流调度问题不同于一般的任务调度,在调度时不仅要考虑为任务选择一个最佳资源,还要考虑各个任务之间的时序与因果关系等一系列的约束条件,以及协调各个任务的执行来达到最终的目标,这种调度集中于多元化相互依存的管理任务的执行及映射[1]。网格工作流调度问题中,在既定的工艺流程下,每一个任务有不同的服务器或机器可供选择,它们完成时间不同,且一个服务器上可能同时有不同的任务需要执行,它类似于柔性流水车间调度问题,相比于传统车间调度问题它更加复杂,大大增加了调度的灵活性,更符合生产的实际情况[2,3]。在现代制造业中,它具有很强的代表性,可以广泛应用于精密仪器生产,化工,制药等流程工业中。

一般来说,在分布式服务上映射任务的问题属于NP难题。尽管工作流调度可以进行穷举搜索,但复杂的求解方法不仅效率低下而且很难得到问题的最优解。本文为解决动态网格环境下的工作流调度问题,拟采用一种鲁棒性较强的全局寻优算法———遗传算法[4]。遗传算法的优点是实际操作简单,搜索能力强,易于并行化,但其缺点是具有局限性,容易产生收敛停滞和易陷入局部极值点的问题[5]。因此本文在传统遗传算法的基础上,引入混沌系统,并利用信息熵的概念动态调整交叉和变异概率,从而提高了算法的准确性及效率。

1 工作流调度问题描述

网格结构可以利用工作流简化成简洁的结构模型[6],以便在研究问题时能够从繁琐的网格结构中得到一种有利于调度研究的模型。一个工作流的运行过程通常可以利用有向图模型(DAG)来建模。设定工作流调度问题为:

①定义一组有限的任务集Ti(i=1,2,…,n)和一组有向连接任务(Ti,Tj)的弧的表单,其中任务Tj是Ti的子任务,父任务执行完毕后子才能开始执行子任务。定义C为完成全部作业任务的成本预算,D为最后一项作业任务完成的截止期限。②定义一组能够执行任务Ti的服务集Sji(i=1,2,…,n,j=1,2,…,mi,mi<m),m为可用服务器的总数。其中每个任务只能由一个服务器来执行。③定义服务器Sji执行任务Ti的时间为Tji,费用为Cji,工作流调度问题即是将每一个任务Ti映射到合适的服务Sji上。

2 混沌遗传算法设计

混沌是一种在确定性系统中不定期而又长期的行为,其对初始条件十分敏感,且与杂乱的随机系统具有明显的差异。混沌系统的随机性实际上是受到约束的,对于空间具有很强的遍历性,这种模式更符合生物的进化。与原有的随机搜索相比,混沌系统的遍历性能够在全局范围内进行无重复搜索,减少搜索的盲目性及随机性[7],进而提高搜索的效率。以下是改进的混沌遗传算法的具体实现过程。

2.1 编码

对于网格环境下的工作流调度问题,用传统的基于工序的编码方法将无法得到最终的解,因为其不仅简单的对所有任务的执行进行合理的排序,更为重要的是为每一个任务的执行分配一个合理的服务器,使得最终的结果满足用户的需求。

图1中的染色体表示工作流调度的一个可行解,其由两部分组成,第一部分为任务的编码,第二部分为服务分配的编码,它的总长度等于调度问题的任务总数。

2.2 种群初始化及适应度函数

在生成初始种群时,本文利用混沌系统来取代原有的随机生成方式。具体做法是将待优变量利用事先定义的混沌机制映射到混沌空间,成为混沌变量。进化中生成的混沌变量可用以下的方程式进行定义:

其中CSi表示第i个混沌变量,k和k+1表示迭代的次数,CSi的取值区间是(0,1)。混沌优化机制的工作步骤如下:(1)将(0,1)区间划分为m个等分区间(m表示能够执行指定任务的服务器总数)。(2)每一个初始随机种群中的基因的值将会被映射到取值范围在(0,1)区间上的新的值CSi上。(3)Si(1)的值是通过线性映射操作机制生成的:

其中Si(1)的值表示的是当代给任务Ti分配的服务器,mi表示能够执行任务Ti的资源总数。④下一次迭代的混沌变量CSi(2),是通过应用方程(4-1)以及上一个步骤中产生的CSi(1)值生成的。⑤混沌变量CSi(2)可用来生成Si(2),生成方程为:Si(2)=[CSi(2)×mi](3)

由此,通过公式(4-1)-(4-3)中定义的混沌机制继续生成每一个染色体中的Si(k)的值。在此阶段,能够计算出每个染色体的适应度值。遗传算法在搜索进化过程中是以适应度函数作为依据,而后利用种群中每一个个体的适应度函数值进行搜索进化,因此如何建立合理的适应度函数是影响最终算法的效率及准确度的关键。

根据成本最小化的原则,本文所建立的适应度函数是基于成本的,于是我们定义对于个体I的成本-适应值函数Min(I)为:

其中C(I)表示执行个体I需实际成本总和,C表示该工作流的预算成本。

2.3 遗传操作

遗传操作是对选择的个体进行交叉和变异操作,产生继承优良特性的下一代,经过不断的迭代,最终将收敛到“最适应环境”的个体。

2.3.1 选择算子

选择即从当前种群中选择适应值高的染色体以生成交配池的过程。本文在选取选择算子时所采用的方法是轮盘赌,该方法能够使得上一代染色体的基因得到遗传,这是由于适应度值较高的个体更容易在算法中被选中[8]。

2.3.2 交叉算子

在进行交叉操作时,本文对利用轮盘赌选出的染色体基于交叉概率交换一部分基因,最终生成新的染色体,此染色体有机会获得更优秀的基因,产生更优的解。本文中我们采用两点交叉的方法,具体操作步骤如下:(1)利用Random函数产生两个随机数作为交叉位,根据交叉位将父代染色体分为三个区域,part1,part2,part3。(2)交换两个父代中的part2部分。(3)生成的子代为交换了part2后的父代,其它的基因位都保持不变。(4)重复步骤(1)-(3),得到所需新种群。

此外,交叉概率(PV)是控制交叉操作的使用频率,本文采用的是动态选取的方法。(见2.4节)

2.3.3 变异算子

变异操作一定程度上能避免种群有效基因的缺失,从而增加种群的多样性。本文针对遗传算法局部搜索能力差的特点,对变异概率(PW)采用动态选取的方法(见2.4节)。

2.4 交叉概率和变异概率设计

自适应遗传算法的核心在于种群的不断优化,而在种群的不同进化时期对于交叉、变异概率有不同的需求。在种群的进化初期,为保证种群的多样性,此时希望种群的变异概率较大;而在进化后期,为避免优秀基因的缺失,则要求变异概率较小。因此,本文提出了一种信息熵的概念,根据种群的进化代数,其能够动态调整交叉、变异概率。信息论中,熵表示的是一种不确定的度量信息的单位,信息量若逐渐变大,体系结构便逐渐完善、熵的值就越小。信息熵的公式如下:

其中:LTi为第i个工件最后完工时间;

为所有工序时间之和;

PV为交叉概率;

PW为变异概率;

PV0,PV1分别为交叉概率的取值下限和上限;

PW0,PW1分别为变异概率的取值下限和上限;

G为算法设置的最大进化代数;

g为表示种群当前的进化代数;

H为种群熵;

a,b为休整参数,通常两者取值相等。

参数见表1。

3 实验与分析

传统的工作流调度问题一般可以分为平衡结构和非平衡结构两类。下面的实验中将采用平衡结构(图3)来验证算法。

为证明算法的有效性,实验中将和传统遗传算法(TGA)进行比较,实验过程如下:

本文使用了J.Yu和R.Buyya[5]的数据集进行测试,主要参数为:种群规模为10,交叉概率和变异概率见2.4节,迭代次数为100,数据集连续运行5次取最优结果。得到的实验结果如图4。

上图中,设定截止期限D=220(H),垂直轴表示总成本除以用户预算的结果。从图中可以看出在较低预算下两种算法表现的都不能令人满意,然而随着用户给定的预算的增加,两个算法的结果都符合用户的需求,但混沌遗传算法(CGA)在每一级预算下的表现都优于TGA。

由实验结果可知,本文所设计的混沌遗传算法在基于用户需求的约束下,表现出的结果优于传统的遗传算法。

4 结束语

针对动态网格环境下工作流调度的特点,本文设计了一种带熵的混沌遗传算法,此算法将混沌机制取代原有算法中的完全随机方式生成初始种群,并利用信息熵的公式动态改变交叉、遗传概率,这样既有效地克服了遗传算法的易早熟收敛等缺陷,又能提高搜索最优解的效率。实验测试结果表明本文所提出的算法更优于传统的遗传算法。

摘要：网格发展的主要思想是有效的利用分布在世界各地的计算资源。而在网格环境下,是通过很多相互依赖的任务来描述作业的,这让工作流调度面临巨大的挑战。在本文中,提出了一个改进型的混沌遗传演算法来解决在工作流应用程序中的调度优化问题,它利用信息熵的概念动态调整了交叉和变异概率,优化了传统的遗传算法,并最终通过实验证明了算法的有效性。

关键词：网格计算,工作流调度,混沌遗传算法,熵

参考文献

[1]李金忠,夏洁武,曾劲涛等.网格工作流调度算法研究综述[J].计算机应用研究,2009,26(8):2916-2820.

[2]李超,朱巧明,李培峰等.一个网格服务工作流的动态调度算法[J].计算机应用研究,2008,25(11):3285-3287.

[3]田国忠,于炯,侯勇等.基于资源状态可靠度的网格工作流调度算法[J].计算机工程与应用,2008,44(18):115-118.

[4]Wannaporn Teekeng,Arit Thammano.Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems[J].Procedia Computer Science,2012,12:122-128.

[5]J.Yu and R.Buyya.Scheduling Scientific Workflow Applications with Deadline and Budget Constraints using Genetic Algorithms[J].Scientific Programming,2006,14:217-230.

[6]Shayan Shahand,Stephen J.Turner,Wentong Cai,et al.A dynamic Web service scheduling and deployment framework for data-intensive Grid workflows[J].Procedia Computer Science,2010(1):593-602.

[7]谭跃,谭冠,叶勇,伍雪冬.具有混沌局部搜索策略的双种群遗传算法[J].计算机应用研究,2011,28(2):469-471.

【混沌DNA遗传算法】推荐阅读：

混沌遗传优化算法05-26

混沌算法08-25

混沌量子进化算法07-06

遗传基因算法08-21

遗传禁忌算法09-01

元胞遗传算法05-11