基于差分进化（Differential Evolution）求解旅行商问题的交叉与变异方法问询

这确实是个非常关键的卡点——传统差分进化是为连续数值优化设计的，直接套用a + F×(b - c)的公式在TSP的排列向量上完全行不通，因为会出现重复元素、非整数甚至无效值，根本不符合TSP解的要求。下面我结合你给出的例子（先修正第二个向量里的重复问题，把[1, 5, 2, 0, 3, 5]调整为合法的排列[1,5,2,0,3,4]），一步步讲怎么改造DE的操作来适配TSP：

一、变异操作：从连续数值加减到离散排列扰动 #

传统DE的变异是通过三个父代个体生成变异向量，但对排列来说，我们需要把“差分”的概念转化为排列的差异调整，常见的适配策略有两种：

1. 基于位置交换的启发式变异 #

假设我们选三个父代：

• X1 = [1, 4, 0, 3, 2, 5]（你的第一个向量）
• X2 = [1, 5, 2, 0, 3, 4]（修正后的第二个向量）
• X3 = [4, 2, 0, 5, 1, 3]（你的第三个向量）

步骤如下：

• 首先找出X2和X3之间的位置差异：遍历每个位置，记录X2和X3元素不同的位置（这里两个向量几乎全不同，共6个差异位置）
• 根据缩放因子F（比如F=0.5），计算需要选取的操作数量：总差异数×F = 6×0.5=3个
• 随机选3个差异位置，比如位置1、3、5：
  • X2在位置1的元素是5，X3在位置1的元素是2 → 在X1中交换元素5（位置5）和2（位置4）的位置
  • X2在位置3的元素是0，X3在位置3的元素是5 → 在X1中交换元素0（位置2）和5（现在在位置4）的位置
  • X2在位置5的元素是4，X3在位置5的元素是3 → 在X1中交换元素4（位置1）和3（位置3）的位置
• 最终得到的变异向量V = [1, 3, 5, 4, 0, 2]（这是一个合法的无重复排列）

2. 基于顺序的变异 #

另一种思路是提取X2和X3中元素的相对顺序差异，然后将部分差异应用到X1上：

• 比如X2的元素顺序是1→5→2→0→3→4，X3的顺序是4→2→0→5→1→3
• 选取两者共同的子序列（比如2→0），然后在X1中调整元素顺序，保留这个子序列，同时调整其他元素的位置，生成新的合法排列作为变异向量。

二、交叉操作：保证生成合法排列 #

传统DE的交叉（比如二项式交叉）会直接复制位置元素，这在排列中会导致重复，所以必须改成无重复的交叉策略，常用的有两种：

1. 部分映射交叉（PMX）+ DE交叉逻辑 #

结合DE的交叉概率CR（比如CR=0.7），步骤如下：

• 取原个体X1 = [1, 4, 0, 3, 2, 5]和变异向量V = [1, 3, 5, 4, 0, 2]
• 遍历每个位置j：
  • 生成随机数rand(0,1)，如果rand < CR，就尝试从V中取第j位的元素
  • 如果该元素还没在子代中出现，就保留；如果已经出现，就从X1中取第j位的元素，或者通过映射替换避免重复
• 更严谨的PMX流程：
  1. 随机选一个交叉区间，比如位置1-3
  2. 把X1的区间部分[4,0,3]放到子代对应位置，把V的区间部分[3,5,4]建立映射：4→3，0→5，3→4
  3. 对V的非区间部分[1,0,2]做映射替换（0替换为5），得到[1,5,2]
  4. 把替换后的非区间部分放到子代对应位置，最终得到合法子代：[1,4,0,3,5,2]

2. 顺序交叉（OX） #

这种方法更贴合TSP的路径特性：

• 随机选一个交叉区间，比如位置2-4
• 保留X1中该区间的元素[0,3,2]，保持原有顺序
• 从V中按顺序取出未在区间里的元素：1,5,4
• 把这些元素填充到子代的非区间位置，得到合法子代：[1,5,0,3,2,4]

三、核心总结 #

• 传统DE的连续数值操作必须完全改造为离散排列的操作，不能直接套用a + F×(b - c)公式
• 变异的核心是通过交换、顺序调整等方式，基于三个父代的差异生成新的合法排列
• 交叉的核心是保证生成的子代没有重复元素，同时保留父代的部分路径特征

内容的提问来源于stack exchange，提问作者Gomo55