遗传算法通过交叉算子来维持种群的多样性,应该说交叉算子是遗传算法中最重要的操作。针对不同的优化问题,有多种不同的交叉算子
前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站
单点交叉
单点交叉通过选取两条染色体,在随机选择的位置点上进行分割并交换右侧的部分,从而得到两个不同的子染色体。单点交叉是经典的交叉形式,与多点交叉或均匀交叉相比,它交叉混合的速度较慢(因为将染色体分成两段进行交叉,这种方式交叉粒度较大),然而对于选取交叉点位置具有一定内在含义的问题而言,单点交叉可以造成更小的破坏。
两点交叉
两点交叉是指在个体染色体中随机设置了两个交叉点,然后再进行部分基因交换。两点交叉的具体操作过程是:
在相互配对的两个个体编码串中随机设置两个交叉点;
交换两个个体在所设定的两个交叉点之间的部分染色体。
多点交叉
多点交叉或称广义交叉,是指在个体染色体中随机设置多个交叉点,然后进行基因交换。其操作过程与单点交叉和两点交叉相类似。如果多点交叉只选择了一个交叉点,那么多点交叉就变成了单点交叉。
部分匹配交叉
部分匹配交叉保证了每个染色体中的基因仅出现一次,通过该交叉策略在一个染色体中不会出现重复的基因,所以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来自剩余基因。
循环交叉
过程如下:
在某个父代上随机选择1个基因,然后找到另一个父代相应位置上的基因编号,再回到第一个父代找到同编号的基因的位置,重复先前工作,直至形成一个环,环中的所有基因的位置即为最后选中的位置。