c# - TSP遗传算法中的交叉操作

Question

我正在尝试解决 Travelling Salesman Problem (TSP)与 Genetic algorithm .我的基因组是图中顶点的排列(推销员的路径)。

我应该如何对我的基因组进行交叉操作？

在哪里可以找到我的问题在 C# 中的实现？

Answer 1

您应该查看 Gokturk Ucoluk 的“Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation”。它概述了用于排列的特殊交叉运算符，并提出了一种巧妙的排列表示形式，可以很好地与标准交叉配合使用(即交叉两个排列总是产生两个排列)。

关键的见解是将排列表示为它的反转序列，即对于每个元素 i，在 a[i] 中存储有多少元素大于 i 在排列中位于 i 的左侧。与直接表示不同，a[i] 的唯一约束是局部的，即 a[i] 不能大于 N - i。这意味着两个有效反转序列的简单交叉总是产生两个有效反转序列 - 无需对重复元素进行特殊处理。