遗传算法GA交叉算子最详细讲解

首席躺平官 2021-07-28 16:08:43 阅读: 4350

遗传算法通过交叉算子来维持种群的多样性，应该说交叉算子是遗传算法中最重要的操作。针对不同的优化问题，有多种不同的交叉算子

单点交叉

单点交叉通过选取两条染色体，在随机选择的位置点上进行分割并交换右侧的部分，从而得到两个不同的子染色体。单点交叉是经典的交叉形式，与多点交叉或均匀交叉相比，它交叉混合的速度较慢（因为将染色体分成两段进行交叉，这种方式交叉粒度较大），然而对于选取交叉点位置具有一定内在含义的问题而言，单点交叉可以造成更小的破坏。

两点交叉

两点交叉是指在个体染色体中随机设置了两个交叉点，然后再进行部分基因交换。两点交叉的具体操作过程是：

在相互配对的两个个体编码串中随机设置两个交叉点；

交换两个个体在所设定的两个交叉点之间的部分染色体。

多点交叉

多点交叉或称广义交叉，是指在个体染色体中随机设置多个交叉点，然后进行基因交换。其操作过程与单点交叉和两点交叉相类似。如果多点交叉只选择了一个交叉点，那么多点交叉就变成了单点交叉。

部分匹配交叉

部分匹配交叉保证了每个染色体中的基因仅出现一次，通过该交叉策略在一个染色体中不会出现重复的基因，所以PMX经常用于旅行商（TSP）或其他排序问题编码。

PMX类似于两点交叉，通过随机选择两个交叉点确定交叉区域。执行交叉后一般会得到两个无效的染色体，个别基因会出现重复的情况，为了修复染色体，可以在交叉区域内建立每个染色体的匹配关系，然后在交叉区域外对重复基因应用此匹配关系就可以消除冲突。

Step1：随机选择一对染色体（父代）中几个基因的起止位置（两染色体被选位置相同）。

Step2：交换这两组基因的位置。

Step3：做冲突检测，根据交换的两组基因建立一个映射关系，如下图所示，以7-5-2这一映射关系为例，可以看到第二步结果中子代1存在两个基因7，这时将其通过映射关系转变为基因2，以此类推至没有冲突为止。最后所有冲突的基因都会经过映射，保证形成的新一对子代基因无冲突。

最终结果为：

最终动画为

均匀交叉

顺序交叉

在两个父代染色体中随机选择起始和结束位置，将父代染色体1该区域内的基因复制到子代1相同位置上，再在父代染色体2上将子代1中缺少的基因按照顺序填入。另一个子代以类似方式得到。与PMX不同的是，OX不用进行冲突检测工作（实际上也只有PMX需要做冲突检测）。

基于位置的交叉

基于顺序的交叉

在两个父代染色体中随机选择几个位置，位置可以不连续，先在父代染色体2中找到父代染色体1被选中基因的位置，再用父代染色体2中其余的基因生成子代，并保证位置对应，将父代染色体1中被选择的基因按顺序放入子代剩余位置中。另一个子代以类似方式得到。OBX与PBX相比，生成子代的“基础”基因来源不同，PBX来自被选中基因，OBX来自剩余基因。