在 TSP 问题中，交叉操作生成的子代个体必须是有效的路径，即每个城市仅出现一次且包含所有城市。为实现这一目标，通常采用专门设计的交叉策略。以下是几种常见的交叉方法及其 Python 实现： ### 顺序交叉（Order Crossover, OX） 顺序交叉从一个父代中选取一个子序列，然后按照另一个父代的顺序填充未被选中的城市，确保子代中城市不重复[^2]。 ```python def ox_crossover(parent1, parent2): n = len(parent1) start, end = sorted(random.sample(range(n), 2)) child = [None] * n child[start:end] = parent1[start:end] current_pos = end for city in parent2[end:] + parent2[:end]: if city not in child: if current_pos >= n: current_pos = 0 child[current_pos] = city current_pos += 1 return child ``` ### 部分匹配交叉（Partially Matched Crossover, PMX） 部分匹配交叉通过建立映射关系来交换两个父代之间的城市，确保子代中每个城市仅出现一次。 ```python def pmx_crossover(parent1, parent2): n = len(parent1) start, end = sorted(random.sample(range(n), 2)) mapping = {} for i in range(start, end): mapping[parent1[i]] = parent2[i] mapping[parent2[i]] = parent1[i] child = parent1[:] for i in range(n): if start <= i < end: continue current = parent2[i] while current in mapping: current = mapping[current] child[i] = current return child ``` ### 循环交叉（Cycle Crossover, CX） 循环交叉基于城市在父代中的位置关系，通过构建循环路径来生成子代，确保每个城市仅出现一次[^3]。 ```python def cx_crossover(parent1, parent2): n = len(parent1) visited = [False] * n child = [None] * n for i in range(n): if not visited[i]: cycle = [] current = i while not visited[current]: visited[current] = True cycle.append(current) current = parent1.index(parent2[current]) for idx in cycle: child[idx] = parent1[idx] return child ``` ### 混合交叉（Cycle and Position Crossover, CPX） 混合交叉结合了循环交叉和位置交叉的思想，通过构建循环路径生成子代[^3]。 ```python def cpx_crossover(parent1, parent2): cycle = [parent1[0]] end = parent2[0] while end != parent1[0]: cycle.append(end) end = parent2[parent1.index(end)] child = parent1[:] for i in range(len(parent1)): if parent1[i] not in cycle: for j in range(len(parent2)): if parent2[j] not in cycle: child[i] = parent2[j] break return child ``` 这些交叉方法均能有效保证生成的子代路径是有效的排列序列，从而确保遗传算法在求解 TSP 问题时的可行性与稳定性。