遗传算法 Genetic Algorithm

By | 2018年10月30日

目录:

  1. 遗传算法的原理
  2. 遗传算法与传统优化算法的比较

 

1.遗传算法的原理

遗传算法(Genetic Algorithm, GA),是一种通过模拟自然进化过程(优胜劣汰)搜索最优解的方法,借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最佳解。

遗传算法的一般步骤如下:

  1. 个体编码(创造染色体);
  2. 产生初始群体(创造初始种群);
  3. 计算适应度(度量物种对于生存环境的适应程度);
  4. 选择运算(基于适应度的优胜劣汰的过程);
  5. 交叉运算(基因重组或杂交);
  6. 变异运算(基因突变)

 

举个例子,求下述二元函数的最大值:

200812202481225480

(1)个体编码

遗传算法的运算对象是表示个体的符号串,所以必须将这里的变量x1、x2编码为一种符号串。

编码方法主要有2种:

  1. 二进制编码法。受人类染色体编码结构的启发,假设我们目前只有“0”、“1”两种碱基,我们也可以用一条链把它们有序地串联在一起,每一单位都能表现出1 bit的信息量,所以一条足够长的染色体就能为我们勾勒出一个个体的所有特征,比如“01001001100101110110001”。此方法虽简单直观,但当个体特征较为复杂时,需要大量的编码才能精确描述,那么相应的解码过程就会十分繁复。
  2. 浮点数编码。浮点数编码能改善计算复杂性,提高运算效率,比如“1.2-3.3-2.0-4.5-7.2-5.8”。

编码原则:

  1. 完备性(completeness):问题空间的所有解都能表示为所设计的基因型;
  2. 健全性(soundness):任何一个基因型都对应于一个可能解;
  3. 非冗余性(non-redundancy):问题空间和表达空间一一对应。

基于本例,将采用无符号二进制编码来表示个体。

因x1、x2为0-7之间的整数,而 “2的一次方< 7 <2的3次方”,所以使用3位无符号二进制数来表示,将它们连在一起所组成的6位无符号二进制数就形成了个体的基因型,表示一个可行解。

如,基因型 X=101110 所对应的表现型为:x=[5, 6]

个体的表现型x和基因型X可通过编码和解码程序相互转换。

(2)产生初始群体

遗传算法是对群体进行的进化操作,需要为其准备一些初始群体表示起始的搜索点。

本例中,将群体规模取为4,即初始群体由4个个体组成,每个个体通过随机方法产生,假设这里为:011101,101011,011100,111001

(3)计算适应度

遗传算法中以个体适应度的大小来评定各个体的优劣程度,从而决定其遗传机会的大小。

适应度函数的选取直接影响遗传算法的收敛速度以及能否找到最优解。

一般而言,适应度函数是由目标函数变换而成的。

适应度函数设计不当有可能出现欺骗问题:

  1. 进化初期,个别超常个体控制选择过程;
  2. 进化末期,个体差异太小导致陷入局部极值;

本例中,目标函数始终为非负值,并且以求函数最大值为优化目标,所以可直接利用目标函数值作为个体的适应度。

 

(4)选择运算

选择运算(复制运算),是把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中,一般要求适应度较高的个体将有更多的机会遗传到下一代群体。

本例中,我们采用“与适应度成正比”的规则来确定各个体“复制”到下一代群体的概率,具体操作过程如下:

  1. 先计算群体中各个体的适应度,及所有个体的适应度总和;
  2. 其次计算各个体适应度占总适应度的比值大小,即该个体被遗传到下一代群体的概率;
  3. 每个概率值组成一个区域,全部概率值之和为1;
  4. 最后随机产生[0,1]之间的随机数,根据该随机数落在哪个概率区域内来确定各个体被选中的次数;

微信截图_20181030105148

(5)交叉运算

交叉运算,是遗传算法中产生新个体的主要操作过程,它以某一概率相互交换某两个个体之间的部分染色体。

对于交叉运算,二进制编码和浮点数编码存在较大差异,其中二进制编码的交叉运算更接近生物过程:

  1. 二进制编码的基因交换过程类似于生物中同源染色体的联会过程——随机把其中几个位于同一位置的基因进行交换,从而产生新的个体;
  2. 浮点数编码也可以做类似操作,直接将浮点数进行交换。但对于单个浮点数的基因交叉,就有不同的重组方式了,比如中间重组(随机产生得到介于父基因和母基因编码值的中间值作为子代基因的编码值),如 5.5 和 6.1 进行交叉,结果可以是 5.6、5.7、5.8、5.9、6.0等任一值。

本例中,采用二进制编码的交叉运算过程,具体操作过程如下:

  1. 先对群体进行随机配对;
  2. 然后随机设置交叉点的位置;
  3. 最后再互相交换配对染色体之间的交叉点基因;

微信截图_20181030112812

可以看出,新产生的个体“111101”,“111011”的适应度较原来的个体都提高了。

(6)变异运算

基因突变,是染色体的某一个位点上基因的改变。基因突变使一个基因变成它的等位基因,并且通常会引起一定的表现型变化。

变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变,它也是产生新个体的一种操作方法。

  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. 然后依照某一概率将变异点的原由基因值取反;

200812202495948037

 

以上,对群体进行的一轮选择、交叉、变异运算之后,就得到了新一代的群体。

微信截图_20181030145939

与初始群体相比,经过“进化”后的子代群体,其适应度的最大值、平均值、总值都得到了明显的改进。(事实上,这里已经找到了最佳个体“111111”,不过这里只是举个随机的例子,实际程序中不一定这么快找到)

总结一下各步骤的意义:

  1. 物竞——适应度函数(fitness function)
  2. 天择——选择函数(selection)
  3. 选择的作用:优胜劣汰,适者生存;
  4. 交叉的作用:保证种群的稳定性,朝着最优解的方向进化;
  5. 变异的作用:保证种群的多样性,避免交叉可能产生的局部收敛。

2.遗传算法与传统优化算法的比较

 

(1)传统优化算法的优点:

  1. 利用解空间的特性,如可导、可微等;
  2. 理论较为完善,计算量较小;
  3. 收敛速度快;
  4. 具有确定的终止准则;

(2)传统优化算法的缺点:

  1. 仅能求出优化问题的局部最优解;
  2. 求解的结果极其依赖于初始值;

(3)遗传算法的优点:

  1. 能够求出优化问题的全局最优解;
  2. 优化结果与初始值无关;
  3. 算法独立于求解域(不要求可微、可导);
  4. 以编码方式工作,可并行搜索多个峰值;
  5. 具有较强的鲁棒性;
  6. 适合求解复杂的优化问题;
  7. 应用较为广泛;

(4)遗传算法的缺点:

  1. 收敛速度慢;
  2. 局部搜索能力差;
  3. 控制变量较多;
  4. 无确定的终止准则;

 

 

参考文献:

  1. 非常好的理解遗传算法的例子
  2. 传统优化算法与遗传算法之间的优缺点和特点比较
  3. 遗传算法详解(GA)(个人觉得很形象,很适合初学者)

发表评论

电子邮件地址不会被公开。 必填项已用*标注