混沌算法

混沌算法（精选九篇）

混沌算法 篇1

本文“一组一密”算法的思想是:通过一定的方法从logistic公式产生的混沌序列中提取出64位的密钥序列, 将其折叠分割, 用其组成分组密码算法的子密钥, 使用分组密码算法对明文进行加密, 每加密一组明文更换一组密钥, 实现“一组一密”。

对于传统的“一组一密”对明文的块的划分是固定的, 而本文算法的思想是让64位的密钥多次折叠后成为分组密钥中的子密钥, 同时明文的块的划分, 随着密钥的多次折叠变化而变化。

对十进制的十个元素进行哈夫曼编码。如表1得到十个数的不同字符编码。

例如:表达式f=0.23457742571956402600的值取小数点后面18位数值化后, 取其密钥序列的前64位, 不足的补0。

根据表1对f数值化:01001110 00100110 11101110 00010100 11011001 11110011 01010000 00010101 0

取其前64位得01001110 00100110 11101110 00010100 11011001 11110011 01010000 00010101

1) 明文以64位8字节为一组, 不需要折叠, 折叠0次得到1个子密钥如图1。

子密钥只有一个, 那么所得的密钥序列不用折叠直接用作加密。

子密钥1:01001110 00100110 11101110 00010100 11011001 11110011 01010000 00010101

2) 明文以32位4字节为一组。需要折叠1次, 折叠1次得到2个子密钥如图2。

密钥序列:01001110 00100110 11101110 00010100 1101100111110011 01010000 00010101

子密钥1:01001110 00100110 11101110 00010100

子密钥2:10101000 00001010 11001111 10011011

这样根据密码折叠的次数越多, 加密的强度也越大, 要破译的难度也越大。由上面的四种分组加密的方法做分析, 分组加密之间的比较如表2。

根据本文“一组一密”算法的设计, 下面我们用下面的流程图来实现具体的整个加密和解密过程。

一组一密加密过程如图3。

2 混沌序列数值化分析

对一篇2000字符的文章进行十次不同密钥加密后的结果进行分析, 明文ASII2码中0和1的个数, 以及经过不同的混沌加密方式相同的密码进行加密后, 0和1的个数。明文和密文ASII2码中0和1的个数如表3。

对表行分析, 得到以下结果:

1) 4种不同的混沌加密方法均可以减少明文中0与1的个数差距。

2) 密文中0与1的比例在减少即意味着该混沌加密算法防止统计分析攻击。

通过上面的结论可得, 该混东加密能够将文章中的内容“混淆”到密文中, 而使统计学无法发挥作用, 使其无法统计。

3 字符分布分析

对一篇2000字符的文章的字符加密前ASCII码分布进行分析, 加密前字符分布情况如图4。

2000字符的文章的字符加密后ASCII码分布进行分析, 加密后字符分布情况如图5。

图4是对一篇长度约2000字符的英文文章的字符出现频率所作的统计图, 图5给出相应加密文的字符出现频率图。明文字符主要为小写英文字符和空格符;而用本文算法加密后相应的密文字符却比较均匀地分布在ASCII码值0-127的整个字符空间, 在ASCII码值128-255空间内几乎没有分布。可见本加密算法产生的密文均匀地扩散到这个空间中。因此, 密文将具有较强的抗统计分析攻击的能力。

摘要：混沌系统对初始条件极端敏感, 由于系统内部存在随机性, 经过多次迭代后, 会产生大量的类似随机数且较宽频谱具有优良的密码学性能的序列。该文的工作重点是用logistic公式产生的随机数来设计混沌加密算法, 对混沌序列进行“折叠”处理, 再根据哈夫曼树编码对其数值化, 较大保留了混沌序列的伪随机性, 作为原始的密钥。然后针对不同加密强度的需求设计“一组一密”加密算法。

关键词：混沌,解密,数据加密,加密算法

参考文献

[1]李海泉, 李键.计算机网络安全与加密技术[M].北京:科学出版社, 2003.

混沌算法 篇2

混沌优化算法在不可分稳态大系统优化中的应用

讨论了整体目标函数关于各子系统不具有可加形式的大规模稳态系统的`优化问题,将混沌优化算法应用于其最优值的求解,利用混沌运动的遍历性来得到优化问题的全局最优值.仿真结果表明,该算法简单易行,求解精度和可靠性较高,是解决不可分稳态大系统优化问题的一种有效方法.

作 者：李薪宇 康波 吕炳朝 LI Xin-yu KANG Bo LU Bing-chao 作者单位：电子科技大学,自动化工程学院,四川,成都,610054刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY年，卷(期)：38(3)分类号：O1关键词：稳态大系统 混沌优化 全局最优

混沌算法 篇3

关键词 Lorenz系统 密码学 混沌加密 数字图像

中圖分类号：TP393.08 文献标识码：A

随着数字多媒体技术和计算机网络技术的迅速发展，数字多媒体的安全性和保密性就越来越重要。数字图像的加密和解密在信息安全技术中尤其重要，希望加密后的图像类似于现实世界的白噪声，这样，未授权者就无法得到图像的有效信息，实现了数字图像信息的安全和保密。而传统的对文本加密的方法无法适应数字图像自身的特点，所以不适合应用于数字图像加密。混沌理论是一种新兴的非线性理论，它具有以下几个特征：对初值敏感性、不可预测性、非线性、伪随机性。这些特性非常适合于数字图像信息的加密。但是混沌序列是一种高度依赖迭代精度的序列，当理论精度是无穷大时，混沌序列可以看作是理想的随机序列，近似于现实世界的白噪声。实际应用中，由于计算部件精度的限制和实现成本的制约，都无法达到无穷的计算精度，这样得到的混沌序列就是一种有周期的伪随机序列。

1 Lorenz系统介绍

Lorenz混沌系统是美国著名的气象学家洛伦兹在1963年研究大气运动时提出的，其方程组表达式如下：

其中表示对流运动的振幅，与运动强度成正比；表示上升流与下降流的温度差；表示垂直温度分布与线性温度廓线的偏差，即垂直温度分布的非线性度；表示流体分子的粘性系数；为瑞利数；为几何因子，没有直接的物理意义。

1.1 加密算法的密钥设计

混沌模型用于加密算法中的时候，这些混沌模型的参数和系统初始值理论上都可以作为加密算法的初始密钥。但是为了使得加密算法有良好的安全性能，必须保证这些超混沌模型能够进入超混沌状态，因此，在算法中，仅仅把这三个模型中每一个模型的初始值，作为算法的初始密钥，由用户输入，而把这些模型中的所有系统参数都按照上面给出的进入超混沌状态时的取值在算法中固定下来。

另外，为了区分不同模型的初始值，将这三个模型中的初始值，分别记作M，N；A，B；U，V。即混沌模型的两个初始值在加密算法中记为M，N；超混沌模型的两个初始值在加密算法中记为A，B；混沌模型的两个初始值在加密算法中记为U，V。

所以初始密钥K是一个6元组，包含6个子密钥：

K=（M，N，A，B，U，V）。

1.2 加密算法原理

利用图像像素值替换算法，对置换后的图形进行像素值的修改，得到最终的密文图像。解密的过程与加密相似，采用相同的初始密钥，对超混沌模型进行迭代，分别生成置换矩阵、密钥流矩阵和替换次序矩阵。先将密钥矩阵与密文按位进行异或操作，再把结果根据置换矩阵进行逆向置换，既可以解密为初始明文。

2 算法的安全性分析及实验结果

对256*256大小的灰度lena图像，采用Matlab工具对优化后的多级混沌加密算法进行实验，并对实验结果进行安全性分析。

2.1 实验结果

对原始图像进行加密，输入的初始密钥（未经字符化处理）K（M，N，A，B，U，V）=（4.32，0.25，0.17，0.66，1.67，2.05）。

可以看出，利用该多级混沌图像加密算法，使得原始图像被充分的置乱与替换，直观上无法看出原始图像的痕迹。

2.2 密钥空间和密钥敏感性分析

本算法的初始密钥未经字符化处理前，为实数，由6个子密钥构成。若计算机的精度为1015，则密钥空间远远大于1090，完全可以抵抗穷举法的攻击。密钥经字符化处理后，密钥空间为位字符（≥6），所以密钥空间为256n，当足够大时，可以抵抗穷举攻击；另外，由于算法加入了时间戳，实际密钥空间也极大增加。利用正确的初始密钥，可以对加密图像进行解密，解密后的图象质量良好。另外，当解密密钥发生微小的错误（0.001）时，不能正确还原图像，解密图像混乱无序，没有意义。这说明，解密过程对密钥非常敏感，算法的安全性较高。

2.3 相关性分析

从加密图像中随机抽取1000对垂直相邻的像素，对它们的相关性进行分析。图中横坐标表示像素点（）的像素值，纵坐标表示像素点（ +1）的像素值。

可以看出加密后图像的相邻像素值较为均匀得分布到了整个像素值空间。相邻像素值不仅仅在低值空间均匀分布，在高值空间也同样均匀分布。这说明，加密后的图像灰度分层现象消失，因而图像的相关性大大减弱。

采用相关性计算公式，对算法的加密图像计算相关系数，结果如表1所示。

表1 加密图像的相关系数

说明加密算法使图像的相关性降低，具有较高的抗攻击能力。

3 实验结论

混沌模拟退火粒子群优化算法 篇4

1 粒子群优化算法 (PSO)

粒子群优化算法 (Particle Swarm Optimization, PSO) 是一种进化计算技术。

PSO求解优化问题时, 问题对应于搜索空间中一只鸟的位置, 称这些鸟为“粒子” (particle) , 其原理是:初始化一群随机粒子, 然后通过迭代寻找最优解。在每一次迭代中, 粒子通过跟踪两个“极值”来更新自己。一个是粒子本身所找到的最优解, 即个体极值pbest, 另一个极值是整个种群目前找到的最优解, 即全局极值gbest。粒子在找到上述两个极值后, 根据下式来更新自己的速度和新的位置:

其中, vk, m为第k个粒子在第m维度上的速度;xk, m为第k个粒子在第m维度上的位置;r1, r2为0和1之间的随机数;c1, c2为算法的学习因子, 非负常数, 通常取值相同, 介于0和4之间, 通常取c1=c2=2;w为惯性权重, 用来控制和提高优化效率。

2 粒子群优化算法的改进

2.1 基于模拟退火思想的粒子群优化算法

2.1.1 模拟退火优化算法

模拟退火优化算法[1] (Simulated Annealing, SA) 是一种模拟高温金属降温的热力学过程, 并广泛应用于组合优化问题上。模拟在进行优化时先确定初始温度, 随机选择一个初始状态并考察该状态的目标函数值;对当前状态附加一个小扰动, 并计算新状态的目标函数值;以概率1接受较好点, 以某种概率Pr接受较差点作为当前点, 直到系统冷却。模拟退火方法在初始温度足够高、温度下降足够慢的条件下, 能以概率1收敛到全局最优值, 由于它以某种概率接受较差点, 从而具有跳出局部最优解的能力。

算法的求解过程为:1) 初始化退火Tk (令k=0) , 产生随机初始解x0;2) 在温度Tk下重复执行如下操作, 直至达到温度Tk的平衡状态;在解x的领域中产生新的可行解x′;计算x′的目标函数f (x′) 和x的目标函数f (x) 的差值Δf;依照概率min{1, exp (-Δf/Tk) }>random[0, 1]接收x′, 其中, random是[0, 1]区间内的随机数。3) 退火操作:Tk+1=CTk, k←k+1, 其中C∈ (0, 1) 。若满足收敛判据, 则退火过程结束;否则转2) 。

其中退火温度T控制着过程向最优值的优化方向进行, 同时它又以概率exp (-Δf/Tk) 来接收劣质解, 因此算法可以跳出局部极值点。只要初始温度足够高, 退火过程足够慢, 算法就能收敛到全局最优解。

2.1.2 基于模拟退火思想的粒子群优化算法

关于基于模拟退火思想的PSO算法, 文献[2]中提出了4种改进方法, 并且用具体例子证明第4种方法更为有效, 在此不再重复, 直接应用第4种方法。其具体改进思想为:1) 在更新位置时, 将其位置限制在xmax之内;2) 比较更新前和更新后的两个位置所对应的适应值, 如果适应值的变化量小于e, 则接受这个新位置;否则就拒绝, xk+1仍为xk。其中, e为允许适应值的变坏范围, 为常数。

2.2 混沌粒子群优化算法

2.2.1 混沌优化算法

混沌[3] (chaos) 是一种普遍的非线性现象, 其行为复杂且类似于随机, 但其有精致的内在规律性。由于混沌的遍历性, 利用混沌变量进行优化搜索会比盲目无序的随机搜索更具有优越性, 它可以避免演化算法陷入局部最优的缺点。

通常, 基于混沌动态的搜索过程分为如下两个阶段:

1) 基于确定性迭代式产生的遍历性轨道对整个解空间进行考察。当满足一定终止条件时, 认为搜索过程中发现的最佳状态 (Best to Far) 已接近问题的最优解 (只要遍历性搜索轨道足够长, 这种情况总能实现) , 并以此作为第二阶段的搜索起始点。

2) 以第一阶段得到的结果为中心, 通过小幅度的扰动进一步进行局部区域内的细搜索, 直到算法终止, 准则满足。其中, 所附加的扰动可以是混沌变量, 或者是基于高斯分布或柯西分布或均匀分布等的随机变量。

产生混沌序列时, 多采用的是logistic模型[4]:

cx${}_k^{s+1}$=u×cx${}_k^s$× (1.0-cx${}_k^s$) i=1, 2, …, n。

其中, cx${}_k^s$为cxk在第s步混沌演变后的值, cxk∈[0, 1.0], 0≤u≤4。当u=4时, 得到以下式子:

cx${}_k^{s+1}$=4cx${}_k^s$× (1.0-cx${}_k^s$) i=1, 2, …, n (1)

当cxk∈ (0, 1.0) 且不等于0.25, 0.5, 0.75时, 将产生混沌现象, cxk将在 (0, 1.0) 内遍历。

对于取值不在 (0, 1.0) 的变量xk (其取值范围为 (ak, bk) ) , 可通过式 (2) , 式 (3) 转换:

cxk= (xk-ak) / (bk-ak) (2)

xk-ak+cxk (bk-ak) (3)

2.2.2 混沌粒子群优化算法 (Chaotic Particle Swarm Optimization, CPSO)

CPSO的主要步骤为:

1) 初始化, 给定粒子的个数, 随机产生每个粒子的位置和速度, 并计算对应的适应值, 求出psbestk和gsbest (其中, k为第k个粒子;s为进行混沌运动的次数) 。

2) 将x${}_k^s$的每个分量通过 (2) 式进行转换, 映射为混沌变量cx${}_k^s$, 各分量cx${}_k^s$∈ (0, 1) 。

3) 更新每个粒子的速度和位置, 并计算每个粒子的适应值。

4) 混沌变量cx${}_k^s$的各分量经过 (1) 式做混沌运动, 得到新的位置点cy${}_k^s$。

5) 将cy${}_k^s$的每个分量通过 (3) 式变换, 映射为{ak, bk}间的普通变量y${}_k^s$, 并计算f (y${}_k^s$) 。

6) 比较f (x${}_k^s$) , f (y${}_k^s$) 和f (psbestk) , 得到ps+1bestk。

7) 比较f (ps+1bestk) , f (gsbestk) , 得到gs+1bestk。

8) 判断是否已经满足终止条件, 若满足, 终止算法运行, 输出当前的最优解与最优值;否则, 返回到2) , 继续进行。

2.3 混沌模拟退火粒子群优化算法

由于模拟退火粒子群优化算法和混沌粒子群优化算法都能达到较好的效果, 且这两种算法并不相冲突, 故文中提出一种新的算法, 即把这两种方法结合起来, 称为混沌模拟退火粒子群优化算法 (the simulated annealing and chaotic particle swarm optimization algorithm) 。1) 对粒子更新的位置进行限制;2) 对粒子个体产生混沌扰动, 以使其跳出局部极值区域。

其具体流程图如图1所示。

其中, 第3, 8, 9步为模拟退火粒子群算法;第4, 5, 6, 7步为混沌粒子群算法。

3 算例

对以下两个经常被国内外学者用来测试优化算法有效性的测试函数进行优化计算, 以精度为0.001时所需的迭代次数作为比较, 粒子数为20个, 每种算法运行1 000次, c1=c2=2, w=1, xmax=2, vmax=1, 结果如表1所示。

$F{}_1=\sin (\sqrt{x{}_1^2+x{}_2^2})\frac{\sin {}^2(\sqrt{x{}_1^2+x{}_2^2})-0.5}{[1+0.001(x{}_1^2+x{}_2^2)]{}^2}+0.5$;

F2=100 (x${}_1^2$-x2) 2+ (1-x1) 2。

在Visual Basic中, 编写了PSO程序, SAPSO程序, CPSO程序和SA-CPSO算法程序, 将计算结果导入到Excel中进行处理, 结果如表1所示。

对于这两个函数, 明显可以观察得出混沌模拟退火粒子群算法的平均迭代次数都比其他算法要少, 并且其平均函数值也要比其他算法求得的平均函数值小, 这证明该算法的效率和有效性。

4 结语

作为群智能的代表性方法之一, 粒子群优化给大量复杂优化问题的求解提供了一种新的思路和解决方法。文中提出了一种改进粒子群算法, 即混沌模拟退火粒子群算法, 该方法同时采用模拟退火粒子群算法和混沌粒子群算法, 实验结果表明了该算法的效率和有效性, 并且证明该方法优于其他三种算法, 具有广泛的应用前景。

参考文献

[1]康立山.非数值并行算法 (第1册) ———模拟退火算法[M].北京:科学出版社, 1997.22-55.

[2]高尚, 杨静宇.群智能算法及其应用[M].北京:中国水利水电出版社, 2006.

[3]张丹, 李长河.基于混沌的粒子群优化算法研究与进展[J].软件导刊, 2007 (3) :109-110.

基于混沌序列的粒子群算法 篇5

粒子群算法 (Particle Swarm Optimization, PSO) 是1995年由美国社会心理学家Kennedy和电气工程师Eberhart受人工生命研究结果的启发共同提出的一种群体智能算法, 它与其他进化算法一样, 也是基于“种群”和“进化”, 通过个体之间的协作和竞争, 实现复杂空间最优解的搜索。同其他算法比较, PSO的优势在于简单、容易实现并且没有许多参数需要调整, 已经被广泛应用于约束优化、电力系统、神经网络等领域。

PSO算法提出以来, 为了提高收敛的全局性, 主要是保证粒子的多样性。Lovbjerg提出了一种自组织临界点控制算法, 对每个微粒增加了当前临界值属性, 以达到控制种群多样性的目的;Suganthan引入了空间邻域的概念, 保证群体的多样性;Miranda等人则使用了变异、选择和繁殖多种操作同时自适应确定速度更新公式中的邻域最佳位置以及惯性权值和加速常数保证了群体的多样性;为了避免PSO算法的过早收敛问题, Riget和Vesterstr提出了一种保证种群多样性的粒子群算法 (Attractive and Repulsive Particle Swarm Optimizer, 简称ARPSO) 。曾建潮等提出了一种保证全局收敛的PSO算法 (简称SPSO) , 当xk (t) =pg=pk时, 粒子k停止进化, 在搜索空间中随机产生一个新的粒子来代替停止的粒子, 与其余经过更新pi, pg后的粒子一起进化, 大大提高了PSO的全局收敛能力与速度。

1 基本粒子群算法

与其他演化算法类似, PSO也是基于群体的。将每个个体看作是维搜索空间中的一个没有重量和体积的粒子, 并在搜索空间中以一定的速度飞行, 根据对环境的适应度将群体中的粒子移动到较好的区域。

设:

Xi= (xi1, xi2, …, xin) 为粒子i的当前位置;

Vi= (vi1, vi2, …, vin) 为粒子i的当前飞行速度;

Pi= (pi1, pi2, …, pin) 为粒子i所经历过的最好位置, 称为个体最好位置, 也可用Pbest表示;

Pg= (pg1, pg2, …, pgn) 为所有粒子经历过的最佳位置, 称为全局最好位置, 也可用Gbest表示。

PSO算法的进化方程为:

其中:下标“i”表示粒子i, 下标“j”表示粒子的第j维, t表示第t代, w为惯性权重, c1、c2为加速常数, 通常在0～2间取值, r1～U (0, 1) , r2～U (0, 1) 为两个相互独立的均匀分布的随机数。

粒子通过不断地学习更新, 最终寻找到解空间中最优解所在的位置, 最后输出的Gbest就是算法找到的全局最优解。

2 基于混沌序列的PSO算法

在PSO算法运行过程中, 很容易发生早熟收敛。为了克服PSO算法的这种早熟收敛问题, 本文提出一种能够保证种群多样性的PSO算法———基于混沌序列的粒子群算法 (简称CPSO算法) 。

PSO算法运行若干代之后, 所有的粒子都趋向于Pg, 此时粒子所搜索的范围相对比较小, 粒子的多样性就相对比较差。

引入欧氏距离公式

设一个以Pg为中心, 以ε为半径的球。则:

即用dig表示Xi到Pg的距离。如果dig≤ε, 说明粒子i位于这个球内。

假设有总共N个粒子, 球内的粒子数为M, 如果M/N的值大于一定数α, 就定义为粒子的多样性比较差。此时为了增加粒子的多样性, 对球内的粒子进行逃逸。即M/N的值大于α时, 对球内的粒子随机选择一部分进行逃逸。

混沌序列可以使粒子较为均匀的分布, 而且可以使以Pg为中心的球内的需要逃逸的粒子跳到这个球外面的其它区域, 所以当M/N的值大于α, 对随机选择出来的球内的部分粒子在搜索空间内运用混沌序列进行逃逸重新产生。

Logistic序列:

其中:xn∈[0, 1], 1≤μ≤4。当μ=4时, 序列完全处于混沌状态。

Logistic序列的变型:

当xij (t) <0时:

当xij (t) ≥0时:

当0≤xij (t) ≤1, 取μ=4;当xij (t) <0或xij (t) >1时, 取μ=1.5。这样, 既不失Logistic序列的混沌性, 又可以增强逃逸的有目的性。

算法步骤如下:

Step1:初始化各粒子的位置与速度;

Step2:计算各粒子的适应值;

Step3:对于每个粒子, 将其适应值与所经历的最好位置Pi的适应值进行比较, 若较好, 则将其作为当前的最好位置;将其适应值与全局所经历的最好位置Pg的适应值进行比较, 若较好, 则将其作为当前的全局最好位置;

Step4:以Pg为中心, 根据公式 (4) 计算所有粒子到Pg的距离d, 如果d<ε, 说明这个粒子在以Pg为中心, ε为半径的球内。

Step5:判断结束条件是否满足, 如果满足, 则结束, 否则, 执行Step6;

Step6:对于所有粒子, 执行如下操作:

(1) 根据公式 (1) 、 (2) 更新粒子的速度和位置。

(2) 对于每个粒子, 将其适应值与所经历的最好位置Pi的适应值进行比较, 若较好, 则将其作为当前的最好位置。

(3) 对于每个粒子, 将其适应值与全局所经历的最好位置Pg的适应值进行比较, 若较好, 则将其作为当前的全局最好位置。

Step7:如果在球内的粒子达到一定数量 (M/N>α) , 执行Step8;否则, 执行Step6;

Step8:对球内的粒子随机选择一部分, 根据公式 (6) 、 (7) 进行逃逸;

Step9:返回Step2。

3 实例计算

本文引入3个多维基准优化问题, 将CPSO与PSO进行对比。

(1) Sphere函数。

(2) Ackley函数。

(3) Griewank函数。

对于PSO和CPSO, 取粒子数N=30, w的取值在[1]之间随代数线性递减, c1=1.2, c2=1.8, vmax=xmax/2。

对于CPSO, 取半径ε=0.3, M/N的值α=0.6。

当M/N>α时, 把球内的M个粒子随机选择M-4个运用混沌序列重新产生。

对于f1、f2、f33个n维测试函数, 我们分别取n=50和n=100。

运行100次, 每次运行3000代, 对PSO和CPSO的收敛率和平均收敛代数进行比较实验。结果如表1所示。

为了进一步比较, 运行次数和代数不变, 对PSO和CPSO在运行中的最大值、最小值和平均值进行比较。结果如表2所示。

从表和表足以证明的寻优率和全局收敛性对于PSO, 有了明显的提高。这都源于CPSO当粒子陷入局部最优时, 运用逃逸策略使陷入局部最优的粒子能够及时地跳出局部最优点, 进入解空间的其它区域进行搜索, 提高了种群的多样性, 能有效地避免早熟收敛问题。

4 结束语

本文将混沌序列引入PSO算法, 提出了一种能够保证种群多样性的PSO算法———基于混沌序列的粒子群算法 (CPSO) 。CPSO使陷入局部最优位置的发生停滞的粒子能够及时跳出局部最优, 进入解空间的其它区域进行搜索, 增大了粒子种群的多样性, 克服了PSO算法的早熟收敛问题大大增强了算法的全局搜索能力。

参考文献

[1]KENNEDY J, EBERHART R C.Particle Swarm Optimization[C].In:Proceedings of IEEE International Conference on Neural Net-works, IEEE Service Center, Piscataway, NJ, 1995.

[2]RAY T, LIEW K M.A swarm with an effective information sharingmechanism for unconstrained and constrained single objective opti-mization problems[A].Proc IEEE Int Conf on Evolutionary Com-putation[C].Seoul, 2001.

[3]PARK J, CHOI K, ALLSTOT D J.Parasitic-aware RF Circuit De-sign and Optimization[J].IEEE Transactions on Circuits and Sys-tems I:Fundamental Theory and Applications, 2004 (10) .

[4]EBERHART R, HU XIAOHUI.Human tremor analysis using par-ticle swarm optimization[A].P roc of the Congress on Evolution-ary Computation[C].Washington, 1999.

[5]LOVBJERG M, KRINK T.Extending particle swarm optimizerswith self-organized critically.In:Proc.of the IEEE Int’l Conf.onEvolutionary Computation.Honolulu:IEEE Inc, 2002.

[6]SUGANTHAN P N.Particle swarm optimizer with neighbourhoodoperator[C].In:Proceedings of the Congress on Evolutionary Com-putation, Washington DC, USA, 1999.

[7]V.MIRANDA AND N.FONSECA.EPSO:evolutionary particleswarm optimization, a new algorithm with applications in powersystems[W].in IEEE/PES Transmission and Distribution Conf.Exhibition Asia Pacific, Oct.2002 (2) .

[8]RIGET J, VESTERSTROEM J S.A Diversity-Guided ParticleSwarm Optimizer-the ARPSO.Technical Report No.2002-02[R].Department of Computer Science, University of Aarhus, EVALife, 2002.

[9]曾建潮, 崔志华.一种保证全局收敛的PSO算法[J].计算机研究与发展, 2004 (8) .

一种混沌加密算法的改进 篇6

随着信息技术的飞速发展,信息安全问题显得尤为重要。混沌信号具有随机性、不可预测性以及对初始值极度敏感等特性,非常适用于保密通信等领域。在过去的几年里,各种基于混沌的保密系统被提出,关于混沌序列的产生及其在加密系统中的应用得到了广泛研究[1,2,3,4,5,6,7,8,9]。现代密码学指出加密体系的安全性不应当依赖于加密方法本身,应当依赖其所采用的密钥。在分析密码系统时,通常假设密码分析者除了密钥之外,熟知加密系统的所有设计细节和工作原理。传统的密码分析方法按照从难到易的顺序排列为:

1)唯密文攻击。攻击者拥有同一种加密算法加密的一些密文,破译出全部或者部分明文或密钥。

2)已知明文攻击。攻击者拥有几段密文以及对应的明文,破译出全部或者部分明文或密钥。

3)选择明文攻击。密码分析者拥有一些密文和密文所对应的明文,能够随意地选择加密的明文,以破译出全部或者部分的明文或密钥,这种情况可视为攻击者已经掌握了加密机的使用权或通过间谍引诱选择明文。

4)选择密文攻击。密码分析者拥有一些密文和密文所对应的明文,能够随意地选择密文,以破译密钥。这种情况可视为攻击者已经掌握了解加密机的使用权或通过间谍引诱选择密文。

Xiang等提出一种基于循环移位操作和XOR运算的混沌加密算法[5],该类算法具有加密速度快等密码学特性。Wang等[6]和Xu等[7]分别指出该类算法存在缺陷,可以选择明文攻击进行破解,并提出了改进型算法。在改进型算法中,混沌序列的产生同时依赖于密钥和明文,使每一个明文比特不仅影响当前轮所得到的密文块,还会影响后续的密文块。测试结果表明,此类改进型算法可以有效抵抗选择明文攻击。然而,此类算法对误码的稳健性较差,一旦密文在存储或传输时发生误码会出现密文比特出错,将导致后续密文无法正确解密,同时在Wang等人工作的基础上,提出了一种可以有效抵抗误码的改进型算法。

1 Xiang等人的算法概述

在Xiang等人的算法中,用到了Logistic映射生成独立同分布的随机变量

将映射生成的随机变量x表示为二进制,即

bi(x)可以表示为

式中:Θt(x)=,由此得到一个二进制序列流其中n代表序列的长度,τn(x)代表Logistic映射第n次迭代的结果。进而得到加密算法为:

1)取迭代的初始点为第N0次迭代的函数值,即。

2)将明文信息m分成若干长度为l(l=8)byte的子信息块wj

每当得到明文信息的长度为8 byte的子信息块pj,pj+1,…,pj+7时,将其转换为64 bit的二进制信息块Pj=pj,pj+1,…,pj+7。

3)根据上述产生二进制序列的方法,在式(3)中令i=3,迭代Logistic映射70次,得到二进制序列Aj=B31B32…B364,Aj′=B365B366…B370,用Dj表示二进制序列Aj′的十进制数值,并在本轮加密后迭代混沌映射Dj次。

4)将二进制信息块Pj循环左移Dj位得到新的二进制信息块Pj′。

5)对序列Pj′和序列Aj作异或运算(用茌表示),得到明文块Pj所对应的密文块Cj

将Cj按8 bit分开便可以得到明文pj,pj+1,…,pj+7所对应的密文cj,cj+1,…,cj+7。

6)若所有明文块已经加密,则加密过程结束,否则令w=τ70+Dj(w),并转至步骤2)。

解密过程和加密过程类似,文献[5]指出这种加密系统具有较快的加密速度和加密性能,然而Wang等和Xu等在文献[6]和文献[7]中分别指出了这种加密系统的缺陷在于无法抵抗选择明文攻击,Wang等和Xu等提出的算法原理相似,笔者将简单介绍Wang等提出的改进算法。

2 Wang等人改进型算法概述

Wang等人在文献[6]中指出,Xiang等人提出的算法无法抵抗选择明文攻击,详细描述了攻击策略:

1)选择一个全0的明文串Pz,其长度与待攻击的密文串相同,假设Pzj(64 bit)为Pz中的第j个子信息块,Czj为其对应的密文

函数F(A,B)将二进制比特序列A循环左移B位,由于Pz为全0串,因此F(Pzj,Dj)=Pzj,从而进一步得到

2)根据Xiang等人提出的加密算法解密过程,可以得到与给定的密文块Cj对应的移位后的明文块

3)选择一个特殊的明文块Ps,其长度与待攻击的密文串相同,每一个子信息块(64 bit)除了第一个比特位为0外,其他全为1。假设Psj为Ps的第j个子信息块,并且Csj为其对应的密文块,则

由于在步骤1)中已经得到了Aj,因此

Csj茌Aj=F(Psj,Dj)茌Aj茌Aj=F(Psj,Dj)(10)

由于在F(Psj,Dj)中只有一个0 bit,可以很容易确定0 bit的位置,从而得到每一个子信息块移位信息,进而结合步骤2)得到明文块。

通过上述步骤,可以对整个密文块进行解密。针对上述缺陷,Wang等人提出了改进型算法,指出Xiang等人提出的算法中异或序列Aj及循环移位数值Dj与明文无关是导致其对抗选择明文攻击脆弱的主要原因,因此最直观的方法是使Aj及Dj数值的产生同时依赖密钥流和明文。考虑到解码端解密时需要产生同样的密钥流而且密文本身与明文相关,Wang等人的改进算法中直接使Aj及Dj的产生依赖于密文。此改进算法与Xiang等人提出的算法相比,前4个步骤保持不变,在第5步中有所改进,当得到Cj后,进行如下操作

式中:ci代表Cj中的第i个字节,在第6个步骤中用D*取代Dj进行混沌映射迭代。

通过上述改进,异或序列Aj与循环移位数值Dj的产生与明文相关,使不同的明文对应不同的Aj与Dj,从而可以有效抵抗选择明文攻击。Wang等人提出的改进型算法在不明显增加运算量的情况下,能够有效抵抗选择明文攻击,具有借鉴性,不过此改进型算法对误码的稳健性较差,即当密文保存或传输过程中如果发生误码,将会导致误码后面的解密完全失败,而且不可恢复,使此加密算法的应用性受到很大限制。

3 Wang等人算法的改进措施

由于存储介质受损或传输信道噪声的影响,数据在存储或传输时不可避免地会受到误码影响,即便用纠错码进行保护,也不能完全保证没有残余误码。密文的存储和传输也要考虑误码的影响,Wang等人提出的改进型算法,对误码的稳健性较差。从式(11)中可以看出,在Wang等人提出的改进型算法中,抵抗选择明文攻击的一个主要措施是使用来对明文进行异或操作和移位操作的二进制比特流的产生,不仅依赖于密钥,而且依赖于之前的密文。如果某个密文比特在存储或传输过程中由于误码影响而出错,将使后续所有用于异或操作和移位操作的二进制比特流发生改变,从而导致解密端后续密文比特流无法正确地进行解密,即误码具有传播效应。误码之所以具有持续的传播效应,原因在于当前的密文会影响后续所有明文的加密,为了将传播效应降到最低,同时又能够较好地抵抗选择明文攻击,笔者提出了改进措施。在改进措施中,引入超级信息块的概念,超级信息块Bi是由L(本文设置L=20)个子信息块w组成的,w由式(4)得到,长度为8 byte,超级信息块Bi表达为

Wang等人提出的算法的前4个步骤保持不变,第5步中得到D*后,需要判断当前加密的子信息块是否为一个超级信息块的第一个子信息块,如果是,则

式中:L_IterateNum是为了每个超级信息块加密结束时,保证混沌映射进行迭代的次数相同而设置的数值,即在每个超级信息块中,混沌映射共迭代L_IterateNum次。

如果当前加密的子信息块不是超级信息块的第一个子信息块,则接着其是否是超级信息块的最后一个子信息块,如果是,令D*=L_IterateNum。其中,D*如式(12)所述。

最后,如果当前加密的子信息块既不是第一个子信息块,也不是最后一个子信息块,则转到第6步。

除了第5步有所变动外,第6步中执行完混沌映射迭代后,增加如下措施

通过在第5步与第6步中增加上述措施,使混沌映射在每个超级信息块中最终迭代的总次数相同。上述措施使得所有超级信息块中加密用的二进制序列的产生不仅依赖于密钥,还依赖于本超级信息块的明文,而与其他超级信息块明文无关,从而在抵抗选择明文攻击的同时,能够保证当超级信息块中发生误码时,仅仅会影响到本超级信息块的解密,而对后续超级信息块无影响,从而增加了算法对误码的稳健性。

为了更加直观地说明Wang等人提出的算法所存在的缺陷及笔者提出改进措施的效果,选取一张152×152的BMP格式Lena灰度图为明文,取密钥(x0,μ)=(0.177 7,3.999 999 5)。图1a给出了明文图像,图1b给出了Wang等人提出算法的密文图像,图1c给出了无误码时用Wang等人提出的算法进行解密后得到的图像,图1d给出了10-4的随机误码下,Wang等人提出的算法进行解密后得到的图像。图2a给出了明文图像,图2b给出了笔者提出算法的密文图像,图2c给出了无误码时用提出的算法进行解密后得到的图像,图2d给出了10-4的随机误码下,提出的算法进行解密后得到的图像。从图1和图2中可以看出,本文提出的算法在保持了Wang等人提出的算法的优点的基础上,能够有效抵制误码的传播效应,将误码的影响局限在超级信息块中,从而使此类算法具有了更广泛的适用性。

4 小结

笔者指出了一种有效快捷的混沌加密算法存在缺陷,当存储或者传输过程中发生误码时,误码具有很强的传播效应,这主要是由于当前明文块加密时所采用的二进制比特流不仅仅依赖于密钥,还依赖于此加密块之前的所有明文信息。通过改进,使当前明文块加密时所采用的二进制比特流依赖于密钥以及该明文块所在的超级信息块中的明文信息,从而能够保证当误码发生时,误码的传播效应仅仅局限在超级信息块中,在保持了上述加密算法优点的同时,增强了其对误码的稳健性,使此类算法具有了更为广泛的适用性。

摘要：分析了一种基于循环移位操作和XOR运算的混沌加密算法,并指出该类算法在增强选择明文攻击安全性的同时,严重降低了加密算法对误码的稳健性,从而限制了该类算法的广泛应用。通过相关算法的描述与比较,提出了一种可以有效抵抗误码的改进算法。

关键词：混沌加密,攻击,误码

参考文献

[1]XUN Y,CHIK H T,CHEE K S.A new block cipher based on chaotictent maps[J].IEEE Trans.Circuits and Systems,2002,49(12):1826-1829.

[2]YANG Huaqian,LIAO Xiaofeng,WONG K W,et al.A new blockcipher based on chaotic map and group theory[EB/OL].[2010-05-07].http://www.sciencedirect.com/science_ob=ArticleURL&_udi=B6TJ4-4PJ0BYR-2&_user=10&_coverDate=04%2F15%2F2009&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1587499259&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=2f5baba001f12c3af2feb59f403cc035&searchtype=a.

[3]TANG Guoping,LIAO Xiaofeng.A method for designing dynamicalS-boxes based on discretized chaotic map[J].Chaos,Solitons&Fractals,2005,23(5):1901-1909.

[4]JAKIMOSKI G,KOCAREV L.Chaos and cryptography:block encryptionciphers based on chaotic maps[J].IEEE Trans.Circuits and SystemsI,2001,48(2):163-169.

[5]XIANG Tao,LIAO Xiaofeng,TANG Guoping,et al.A novel block cryptosystem based on iterating a chaotic map[J].Physics Letters A,2006,349(1-4):109-115.

[6]WANG Yong,LIAO Xiaofeng,XIANG Tao,et al.Cryptanalysis andimprovement on a block cryptosystem based on iteration a chaoticmap[J].Physics Letters A,2007,363(4):277-281.

[7]徐淑奖,王继志.一类改进的混沌迭代加密算法[J].物理学报,2008,57(1):37-40.

[8]刘刚,王立香.一种新的基于混沌的图像加密算法[J].电视技术,2008,32(12):22-24.

基于混沌算法信息安全系统的研究 篇7

信息时代, 我们的工作和生活与互联网联系越来越紧密,网络的应用给我们带来了极大的便捷和效益,但是安全问题却不容忽视,黑客、病毒、非法攻击等层出不穷, 使我们的个人信息及财产信息面临严重的安全隐患。信息安全问题主要包括信息的保密性、完整性、可用性和可控性。本文对目前较为流行的信息安全加密技术进行研究, 搭建基于混沌算法的信息安全系统, 对信息安全加密系统的研究具有一定的参考价值和研究意义。

2 混沌算法概述

2.1 混沌加密算法原理

设区间I[a,b]上的映射f(x)是连续的自映射,在f(x)满足有n周期点没有上界的前提下,f(x)对任意的正整数n满足有n周期点,同时不可数字集S满足条件:

不可数子集S被称作f在不可数子集S上是混沌。如果f(x)是在某个闭区间的一个周期点上有若干正整数的连续函数,则其就可以发生混沌现象。

采用混沌算法设计的信息安全系统是通过混沌序列密码对系统信息进行加密, 混沌自身具有优良的保密特性, 建立两个独立混沌系统作为信息的发送方和接收方,二者具有相互的独立性,具有相同的结构,加密密钥通过混沌信号发生器产生混沌信号序列流,明文序列在发送端加密后直接送往接收端解密,或者接收端在全部接收明文序列后一起解密,也可以建立同步关系实时解密。

2.2 混沌算法特点

混沌算法具有极敏感性, 如果初始值略有不同,则所得结果会大不相同,由于混沌对初始值和参数极度敏感,所以由混沌系统动态生成的混沌序列具有不可预测性,同一明文对应的是互不相同、互不相关的密文,对分组加密的穷举攻击和抗明文 - 密文对的选择性攻击能力是无效的; 混沌算法中具有许多相似的层次和规则,不同的函数带入相同的数,所得到的迭代计算结果可能相同;混沌算法不受外界变化影响,其具有一定的独立性和随机性,同时混沌算法不会出现相同的迭代计算过程,因此去具有非周期性;混沌算法应用在混沌系统中可在规定内经历全部的状态,具有历遍性。此外,其可通过混沌加密可用C、C++、Java、Matlab等语言仿真实现,在运行过程中占用的时间、空间都很少。由此,根据混沌算法的特点,其在信息安全系统中,非常适用于作为密码加密技术应用。

2.3 混沌算法在信息安全中的应用优势

混动算法自身的特点在对初始值和参数具有很好的敏感性,对于信息安全中微小的差别具有较高的分辨能力,通过混沌算法可将两个几乎相同的初始值经过迭代计算输出较大差别的计算结果。同时,混沌算法的随机性和非周期性使得其作为信息加密方法具有不可预测和不可罗列演算的能力,可有效防范利用穷举和选择进行系统攻击的黑客。混沌算法的历遍性能够提高信息安全系统保护的全面性,其加密准备时间短,可通过循环产生密钥流,提高加密能力。

3 基于混沌算法的信息安全系统设计

3.1 设计方案

采用时钟变换技术以获取系统时间为加密基础,通过利用三种映射相复合的方式来产生位置置乱矩阵和参数值变换矩阵,并且能够通过随机改变系统的多个初始值来提高信息传输的安全性,这部分采取了系统时钟变换法,这些方法结合最终达到近似于“一次一密”的加密效果。 本文选择 利用分段 线性混沌 映射、k阶Chebychev映射和Logistic映射进行复合实现随机改变系统多个初始值提高信息安全传输过程中的一次一密。设计方案如图1所示。

系统在发送端首先在任意时间点获取系统时钟信息,再将时钟信息进行加密,利用公钥信道传输到接收端,与此同时,将发送端所获取的时钟信息代入复合混沌系统的多级参数中,对信息原文进行加密,通过信道传输到接收端,最后可在接收端通过密钥解密后恢复出明文。

2.2设计内容

本文所设计的信息安全系统是采用分段线性混沌映射、k阶Chebychev映射和Logistic映射进行复合,其中分段线性混沌映射采用一维混沌映射, 运算速度快,实现简单 ;k阶Chebychev映射定义 区间为 [-1,1];Logistic映射是将密钥转换为序列 , 所得结果为混沌序列,对其解密则是将序列转换为密钥。复合信息安全系统模型如图2所示。

基于复合混沌算法的信息安全系统通过提取系统时间影响第一个分段线性混沌映射中的控制参数p,分段线性映射具有提高控制参数p的破译难度的能力,在相同密钥混沌映射中可等效出若干个不同的模型。此外,二级Chebychev映射通过系统所提取的时间作为初始参数值,利用时间的变化得到不同的序列索引号,由此实现一次一密,提高系统的保密级别和安全程度。

3.3 系统实现

基于混沌算法的信息安全系统实现是通过提取系统时间进行加密,系统时间可分为年、月、日、时、分、秒。在加密过程中,首先提取系统的时钟信息,时钟信息可组合成为相应的数字组合, 通过线性映射转换为0,1之间的数值,再通过Logistic映射将初始密钥值转换为M混沌序列 , 此过程每 个被N-1次迭代的 初始值生 成N个序列 , 即M×N混沌序列。其次,对M×N混沌序列进行排列 ,得到矩阵J,再将矩阵J进行由大到小排列生成矩阵G,由此,G中的元素与矩阵中的位置集合就建立起一级混沌矩阵C。第三,利用所提取的时钟信息进行转换取整,映射到[0,M]之间,将结果作为M个序列的索引号,该数值在k阶Chebychev映射中初始值的数值作为索引号对应在M中的值,生成M×N个混沌序列。

4 算法描述

Lyapunov指数 :yapunov指数被称为李雅普诺夫指数,其是衡量混沌的标准,一维混沌映射方程:Xn+1=F(Xn), 设Xn有偏差dX n,Xn+1偏差为d Xn+1, 则Xn+1+dX n=F (Xn+dX n) ≈F (Xn)+d Xn·F’ (Xn), 即 :dX n+1=d Xn·F’ (Xn), 设轨道按 指数规律 分离 ,|dX n+1|=|d Xn|·eλ,λ为判断指数,经过运算得:

利用分差方程计算Lyapunov指数, 设分差方程在Rn空间上有Xi+1=f(Xi),f为Rn 上的连续可微映射。再设f’(x)表示f的Jacobi矩阵:

Ji=f’(x0).f’(x1),...,f’(xi-1)

由大到小排列的|λ1(i)|≥|λ2(i)|≥...|λn(i)|

得Lyapunov指数

分段线性混沌映射:设p为控制参数,p∈(0,1)时,Lyapunov指数为正值,系统进入混沌状态 ,方程为:

Xn+1=Xn/p,Xn∈(0,p)

Xn+1=(1-Xn)(1-p),Xn∈(p,1)

Logistic映射 :设Xn为n的个体数目 ,n为整数值 ,当n+1时,数目为Xn+1,得Xn+1=f(Xn),n∈{1,2,...},

转换为Xn+1=μXn(1-Xn)。当0<μ≤1,迭代方程值等于0, 当1<μ≤3, 不动点0,1-1/μ有两个周期点,当3<μ≤4系统变为 混沌。因 此 ,Logistic方程在3.5699456<μ≤4的情况下出现混沌状态。

k阶Chebychev映射 :k阶Chebychev映射是一 维映射,其算法映射方程为:

xn+1=cos[k arccos(xn)]

x=[-1,1],k为任意正整数 ,当k=6,时映射为混沌状态。

5 结束语

基于混沌和动态变异的蛙跳算法 篇8

混合蛙跳算法是进化计算领域兴起的一种新型优化算法,它是由Muzaffar Eusuff和Kevin Lansey于2003年提出的一种基于群体的协同搜索方法[1]。该算法模拟青蛙群体寻找食物时,按种群分类进行思想传递的过程,将整个群体青蛙间能够交流的全局广泛搜索和子群内青蛙个体信息能够交流的局部深度搜索相结合[2],使算法向着全局最优解方向进行。与其他优化算法相比,SFLA结合了基于遗传基因的元进化算法MA(memetic algorithm)和基于群体觅食行为的粒子群算法PSO(particle swarm optimization)的特点,具有概念简单、参数少、易于编程实现及寻优能力强的优势。

作为重要的优化工具,SFLA已广泛应用于连续优化问题、离散优化问题、聚类问题,多变量PID控制器参数调节问题等领域。而如何避免陷入局部最优和提高算法的收敛速度也成为该算法的一个研究热点。文献[3]为提高SFLA的收敛效率,提出在SFLA深度搜索方向上融合极值动力学优化算法。文献[4]针对SFLA易陷入局部最优,求解精度低的缺点,提出利用差分进化中的变异思想对SFLA的更新策略进行局部扰动。文献[5]引入遗传算子增加对局部极值的扰动以避免陷入局部最优,同时对青蛙移动策略进行了优化,从而提高算法的性能和解的质量。文献[6]在全局搜索中加入自适应logistic序列的混沌变异操作,同时结合个体适应度和进化代数自适应调整变异尺度,从而提高算法最优解的精度。受此启发,本文先利用Tent映射构成的混沌序列初始化青蛙群体,从而提高初始解的质量。再通过引入群体适应度方差可知各青蛙的聚集程度,对于适应度方差较小的青蛙,取较大的变异概率进行变异操作;反之,对于适应度方差较大的青蛙,取较小的变异概率进行变异操作。因此新算法可根据各青蛙的位置动态地调整变异概率,达到跳出局部最优解的目的。

1 SFLA介绍

对于d维问题,随机生成F只青蛙(解)组成初始群体,第i只青蛙可以表示为Xi=(xi1,xi2,…,xid),将种群内青蛙个体按适应度降序排列。然后将整个群体分为s个子群,每个子群包含n只青蛙,满足F=s×n。第1只青蛙被分入第1个子群,第2只青蛙被分入第2个子群,…,第s只青蛙被分入第s个子群,第s+1只青蛙被分入第1个子群。依此类推,直到所有青蛙分配完毕[7]。

在每个子群中,具有最好适应度的青蛙记为Xb,最差适应度的青蛙记为Xw,而整个群体中具有最好适应度的青蛙记为Xg,对每个子群进行局部搜索,每次迭代只更新子群中的最差青蛙,更新策略为:

Di=rand( )·(Xb-Xw) (1)

Xw=Xw(当前位置)+Di (-Dmax≤Di≤Dmax) (2)

式中,Di表示分量i上移动的距离;rand( )是0到1之间的随机数;Dmax是青蛙允许移动的最大距离。

经过更新后,如果得到的解Xw优于原来的解Xw(当前位置),则取代原来种群中的解;否则用Xg取代Xb,重复执行更新策略式(1)、式(2);如果仍然没有改进,则随机产生一个新解取代原来的Xw。重复这种更新操作,直到设定的迭代次数,就完成一轮各子群的局部搜索。然后将所有子群的青蛙重新混合排序,划分子群,进行下一轮的局部搜索,如此反复直到满足终止条件。

2 基于混沌和动态变异的蛙跳算法(新算法)

2.1 用混沌序列产生青蛙群体

初始群体的分布性质严重影响整个算法的收敛性能。若初始群体性质差,不但会造成算法收敛速度慢,而且会使算法不收敛。在SFLA中,随机生成的初始群体的各青蛙都集中在解空间的某一局部区域,很容易使算法陷于局部最优。因此,本文利用混沌的遍历性初始化青蛙群体以增强群体的多样性,从而提高初始解的质量。

混沌是非线性系统中一种普遍的现象,且混沌运动能在一定范围内按其自身的“规律”不重复遍历所有状态,这种遍历性可作为搜索过程中避免陷入局部最优的一种有效的优化工具,因而,混沌优化搜索比随机搜索更具优越性[8]。其优化算法的主要思想是:首先产生一组与优化变量数目相同的混沌变量,将混沌运动的遍历范围放大到优化变量的取值范围,然后利用混沌变量的遍历性、随机性进行搜索。

一个好的混沌模型能提高混沌变异的概率,本文用能产生均匀序列且迭代速度快的Tent映射构造混沌模型,可以提高初始解的速度和精度,Tent序列的迭代公式如下:

${\rm Z}{}_{m+1}=\{\begin{array}{l}2{\rm Z}{}_{m}0\le {\rm Z}{}_m\le 0.5\\ 2(1-{\rm Z}{}_m)0.5\le {\rm Z}{}_m\le 1\end{array}(3)$

式中,Zm为混沌变量,m为迭代次数。

在(0,1)范围内,随机产生一个Q维的向量Z1=(Z11,Z12,…,Z1Q),应用式(3)得到M个分量Z1,Z2,…,ZM,将Zi用式(4)表示,通过计算适应度值,从M个初始种群中选择适应度值较优的F个(青蛙)作为初始解。

xij=aj+(bj-aj)Zij (4)

式中,i=1,2,…,M;j=1,2,…,Q。

2.2 群体适应度方差

各青蛙的位置可通过其适应度值来体现,由适应度值可知群体中青蛙的聚集程度,因此引入群体适应度方差来衡量解的质量。

设群体青蛙总数为F,第i只青蛙的自适应度值为fi,群体适应度值的平均值为favg,适应度方差δ(t)2定义为:

$\delta (t){}^2={\displaystyle \sum _{i=1}^F\left(\frac{f{}_i-f{}_{avg}}{f}\right)}(5)$

式中,f是限制适应度方差的大小,它的取值随式(6)变化;δ(t)2为第t次迭代的适应度方差;t=itj×titk,itj为当前子群内的迭代次数,it为子群内迭代总次数;titk为当前混合迭代次数,tit为混合迭代总次数,j∈[1,it]的整数,k∈[1,tit]的整数。

$f=\{\begin{array}{l}\max |f{}_i-f{}_{avg}|\text{i}\text{f}\max |f{}_i-f{}_{avg}|>1\\ 1\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(6)$

从式(5)、式(6)可知,群体适应度方差反映群体中所有青蛙的“收敛”程度,δ(t)2越小,则青蛙群体越趋于收敛;当δ(t)2=0时,则群体各青蛙的自适应度值几乎相同,算法陷于局部最优或达到全局最优;反之,青蛙群体处于随机搜索阶段。

2.3 动态变异操作

为了让青蛙在算法陷入局部最优之前找到新的搜索方向,动态变异操作应根据青蛙聚集程度来确定,即变异操作的概率应随群体的适应度方差的大小而改变:

P(t)=Pmax-(Pmax-Pmin)(δ(t)2/F) (7)

式中,P(t)为第t次迭代中群体全体极值的变异概率;Pmax为当前变异概率的最大值;Pmin为当前变异概率的最小值;F为群体青蛙总数。

从式(7)可知,当群体的适应度方差较小时,变异概率取值较大;反之,当群体的适应度方差较大时,变异概率取值较小。算法可根据各青蛙的位置来动态调整变异概率的大小,即若青蛙在最优解附近,群体适应度方差较小,则应取较大的变异概率进行变异操作;反之,若青蛙距最优解较远,群体适应度方差较大,则应取较小的变异概率进行变异操作,从而使算法达到跳出局部最优的目的。

对于Xg的变异操作,采用如下变异方程:

X′g = Xg + ξN(0,1)Xg (8)

式中,ξ为变异参数;N(0,1)是均值为0且方差为1的随机变量;X′g为变异后的全局最优。

2.4 新算法的流程

Step1 参数初始化,青蛙种群数F,子群数s,每个子群内青蛙数n,子群内迭代总数it,混合迭代总数tit;变异参数ξ,变异概率Pmin、Pmax;

Step2 利用式(3)混沌Tent序列初始化青蛙群体;

Step3 对每只青蛙,计算其适应度值f(xi)(即目标函数值),按照f(xi)以降序对青蛙群体进行排序并分为s个子群;

Step4 确定每个子群中的Xb、Xw及群体全局最优Xg,对每个子群中最差青蛙按式(1)、式(2)进行更新,直到设定的迭代总次数it,对更新后的子群进行混合,取代原来的群体;

Step5 利用式(5)、式(6)计算群体的适应度方差;

Step6 利用式(7)计算变异概率,并按照式(8)对全局最优解Xg进行变异操作,得到全局最优解X′g;

Step7 用X′g代替当前群体中全局最优解Xg;

Step8 若当前迭代次数达到预定设定的最大次数tit,则迭代停止,输出最优适应度值的相关信息,算法结束,否则转到Step3。

3 仿真实验

3.1 参数设置与测试函数的选择

为了测试本文算法性能,选取算法的平均最优适应度值、标准差、CPU运行时间及迭代曲线最为评价标准。平均最优适应度值是对所有实验次数得到的函数适应度值取算术平均数,平均最优适应度值越小,表明与理论值越接近,算法性能越好。

采用文献[9]中建议的参数设置,青蛙总数F=200,子群数s=20,子群内迭代总次数it=10,混合迭代总次数tit=500;变异参数ξ=0.5,变异概率Pmin=0.01、Pmax=0.1。选取6个经典的连续函数[10]进行测试,并与标准蛙跳算法SFLA、文献[10](ISFLA1算法,该算法是将生物学中的吸引排斥思想引入到混合蛙跳算法中,修正了更新策略,从而保持了子群的多样性。)进行比较,表1为测试函数的基本情况。

3.2 收敛性测试

取测试函数维数为30,预设精度为10-9,若算法在500次迭代中,最终结果满足精度要求,则该次运算算法收敛,反之为不收敛。算法收敛率为收敛次数与函数运行次数的比值。称算法收敛时,满足预设精度的迭代次数的最小值为算法的收敛代数,若最终优化结果不满足预设精度的要求,则该次收敛代数为指定迭代次数。平均收敛代数为各次收敛代数之和与函数运行次数的比值,实验结果如表2所示。

3.3 不同维函数的测试

函数变量维数D=30,每种算法运行30次,3种算法对6个测试函数的实验结果如表3～表8所示。比较6个表中的计算结果可知,在相同迭代次数及相同精度要求的前提下,新算法得到的平均最优适应度优于其他两种算法,并且标准差和CPU平均运行时间较小。由此可知新算法与SFLA、ISFLA1相比有较好的全局搜索能力和较高的收敛精度,有效避免了早熟现象。可见本文在SFLA中引入混沌初始化群体和动态变异操作是可行的。

3.4 高维函数的测试

为测试新算法对高维函数的求解能力,取函数变量维数D=100,3种算法对6个测试函数的迭代曲线如图1～图6所示。

Ackley是复杂的多峰函数,具有全局最小值0,在搜索后期新算法快速收敛,能较快地得到最优适应度值。Griewank是均匀的多峰函数,它考察算法的全局寻优能力,由于新算法中引入了动态变异操作,对群体适应度方差较小的解以较小的概率变异,而对群体适应度方差较大的解以较大的概率变异。从而避免陷于局部最优,对算法的早熟具有很好的抑制作用。对Schafferf7非均匀的多峰函数的实验说明,新算法具有更好的收敛速度,在摆脱局部极值,提高收敛精度等方面均有明显的优势。

从图1～图6可知,由于新算法采用混沌Tent序列初始化群体,因而得到较好的初始解(初始适应度值较小),而SFLA和ISFLA1初始群体随机分布,故初始解较差。由于新算法可根据群体适应度方差动态调整变异概率,故使算法能很快地获得最优解,从而使迭代次数较少,而ISFLA1无此操作,在最优解附近徘徊时间较长,使得迭代次数较多,运行时间较长,易陷入局部最优。

4 结 语

本文针对混合蛙跳算法易陷入局部最优、收敛速度慢的问题,提出改进的蛙跳算法。该算法就3方面进行了改进:(1) 用混沌Tent序列初始化青蛙群体,提高初始解的质量从而减少迭代时间;(2) 引入群体适应度方差反映群体中所有青蛙的“收敛”程度,并可以判断解的优劣;(3) 变异操作的概率应随群体的适应度方差的大小而改变,对较差解选取较大的变异概率,使得算法向全局最优解靠近。实验结果表明,无论是二维还是高维问题,新算法都得到了良好的效果。SFLA优化算法已取得了较多的研究成果,但在优化复杂问题时,各参数的设置仍比较薄弱,这也是今后研究的方向。

摘要：针对混合蛙跳算法SFLA(shuffled frog leaping algorithm)易陷入局部最优、收敛速度慢的问题,提出一种改进的混合蛙跳算法。该算法首先用混沌的Tent序列初始化青蛙群体以增强群体的多样性,提高初始解的质量;再根据每只青蛙的群体适应度方差值选取不同的变异概率,有效增强了SFLA跳出局部最优解的能力。通过对6个经典函数的仿真测试,结果表明,新算法比SFLA和ISFLA1的寻优能力更强,迭代次数更少,解的精度更高。

关键词：混合蛙跳算法,混沌优化法,动态变异,适应度方差,更新策略,全局最优

参考文献

[1]Eusuff M M,Lansey K E.Optimization of water distribution network de-sign using the shuffled frog leaping algorithm[J].Journal of water sources planning and management,2003,129(3):210-225.

[2]赵守法.蛙跳算法的研究与应用[D].华东师范大学软件学院,2008.

[3]骆剑平,陈泯融.混合蛙跳算法及其改进算法的运动轨迹及收敛性分析[J].信号处理,2010,26(9):1428-1433.

[4]赵鹏军.基于差分扰动的混合蛙跳算法[J].计算机应用,2010,30(10):2575-2577.

[5]欧阳,孙元姝.基于改进混合蛙跳算法的网格任务调度策略[J].计算机工程,2011,37(16):1-3.

[6]葛宇,王学平,梁静.自适应混沌变异蛙跳算法[J].计算机应用研究,2011,28(3):945-947.

[7]Babak Amiri,Mohammad Fathian,Ali Maroosi.Application of shuffled frog-leaping algorithm on clustering[J].Adv Manuf Technol,2009,45:199-209.

[8]单梁,强浩,李军,等.基于Tent映射的混沌优化算法[J].控制与决策,2005,20(2):179-182.

[9]Elbeltagi E,Hegazy T,Grierson D.Comparison among five evolutionary-based optimization algorithms[J].Advanced Engineering Informatics,2005,19(1):43-53.

混沌算法 篇9

关键词：图像加密,混沌,Baker映射

0 引 言

数字图像与纸面图像相比,在防攻击、防伪造方面的抵抗性是比较弱的,现在对数字图像较为通用的一种保护机制是通过传统密码学理论(如常用的3DES,IDEA,RC5等)的计算复杂度来实现。另一方面,混沌加密作为一种实现简单且安全性高的算法也应用于流密码或块密码加密中。

混沌理论是一种非线性的理论,它具有对初值敏感性、不可预测性、非线性、伪随机性等特征。

目前已有不少关于混沌图像的加密算法,这些算法都是利用混沌函数实现图像像素变换。其中Fridrich提出了一种混沌图像加密算法[1,2],它利用二维的Baker映射对像素位置进行交换。但这个算法存在着弱密钥缺陷[3],且用于加密的图像只能是正方图。

本文提出的算法是建立在Fridrich二维Baker映射混沌图像加密的基础上的[1,2],通过对图像置乱和像素值变换实现对图像的加密。实验证明该算法密钥空间大、安全性强,克服了原算法的弱密钥性,可以实现对任意大小图像的加密,具有良好的加密效果和加密效率。

1 二维离散Baker映射

本算法用到的是二维离散Baker映射,其步骤为(见图1):

(1) 将N×N正方形在水平方向上分为k个矩形块,每个矩形块有N×ni个像素;

(2) 每个矩形块再分成ni个子块,因为每个大矩形块有N×ni个像素,所以在分成ni个子块后,每个子块正好有N个像素。由于N不一定能整除ni,故分成的子块不一定会正好呈矩形;

(3) 在每个矩形块内,按从下到上,从左到右的顺序重新将像素排列成一行。

2 算法设计

常用的图像加密方法有两种:图像置乱和图像像素值变换。本文提出的算法是一种混沌空间域图像加密算法,先利用二维离散Baker映射对图像进行置乱,然后利用非线性反馈置换函数对图像像素进行变换,通过多次迭代运算实现图像加密。

本算法需要的系统参数为:

(1) 预加密过程中的参数kp(128bit);

(2) Baker映射中的参数kseg;

(3) 迭代次数kr。

kp用来产生预加密过程中的密码,消除弱密钥性,并影响kseg的值,kr决定了算法的安全等级,kr越大密码的安全性越强。

2.1 初始化图像

在本算法中,为了实现对任意大小图像的加密,需要对图像进行初始化,其操作如下:

I表示一个大小为m×n的图像,m、n分别代表图像的行、列,I(x,y)表示在位置(x,y)的灰度值(0<x≤m-1,0<y≤n-1),在加密前,对图像进行初始化,将填充像素加到原始图像中,使生成的新图像正好能被分割成整数个b×b大小的小正方图,分块和填充条件为:

如果m=n,图像正好能被分成a2块,此时m=ab;

如果m<n,图像能被分成a块,此时a=(n+填充像素)/m,b=m;

如果m>n,图像能被分成a块,此时a=(m+填充像素)/n,b=n。

2.2 预加密

将初始化后图像的每个像素都与kp的一部分子集作异或运算,当kp的每个子集都使用过后,在下一次加密前kp序列左移一位,原序列中第1位移到最后一位。

2.3 图像置乱(二维离散Baker映射过程)

根据kseg(kseg={s1,s2,…,si},s1+s2+…+si=b,b为分割成的小正方图边长)的值,把预加密生成的图像分割成多个小正方图分别进行二维离散Baker映射,完成后按照分割的顺序将各个置乱后的小正方图拼接得到置乱图像。

2.4 图像像素值变换

我们通过一个bit位非线性反馈操作来实现像素值变换。

f ′(xl+1,yk)=f(xl,yk)XOR f(xl+1,yk)

算法为:

2.5 迭代加密

根据kp的值重复步骤2.3、2.4,通过多次迭代运算提高加密强度。

2.6 解密算法实现

用户输入正确的密钥后,将加密算法逆向运算,可获得解密图像。

3 实验分析

我们选择大小为220×60的灰度图像(如图2所示)作为实验对象,利用MATLAB 6.5编程实现算法。选取密钥kp为随机产生的128bit数据,kseg={6,6,6,6,6,6,6,6,6,6}。

图3是经过初始化处理后的图像,图中最右边的黑块为填充像素,大小为20×60,填充像素的加入使图像正好能分成4个大小为60×60的小正方图,初始化后的图像大小为240×60,因此加密后的图像大小也为240×60。图4是kp=5时产生的加密图,从加密图及灰度直方图中可以看出,经过图像置乱和像素值变换,图像的原始信息完全被掩盖了,像素变得分散、混乱。图5是kp=20时产生的加密图,随着迭代值kr增大,加密效果更好,安全性更强。图6是正确解密图,可以看出,正确解密图像失真度小,能够完整恢复出原图像。

4 安全性测试

4.1 保密性测试

本算法具有多密钥,密钥空间大,且对初值相当敏感,图7是kseg中的一个元素错误时产生的错误解密图像,图8是kp错误时产生的错误解密图像,可知在解密过程中,如果不能取得完全准确的全部密钥,是无法恢复出原始图像信息的。

4.2 置乱度分析

我们使用文献[4]中定义的置乱度(SM)来评估加密图像的像素置乱程度,它的计算式为:

$S{\rm M}(X,\widehat{X})=\frac{{\displaystyle \sum _{i=1}^m{\displaystyle \sum _{j=1}^n(}}x{}_{ij}-\widehat{x}{}_{ij}){}^2}{{\displaystyle \sum _{i=1}^m{\displaystyle \sum _{j=1}^n(}}x{}_{ij}-r{}_{ij}){}^2}$

其中,$X=\left\{x{}_{ij}\right\}{}_{m\times n}$表示原始图像,$\widehat{X}=\left\{\widehat{x}{}_{ij}\right\}{}_{m\times n}$表示置乱后图像,$R=\left\{r{}_{ij}\right\}{}_{m\times n}$表示与原始图像大小相同的标准置乱图像。

在本算法中,我们将R定义为均匀噪声图像,均匀噪声具备良好的随机性和混乱性,可以作为衡量像素置乱度的标准。利用试验结果多次计算SM得到平均值为:$\overline{S{\rm M}}$=0.887。

可见,加密图像的像素置乱度与均匀噪声相近,具有良好的置乱性。

4.3 抗攻击测试

图9是加密图像经JPEG压缩为原大小20%后的解密图像,图10是加密图像受到10%强度的高斯噪声干扰后的解密图像。可以看出解密图像效果较好,具有较强的抗攻击能力。

5 结 论

本文在Fridrich二维Baker映射混沌图像加密的基础上提出了新的混沌图像加密算法,克服了原算法的弱密钥性,同时实现了对任意大小图像的加密。实验证明,该算法密钥空间大,安全性强,可以实现对任意大小图像的加密,具有良好的加密效果和加密效率。

参考文献

[1]Fridrich J.Symmetric Ciphers Based on Two-Dimensional Chaotic Maps,Int J.Bifurcation and Chaos,1998.

[2]Fridrich J.Image Encryption Based on Chaotic Maps.Proc.Ieee Conf on Systems,Man,and Cybernetics,1997.

[3]Salleh M,Ibrahim S,Isnin I F.Ciphering Key Of Chaos Image Enryp-tion.International Conference on Artificial Intelligent in Engineering and Technology,2002.