3

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）不可能计算所有排序的概率。我想使用遗传算法来解决这个问题。

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

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

可以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”的序列复制并粘贴到第二个排序。

版本：不对称 TSP 可以变成对称 TSP，但有禁止的子排序，这使得 GA 方法不适合。

4

3 回答 3

3

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

我将提供一些关于句法元素的信息——你如何以有意义的方式进行交叉和/或突变。显然，正如您在与 TSP 平行时所指出的那样，您有一个排列问题。因此，如果您想使用 GA，候选解决方案的自然表示只是您的点的有序列表，小心避免重复 - 即排列。

TSP 就是这样一个排列问题，您可以从 TSP 算法中获取并直接使用许多交叉运算符（例如Edge Assembly Crossover ）。但是，我认为您会遇到这种方法的问题。基本上，问题是这样的：在 TSP 中，解决方案的重要质量是邻接性。也就是说，abcd与cdab具有相同的适应度，因为它是相同的游览，只是在不同的城市开始和结束。在您的示例中，绝对位置比这种相对位置的概念重要得多。abcd在某种意义上意味着a是最好的点——重要的是它排在列表的首位。

要获得有效的交叉算子，您必须做的关键是考虑使它们成为良好的父项中的属性，并尝试准确地提取和组合这些属性。Nick Radcliffe 称之为“尊重重组”（请注意，论文相当古老，现在对理论的理解有所不同，但原理是合理的）。采用 TSP 设计的运算符并将其应用于您的问题将最终产生试图保存来自父母的不相关信息的后代。

理想情况下，您需要一个尝试在字符串中保留绝对位置的运算符。我所知道的最好的副手称为 Cycle Crossover (CX)。我想念一个很好的参考资料，但我可以向您指出一些我在研究生工作中实现它的代码。CX 的基本思想描述起来相当复杂，而且在实际操作中更容易看到。采取以下两点：

abcdefgh
cfhgedba

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

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

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

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

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

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

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

  8. 对循环中包含的头寸进行交换。

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

cbhdefga
afcgedbh
X X    X

继续寻找和交换周期，直到你完成。

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

请注意，您可能会从针对您的特定域进行更多定制的事情中获得很多。我认为像 CX 这样的东西会比基于 TSP 运算符的东西更好的黑盒算法，但黑盒通常是最后的手段。其他人的建议可能会引导您获得更好的整体算法。

于 2012-04-16T12:19:06.627 回答
2

我研究了一个有点类似的排名问题，并遵循了类似于我在下面描述的技术。这对你有用吗：

假设value对象的未知数通过某种分布（例如，正态分布）偏离您的估计。解释您的排名陈述，例如a > b, 0.9陈述“价值a位于以 为中心的分布的 90% 百分位b”。

对于每个语句：

def realArrival = calculate a's location on a distribution centered on b
def arrivalGap = | realArrival - expectedArrival | 
def fitness = Σ arrivalGap

健身功能是MIN(fitness)

FWIW，我的问题实际上是一个装箱问题，其中相当于您的“排名”语句是用户提供的排名（1、2、3 等）。所以不是TSP，而是NP-Hard。OTOH，装箱有一个与接受的错误成比例的伪多项式解决方案，这是我最终使用的。我不太确定这是否适用于您的概率排名陈述。

于 2012-04-14T18:50:48.247 回答
2

多么有趣的问题！如果我理解它，你真正要问的是：

“给定一个加权的有向图，图中的每个边权重表示弧线在正确方向上绘制的概率，返回具有最大概率成为图拓扑排序的完整节点序列。”

因此，如果您的图有 N 条边，则有 2^N 个不同可能性的图，其中一些排序出现在不止一个图中。

我不知道这是否会有所帮助（非常简短的谷歌搜索并没有启发我，但也许你会更加坚持不懈地取得更大的成功）但我的想法是寻找“拓扑排序”与任何“概率”相结合，“随机”，“噪声”或“错误”（因为边缘权重可以被视为可靠性因素）可能会有所帮助。

不过，我强烈质疑您的断言，在您的示例中，不需要 P(a>c)。您最了解您的应用程序空间，但在我看来，指定 P(a>c) = 0.99 将给出与指定 P(a>c) = 0.01 不同的 f(abc) 适应度。

您可能还想加入“贝叶斯”，因为根据您的条件和假设的解决方案，您可能能够开始推断（在您的示例中） P(a>c) 的值。问题是，“拓扑排序”和“贝叶斯”会给你带来一大堆与马尔可夫链和马尔可夫决策问题相关的命中，这可能有帮助，也可能没有帮助。

于 2012-04-14T22:02:23.427 回答