遗传算法的改进

1、 遗传算法的改进王晶北京工业大学应用数理学院(100022E-mail:wangjing820617摘要: 标准的遗传算法对种群的进化实施统一的交叉变异操作。本文引入了生物进化过程中的渐变与突变机制,提出按适应度大小将种群分为适应度高的渐变种群和适应度低的突变种群的方法,对不同种群采用不同交叉变异算子,使得种群的进化能达到全局最优解而不陷入局部极值;同时改进的子代种群生成的方法保证了每代种群的多样性。数值实验表明改进的遗传算法可以减少种群进化的代数,提高算法的效率,保证了算法的全局收敛性。关键词:标准遗传算法(SGA,渐变种群,突变种群中图分类号: TP183文献标识码: A1. 引言遗传算法

2、最初是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性1中提出的,它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法通过模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因变异的现象2,在每次迭代中都保留一组候选解,并按一定的指标从种群中选取较优的个体,并利用遗传算子3(选择、交叉和变异对这些个体进行组合,产生新一代的候选种群,重复此过程,直到满足某种收敛指标为止。遗传算法由于其操作简单,目前已在复杂函数优化、生产调度、图像识别、机器学习等众多领域都获得了成功的应用。然而标准的遗传算法又有很多弊端:如部分个体过分早熟使种群陷入局部极值点;局部搜索能力差

3、;若干步迭代之后由于种群过分相似而降低了交叉算子的效率;降低了收敛的速度等。本文针对标准遗传算法6中存在的一些缺点提出了采用模拟自然界进化过程中同时存在渐变和突变的机制,将种群按适应度的高低分为适应度高的渐变种群和适应度低的突变种群,对于渐变种群其可能已经接近局部最优解,因此我们控制交叉和变异算子使个体做较小改变,加强局部搜索,以保证目标函数在局部达到最优值;而对于突变种群的交叉变异算子使个体进行较大的改变,不断引入新的优秀个体,保证种群的多样性,从而避免个别个体早熟使算法陷入局部极值而收敛不到全局最优值。2. 改进的遗传算法标准的遗传算法应有如下几部分组成:(1编码(产生初始种群(2适应度函

4、数(3遗传算子(选择、交叉、变异(4运行参数。以下分别介绍本文对标准遗传算法各部分的改进。1.编码与初始种群的产生:常用的遗传算法采用的是二进制编码,由于二进制编码具有容易进行交叉变异操作的特点,编码的原则是二进制码通过解码函数解码后能与实值的取值范围相对应。初始种群的构造就是利用随机数发生器随机地产生一系列方案,然后以此为基础进行迭代。-1- 2. 选择算子:遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰的操作,适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代种群中选取一些个体,遗传到下一代群体。标准遗传算法中

5、选择算子采用轮盘赌选择方法,个体适应度越大,其被选中的概率就越高,反之亦然。按(F =n i i i i F F P 1/i为第i 个个体的适应度计算出群体中各个个体选择概率后,就可以决定那些个体被选出。但是,由于该方法是基于概率的选择,存在统计误差。同时在种群进化过程中,有时会产生一些超常的个体,这些个体因竞争力太突出而控制了选择运算过程,从而影响算法的全局优化性能,导致算法获得某个局部最优解。本文所提出的选择算子是直接通过不同的父代种群来构造子代种群的过程。方法如下:父代的部分最佳个体及经过渐变进化的优秀个体可以直接进入下一代;部分次优个体和突变进化后的优秀个体可以进入下一代。这样的种群构

6、造方式不仅保证了优秀个体可以保留同时保证了各代种群的多样性,降低了种群之间的相似性,提高了交叉操作了效率。适应度高低排序高 低 -2-适应度排序图1 种群进化结构图 3. 交叉操作:所谓交叉运算4,是指对两个相互配对的染色体依据交叉概率Pc 按某种方式相互交换其部分基因,从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征,它在遗传算法中起关键作用,是产生新个体的主要方法。常用的交叉算子有单点交叉,两点交叉等。 单点交叉:两点交叉交叉前:交叉前:00000|01110000000010000 00000|0111000000001|000011100|0000011111100

7、0101 11100|0000011111100|0101 交叉后:交叉后:00000|00000111111000101 00000|0000011111100|000011100|01110000000010000 11100|0111000000001|0101由于我们将种群分为了渐变种群和突变种群,为了使渐变种群能够达到局部最优,因此我们依据交叉概率Pc对渐变种群做两点交叉的交叉操作,以减小其改变量,使其在最优解邻域内做局部搜索;对于突变种群为保证其能在整体范围内寻优,我们可以采用再次随机产生新个体的方法,使其以大概率与突变种群的个体做交叉操作,通过不断引入新个体,使种群做较大的改变。

8、4.变异算子:所谓变异运算,是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换,从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法,它决定了遗传算法的局部搜索能力,同时保持种群的多样性。交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。标准遗传算法中变异算子采用基本位变异算子。如二进制编码符号串所表示的个体若需要进行变异操作方法如下:即某一基因座上的原有基因值为0,则变异操作将其变为1;反之,若原有基因值为1,则变异操作将其变为0。0000001110000000010000变异后0000000110000000010000通过如上变异我们发现,

9、二进制各基因位所表现出的位权重不一样,导致变异后解增量的是不同的,如二进制串0110,若第一位变异(为0111,串值改变量是1,而第四位变异后(为1110,串值改变量是8,变异越往高位,串值的改变量越大,结果可能导致接近最优点的个体遗漏。因此在变异操作时我们要求渐变种群以变异概率做较少的基本位变异,且控制变异区的权重较小,避免串值的改变量太大,导致接近最优点的个体遗漏;对于突变种群,我们允许多个基因位以变异概率同时变异且变异位不受限制。5.参数控制:遗传算法的运行需要很多参数进行控制,参数的不同可能导致收敛的速度与效率,尤其是本算法中有更多的可控因素。M:种群规模;T:遗传运算的终止进化代数;

10、Pc:交叉概率;Pm:变异概率等。Schaffer建议的最优参数范围是:M = 20-100,T = 100-500,Pc = 0.4-0.9,Pm = 0.001-0.01。本文所提出的渐变种群与突变种群的交叉变异概率可根据具体问题做适当调整。如使突变种群的变异概率为渐变种群变异概率的2倍。3. 改进的遗传算法收敛性分析遗传算法本质上是对染色体模式所进行的一系列运算,即通过选择算子将当前种群中的优良模式遗传到下一代种群中,利用交叉算子进行模式重组,利用变异算子进行模式变异。通过这些遗传操作,模式逐步向较好的方向进化,最终得到问题的最优解。本文所提出的针-3- -4-对渐变和突变种群实施不同的

11、交叉变异操作的方法提高了算法的效率,加快了全局最优解收敛的速率5,具体分析如下:(1 选择操作对收敛性的影响改进的选择操作保证了每代种群的多样性,降低了个体之间的相似度,使高适应度的父代个体能够从直接进入子代,进化后的较优个体也可以进入子代,解决了标准遗传算法中经过若干代后种群内个体高度相似缺点;使种群可以收敛到的全局最优解。本方法对于复杂的多峰多谷的函数求最值具有较好的效果。(2 交叉操作对收敛性的影响交叉操作用于个体对,产生新的个体,实质上是在解空间中进行有效搜索。渐变种群的交叉操作保证了种群中个体不至于更新很快,不会造成高适应度值的个体很快被破坏掉;突变种群的交叉操作,保证了交叉的有效性

12、,从而不会使搜索停滞不前,造成算法的不收敛,或陷入局部最优解。(3 变异操作对收敛性的影响变异操作是对种群模式的扰动,有利于增加种群的多样性。渐变种群的变异保证了最佳个体渐进达到局部最就解,增强了个体的局部搜索能力;突变种群的变异保证了新模式的产生,保证种群的多样性。从而保证了最终达到全局最优解。 4. 数值实验为验证本文所提出的改进的遗传算法的有效性,下面给出与标准遗传算法对比的实验结果。本实验测试程序是作者用C +编程语言开发的。(1 测试函数:max f (x 1,x 2=100(x 12-x 22+(1-x 12-2.048<=x 1,x 2<=2.048(2 采用二进制编

13、码,x 1,x 2对应的染色体长度均为10(3 解码函数:4.096*CodeValue/1023.0-2.048(4 测试中的参数 交叉概率:pc =0.8,变异概率:pm =0.08(5 测试函数的性质:此函数有两个局部极大点,分别是f (2.0048,-2.048=3897.734227对应的编码为11111111110000000000;f (-2.0048,-2.048=3905.926227 对应的编码为00000000000000000000 ;后者为全局极大点。一般的遗传算法常常陷入前者局部极值点,但改进后的算法明显提高了全局极值点的收敛概率,降低了种群进化的代数表1 标准遗传

14、算法与改进遗传算法比较标准遗传算法(SGA 改进的遗传算法 种群大小 收敛全局极值概率平均进化代数 收敛全局极值概率平均进化代数80 31% 205 53% 81150 55% 103 90% 51 200 80% 49 98% 23 5. 结束语通过数值实验可以发现本文所提出的方法,使得渐变种群在局部最优解附近做逼近搜索,突变种群通过不断引入新个体,在全局范围内搜索最优值。与标准遗传算法相比本方法可以减少种群进化的代数;增强了个体的局部搜索能力;提高了算法的效率;保证了算法达到全局最优解;对于复杂的多峰多谷函数寻求最优值具有良好的效果。参考文献1J.Holland. 自然界和人工系统的适应性

15、.19752Srinivas M,Patnaik L M. 遗传算法中的自适应交叉和变异概率J IEEE系统. 人和控制论学报,1994, 24(4:656667(英文版3郑金华,叶正华,蒙祖强等. 基于空间交配的遗传算法J. 模式识别与人工智能,2003,16(4:4824854陈小平,于盛林. 实数遗传算法交叉策略的改进. 电子学报,2003:31(15李茂军,童调生. 单亲遗传算法的全局收敛性分析. 自动化学报,1999,25(1:2680.6焦李成,保铮. 进化计算与遗传算法-计算智能的新方向. 系统工程与电子技术,1995(6:2032The improvement of genet

16、ic algorithmWang JingBeijing University Of Technology (100022AbstractThe standard genetic algorithm carried out uniform cross - mutation implementation on populations. This paper introduces an improved genetic algorithm. According to the difference of fitness of the population, we carry out different cross - mutation implementation on populations. Numerical expe