2019-04-16派森学习第148天

遗传算法中的crossover和VRP问题中的2-Opt算法。

交叉(crossover)

两个染色体的某一相同位置处DNA被切断，前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交；

2-opt算法

2-opt算法的核心在于随机选择一个区间段进行优化，这个优化只是对于当前一个状态的优化，并不是对全局的优化。

算法的步骤：

首先确定算法的最大迭代次数MAX，初始化一个计数器N用于记录迭代次数

1、随机一条初始化可选择的路线，途径所有城市，比如: A => B => C => D => E => F => G = > H => A， 假设这一条就是最短的路径。

2、 随机选择两个不同的途径的城市，反转这两个城市在内的中间的路线，比如随机选择（C、F）

那么此时老路径被分割成了三段:

（A => B） =>（ C => D => E => F ）=> （G = > H => A）

翻转后，得到的新路径：

（A => B） =>（ F => E => D => C ）=> （G = > H => A）

3、如果新路径（A => B => F => E => D => C => G = > H => A）的距离总长小于老路径（A => B => C => D => E => F => G = > H => A）距离总长，那么最短的路径变为新路径，计数器N=0；如果新路径距离总长大于老路径，那么老路径还是当前的最短路径，计数器N+1。如果 N ≥ MAX ， 算法结束，当前的路径就是最短路径（局部最优的最短路径）。

这个算法得到的路线是局部最优的，也就是它会根据迭代次数的不一样，可能呈现出不一样结果，并不是绝对正确的结果，只是优化后的相对正确。如果要得到绝对正确的结果，就需要把所有的路线都列出来计算所有的距离，这样就会爆炸。