遗传算法中的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 ， 算法结束，当前的路径就是最短路径（局部最优的最短路径）。
这个算法得到的路线是局部最优的，也就是它会根据迭代次数的不一样，可能呈现出不一样结果，并不是绝对正确的结果，只是优化后的相对正确。如果要得到绝对正确的结果，就需要把所有的路线都列出来计算所有的距离，这样就会爆炸。
网友评论