遗传算法入门到掌握

3.基因突变是不定向的。

题外话： 染色体变异

基因突变是染色休的某一个位点上基因的改变，这种改变在光学显微镜下是无法直接观察到的。而染色休变异（chromosomal variations）是可以用显微镜直接观察到的，如染色体结构的改变、染色体数目的增减等。 1.染色体结构的变异

人类的许多遗传病是由染色体结构改变引起的。例如，猫叫综合征是人的第5号染色体部分缺失引起的遗传病，因为患病儿童哭声轻，音调高，很像猫叫而得名。猫叫综合症患者的生长发育迟缓，而且存在严重的智力障碍。

在自然条件或人为因素的影响下，染色体发生的结构变异主要有以下4种类型。（如图组2-5）

（1）染色体某一段缺失引起变异。 （2）染色体中增加某一片段引起变异。

（3）染色体某一片段移接到另一条非同源染色体上引起变异。 （4）染色体中某一片段位置颠倒也可引起变异。

上述染色体结构的改变，都会使排列在染色体上的基因的数目和排列顺序发生改变，从而导致性状的变异。大多数染色体结构变异对生物体是不利的，有的甚至导致生物体死亡。 2. 染色体数目的变异

一般来说，每一种生物的染染色体数目都是稳定的，但是，在某些特定的环境条件下生物体的染色体数目会发生改变，从而产生可遗传变异。染色体数目的变异可以分为两类：一类是细胞内的个别染色体增加或减少，另一类是细胞内的染色体数目以染色体组的形式成倍地增加或减少。（择自《高中生物课本》） 读 者应该察觉到我们用在遗传算法上的基因突变也没有包括染色体的变异过程。因为一般来说这种大规模的变异对原来的个体的基因序列破坏性比较大。所以一般来说 很难得到一个适应度高的个体。但是染色体变异，特别是染色体数目的突变使到生物从简单进化到复杂成为了可能，这也是非常具有意义的。

1.染色体某一段缺失引起变异。 2.染色体中增加某一片段引起变异。

3.染色体某一片段移接到另一条非同4.染色体中某一片段位置颠倒也可引源染色体上引起变异。 起变异。

图组2-5

好了，到此为止，基因编码，基因适应度评估，基因选择，基因变异都一一

实现了，剩下来的就是把这些遗传过程的“零件”装配起来了。先让我们定义一个遗传算法的类：CGenAlg

遗传算法引擎――CGenAlg

1. class CGenAlg 2. 3. { 4.

5. public: 6.

7. //这个容器将储存每一个个体的染色体 8.

9. vector m_vecPop; 10.

11. //人口(种群)数量 12.

13. int m_iPopSize; 14.

15. //每一条染色体的基因的总数目 16.

17. int m_iChromoLength;

18.

19. //所有个体对应的适应性评分的总和 20.

21. double m_dTotalFitness; 22.

23. //在所有个体当中最适应的个体的适应性评分 24.

25. double m_dBestFitness; 26.

27. //所有个体的适应性评分的平均值 28.

29. double m_dAverageFitness; 30.

31. //在所有个体当中最不适应的个体的适应性评分 32.

33. double m_dWorstFitness; 34.

35. //最适应的个体在m_vecPop容器里面的索引号 36.

37. int m_iFittestGenome; 38.

39. //基因突变的概率,一般介于0.05和0.3之间 40.

41. double m_dMutationRate; 42.

43. //基因交叉的概率一般设为0.7 44.

45. double m_dCrossoverRate; 46.

47. //代数的记数器 48.

49. int m_cGeneration; 50.

51. //构造函数 52.

53. CGenAlg(); 54.

55. //初始化m_dTotalFitness, m_dBestFitness, m_dWorstFitness, m_dAverageFitness 等变

量 56.

57. void Reset(); 58.

59. //初始化函数 60.

61. void init(int popsize, double MutRate, double CrossRate, int GenLenght); 62.

63. //计算m_dTotalFitness, m_dBestFitness, m_dWorstFitness, m_dAverageFitness等变量 64.

65. void CalculateBestWorstAvTot(); 66.

67. //轮盘赌选择函数 68.

69. CGenome GetChromoRoulette(); 70.

71. //基因变异函数 72.

73. void Mutate(vector &chromo); 74.

75. //这函数产生新一代基因 76.

77. void Epoch(vector &vecNewPop); 78. 79. };

其中Reset()函数，init()函数和CalculateBestWorstAvTot()函数都比较简单，读者查看示例程序的代码就能明白了。而下面分别介绍init函数和Epoch函数。

类的初始化函数――init函数

init函数主要充当CGenAlg类的初始化工作，把一些成员变量都变成可供重新开始遗传算法的状态。（为什么我不在构造函数里面做这些工作呢？因为我的程序里面CGenAlg类是View类的成员变量，只会构造一次，所以需要另外的初始化函数。）下面是init函数的代码：

1. void CGenAlg::init(int popsize, double MutRate, double CrossRate, int GenLenght) 2. 3. { 4.

5. m_iPopSize = popsize; 6.

7. m_dMutationRate = MutRate; 8.

9. m_dCrossoverRate = CrossRate; 10.

11. m_iChromoLength = GenLenght; 12.

13. m_dTotalFitness = 0; 14.

15. m_cGeneration = 0; 16.

17. m_iFittestGenome = 0; 18.

19. m_dBestFitness = 0; 20.

21. m_dWorstFitness = 99999999; 22.

23. m_dAverageFitness = 0; 24.

25. //清空种群容器，以初始化 26.

27. m_vecPop.clear(); 28.

29. for (int i=0; i

31. { 32.

33. //类的构造函数已经把适应性评分初始化为0 34.

35. m_vecPop.push_back(CGenome()); 36.

37. //把所有的基因编码初始化为函数区间内的随机数。 38.

39. for (int j=0; j

41. { 42.

43. m_vecPop[i].vecWeights.push_back(RandFloat() * 44.

45. (g_RightPoint - g_LeftPoint) + g_LeftPoint); 46.

47. } 48.

49. } 50. 51. }