改进的混沌遗传算法

1、改进的混沌遗传算法李辉( 计算机学院 2004 级研究生 04720746)摘 要： 混沌遗传算法 (chaos genetic algorithm, CGA) 是基于混沌优化的遗传操作 , 将使子代个体均匀地 分布于定义空间 , 从而可避免早熟 , 以较大的概率实现全局最优搜索. 与传统的遗传算法相比较 , CGA 的在线和离线性能都有较大的改进。而遗传算法作为一种智能算法，是解决非线性复杂优化问题的有利工具， 但它在搜索过程中易陷入局部最优，收敛速度慢的缺陷又限制了它的寻优效能。混沌遗传算法具有两者的 优点，大大提高了优化的效率。关键词： 遗传算法 混沌 混沌优化Abstract ： Ch

2、aos genetic algorithm (CGA)is a genetic operation,which based on chaos optimization,makes the individuals of subgeneration distribute uniformly in the defined space and avoids the premature of subgeneration.To compare the performances of the CGA with those of the traditi onal GA,The results dem on s

3、trated that the CGA-li ne and o ine performa nee was allsuperior to that of the traditional GA.As an inteliengence algorithm,GA is a effectual toos to resolve the problem of the liner-optimization,but the slower eonvergenee and the premature restriet its effieieney.And CGA whieh has the two strongpo

4、int has promoted is effieieney in optimization.Key words: genetie algorithm ehaos ehaos optimization引言：遗传算法 (GA) 最早由美国 Miehigan 大学的 John Holland 教授提出，通过模拟自然界中的生命 进化过程，有指导地而不是盲目地进行随机搜索， 适用于在人工系统中解决复杂特定目标的非线性 反演问题。 De Jong 首先将遗传算法应用于函数优 化问题的研究，他的工作表明在求解数学规划时， GA 是一种有效的方法。但对于大型复杂系统，尤 其是非线性系统优化问题的求解， GA

5、 仍有许多缺 陷，如无法保证收敛到全局最优解，群体中最好的 染色体的丢失，进化过程的过早收敛等。混沌是自然界中一种较为普遍的现象，具有 “随机性”、“遍历性”及“规律性”等特点，在一 定范围内能按其自身的“规律”不重复地遍历所有 状态的。在搜索空间小时混沌优化方法效果显著， 但搜索空间大时几乎无能为力。混沌遗传算法 (CGA) 的基本思想是将混沌状态 引入到优化变量中，并把混沌运动的遍历范围“放 大”到优化变量的取值范围，然后把得到的混沌变 量进行编码，进行遗传算子操作。再给混沌变量附 加混沌小扰动，通过一代代地不断进化，最后收 敛到一个最适合环境的个体上，求得问题的最优 解。2 传统遗传算法

6、 传统遗传算法：population old_pop,new_pop;/*eurrent and next population*/int pop_size,generation;float p_eross,p_mutation; /*prob. Of erossover & mutation*/old_pop=initial random population=ind1,ind2,.indpopsizewhile(generationMAX_GEN) /*termination eondition not met do*/fitness_evaluate(old_pop); /*ealeul

7、atefitness of indieiduals*/new_pop=seleet_eopy(N,old_pop);/*seleet N member of old_pop*/new_pop=erossover(p_eross,new_pop);old_pop=mutate(p_mutation,new_pop);generation+;endWhilereturn(individual with greatest fitness);population 为种群， in 为求解问题许可解的染 色体代码表示，其中 fitness_evaluate, seleet_eopy, erossover,

8、mutate 是 4 种遗传算子，分别代表适应度 估值、选种、杂交、变异等操作。通过其伪码，我们可以看出，传统遗传算法的 对遗传算子的操作进行的仅仅是复制、交叉和变 异，这样对比较简单的系统可能很快求岀最优解， 随着系统的庞大，尤其是求解非线性系统优化问题 的时候，很容易陷入局部寻优，染色体丢失，进化 过程过早收敛等等。3混沌提岀混沌的起因有很多，其中之一时这样的： 巴西热带雨林的一直蝴蝶拍动了一下翅膀，结果导 致美国德克萨斯州的一场龙卷风，事实固然可能没 有那么严重，但是也从侧面反映了一个微小事物的 扰动可能引起的巨大后果。有的地方把混沌分为 8种8：女口 lorenz蝴蝶 效应现象、阿瑟的

9、路径锁定效应、Logistic 倍周期 分叉现象等。其中，Logistic倍周期分叉现象是指 事物在经历了一定的阶段之后，就必然会迎来一个 崭新的阶段。在新旧阶段交替的点上，人们将面临 选择的两难困境，同时，人们也只能在各种两难选 择方案中确定其中之一种，作为其发展的道路。这 种选择的过程，就称为倍周期分叉现象。下面从数学的角度对 Logistic分配现象做一下解释3:Logistic方程通常写为：X+i = u *Xn*（1-x n），它是定义一类把 0到1区间映射到自身的不可逆映 射。通过上式我们可以看出当Xn=0.5时，Xn+1最大，所以u的范围为（0, 4），为了便于理解，对此函数 用

10、matlab做图：遗传可能有着密切的联系，在此作者将其引入混沌遗传算法。4改进混沌遗传算法原理4、 1一般混沌遗传算法：结合传统遗传算法，一般的混沌算法的基本步骤如下：步骤0对优化对象二进制编码，生成初始群体，计 算各个适应值；步骤1根据选择概率 口= 八，fi （ fi为个 体适应值）按规定的种群规模选择个体进入下一代 ； 步骤2以交叉概率pc按适当的交叉方式对选中的多对个体交叉；步骤3以变异概率pm按适当的变异方式对选中 的个体变异；步骤4解码，计算各个体适应值；步骤5对适应值最大的部分个体做混沌优化运算,若新个体适应值大于原个体，则替换，否则不变； 步骤6重复步骤1至步骤5,直到终止条件

11、得以满 足。改进的混沌遗传算法原理从一般的混沌遗传算法步骤可以看岀：它的算法是先进行遗传算法，后进行混沌优化，没有考虑它们之间在优化时的某种 相似之处。其实，步骤5所进行的混沌优化和遗传算 法的交叉和变异两个算子存在重复性的工作4.2改进的混沌遗传算法4. 2. 1 编 码为了克服二进制编码的 Hamming悬崖，使用 Gray编码（一种循环编码机制），采用交叉编码方 案。例如：当 011111 + 0000001 = 100000 时，各个数字都要变化，而采用Gray编码，可以仅改变一位。4.2 . 2模型优化不失一般性，考虑如下的优化问题m ax f （X, xr ）（ A ）a i _

12、xi _ bi （i = 1,., r ）（ B ）ai , bi 为x的变化区间，r变量个数。式（A）是模型的优化函数，式（B）是 模型的约束条件.logistic倍周期分配图当口 =3时，主序列在周期1和2之间开始分叉，当-1 、一6 =3.45时，主序列在周期 2和4之间开始分叉，最终进入混沌。当u =4的时候到达完 全混沌。由于该现象类似于昆虫的繁殖，因此和生物的4. 2. 3随机扰动令 Xk =（1 - ：.）X* 卷二Xk（3）X*为当前最优解（X；,X*）映射到:0, 1区间后形成的向量，称为最优混沌向量； Xk为迭代k次后的混沌向量，X k为加了随机扰动 后（X1, ,， Xr

13、）对应的混沌向量；其中 0a 1,采用 自适应选取，这是因为搜索初期希望（X“， Xr）变动较大，需要较大的a。随着搜索的进行，（X!,， Xr）逐渐接近最优点，故需要选用较小的a，以便在(X；,X：)所在的小范围内搜索。由下式确定 TOC o 1-5 h z k1:- k -.(4)其中m为一整数，依优化目标函数而定; 迭代次数。4. 2 . 4改进的混沌遗传算法步骤：为优化变量，进行迭代。随着次数的增加，式(4)计算岀的a值不断改变，迭代逐渐向最优解逼近， 直到前后两次计算岀的适应度平均值之差小于预先给定的某个小正数为止。步骤0:对待优化参数进行 Gray编码，选取适应度 函数，此函数由待

14、优化的目标函数决定，设定变量 的取值范围a , bj、群体规模 m及父代间的交叉率Pc和子代的变异率Pm。步骤：根据选择概率pi= fi /刀fi按规定的种群规模 选择个体进入下一代； 步骤2:据pc按适当的交叉方式对选中的多对个体 交叉； 步骤3:.以变异概率Pm按适当的变异方式对选中的 个体变异； 步骤4:解码；步骤5 选用Logistic映射(如图):Xn+1= U . Xn(1-Xn)( 5)式中，取4时，达到完全混沌，当口逐渐减小时,Xn+1和Xn构成的相空间吸引子范围逐渐变小(Xn+1值的范围由两头收缩靠拢)，直到退岀混沌。 本文|1 =4o步骤6:按照式(5)得到的混沌变量通过变

15、换映 射到要优化的变量，并要注意待优化变量的取值范 围和约束条件，以免在不必要的空间搜索，变换公 式如下：X ；=Ci +di * X i(6)步骤7: 计算每个个体的适应度值，选取前 ？(例 如取20%)具有最大适应度值的个体，不参加三遗传 算子操作，直接带入下一代，另外的 1-?%(80% )由 三操作产生，对子代群体进行解码。步骤8:计算新的适应度值，求岀适应度的平均值 并将之与最大值按下式比较，如果下式成立，则认 为寻优过程结束，输出最优结果作为最优值，否则 执行步骤9| f(X ) - f(X 扁 I”： ；1 1 mftx，)=送瓦 f / j ( X / )其中m j , “预先

16、给定的某个小正数。步骤9:给当前代群体中适应度较小的 90%对应的 优化变量按式(3)加一混沌扰动，然后按式(6)映射| fk(x) fk 申(x) | 棗(8)其中k为迭代次数，k=0，1，, o步骤10:求岀适应度的平均值并将其与最大值按 式(7)比较，如果式(7)成立，则认为寻优过程结束, 输岀最优值，否则转向步骤1 o5局限性&扩展上述方法只能在处理器上串行执行执行，想当 然运行速度受到限制，当运行的数值或着选择的迭 代次数比较大时，其在 pc上运行就会岀现问题， 因此只能解中小规模的应用任务，能否分而治之”呢？也就是并行算法考虑的问题。各种并行遗传算法：msGA， cgGA，fgGA

17、， mIGA其中,cgGA是粗粒度(coarse-grain) 并行遗传 算法，又称分布式或MIMD遗传算法，或岛模式GA 在该方法中，整个种群分解成多个子种群，子种群 形象一岛屿，大部分时间孤立地进行演化，偶尔和 邻近岛屿交换个体，如此个体交换称为迁移。因此， 种群的划分以及迁移策略是 cgGA考虑的关键。Grosso最早系统地研究了 cgGA目的是模拟几 个并行子种群之间的相互作用，并发现多个小子种 群进化过程中，个体的平均适应度的改善比较快。 但若子种群是孤立的，个体的适应度收敛于较小的 值，即解的质量较大种群要差。另外，若子种群间 迁移率很小，则所得解类似孤岛模型。若迁移率很 大，则解

18、雷同于串行 GA Cohoon通过实验观察到 在cgGA运行的动态过程中，大部分时间群体处于 一种平衡态，也就是说遗传物质无显著变化。但当 生存环境发生变化时，则激起振荡，导致短时间的 快速进化。在子种群间的通信互连方面，传统的GA经常将其忽略，但通信拓扑结构是重要的。例如紧 耦合和短直径的互连结构可以回忆优势个体的传 播、混合和杂交，同时也收起较大的通信成本。CgGA 的趋势是采用静态拓扑结构，即整个进化过程中子 种群间的通信连接不变。最近，Can在4维超立方体、4*4环网以及双向环上做了大量的实验证实：紧耦合比松耦合拓扑结构在求解过程，调用适 应度估值函数的次数要少。总之，cgGA是串行GA的扩充，每个并行处理 器上维持一个子种群，且定期交换少量个体信息， 相比cgGA而言，通信开销减少，且不存在处理器 同步问题。虽单个处理器的性能并不具有优势，整 个算法的功效取决于所有处理结点的合作，性能改 善的程度近似正比于并行计算机的数目。但大规模 并行机是昂贵的，幸好可用网络工作站群通过运行 MPI或PVM软件来模拟实现。Internet 上通过Java 编程也容易实现cgGA在相同的停止条件下，cgGA 和串行GA的迭代次数不相等，因为前者遗传算子 都是局部操作。cgGA的难点在于确定合适的迁移策 略，目前尚无法优化迁移率、迁移间隔等参数。6 总结利