用遗传算法建立排名，

BIG 版本后的问题：

我需要使用遗传算法建立排名，我有这样的数据：

P(a>b)=0.9
P(b>c)=0.7
P(c>d)=0.8
P(b>d)=0.3

现在，让我们解释一下a,b,c,d作为足球队的名称，以及P(x>y)是概率x赢与y。我们想要建立团队排名，但我们缺乏一些观察P(a>d),P(a>c)由于a vs d 和a vs c 之间缺少比赛而缺失。 目标是找到最能描述四支球队联盟现状的球队名称排序。

如果我们只有 4 支球队，那么解决方案就很简单，首先我们计算所有球队的概率4!=24四支球队的排序，同时忽略缺失值，我们有：

P(abcd)=P(a>b)P(b>c)P(c>d)P(b>d)

P(abdc)=P(a>b)P(b>c)(1-P(c>d))P(b>d)

...

P(dcba)=(1-P(a>b))(1-P(b>c))(1-P(c>d))(1-P(b>d))

我们选择概率最高的排名。我不想使用任何其他健身功能。

我的问题 ：

由于 n 个元素的排列数为n!计算所有的概率 对于大 n 来说，排序是不可能的（我的 n 约为 40）。我想用遗传算法来解决这个问题。

变异运算符是两个（或更多）排名元素位置的简单交换。

但是如何使两个排序交叉呢？

Could P(abcd)被解释为非对称 TSP 问题中路径“abcd”的成本函数，但从 x 到 y 的成本与从 y 到 x 的成本不同，P(x>y)=1-P(y<x)？ TSP问题有很多交叉算子，但我想我必须设计自己的交叉算子，因为我的问题与TSP略有不同。您对解决方案或概念分析框架有什么想法吗？

在概念和实现层面上，最简单的方法是使用交叉运算符，它可以在两个解决方案之间交换子顺序：

CrossOver(ABcD,AcDB) = AcBD

对于元素的随机子集（在本例中为大写字母“a，b，d”），我们将第一个子排序 - 元素“a，b，d”的序列复制并粘贴到第二个排序。

Edition：非对称 TSP 可以转化为对称 TSP，但具有禁止的子排序，这使得 GA 方法不适合。

这绝对是一个有趣的问题，似乎大多数答案和评论都集中在问题的语义方面（即适应度函数的含义等）。

我将补充一些有关句法元素的信息——如何以有意义的方式进行交叉和/或变异。显然，正如您在与 TSP 的相似之处所指出的，您遇到了排列问题。因此，如果您想使用 GA，候选解决方案的自然表示就是您的点的有序列表，小心避免重复 - 即排列。

TSP 就是这样一种排列问题，并且有许多交叉算子（例如，边缘组装交叉 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.5015）您可以从 TSP 算法中获取并直接使用。但是，我认为您会遇到这种方法的问题。基本上，问题是这样的：在 TSP 中，解决方案的重要质量是邻接。那是，abcd具有相同的适应度cdab，因为这是同一次旅行，只是在不同的城市开始和结束。在你的例子中，absolute立场比这个概念重要得多relative位置。abcd在某种意义上意味着a是最好的一点——重要的是它排在列表的第一位。

要获得有效的交叉算子，关键的事情是考虑父代中哪些属性使它们变得优秀，并尝试准确地提取和组合这些属性。尼克·雷德克利夫称这种“尊重的重组” http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.5083（请注意，这篇论文相当古老，现在对理论的理解有点不同，但原理是合理的）。采用 TSP 设计的算子并将其应用于您的问题，最终会产生试图保存来自父母的不相关信息的后代。

理想情况下，您需要一个尝试保存的操作员absolute字符串中的位置。我所知道的最好的即兴产品被称为“Cycle Crossover”（CX）。我脑子里缺少一个很好的参考，但我可以给你指出我在研究生工作中实现了一些代码 https://github.com/deong/sls/blob/master/src/crossover.cpp。 CX 的基本思想描述起来相当复杂，但在实践中更容易理解。采取以下两点：

abcdefgh
cfhgedba

1. 在父级 1 中随机选择一个起点。为简单起见，我将从位置 0 的“a”开始。

2. 现在直接下降到父级 2，并观察那里的值（在本例中为“c”）。

3. 现在在父级 1 中搜索“c”。我们在位置 2 处找到它。

4. 现在再次垂直下降，观察父项 2 中位置 2 的“h”。

5. 再次在父级 1 中搜索这个“h”，在位置 7 处找到。

6. 直接下降并观察父级 2 中的“a”。

7. 此时请注意，如果我们在父级中搜索“a”，我们将到达我们已经到达的位置。继续过去就会循环。事实上，我们将访问的位置序列 (0, 2, 7) 称为“循环”。请注意，我们可以简单地在父母作为一个组之间交换这些位置上的值，并且两个父母都将保留排列属性，因为我们在两个父母的循环中的每个位置上都有相同的三个值，只是顺序不同。

8. 交换循环中包含的位置。

请注意，这只是一个周期。然后，每次从新的（未访问过的）位置开始重复此过程，直到所有位置都包含在一个循环中。在上述步骤中描述的一次迭代之后，您将获得以下字符串（其中“X”表示循环中在父级之间交换值的位置）。

cbhdefga
afcgedbh
X X    X

只要继续寻找和交换循环，直到完成。

我从 github 帐户链接的代码将与我自己的元启发式框架紧密绑定，但我认为从代码中提取基本算法并使其适应您自己的系统是一项相当简单的任务。

请注意，通过针对您的特定领域进行更定制的操作，您可能会获得很多收益。我认为像 CX 这样的东西会比基于 TSP 算子的东西产生更好的黑盒算法，但黑盒通常是最后的手段。其他人的建议可能会引导您获得更好的整体算法。