遗传算法入门到掌握

由天下分享时间：2024/9/15 9:12:01 加入收藏我要投稿点赞

3. CGenome GetChromoRoulette() 4. 5. { 6.

7. //产生一个0到人口总适应性评分总和之间的随机数. 8.

9. //中m_dTotalFitness记录了整个种群的适应性分数总和) 10.

11. double Slice = (RandFloat()) * m_dTotalFitness; 12.

13. //这个基因将承载转盘所选出来的那个个体. 14.

15. CGenome TheChosenOne; 16.

17. //累计适应性分数的和. 18.

19. double FitnessSoFar = 0; 20.

21. //遍历总人口里面的每一条染色体。 22.

23. for (int i=0; i

27. //累计适应性分数. 28.

29. FitnessSoFar += m_vecPop[i].dFitness; 30.

31. //如果累计分数大于随机数,就选择此时的基因. 32.

33. if (FitnessSoFar >= Slice) 34.

35. { 36.

37. TheChosenOne = m_vecPop[i]; 38.

39. break; 40.

41. } 42. 43. } 44.

45. //返回转盘选出来的个体基因 46.

47. return TheChosenOne; 48. 49. }

遗传变异――基因重组（交叉）与基因突变。

应该说这两个步骤就是使到子代不同于父代的根本原因（注意，我没有说是子代优于父代的原因，只有经过自然的选择后，才会出现子代优于父代的倾向。）。对于这两种遗传操作，二进制编码和浮点型编码在处理上有很大的差异，其中二进制编码的遗传操作过程，比较类似于自然界里面的过程，下面将分开讲述。 1.基因重组/交叉(recombination/crossover) （1）二进制编码

回顾上一章介绍的基因交叉过程：同源染色体联会的过程中，非姐妹染色单体（分别来自父母双方）之间常常发生交叉，并且相互交换一部分染色体，如图2-3。事实上，二进制编码的基因交换过程也非常类似这个过程――随机把其中几个位于同一位置的编码进行交换，产生新的个体，如图2-4所示。

图2-3 图2-4 （2）浮点数编码

如果一条基因中含有多个浮点数编码，那么也可以用跟上面类似的方法进行基因交叉，不同的是进行交叉的基本单位不是二进制码，而是浮点数。而如果对于单个浮点数的基因交叉，就有其它不同的重组方式了，比如中间重组：

这样只要随机产生就能得到介于父代基因编码值和母代基因编码值之间的值作为子代基因编码的值。

考虑到“袋鼠跳”问题的具体情况――袋鼠的个体特征仅仅表现为它所处的位置。可以想象，同一个位置的袋鼠的基因是完全相同的，而两条相同的基因进行交叉后，相当于什么都没有做，所以我们不打算在这个例子里面使用交叉这一个遗传操作步骤。（当然硬要这个操作步骤也不是不行的，你可以把两只异地的袋鼠捉到一起，让它们交配，然后产生子代，再把它们送到它们应该到的地方。）

题外话：性的起源

生命进化中另一个主要的重大进展是伴随着两性的发育――两个生物个体间遗传物质的交换而来的。正是这种交换提供了自然选择可以发生作用的变异水平。

性可能起源于在某种同类相食中。一个生物吞噬了另一个生物。含有双倍遗传物质的吞噬后生物为了解救自己而一分为二。这时，一种单倍遗传物质与双倍遗传物质的单位持续相互交换替的模式就会产生。直至到达一个各项规则都适合于双倍系统的环境。在这个系统中，从双倍体到单倍体的分裂只发生在性细胞或配子形成中，然后来自不同母体的配子结合成一个新的个体而恢复正常的双倍体系统。由于两性的出现，使进化的步伐加快了。（择自《吉尼斯－百科全书》1999年版）

由于基因交叉和两性有莫大的关联，所以我们可以从这个角度去深入了解基因交叉。性别的出现是在生物已经进化得相对复杂的时候。那个时候生物的基因基本形成了一种功能分块的架构。而自然界的基因交叉过程又一般不是单个基因，或者随便几个基因的交叉，而是一块基因，往往是表现某种个体性状的那块基因，所以从宏观上看，基因交叉的表现是性状的分离（孟德尔在实验中总结出来的规律。）。而性状又往往表现相对独立的个体特征。比如豌豆的高茎和矮茎，圆滑和皱缩。（参照第一章对孟德尔实验的介绍。）这些都是相对独立的特征，它们之间可以自由组合互相搭配。这时候，交叉过程将起到从宏观上调整基因块之间搭配的作用。经过物竞天择的过程，最后就能得到相对较好的特征组合方式，从而产生更优的个体。我想这才是基因交叉的意义所在吧。所以对于很多问题，使用基因交叉操作的效果不太明显，往往只能充当跳出局部最优解，相当于大变异的功能。真正意义上的基因交叉应该使用在大规模参数的进化过程当中，它将承担起对基因块进行组合优化的职责，从更宏观的角度去优化个体。对于交叉操作以后还将进行更具体的探讨。

2.基因突变(Mutation) （1）二进制编码

同样回顾一下上一章所介绍的基因突变过程：基因突变是染色体的某一个位点上基因的改变。基因突变使一个基因变成它的等位基因，并且通常会引起一定的表现型变化。恩，正如上面所说，二进制编码的遗传操作过程和生物学中的过程非常相类似，基因串上的 “ 0”或“ 1”有一定几率变成与之相反的“ 1”或“ 0”。例如下面这串二进制编码：

101101001011001

经过基因突变后，可能变成以下这串新的编码： 001101011011001 （2）浮点型编码

浮点型编码的基因突变过程一般是对原来的浮点数增加或者减少一个小随机数。比如原来的浮点数串如下：

1.2, 3.4, 5.1, 6.0, 4.5

变异后，可能得到如下的浮点数串：

1.3, 3.1, 4.9, 6.3, 4.4

当然，这个小随机数也有大小之分，我们一般管它叫“步长”。（想想“袋鼠跳”问题，袋鼠跳的长短就是这个步长。）一般来说步长越大，开始时进化的速度会比较快，但是后来比较难收敛到精确的点上。而小步长却能较精确的收敛到一个点上。所以很多时候为了加快遗传算法的进化速度，而又能保证后期能够比较精确地收敛到最优解上面，会采取动态改变步长的方法。其实这个过程与前面介绍的模拟退火过程比较相类似，读者可以做简单的回顾。下面是针对浮点型编码的基因突变函数的写法：

1. //基因突变函数 2.

3. void Mutate(vector &chromo) 4. 5. { 6.

7. //遵循预定的突变概率,对基因进行突变 8.

9. for (int i=0; i

13. //如果发生突变的话

14.

15. if (RandFloat() < m_dMutationRate) 16.

17. { 18.

19. //使该权值增加或者减少一个很小的随机数值 20.

21. chromo[i] += (RandomClamped() * g_dMaxPerturbation); 22.

23. //保证袋鼠不至于跳出自然保护区. 24.

25. if(chromo[i] < g_LeftPoint) 26.