建立与遗传算法排名，(Building ranking with genetic algorithm

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)丢失，由于缺乏VS 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问题，但从X行进到y的成本路径“ABCD”的代价函数大于从y中行进至x，成本不同P(x>y)=1-P(y<x) 有这么多的交叉运营商TSP问题，但我想我要设计我自己的交叉操作，因为我的问题是，从TSP略有不同。你有解决方案或框架概念分析任何想法？

最简单的方法，在概念和执行层面，就是用交叉操作，这使得两种解决方案之间suborderings的交流：

CrossOver(ABcD,AcDB) = AcBD

为元素的随机子集（在这种情况下，“A，B，d”大写字母），我们复制和粘贴第一subordering - 元素“A，B，d”来第二顺序的序列。

版：不对称TSP也可以变成对称TSP，但禁止suborderings，使GA做法不合适。

Answer 1:

这绝对是一个有趣的问题，似乎大部分的答案和评论都集中在这个问题的语义方面（即，健身功能等的意思）。

我会凑钱有关语法元素的一些信息 - 你是怎么做到的方式，意义交叉和/或突变。很显然，当你与平行于TSP指出，你有一个置换问题。所以，如果你想使用GA，候选方案的自然表现简直是贵点的有序列表，注意避免repitition - 即置换。

TSP是一个这样的排列问题，有一些交叉运营商（例如， Edge装配交叉），您可以从TSP算法和直接使用。不过，我觉得你有这种做法的问题。基本上，问题是这样的：在TSP，解决方案的重要的素质是邻居。也就是说，ABCD具有相同的健康，CDAB，因为它同游，刚开始，并在不同的城市结束。在你的榜样，绝对位置是多少，这个概念相对位置更重要。 ABCD指在一定意义上，一个是最好的一点-这一点很重要，它首先出现在列表中。

你必须做的就是有效的交叉操作的关键是要占到什么属性都使他们的好父母，并尝试提取并准确结合这些属性。尼克·拉德克利夫称之为“尊重重组” （注意，纸很旧，现在的理论理解有点不同，但原理是声音）。采取TSP-设计的操作员，并把它应用到你的问题将最终产生后代尽量节省从父母不相关的信息。

理想情况下，您需要试图保持在字符串中的绝对位置的运营商。最好的一个，我知道随便被称为循环交叉（CX）。我失去了一个很好的参考了我的头顶部，但我可以指出你的一些代码，我实现了它作为我的毕业作品的一部分。 CX的基本思想是相当复杂来形容，也更容易在行动中看到的。采取以下两点：

abcdefgh
cfhgedba

随机挑母1的起点。为简单起见，我就开始在与“一”位置0。
现在降直降成父2，并观察值出现（在这种情况下，“C”）。
现在搜索“C”父1.我们发现在位置2。
现在直降再下来，在父2，位置2遵守“H”。
再次，搜索在父1此“H”，在位置7找到。
降直降，并遵守“一个”父2。
此时注意，如果我们在父母一个搜索“一”，我们到达那里我们已经去过的位置。继续过去那种只会周期。事实上，我们所说的位置，我们参观的序列（0，2，7）一个“循环”。需要注意的是，我们可以简单地在父母之间的这些位置作为一个组交换价值和双方父母将保留排列的财产，因为我们在周期为父母双方各位置具有相同的三个值，只是不同的订单。
让包括循环中的位置的互换。

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

cbhdefga
afcgedbh
X X    X

只是不断寻找，直到你完成交换循环。

我从我的github帐户相关联的代码将被紧密结合我自己的启发式框架，但我认为这是一个相当简单的任务，从代码中提取的基本算法并使其适用于您自己的系统。

请注意，您可以潜在地做一些更加个性化您的特定领域取得了不少。我认为像CX将创造一个更美好的黑盒子算法比基于TSP运营商的东西，但黑匣子通常是最后的手段。其他人的建议，可能会带你到一个更好的整体算法。

Answer 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难问题。 OTOH，装箱具有正比于接受的错误，这是我最终使用伪多项式的解决方案。我不太肯定将与您概率排名语句的工作。