元胞遗传算法（精选7篇）
元胞遗传算法 篇1
摘要：元胞遗传算法是一种将元胞自动机与遗传算法相结合的进化算法,这种算法具有遗传算法的适用性、并行性和扩展性,但是在后期的二维元胞空间扩散速度过慢。提出了一种基于三维球形元胞空间的多目标元胞遗传算法,其基本思想是:取元胞空间为三维球,根据Pareto支配关系找出种群中的非支配解并保存到精英集,根据元胞自动机中拓扑结构和邻居等机制,使精英集中的Pareto非支配解在种群中扩散。指标分析和数值实验表明,新算法的解不仅多样性和均匀性较好,而且在后期具有较快的扩散速度。
关键词：多目标遗传算法,元胞自动机,三维元胞空间,均匀性
0 引言
20世纪80年代初,著名物理学家Wolfram开始研究元胞自动机,他先后研 究了一系 列一维和 二维元胞 自动机,并根据研究成果,提出了著名的Wolfram规则。在此基础上,Wolfram 2002年出版了专著《A New of Science》。1987年,Robertson提出世界 上第一个 元胞遗传 算法模型,该算法运行在CMI计算机上。此模型的所有遗传操作(父代个体的选择、替换、交叉和变异操作)都是并行执行。一年之后,Muhienbein等发表了 一篇利用 运行在大规模并行机器上的元胞遗传算法求解TSP问题的文章,该算法添加了一个局部搜索,改善了由交叉和变异算子产生的解。因此,该算法被 认为是第 一个混合 元胞遗传 算法。之后,又出现了一些元胞遗传算法。它们被称为Pollination plants、Parallel individual、Diffusion、Fine grained、Massively parallelm模型。
鉴于元胞遗传算法对于搜索空间能够带来全局搜索和局部寻优的良好平衡,具有优越的复杂问题解决能力,许多学者将其用于解 决实际工 程问题中,主要应用 领域有:神经网络训练、电子信息、机械设计制造、调度决策问题数学优化、交通控制、3D动画设计、图像处理、经济学、生物学等。
本文根据元胞遗传算法操作特点,对遗传算法的元胞空间进行分析,提出一种基于三维元胞空间的多目标元胞遗传算法,并对该算法进行性能分析和数值实验。
1 元胞遗传算法与元胞空间
1.1 元胞遗传算法
元胞遗传算法(Cellular Genetic Algorithms,CGA)是一种将遗传算法和元 胞自动机 原理相结 合的进化 算法。在元胞遗传算法中,元胞模型从初始个体出发对自然界的进化过程进行模拟,初始种群被分布在一个相互联通的平面或空间拓扑结构中,在这种相互联通的网状结构中,个体被安放在网格点上,每个个体只能与其邻近的个体进行信息交换,而且交叉操 作也被严 格限制在 邻近个体 间进行。这样,可以使得种群中的个体产生一定的隔离,类似于自然界中的小生境,从而保持种群的多样性。
CGA算法流程见图1。
1.2 元胞空间
在元胞自动机中,空间和时间都是离散的,物理量只取有限值集。元胞自动机由元胞、元胞空间、邻居和规则这4个基本部分组成。许多对元胞遗传算法的改进多集中于对元胞自动机各组成部分的改进,本文主要对元胞空间进行改进。
元胞所分布的空间网点的集合称为元胞空间,可以按照几何开关、边界条件对元胞空间进行分类。目前,元胞遗传算法多采用一维和二维元胞空间。对于一维元胞自动机,元胞空间的划分只有一种。而高维的元胞自动机,元胞空间的划分可有多种形式。在二维元胞自动机中,三角形、四边形和六边形元胞空间最为常见,见图2。
三维元胞空间可以是多种形状,考虑到网格点的均匀分布,本文采用三维球形元胞空间,见图3。
2 多目标元胞遗传算法
考虑到元胞遗传算法的优良特性,Alba于2007年提出了第一个元胞多目标遗传算法cMOGA。之后,Alba又对其进行了 改进,给出了改 进的cMOGA,即MOCell。Durillo将广义差分算法引入MOCell算法,提出了一种混合元胞多目标遗传算法CellDE,大大提升了MOCell解决三目标问题的效果,此算法在解决三目标问题时明显优于NSGAII和MOCell。Li等提出了一种自适应元胞多目标遗传算法,使得算法的 收敛速度 在一定程 度上得到 了提高。张屹等在CellDE中添加了一个变异算子,提出了新的差分进化多目标元胞算法DECell,有效地保持了种群多样性,增大了解集的覆盖范围。
2.1 多目标遗传算法
多目标优化问题的数学模型为
其中,x是决策向量,F(x)是目标函数,gi(x)≥0是约束条件。
定义1:若xA,xB是两个可行解,且
则称xA支配xB或xA比xBPareto占优,记为xA>xB。
定义2:若可行解x*满足
则x*称为Pareto最优解或Pareto非支配解。
定义3:Pareto非支配解的集合称为Pareto非支配解集或Pareto最优解集,记为P*。
定义4:Pareto最优解集P*中的所有Pareto最优解集对应的目标函数向量构成的曲线或曲面称为Pareto最优前沿,记为
双目标优化问题 的Pareto最优前沿 通常是平 面曲线,而三目标优化问题的Pareto最优前沿往 往是空间 曲面。
2.2 最优解集评价标准
对多目标优化算法性能的评价包括算法的运行效率和最优解集的质量。算法的运行效率主要指算法的复杂性,可以用算法占用的CPU时间表示,最优解集的质量包括算法的全局、局部收敛性和最优解集的均匀性、分布性。目前,评价多目标优化算法性能主要依靠典型测试问题的数值实验和量化评价指标值,本文采用的量化评价指标值如下:
(1)代间距离(Generation Distance,GD):
其中,n为最优前 沿PFknown中向量的 数目,di为PFknown中每个向 量到最优 前沿PFtrue中最近向 量的距离[9]。GD描述了PFknown对PFtrue的逼近程度。
(2)错误率(Error Ration,ER):
其中,n为PFknown中的向量个数,且PFknown= {X1,X2,…,Xn},ei定义如下:
ER描述了最优解集的分布性[10],即PFknown对PFtrue的覆盖程度。
(3)分布性(Spaing,SP):
其中,n和di与(1)中相同。实际上,SP就是di的标准差。根据标准差的意义,SP描述的是最优解集的均匀性。
2.3 多目标三维元胞空间遗传算法
在CGA中,遗传算法将初始种群均匀地分布在元胞空间拓扑结构中。在这种元胞空间的网状结构中,每个个体被置于网格点上,每个个体 只能与其 邻近个体 交叉操作。元胞遗传算法最主要的优点在于,在对解空间进行搜索时,能保持全局搜索和局部寻优平衡。但是在这种平衡下,后期的最优解在种群中扩散的速度比较缓慢,效率不高,这时候算法的繁殖周期较大,即最优个体占据元胞空间所需要的周期比较长。
为了改善后期效率,可以对元胞空间进行改进,将初始种群中的个体安置于三维元胞空间中。类似于二维元胞空间,将初始种群均匀分布在球体的表面网格中,这种网状结构的边界是同心球球面,一个个体的邻居是根据它在种群网格中与其它个体之间的距离(二个同心球的半径距离)来定义的。对于二维元胞空间遗传算法,个体与自己的邻居进行进化产生的新个体,繁殖的周期一致,但是当繁殖周期到一定程度时,原先的元胞遗传算法会出现种群中最优个体扩散到窄边界的情况,这时候最优个体扩散速度明显下降。但是在三维元胞空间中,种群分布在球的表面,不会出现上述情况,这时最优个体所占比例增长速度不会出现变慢的现象。
算法流程如下:1将初始种 群分布在 三维元胞 空间中;2在相邻的元胞中选择一个个体作为父代;3将选择出来的邻居元胞与中心元胞进行交叉,变异操作;4根据Pareto支配关系找出种群中的非支配解并保存到精英集中,产生新的个体;5如果产生的新个体优于中心元胞,则将中心元胞替换,否则,不替换;6如果代数小于最大进化代数,则返回到步骤2;7将当前最优解输出。
3 数值实验
为了检验算法性能,下面对两个多目标进化算法标准测试函数DTLZ1和DTLZ2进行数值计算,并将优化结果与普通多目标元胞遗传算法的优化结果进行比较。
数值实验参数是:群体规模为200,进化代数为200,交叉概率为0.85,变异概率为0.1。
(1)DTLZ1测试函数:
其中,
由于搜索空间包含11k-1个PFlocal,往往会使多目标进化算法收敛到局部最优解,而难以收 敛到Pareto全局最优边界。M =3时的PFlocal如图4所示。
(2)DTLZ2测试函数:
M =3时的PFlocal是第一卦限内的单位球面,如图5所示。
图6-图9分别是常 规多目标CGA和三维多 目标CGA求出的DTLZ1和DTLZ2的Pareto最优前端。从图中可以很清楚地看出,三维多目标CGA在算法的收敛性和解的分布性、均匀性方面均明显优于常规多目标CGA。
表1给出了常规多目标CGA和三维多目标CGA的GD、ER、SP的对比数据,以进一步定量评测三维多目标CGA的性能。由于解具有随机性,表中给出的是20次计算结果的平均值。
从表1和表2可以看出,基于三维元胞空间的多目标元胞遗传算法的GD指标明显优于常规CGA算法,表明引入三维元胞空间的确明显改善了CGA的全局收敛性。三维CGA的ER和SP指标较常规CGA算法也显 著占优,表明三维CGA解的分布性和均匀性也有明显提高。
由此得出明确结论:基于三维元胞空间的多目标元胞遗传算法与二维多目标遗传算法相比,在解的分布性、均匀性和收敛性方面有明显改善。
4 结语
针对二维元胞遗传算法后期解的扩散速度较慢这个缺陷,将三维球形元胞空间引入多目标元胞遗传算法。指标分析与数值实验结果表明:三维多目标元胞遗产算法在后期的扩散速度较快,解的分布性、均匀性、收敛性均明显优于二维多目标元胞遗传算法。
目前,遗传算法、多目标进化算法、元胞遗传算法的理论基础还很薄弱,性能研究只能依赖于对测试问题的对比实验。元胞遗传算法的收敛性及解的性能等有待进一步研究。
元胞遗传算法 篇2
井间地震速度反演的遗传算法
井间地震速度反演具有重要的意义,不仅对于准确圈定地下构造的传统地震勘探是重要的,而且速度的`变化可以指示非背斜型的地层岩性圈闭.传统的射线追踪方法一般是先给出入射角,然后根据折射定律修改入射角以达到反演的目的.该方法对每条射线均需通过扫描确定入射角,计算量较大,对初始地质模型的要求较高.遗传算法具有全局收敛性,是一种不用梯度信息的优化方法,特别适用于大型的组合优化问题.采用多项式展开表示界面深度和速度,通过弯曲射线追踪算法来计算射线的旅行时间,利用遗传算法进行迭代优化,可以同时反演出地下复杂构造的界面形态和速度变化.该方法与网格化速度反演相比,减少了未知参数,较好地克服了多解性问题,试验结果表明,该方法可以达到较高的反演精度.
作 者：乐友喜 安鹏 王俊 YUE You-xi AN Peng WANG Jun 作者单位：中国石油大学,地球资源与信息学院,山东,东营,257061刊 名：物探化探计算技术 ISTIC英文刊名：COMPUTING TECHNIQUES FOR GEOPHYSICAL AND GEOCHEMICAL EXPLORATION年，卷(期)：30(2)分类号：P631.8+15关键词：速度反演 遗传算法 井间地震 射线追踪 多项式
元胞遗传算法的多样性研究 篇3
关键词：全局寻优/局部收敛平衡,邻域结构,多样性度量方式,种群多样性
在进化算法[1]研究中，全局寻优/局部收敛平衡是一个重要因素，全局寻优与种群个体的分布有较大关系。进化算法的主要问题就是存在过早收敛[2]。过早收敛的起因就是全局寻优/局部收敛平衡问(Exploration/Exploitation Balance,EEB)[3]。生物学的多样性往往与种群个体的外在特征有关，即表现型多样性，遗传算法则更多从基因型多样性来讨论多样性特征。
关于元胞遗传算法种群多样性的研究中，Alba[4]等人运用算术交叉，均匀变异并提出了一种新方法，处理具有元胞遗传算法的连续搜索空间来解决实际编码问题，并在此基础上采用非均匀变异的方法在初始空间进行均匀搜索，采用适应度高的个体代替当前个体的精英替代策略。申元霞[5]等人提出一种新型保持群体多样性的遗传算法，并从种群的熵和个体基因座的多样性来进化种群的多样性。李军华[6]等人提出一种对遗传算法多样性的检测方法，通过计算连接种群个体的连接矩阵的熵来反映种群的多样性。鲁宇明[7]等人提出了一种具有演化规则的元胞遗传算法，并采取算法元胞演化选取规则，比较了元胞遗传算法和遗传算法对多样性的维持能力。因此，元胞遗传算法可以降低高适应度个体的基因传播速度，在一定程度上保持种群多样性，改善遗传性能具有较大的优势。
1 元胞遗传算法多样性分析
1.1 元胞遗传算法原理
元胞遗传算法种群多样性的研究正是基于元胞自动机多变的演化规则，元胞空间能在复杂规则下情况下寻找函数进化过程的寻优[8]和收敛。其基本操作如图1所示。不同于标准的遗传算法，元胞遗传算法中群体的个体分布在两维网格中，每个个体分别占据网格中的一个节点，如图2所示。
1.2 多样性分析
元胞遗传算法以元胞自动机的主要理论为基础，交叉变异在邻域之间进行的一种遗传算法。该算法核心思想是，选择和交叉都只在一个邻域内完成，然后保留子代和父代中较优秀个体，这样就有效防止了过早收敛的发生。同时，由于邻域的重叠，保证基因不能越过邻域传递，仅可在网格之间相互传递，最优个体扩散速度减慢，这样大幅维持了种群的多样性。
2 多样性度量方式
尽管目前还没有统一的概念来定义种群多样性[9]，但影响多样性主要由种群个体之间的距离[10]和种群基因频率两种因素。本文提出了遗传多样性度量方式[11](Genotypic Diversity Measures,GDM)，是一种专门衡量进化过程中种群的多样性值，其能较好地控制EEB平衡。为了更好的测量GDM值，在此处提出GDM的规范化，当然一个好的GDM要能准确测量迭代过程中种群多样性值，为整个种群进化提供依据。
GDM值与种群个体之间的距离是相关的，同时也跟个体基因位出现的频率有较大关联。GDM值在评价种群多样性具有重要的参考性，表1是GDM规范条件下参数的设计。
式(1)所示
其中，DNRP代表种群的半径，代表种群中最远个体与种群中心位置的距离，目的是测量中心位置，半径范围内所有个体所占的比例，比例越高，多样性就越丰富。式(2)所示
其中，DDTNPN[12]代表种群的平均距离，其能较好地反映种群半径，通常情况下，DNDTNP越大种群多样性就越大。但DNDTNP只能表示种群的个体总体偏离程度，必然导致存在一定的偏差
其中，GF测量方式[13]与香农熵有较大的相似性，GFNHC(α)[14]能最大的真实定义GDM值，且当M≤N,pm,k=1/M或pm,k=1/N时，基因频率是相似的，GDM取得最大值。对于所有基于GF的测量结果，GDM值的最优值与M,N有较大关系。GF测量方式因采用基因编码，更能够从内部反映个体的内在多样性，较前两者而言，能最大接近多样性的真实值，改进空间较大。
3 基于提高变异算子概率的算法
3.1 算法的定义
简单的元胞遗传算法CGA能反映元胞空间最初的个体生死状态，在进化过程中，选择和交叉算子通常正比于种群多样性，但选择与交叉算子并不能完全反映种群的多样性发展。因此，在元胞遗传算法的基础上提出了加强变异概率的模拟机制，其本质就是在二进制编码方式的基础上提升概率来促进个体适应度。为达到效果，本文提出了一种新的遗传算法(Diversity Maintaining Cellular Genetic Algorithm,DMCGA)，该算法的精髓就是在选择，交叉操作后，种群会造成一部分优秀个体的损失，采取对个体进行基因变异，提高竞争压力，促进多样性的保持。
变异算子通过基因座的二进制编码进行判定，优秀个体继续保留，不适应个体则进行变异，这样就随机产生一些新个体，算法在一定周期内对全局进行变异，从而保持多样性。
3.2 DMCGA算法原理
推导:设xi,j为元胞空间种群个体，且xi,j采用基因座的二进制编码表示。初始下基因座是平衡的，也就是基因座“1”和“0”恰好各占1/2，用P(xij)=M/R公式来表示，其中M和R，分别代表种群个体xi,j“1”和“0”的总个数。在选择交叉操作后会有大量优秀个体的缺失，优秀个体的基因型特征用Φ表示，其Φ0和Φ1分别对应其两边临界点，即Φ0≤P(xij)≤Φ1，在这里取Φ0=2/3，Φ1=1。当P(xij)超出这个范围就进行变异操作，在这里用T表示，当MR时，则有“M-R”个数目进行变异;反之当RM时，则有“R-M”进行变异。
4 算法性能测试及结果分析
在测试中，选用6个测试函数对带演化规则的元胞遗传算法灾变机制下的元胞遗传算法(Celluar Genetic Algotithm With Disaster,CGAD)和本文算法DMCGA两种算法进行测试。在优化算法的全局收敛性，群体多样性以及稳定性进行分析和比较，并采用式(3)来测试新算法对GDM值保持的效果。
4.1 测试函数
F1:Shubert函数
该函数有760个局部最小值，其中18个是全局最小，其值为-186.73。
F2:Camel函数
该函数有6个局部极小值点，其中(-0.089 8,0.712 6)和(0.089 8,-0.712 6)为两个全局最小点，最小值为-1.031 628。
F3:Schaffer函数
该函数全局最优解为0，分布在(0,0)。
F4:Griewangk函数
该函数有无穷多个局部极小值点，xi=±kπ槡i,(i=1,2，…，n;k=1,2，…，n)为函数局部极小值位置，在xi=0时，函数取得全局最小值。
F5:Ackley函数
该函数为一多峰函数，具有大量局部最优点，全局最小值在xi=0处取得，最小值为0。
F6:Shifted Rosenbrock函数
该函数每个变量之间都具有关联性，在xi=1时，函数取得全局最小值0。
4.2 参数设置及结果分析
测试中，将种群规模p设置为400，高维测试时，将2维设置进化最大代数为10代，在10维以上时设置为3 000代。函数优化均独立运行50次，交叉率为0.8，变异率为0.15。
统计结果如表2所示，其中，OP代表平均寻优值，CV代表平均收敛代数，GL全局收敛率，“—”表示不符合收敛条件。图3和图4是对Shubert函数和Camel函数在2维测试下的GDM值对比图。图3中DMCGA算法GDM值下降速率明显低于CGAD算法，CGAD算法在进化代数到达50代后GDM值基本就降到最低点。而从图4Camel函数的测试结果来看，虽然最初DMCGA算法对种群多样性损失较大，但迭代次数到70代左右时，发生逆转。长期进化来看，DMCGA算法对多样性的维持好于CGAD算法。
为更好地验证本文算法对高维函数的寻优能力，将本文算法对F4～F6这3个高维函数进行测试，其结果如图5～图7所示。从3个测试函数的结果来看，DMCGA算法对高维测试有较高的稳定性和收敛能力。
5 结束语
元胞遗传算法 篇4
关键词：主动队列管理,CHOKe,击中,平均队列长度,元胞遗传
随着Internet的迅速发展,网络拥塞现象日益明显,如何有效地避免拥塞的发生并保障网络的公平性已成为研究的重点。目前,常用的技术是进行主动队列管理[1,2];而随机早期检测(Random Early Detection,RED)算法[3,4,5]是最早出现的主动队列管理方法,其基本思想是通过平均队长来控制网络拥塞,使源端在队列溢出前减小拥塞窗口,降低发送速度。但是RED算法存在参数设置敏感和缺乏公平性的不足。
CHOKe[6,7]作为RED改进的算法,它提供了无状态的近似公平队列管理机制,能够有效地提高带宽分配的公平性。当有分组到达时,它随机从队列中抽取某个分组与到达分组进行匹配,若两者都属于同一种流就同时丢弃这两个分组,否则按照RED算法进行队列管理。但是CHOKe算法对于非适应流(即UDP流)的惩罚力度不够,当网络中有较多流时其命中效果不佳。因此,国内外学者对此提出了大量改进算法,最有代表性的是M-CHOKe、A-CHOKe ECHOKe和LA-CHOKe算法[8,9]。M-CHOKe改进了CHOKe一次比较来决定丢包的方式,它随机取n(n>1)个分组与刚到达的分组进行匹配,一旦匹配上就丢弃击中的分组,其它分组返回队列,否则还是按照RED进行处理。但是由于每次只丢弃一个分组,所以对于非适应流的惩罚力度还需加大,并且参数n难以确定。而A-CHOKe改进了M-CHOKe中参数n难以确定的问题,将RED算法的最大和最小门限值划分为多个区间,队列长度越大越长抽取的分组越多,但是缺乏准确识别非适应流的缺点。ECHOKe针对M-CHOKe惩罚力度不够的问题,如果匹配上就将取出的n个分组全部丢弃,否则按照RED方式处理,丢弃流数量最多的一个分组。但是源端发现丢包,就会降低发送速率,从而造成惩罚精度不高。LA-CHOKe则通过当前队列长度和链路负载来判断拥塞情况,它没有依赖状态信息来提高算法的公平性,但还需要加大对非适应流的惩罚力度。
针对上述问题,提出了一种新的主动队列管理方法。该方法通过改进丢包概率和丢包策略以提高队列管理效率,同时利用元胞遗传方法[10,11,12,13]刻画了平均队列长度。
1S-CHOKe算法
在文献[7]中提出过一种增强CHOKe公平性的算法S-CHOKe,其主要思想是利用采样击中取代CHOKe击中,以此提高击中概率,并基于自适应方式确定丢包数,加大对UDP流的惩罚力度,同时以较小开销的队列击中提高了击中有效性。S-CHOKe算法描述如下:
Step 1在某时刻t对到达分组进行采样,将该分组的流标识加入列表,并计算当前队列长度qavg;
Step 2如果列表未满时,直接接受到达分组,重新执行Step 1;
Step 3如果平均队列长度qavg大于上限阈值qmax,则直接丢弃到达分组,跳转到Step 1;
Step 4如果平均队列长度qavg小于下限阈值qmin,则让到达分组直接进入队列,跳转到Step 6;
Step 5如果qmin≤qavg≤qmax,比较到达分组与列表中随机抽取的一个流标识,并执行采样击中,如果没有击中则以RED方法进行丢包处理,否则跳转到Step 6;
Step 6对当前队列执行自适应丢包,为了适度惩罚非适应流,随机从队列中抽取N个分组与采样击中分组比较,执行队列击中,若被击中则删除击中分组,否则将分组放回队列;
Step 7令t=t+1,跳转到Step 1,重新开始下一次采样和击中操作,直至算法结束。
但是,S-CHOKe算法在记录非适应流击中次数的同时也记录了适应流的击中次数,可能导致对适应流的惩罚。同时,当网络中存在多条非适应流时,仅仅依靠S-CHOKe算法的队列击中不能有效地惩罚非适应流。因此,提出在队列击中之前增加一个筛选器,如果到达分组被击中的次数超过设定阈值,则按照一定概率丢弃当前分组,否则进行队列击中操作。采用这种方法的原因在于,如果某条流被采样击中的次数越多,说明该流是高速流的可能性就越大。
2New-SCHOKe算法
2.1算法流程
结合上一节提出的改进思想,筛选器的判断依据是到达分组被击中的次数是否超过设定阈值,假设阈值为M。同时,这里首先给出筛选器中的丢包概率p:
同时在图1中给出了改进算法New-SCHOKe的流程图,并且在算法New-SCHOKe中采用如下措施来加强对公平性的控制。
(1)New-SCHOKe并非对所有记录的流进行丢包操作,在筛选器的控制下只针对击中次数超过设定阈值的分组数据流做丢弃处理。按照普遍研究的结论,非适应流的击中次数远远高于适应流,可以有效避免对适应流进行错误惩罚;
(2)New-SCHOKe每经过一段固定时间判断当前平均队列长度是否小于下限阈值qmin的三分之一,如果是则清除表中记录,否则继续保持记录信息,这样可以降低对适应流的惩罚;
(3)由于实际流量具有分形特性,所以这里基于大数据流的分组技术进行采样,可以避免大数据流中的非响应流占据了大部分比例。算法假设分组中每个比特被采样的概率为p1,则长度为d比特的分组被采样的概率为p2:
p2=1-(1-p1)d (2)
(4)如果在执行队列击中过程时某分组未被击中,说明该分组属于非适应流的可能性较大,则按照如下丢包概率p3进行丢弃处理:
式(3)中,y为该分组被击中次数,Y为设定阈值。
2.2平均队列长度计算
对于上述提出的New-SCHOKe算法,关键在于如何能够有效地获得下一时刻的平均队列长度,以便进行预处理,减少拥塞发生的可能性。现利用元胞遗传算法来刻画平均队列长度。元胞遗传算法的主要思想是不断重复微观的简单演化规则,并且反复进行局部交互作用能够成为全局计算的目的。它利用元胞演化规则替代遗传基因组之间的选择和交叉机制。
首先在图2中定义了元胞体结构,中心元胞受到相临四元胞状态的影响,下一时刻中心元胞状态取为想临四元胞中状态最优者,并且循环执行上述操作实现对元胞的选择。同时,这里定义元胞状态为适应度函数对应的值,适应度函数f表示为:
式(4)中,q为当前队列长度。f值越大,该元胞被选中的可能性就越高。将选中的元胞体作为父体,并根据定义的元胞演化规则以概率ε进行交叉操作,获得下一时刻元胞状态。同时,为了避免陷入局部最优,这里以小概率λ对交叉产生的新个体进行变异:
式(5)中,ψ为变异概率阈值,f’为变异之后的新状态,fa和fb分别为最大和最小适应度函数值,μ为(0, 1)之间的随机常数。
同时,针对遗传过程中所采用的交叉和变异操作,本文结合分组到达速率v和当前队列长度q进行定义:
(1)在某时刻t,如果到达分组的队列长度q大于上限阈值qmax,说明当前拥塞比较严重,则令v(t+1)= v(t)-k,进行拥塞控制操作;
(2)如果到达分组k的队列长度q满足qmin≤qavg≤qmax,说明当前进入轻度拥塞状态,进一步判断到达速率v与当前拥塞窗口w之间关系:
(1)如果v(t)≥w,则令v(t+1)= v(t)-w/3;
(2)如果v(t)<w,则令v(t+1)= v(t)-1;
(3)如果到达分组的队列长度q满足qmin≤qavg≤qmax,说明当前网络未出现明显拥塞现象,则令v(t+1)= v(t)+1;
(4)分组在t+1时刻的到达速率更新为:
式(6)中,τ为时延。
3性能分析
为了验证上述方法的有效性,这里结合NS2和MATLAB进行仿真实验。首先,在NS2中建立如图3所示的仿真结构图,R1和R2为路由器,an为发送端节点,bn为an对应的接受端节点(仿真过程中n取为50),R1和R2之间的链路带宽设置为2 M,时延为5 ms,各节点和路由器之间的链路带宽设置为15 M,时延为2 ms,分组大小为500 b,队列下限阈值qmin和上限阈值qmax分别为300和500。
这里进行了如下两个实验,实验1设定an到bn的数据流中,有40条TCP流(对应a1, a2, …, a40)和10条UDP流(对应a41, a42, …, a50)。在图4中给出了New-SCHOKe算法、SCHOKe算法和CHOKe算法的TCP吞吐量的情况。从图4可以看出,New-SCHOKe算法的TCP吞吐量最大,说明处理到达报文的能力最强。并且在图5中给出了非适应流击中概率与UDP流发送速率之间的关系。随着UDP流发送速率的增加,非适应流击中概率也随之增加。但是当处于小UDP流发送速率时,New-SCHOKe算法对应的非适应流击中概率最小,CHOKe算法对应的非适应流击中概率最大。而当处于大UDP流发送速率时,情况正好相反。这是因为New-SCHOKe算法和SCHOKe算法均增加了采样方式进行击中,在实验开始阶段分组较少,导致采样击中的效果不佳。
在实验2中,设定a1, a2, …, a30对应的传输链路为30条TCP流,a31, a32, …, a50对应的传输链路为20条UDP流。同样在图6中给出了New-SCHOKe算法、SCHOKe算法和CHOKe算法的TCP吞吐量的情况。从图中可以看出,New-SCHOKe算法仍然表现出较好的性能。同时,图7给出了实验2环境下非适应流击中概率与UDP流发送速率之间的关系。类似于图5中的情况,小UDP流发送速率下,New-SCHOKe算法对应的非适应流击中概率最小,而大UDP流发送速率下,New-SCHOKe算法对应的非适应流击中概率最大。
进一步地,在表1中给出了这三种算法在不同UDP流发送速率下TCP流所占带宽比例。从表1可以看出,在UDP流发送速率增加的过程中,New-SCHOKe算法能够更加保证TCP流所占带宽比例,同时也加大了对非适应流的惩罚力度。
从以上仿真过程可以看出,提出的New-SCHOKe算法在性能上较SCHOKe算法和CHOKe算法有了一定程度的提高,并且能够保证击中的有效性。
4结束语
针对CHOKe算法存在的问题,提出了一种新的主动队列管理算法New-SCHOKe。该算法通过定义采样击中和分组击中方法,并结合筛选器给出了具体丢包概率和丢包策略。同时,以实际数据进行仿真实验,对比分析了该算法与CHOKe算法、CHOKe算法之间的性能,结果表明CHOKe算法具有较好的适应性。在今后的研究中,可以考虑结合其它主动队列管理等方法(如BLUE、SRED、PI、PID等)来建立一套完整的拥塞控制方法,以此解决网络拥塞现象。
元胞遗传算法 篇5
生产调度是制造业生产的主要工作, 对其进行优化设计能提高设备利用率、缩短交货时间、降低库存及成本, 从而确保企业的经济目标。遗传算法以其通用性强、计算性能优良, 具有隐含并行性和全局搜索能力等特点而在FJSP中得到了广泛应用。多目标元胞遗传算法 (MOCell) 是一种将元胞自动机模型和多目标优化理论引入遗传算法而发展起来的进化算法, 本文对其交叉变异算子做出相应的调整, 使算法具有更高的求解精度和更快的收敛速度。将改进的算法与经典的FJSP求解算法进行实验仿真, 并对结果进行比较分析。
1 柔性作业车间调度问题描述
柔性作业车间调度问题一般描述为:n个工件{J1, J2, …, Jn}在m台机器{M1, M2, …, Mm}上进行加工。在FJSP中通常希望多个目标同时达到最优, 本文综合考虑3个性能指标:最大完工时间Cmax最小、最大负荷机器的负荷Wmax最小及所有机器的总负荷WT最小。
2 柔性作业车间调度的元胞遗传算法
2.1 元胞遗传算法框架
同一般遗传算法不同的是, 元胞遗传算法将种群中的每个个体分布在一个环形联通的网状空间拓扑结构中, 每个个体具有相同的邻居结构, 并且每个个体只能与其邻近个体进行遗传操作。元胞遗传算法中个体的进化循环过程, 相对于个体间随机遗传操作的一般遗传算法而言, 元胞遗传算法能够使不同范围的个体快速收敛到搜索空间的不同区域, 形成多个小生境, 每个小生境的最优解又能够在整个种群中缓慢扩散, 保持种群多样性, 从而使算法在具有较快收敛速度的同时, 又具有较好的空间探索能力。
2.2 编码和解码
传统的JSP中大都采用基于工序的编码, 本文对FJSP所采用的编码方式由两部分组成:第一部分为基于工序的编码, 用来确定工序的加工顺序;第二部分为基于机器的编码, 用来为每道工序选择合适的机器。如图1所示为FJSP的染色体编码示意图。第一部分基因串采用基于工序的编码, 每个基因上的自然数i表示对应的工件i, 自然数i第j次出现表示工件i的第j道工序Qij;第二部分基因串采用基于机器分配的编码, 基因串上的数字表示对应工序的加工机器号。对于每个基因从左到右依次扫描便可得到一个合理的工序调度安排。以图1所示编码[1, 2, 2, 1, 2, 1][2, 2, 1, 2, 1, 3]为例, 得到该工序调度安排为:O11, O21, O22, O12, O23, O13, 所用的机器依次为:M2, M2, M1, M2, M1, M3。
2.3 交叉
鉴于本文采用的染色体编码方式由相互联系的两部分组成, 一般算子应用困难, 将第一部分基因串采用张超勇等[1]提出的POX交叉算子进行交叉操作, 对第二部分基因串, 直接生成多个交叉点, 然后将交叉点处的基因进行互换即可。
3 实例求解与分析
为了验证多目标元胞遗传算法求解FJSP的有效性, 采用与KACEM等[2]、张超勇等[3]、XIA等[4]相同的标准测试数据集进行算法性能测试。KACEM等利用时间表的局部初始化方法来进行种群的初始化;张超勇等的方法主要是采用全局搜索、局部搜索和随机初始化相结合的方法来产生初始种群;XIA等采用粒子群算法结合模拟退火的混合算法来求解FJSP。数据集1是一个8个工件8台机器共27道工序的部分柔性调度问题, 数据集2是一个10个工件10台机器共30道工序的完全柔性调度问题, 数据集3是一个15个工件10台机器共56道工序的完全柔性调度问题。这3个测试集的原始数据见文献[2]。
从表1可以看出, 针对3个典型的测试实例, 元胞遗传算法所获得的Pareto解要么支配其他3种算法得到的解, 要么与其他算法所得解互不支配。值得指出的是, 由于遗传算法的寻优具有概率性, 经过不同的测试仿真, 本文算法也得到了其他几种算法得到的Pareto解。图2显示了本文算法在8×8部分柔性实例上得到的最大完工时间为15的甘特图, 和KACEM的结果相比在几个目标上都取得了更好的解。
采用Java进行编程, 多目标元胞遗传算法的参数为:种群大小为100, 采用Moore型邻居结构, 交叉概率为0.8, 变异概率为0.1, 终止代数为100代, 针对每个实例分别独立运行10次, 找出其中的Pareto解。
4 结论
针对柔性作业车间调度的多目标优化问题, 提出了一种改进的多目标元胞遗传算法。根据FJSP的特点, 结合基于工序分配编码和基于机器分配编码两种编码方式形成染色体。针对每一部分编码, 采用不同的交叉变异算子。通过对典型实例求解表明, 与其它算法相比, 本文得到的Pareto解具有更高的精度和更好的覆盖范围, 表明该算法在求解FJSP时具有较好的性能。
摘要：针对柔性作业车间调度问题的特点, 采用基于工序和基于机器分配的两部分编码方式, 在交叉变异时对两部分基因串分别进行操作。与其它优化算法的结果进行对比分析, 利用该算法求解经典柔性作业车间调度问题具有有效性。
关键词：柔性作业车间调度,元胞自动机,非支配排序,精英策略
参考文献
[1]张超勇, 饶运清, 李培根, 等.柔性作业车间调度问题的两级遗传算法[J].机械工程学报, 2007, 43 (4) :119-124.
[2]KACEM I, HAMMADI S, BORNE P.Approach by lo-calization and multi-objective evolutionary optimization for flexible jobshop scheduling problems[J].IEEE Transactions on Systems, Man and Cybernetics (Part C) , 2002, 32 (1) :408-419.
[3]刘琼, 张超勇, 饶运清, 等.改进遗传算法求解柔性作业车间调度问题[J].工业工程与管理, 2009, 14 (2) :59-65.
元胞遗传算法 篇6
LDPC (Low-density Parity-check,低密度奇偶校验 )码是由Gallager在1963年提出的一类具有稀疏校验矩阵的线性分组码 (Linear Block Codes),然而在接下来的30年来由于计算能力的不足 ,它一直被人们忽视。1993年,D Mac Kay、M Neal等人对它重新进行了研究, 发现LDPC码具有逼近香农限的优异性能 ,并且具有译码复杂度低、可并行译码以及译码错误的可检测性等特点,从而成为了信道编码理论新的研究热点。
好的图码模型具有实际上可以实现的复杂度的近优译码算法。性能好的LDPC码的Tanner图中没有太多的回路 , 只是具有 较长的最 短回路并 不一定是 好的LDPC码。码的正则性也是影响LDPC码的一个重要因素,不规则的LDPC码一般相比规则的LDPC有较好的性能。
因LDPC码的译码采用迭代译码,其原理是节点间传递的信息统计独立, 当LDPC码的校验矩阵对应的Tanner图有回路存在时,某一节点发出的信息经过回路后会被传回本身,从而造成自身信息的重复,影响算法的收敛性,也影响译码的准确性。
2 图论基础知识
无向图G(V,E),其中有限非空子集V是顶点集,有限非空子集E是边集, 且E是有成对的子集{{u,v}:u,v∈V,u≠v}
图G(V,E)中一条长度为n的路径就是一个节点序列v1,v2, … ,vn,vn+1,vi∈V,i=1,2,…,n,n+1并且对于i∈[1,n]都有{vi,vi+1}∈E,如果vi+1和vi相同,并且对于任意的i≠j∈[1,n],有vi≠vj,则是一条长n的回路。如果图G没有回路,则G为树。
若G (V, E ) 为无向图,则下面叙述等价:
(1) G是树;
(2) G中任意两个节点由唯一的一条路径相连接 ;
(3) G是连通的,但去除任意一条边后不再连通;
(4) G连通,且| E | = | V | -1;
(5) G中无回路且| E | = | V | -1;
(6) G中无回路,但是任增加一条边,则会出现回路。
若G (V, E )是一个无向图,如果顶点集V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集 (i∈A,j∈B),则称图G为一个二分图。
因此对于Tanner图中回路的求解,实质上是二分图中的回路的求解问题。树是连通的没有任何回路的二分图,叶节点是度为1的节点,树中的内部节点是一个度最少是2的节点。
3 截断节点树原理
利用树求解Tanner图中的回路, 其原理是这样的,比如对于校验矩阵H为:
(1)选定一个码字节点或校验节点为根节点 ,比如校验节点C1。
(2)从这个根节点C1出发,选取和其连接的节点并用边相连接,如上图为x1,x3,x5,x7。
(3)再从这些节点出发,选取和它们连接的节点。
(4)如果节点不能再生长出新的节点或者在以前的树枝中出现过,则终止生长。我们统称之为端节点,并把不再生长的节点称为叶,而把前面树生长的过程中已经出现强行截断的节点为截断节点,也就是说端节点包括叶和截断节点。
(5)对于既不是叶也不是截断节点的节点,继续(3)。如果最终所有的端节点都是叶或截断节点,则停止生长。
把按上述方法得到的LDPC码的树称为码树。
我们把最先选择的节点称为根节点,从根节点长出的树枝的端点称为1级节点, 也称为根节点的子节点,而1级节点也称为2级节点的父节点,依次类推,直到端节点,如果两个节点是由同一个节点所生成,那么我们称此节点为干节点,并且按照标号由小到大的顺序定义节点的级别。由级别高到低的顺序,选择节点,凡在树中出现至少两次的节点即为Tanner图中的一个回路,这时因为在上面的树生成的过程中,节点的第二次或更多次出现必然是截断节点,这样按照上述办法可以得到上例中的回路。
如果按节点级别排列这些环, 并除去相同的环,那么就可以得到LDPC码Tanner图中的所有回路。由于上面的树图中,包含了所有的节点,称这样的图为连通图或单树,否则称为森林。
由上作树图方法可以看出公理或结论。
(1)除根节点外,一个节点有且只有一个父节点。
(2)叶是度数为1的节点 ,端节点全为叶而无截断节点的树没有回路。
(3)在树图中 ,除截断节点外 ,每个节点连接的边数即为节点的度。
(4)按上面方法 ,得到的一定是森林(多树),不一定是单树(即连通图)。
(5)对于多树的情况 ,如果在两个树上任意选择两个节点(不同类型)相连,对应于H中增加一个“1”,则森林的树目的个数少1,且没有任何新的回路增加。
这里,下面凡未特别提及,我们只讨论连通图的情况。
引理:由树图可恢复出Tanner图,从而可以得到校验矩阵H。
证明:根据上面作树图的方法知道,所有节点都将出现一次(除非它还是截断节点,意味着该节点在前面已经出现过),同时它也表示除了它的度和它的邻节点,如果按照Tanner图的方式,进行描述,将恢复出原来的图,并可以得到H。
定理1:回路中包含至少一个截断节点。
证明: 截断端点的出现必然意味着节点的重复出现,又由于它们是树上的不同的分支,所以,那么必定有回路的出现。
定理2:对于连通图,树图中包含了Tanner图中的所有回路。
由引理很容易得到定理的结果,证明在此略去。
定理3:如果一个节点在树图中总共出现n次,那么此节点出现在Cn2个不同的回路中。
证明:n中选取2个,总共有Pn2种选法,由于回路没有方向,每个节点都将重复一次,显然不同回路的数目是Pn2/2=Cn2。
如果一个节点两次出现,且它们距最近的祖先节点分别为h1和h2, 则存在一个长度为h=h1+h2的回路,并且这个祖先节点也处于这个回路中, 由于h为偶数,h1、h2奇偶性相同。
由树图方法可以看出,每个回路中包含至少一个截断端点。因为截断端点的出现必然意味着节点的重复,又由于它们是树上的不同的分支,所以,那么必定有回路的出现。且如果一个节点在这样的树图中总共出现n次,那么此节点出现在Cn2个不同的回路中。
循着这样的原理,本论文通过Matlab仿真,实现求解LDPC码回路的算法如下图6。
仿真实现与结果:
对于校验矩阵为H= [1 0 1 0 1 0 1 0;1 0 0 1 0 1 0 1;01 1 0 0 1 1 0;0 1 0 1 1 0 0 1], 可以得到如下的树矩阵T,并采用matlab的元胞数组进行描述:
其中树矩阵T中的元素Tij的前两个值Tij(1,2)描述当前节点,随后的两个值Tij(3,4)表明当前节点的父节点,父节点唯一,接续的值为1,1的个数表示此节点被截断次数,空矩阵表示无节点。由T可知,H的3行7列的(3,7)节点被截断1次,它存在于1个回路中,同理(4,2)节点被截断3次,存在于3个不同的回路中,依次类推。从而可以得到回路如下:
回路1: 截断节点 (3,7)—(1,7)—(1,1)—(1,3)—(3,3);
回路2: 截断节点 (3,6)—(3,3)—(1,3)—(1,1)—(2,1)—(2,6);
回路3: 截断节点 (3,7)—(3,3)—(1,3)—(1,1)—(1,7);
回路4: 截断节点 (4,2)—(4,5)—(1,5)—(1,1)—(1,3)—(3,3)—(3,2);
回路5: 截断节点 (4,4)—(4,5)—(1,5)—(1,1)—(2,1)—(2,4);
回路6: 截断节点 (4,8)—(4,5)—(1,5)—(1,1)—(2,1)—(2,8);
回路7: 截断节点 (4,4)—(2,4)—(2,1)—(1,1)—(1,5)—(4,5);
回路8: 截断节点 (3,6)—(2,6)—(2,1)—(1,1)—(1,3)—(3,3);
回路9: 截断节点 (3,6)—(2,6)—(2,1)—(1,1)—(1,7)—(3,7);
回路10: 截断节点 (4,8)—(2,8)—(2,1)—(1,1)—(1,5)—(4,5);
回路11:截断节点(4,8)—(2,8)—(2,4)—(4,4);
回路12: 截断节点 (4,2)—(3,2)—(3,3)—(1,3)—(1,1)—(1,5)—(4,5);
回路13: 截断节点 (4,2)—(3,2)—(3,3)—(1,3)—(1,1)—(2,1)—(2,4)—(4,4);
回路14: 截断节点 (4,2)—(3,2)—(3,3)—(1,3)—(1,1)—(2,1)—(2,8)—(4,8)。
通过对回 路的重新 排序容易 找出重复 出现的回路,排序规则如下:选择回路中节点(m,n),m+n值最小的为排序第一个节点,如果有多个节点m+n的值最小且相等,则选择m值小的优先,其次选择余下节点n值小的节点为排序第二个接点, 然后按回路。由上面结果:回路1等价于回路3,回路2等价回路8,回路4等价回路10,回路5等价回路7,回路6等价回路9。由于截断的次序,它们的出现只是方向不同而已,重新排序后一样。也就是说其中的回路只有回路1 (3)、2(8)、4(12)、5(7)、6(10)、9、11、13、14, 其回路的长度分别为4、6、6、6、6、6、4、8、8。但由于H的复杂性 ,需要注意的下面几点:
HE为结束标志矩阵 , 初始值为H, 在生长的过程中,被找到的节点H中对应HE的节点置0。如果H为连通的,则为单个的截断树矩阵,HE元素全为零,即为结束标志。否则为多树,此时对每次不再生长后的HE,作为新的矩阵,按上面方法重求截断树矩阵,形成迭代运算,直到最终HE的元素全为0。
4 结束语
求解校验矩阵的回路是个复杂的过程,特别对于大型的H矩,而且对于回路缠绕情况下有待给出更明确的定义。本文利用Matlab的元胞数组,把Tanner转换为图论中的截断树, 并且利用Matlab将截断树表示为元胞矩阵,以矩阵的形式表述树,从而给出了求解LDPC码Tanner图中的回路的算法 ,并通过计算机进行仿真。仿真结果对于分析回路和性能之间的关系奠定了基础。
摘要：LDPC码是性能限与香农限仅差0.0045d B的一种差错控制码,译码采用SPA(和积算法),其性能受Ta nne r图中回路长度和回路数目的影响,回路的存在使译码信息重复迭代,性能下降。论文通过计算机仿真,采用Ma tla b元胞数组,将二元校验矩阵转换为截断树矩阵,实现了求解LDPC码回路的算法,既给出回路的长度,又能得出回路的分支路径,并且能够对所有回路作整体性的描述。
元胞遗传算法 篇7
研究人员提出了一些基于元胞自动机的加密算法[1,2]。建立在二维二值元胞自动机演化基础上的密码系统难以被破解,因为其可逆性是NP问题,可以抵抗密码分析的攻击[3]。本文的加密系统正是基于此,优势如下:半并行操作加快了加密速度;密钥空间大大提升;破解难度显著增加。
1 二维触发元胞自动机理论
元胞自动机最常见的是一维和二维[4]。二维元胞自动机被定义为元胞的点阵,可根据一些规则进行编码[5]。有三种相邻位配置,如图1所示。
在所有2n个规则中有一系列被称为触发规则的规则,其特性是在不改变其他相邻位的前提下,改变触发位的值将会扭转规则的运算结果。以冯诺依曼型相邻位配置为例,选择标示为“E”的元胞作为触发位,触发规则可表示为:
a
式(1)可被表示为用2n-1项确定的真值表的值,令规则运算结果为1与令其为0的触发位值模2互补(见表1)。
2 二维触发元胞自动机加密算法描述
2.1 规则设计
参考图1,摩尔型无法进行半并行编码,扩展冯诺依曼型结构过于笨重。因此本系统采用冯诺依曼型相邻位配置,在设计时采用式(1)。规则由触发规则和非触发规则组成。触发规则的加密解密路径具有唯一性,而非触发规则却不唯一,所以只能选取触发规则。本系统在设计时回避了对所选取的规则是否为触发规则的判定,即读入相邻位时少读一位,默认未读入位就是触发位。在将规则转为二进制时,原来需转成24*r位,现只需(24*r-1)位,这样所用规则就是触发规则。
2.2 加密算法
加密过程使用两个相互独立的密钥:密钥1即为上述触发规则;密钥2由一组连接位组成,数目为2×r×(X+Y),其中X和Y是信息位矩阵的边长。根据文献[1]所述,取X=Y=N=32。以3×3明文矩阵详述加密过程:将明文转换为二进制,每次读入9位填入编码矩阵,再填入连接位。加密是多轮反向编码的过程,即按照规则将t+1时刻触发位的值编码为t时刻的值。首先按序读入除触发位以外的相邻位,然后查找规则真值表,如图2中明文第一位为1,按冯诺依曼型配置以中上左下的顺序读入各相邻位是1111;查表1最后一行第二列t+1时刻触发位值与之相同,则编码为1。可对每一列各位并行编码。
①由西向东 ②由北向南 ③由东向西 ④由南向北
一轮加密由四步编码组成,如图2所示,每步编码都是将3×3矩阵周围连接位顺时针旋转90度。因连接位分布离散,只能逐行/列编码。经分析,作者提出:放弃连接位顺时针旋转,采用待加密矩阵逆时针旋转的方法。旋转后坐标计算公式如下:
顺/逆时旋转90度行/列坐标=原列/行坐标
顺/逆时90度列/行坐标=(N+1)-原行/列坐标
这样使得每一步编码操作都按式(1)进行,不需更换触发位的位置。否则不仅加大了坐标编码的复杂度,而且更换触发位使工作量增加了三倍。所以该方法对精简程序起了很大的作用。
2.3 解密算法
解密过程就是将加密四步顺序进行反置,先由南向北编码,再依次由东向西,由北向南,由西向东。需注意以下三点:第一,解密的过程将矩阵顺时针旋转90度;第二,解密操作编码时相邻位的读入顺序应与加密时一致;最后,解密是从信息位矩阵第32列编码至第1列。
3 算法实现
程序实现大致分为如下步骤:
加密算法有三重循环,最内重循环对待操作矩阵的信息位进行半并行编码,第二重是四轮编码,第三重循环按序每次对1024位明文密文进行操作。关键部分是实现单个元胞的状态编码,再通过循环完成所有元胞的状态编码。
(1) 读入各相邻位
radius为元胞自动机的半径,p_ma数组存放的是待编码矩阵,p_ruletablearray存放从矩阵中提取的相邻位。i2和i3标明待编码位的位置,j2和j3用于控制读入。将待编码位半径以内的相邻位按右下左上中的顺序读入。
(2) 转换为相应的十进制去查触发规则表
将p_ruletablearray中的各相邻位转换为十进制数,附值给变量k。
(3) 进行加密编码
查找存放触发规则的p_togglearray数组的第k位,所得结果与待编码位异或,得编码结果。
4 安全性分析
常规加密的安全性取决于密钥的安全性,而不是算法的安全性。因此,密钥空间对于安全性来说非常重要[6]。二维触发元胞自动机加密系统的密钥空间由演化半径、规则、轮数和连接位组成:规则的密钥空间为224*r;半径和轮数的密钥空间原理上为无穷大,实现时演化轮数采用long double型,密钥空间为264;连接位密钥空间为2128×r。综上,系统密钥空间为2128*r+24*r+64。
利用本文实现的密码系统对由56个单词“alex”组成的信息进行加密。令轮数为32,规则和半径均为1,加密程序自动产生128位随机位作为连接位,加密结果如图3所示。
r=1时最坏情况需尝试2208次。当r的取值大于5时,攻击者至少尝试21049280次以上,使得蛮力攻击变得不可能。
5 结 论
本文介绍了元胞自动机的相关理论,研究如何应用二维触发元胞自动机原理实现加密解密系统,编程实现时采用VC++6.0作为开发平台。与AES等加密算法相比,二维触发元胞自动机的密钥空间要大得多。而且元胞自动机具有单元的简单规则性、单元之间作用的局部互连性和信息处理的高度并行性等优点。根据文献[1]中的分析,二维触发元胞自动机只需要几步就可以使误差扩展到整个密文,避免密文中的相似性问题,从而能够抵抗蛮力攻击和差分分析方法攻击。
参考文献
[1]Maria Madiarova,Mitsugu Kakuta,Takashi Obi,et al.Opto-Electronic Block-Cipher Based on Iteration of the2-D Toggle Cellular Automata.Algorithm,1999,6(2):110-117.
[2]Gutowitz H.Cryptography with dynamical systems.In Cellular Automata and Cooperative Systems.Kluwer Academic Publishers,1993:237-274.
[3]Durand B.ArandomNP-complete problemfor inversion of2-D cellular automata.Theoretical Computer Science,1995,148:19-32.
[4]张传武,彭启琮,朱甫臣.细胞自动机置换群加密技术研究.计算机科学,2003,30(3).
[5]Jorg R Weimar.Coupling Microscopic and Macroscopic Cellular Autom-ata.Parallel Computing,2001,27:601-611.