欢迎光临本站!

大变异操作的思想

来源:技术探讨    更新时间:2019-12-20 14:44:13    编辑:老王    浏览:1485
  众所周知,简单遗传算法存在一个“早熟”的问题,也就是算法过早收敛于一个非全局最优点。出现这种问题的主要原因是由于一种被称为“顶端优势”的现象存在,即当算法进行到某一代时,在种群中某个个体m的适应度远远大于其它任何个体的适应度,因为个体被选中进行复制的概率由式(1)确定,这样就会造成子代中许多个体来自同一祖先m,从而彼此近似。这种现象的极限情况就是所有个体来自同一祖先,这就是我们常说的“早熟”,一旦出现“早熟”,SGAs中的选择和交叉操作就会失效。

  理论上,SGAs中的变异操作可以使算法跳出“早熟”,但是,为了保证算法的稳定性,变异操作的变异概率通常取值很小(例如0。01),所以算法一且出现“早熟”,单靠传统的变异操作需要很多代才能变异出一个不同于其它个体的新个体m.而且,如果新个体m的适应度Fm满足以下关系。

图片.png

  由式(1)可知,新个体m在进行下一次选择操作时被选中的概率会远远小于1。目前,对于这个问题已有的解决方法是采用对个体的适应度进行一个称为尺度化( Scaling)的操作,但是,这种方法改变了原问题的适应度函数,会在很大程度上影响遗传算法的收敛速度。

  大变异操作就是在这样的背景下提出的,它的思路是:当某代中所有个体集中在一起时我们以一个远大于通常的变异概率的概率执行一次变异操作,具有大变异概率的变异操作(即大变异操作”)能够随机、独立地产生许多新个体,从而使整个种群脱离“早熟”。

  这个思路在实现时有两个要解决的问题:1)如何判断某代中所有个体集中的程度?我们采用比较每代中所有个体的最大适应度Fmax和平均适应度Fmax的接近程度的方法来判断,因为通常某代的最大适应度Fmax和平均适应度Fwx越接近,该代中个体就越集中,2)如何保证前代具有最大适应度的个体不被大变异操作破坏掉?我们采用的策略是:在当代所有适应度等于最大适应度的个体中,选择一个个体,对它不进行大变异操作。

  此外,在进行大变异操作前,我们还将所有个体都设为具有最大适应度的个体的形式,进行这个操作的原因是对于一个未知的待优化问题,在一个较优的点的附近常常会以较大的概率出现一个更优的点,逆向思考就是,最优点的附近的点也较优。我们可以用以下的变异概率转移矩阵M[4来描述变异操作:

图片.png

  其中L是个体长度,Pm是变异概率,p(i,j)是i号个体**与j号个体间的 Haming距离。我们在图1中绘出了在L=6,Pm=0.12时,个体010101和个体11100,行变异操作时的概率转移曲线由曲线和式(2)可以得出:当变异概率小于0。5时每个个体以较大的概率变异为与它“临近”的个体。我们把所有个体设为当代最大适应度的个体,再对设定后的个体进行大变异操作的结果是:新个体会以很大的概率出现在当代最大适应度的个体的“临近”,这正是我们进行优化时所期望的。

大变异操作的思想

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜