使用遗传算法构建排名

Question

使用遗传算法构建排名

optimizationgenetic-algorithmrankingmathematical-optimizationtraveling-salesman

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的概率。我们想要建立团队排名，由于缺乏a与d和a与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。虽然有许多TSP问题的交叉算子，但我认为我必须设计自己的交叉算子，因为我的问题与TSP略有不同。您是否有任何解决方案或概念分析框架的想法？



在随机选择的元素子集（在此示例中为大写字母'a，b，d'）上，我们将第一个子序列 - 元素序列'a，b，d'复制并粘贴到第二个排序中，以实现交叉操作：

CrossOver(ABcD,AcDB) = AcBD

编辑：非对称TSP可以变为带有禁止的子序列的对称TSP，这使得GA方法不适用。

- Qbik

遗传算法优化参数以最大化或最小化适应值。您能否编写一个包含所有数据的适应函数？在TSP中，它将是总距离的计算。 - Stephan

在我看来，如果以 b,c,d,a 为例，总概率应该被最大化。你可以计算适应度函数 f(b,c,d,a) = p(b>c) * p(c>d) * p(d>a)。但是 p(d>a) 是什么呢？如果你计算出它，剩下的就很容易了。 - Stephan

我知道如何计算适应函数，例如对于给定的数据：a>b, 0.9，b>c, 0.7，f(abc)=p(a>b)*p(b>c)，而对于f(acb)=p(a>b)*(1-p(b>c))，它非常简单，不需要考虑p(a>c)的概率。 - Qbik

你的方法不正确。你没有计算出a和c的排名。在你的公式中，你计算了p(a>b)和p(c>b)，但这并不意味着p(a>c)。如果你知道a大于b且c大于b，你并不知道a是否大于、小于或等于c。 - Stephan

3个回答

2

这是一个有趣的问题！如果我理解正确，你实际上想问的是：

“给定一个带权有向图，图中每条边的权重表示该弧被正确方向连接的概率，返回最大可能成为该图拓扑排序的完整节点序列。”

因此，如果你的图有N条边，则有2^N个具有不同概率的图，其中某些顺序在多个图中出现。

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

然而，我强烈质疑你在例子中所说的不需要P(a>c)。你最了解你的应用领域，但在我看来，指定P(a>c)=0.99将为f(abc)提供与指定P(a>c)=0.01不同的适应度。

你可能还想加入“贝叶斯”，因为你可以开始推断（在你的例子中）P(a>c)的值，给定你的条件和假设解决方案。问题是，“拓扑排序”和“贝叶斯”将给你一大堆与马尔可夫链和马尔可夫决策问题相关的结果，这可能有助于解决问题，也可能没有。

- Novak

谢谢回答，但拓扑排序仅适用于没有有向环的图。 - Qbik

没错，我在想一组数据的解释，例如 P(a>b) = P(b>c) = P(c>a) = .5。显然，按照我提出的形式，图形具有循环，并且没有拓扑排序，因为这些条件不能同时成立。但是，P(a>b) = P(b>c) = P(a>c) = .5 是完全相同的问题，对吧？而且那个图形确实有一个拓扑排序。所以，就像我说的，可能没有用，但这是我首先想到的事情。 - Novak

2

我曾经处理过一个类似的排名问题，并采用了下面所描述的技术。以下方法是否适合您：

假设目标对象的未知值通过某个分布（如正态分布）与您的估计存在差异。将您的排名语句解释为“值 a 处于以 b 为中心的分布的第90百分位数”的语句，例如 a > b, 0.9。

对于每个语句：

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

健身函数是 MIN(fitness)

顺便提一下，我的问题实际上是一个装箱问题，其中你所说的“rank”语句的等效物是用户提供的排名（1、2、3等）。因此不完全是TSP，但是属于NP-Hard。另一方面，装箱问题具有伪多项式解，与接受的误差成比例，这正是我最终使用的方法。我不太确定这是否适用于你的概率排名语句。

- Larry OBrien

是的，你的问题和我的非常相似。但我不知道你和我数据中缺失的观察是否有相同的解释。你的问题有什么解决方案吗？能提供一些提示吗？ - Qbik

我使用了我提到的伪多项式背包算法，正如Vazirani的《近似算法》中所描述的那样。http://www.amazon.com/Approximation-Algorithms-Vijay-V-Vazirani/dp/3642084699/ref=sr_1_3?ie=UTF8&qid=1334601580&sr=8-3但说实话，领域专家反对使用排名作为隐藏价值的代理，因为他们有意地操纵排名，试图玩弄现有的算法。所以我从来没有把它投入生产 :-(（哦，我们没有缺失数据...） - Larry OBrien

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- deong · Accepted Answer

这绝对是一个有趣的问题，似乎大多数答案和评论都集中在问题的语义方面（即适应度函数的含义等）。我会提供一些关于句法元素的信息--如何以合理的方式进行交叉和/或变异。显然，正如您指出的与TSP的类比，您有一个排列问题。因此，如果您想使用GA，则候选解的自然表示形式只是您的点的有序列表，注意避免重复--也就是一个排列。

TSP是一种排列问题，有许多交叉算子（例如 Edge Assembly Crossover）可以从TSP算法中直接使用。然而，我认为你会遇到问题。基本上，问题在于：在TSP中，解决方案的重要质量是邻接性。也就是说，abcd与cdab具有相同的适应度，因为它们是相同的旅行路线，只是起点和终点不同。在你的例子中，绝对位置比相对位置更重要。abcd在某种意义上意味着a是最好的点--它很重要，因为它在列表中排名第一。

要获得有效的交叉算子，关键是要考虑父代中使它们优秀的属性，并尝试提取和组合这些属性。Nick Radcliffe 称之为“尊重重组”（请注意，该论文相当古老，现在的理论有所不同，但原则是正确的）。将 TSP 设计的算子应用于您的问题将会产生试图保留父代中无关信息的后代。

最好的算子应该尝试保留字符串中的绝对位置。我知道的最好的算子是 Cycle Crossover (CX)。我暂时想不起一个好的参考文献，但我可以指向我在研究生工作中实施它的代码。 CX 的基本思想很难描述，但在实际操作中更容易理解。取以下两个点为例：

abcdefgh
cfhgedba

随机选择父代1中的起始点。为了简单起见，我将从位置0开始，使用字母"a"。
现在直接跳到父代2，并观察那里的值（在这种情况下是"c"）。
现在在父代1中搜索“c”。我们发现它位于位置2。
再次直接跳下去，在父代2中观察到位置2的“h”。
同样，在父代1中搜索此“h”，在位置7处找到。
直接下降并观察父代2中的“a”。
此时请注意，如果我们在父代1中搜索“a”，则会到达一个已经访问过的位置。继续超过该位置只会循环。事实上，我们称访问的位置序列（0、2、7）为“循环”。请注意，我们可以简单地在父代之间交换包含在循环中的这些位置的值，并且两个父代都将保留排列属性，因为对于两个父代，在循环的每个位置上都有相同的三个值，只是顺序不同。
交换循环中包含的位置。

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

cbhdefga
afcgedbh
X X    X

只需继续查找和交换循环，直到完成。

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

请注意，您可以通过对特定领域进行更多定制化的操作来获得相当大的收益。我认为像CX这样的东西会比基于TSP运算符的东西更好地成为黑匣子算法，但黑匣子通常是最后的手段。其他人的建议可能会引导您找到更好的整体算法。