健身大比例的“轮盘赌”的选择的高效实现(Efficient Implementation of Fi

我目前正在写在C（如一个由彼得Klausler设计），我想实现一个健身比例选择这里（所描述的键盘布局优化算法PDF链接）：

随着轮盘赌选择您选择一个基于roullete轮模型群体成员。使一个饼图，其中一个构件的切片到整个圆的面积是成员音响适应度与总人口的比率。正如你可以看到，如果在圆的圆周点随机拾取那些群体成员具有更高的适应度音响将有被挑选的概率更高。这确保自然选择发生。

问题是，我不知道如何有效地实现它。我认为有两种方法：一种是不可靠的，而另一种是缓慢的。

首先，慢之一：

对于长度为N的键盘池，创建的，其中阵列的每个元素实际上包含两个元素，最小和最大值长度N的阵列。每个键盘具有相应的最小值和最大值，该范围是基于键盘的健身。例如，如果键盘零有10健身，键盘一个具有20健身，和键盘二包含的25健身，它是这样的：代码：

array[0][0] = 0; // minimum
array[0][1] = 9; // maximum
array[1][0] = 10;
array[1][1] = 30;
array[2][0] = 31;
array[2][1] = 55;

（在这种情况下的下适应度为好，因为这意味着需要较少的努力。）

然后生成一个随机数。对于任何一个范围，这个数字属于，对应的键盘“封杀”，并用不同的键盘的后代所取代。根据需要重复此多次。

这里的问题是，它是非常缓慢的。这需要O（N ^ 2）的操作来完成。

接下来快1：

首先找出了键盘的最低和最高的适应度是。然后生成之间的随机数（最低健身）（适应度最高），并具有比生成的数字更高健身杀死所有的键盘。这是有效的，但它不能保证只杀一半的键盘。它也有从“轮盘赌”的选择有所不同机制，所以它甚至可能不适用。

所以，问题是，什么是有效的执行？

有这本书（第36页上有点高效的算法链接），但问题是，如果你做的轮盘赌选择只有一个或少数时候，它唯一有效的。有没有什么有效的方式做很多轮盘选择并行？

一方面，这听起来像你说的是不相宜的分数，如果你想“扼杀”您的选择（这很可能是与高分键盘）。

我认为没有必要维持两个数组。我认为，最简单的方法是保持分数的单一阵列，然后您可以遍历做出选择：

/* These will need to be populated at the outset */
int scores[100];
int totalScore;

for (gen = 0; gen < nGenerations; ++gen) {
    /* Perform a selection and update */
    int r = rand() % totalScore;        /* HACK: using % introduces bias */
    int t = 0;
    for (i = 0; i < 100; ++i) {
        t += scores[i];
        if (r < t) {
            /* Bingo! */
            totalScore -= scores[i];
            keyboards[i] = generate_new_keyboard_somehow();
            scores[i] = score_keyboard(keyboards[i]);
            totalScore += scores[i];    /* Now totalScore is correct again */
        }
    }
}

每个选择/更新需要O（n）的时间对于n键盘。