代码之家 › 专栏 › 技术社区 › Michael Dickens

有效实施健身比例“轮盘”选择

roulette-wheel-selection keyboard-layout genetic-algorithm c

Michael Dickens · 技术社区 · 17 年前

我目前正在用C语言编写一个键盘布局优化算法(比如由PeterKlausler设计的算法),我想实现一个合适的比例选择,如下所述( PDF Link ):

选择轮盘赌基于车轮模型。做馅饼图表,成员的区域切片与整个圆的比例是成员总数人口。就像你看到的那样在圆的圆周上是随机挑选那些人具有更高级别的成员将具有被选中的概率更高。这确保了自然选择需要地点。

问题是,我不知道如何有效地实施它。我想到了两种方法:一种是不可靠的,另一种是缓慢的。

首先,慢一点:

对于长度为n的键盘池,创建长度为n的数组,其中数组的每个元素实际上包含两个元素,最小值和最大值。每个键盘都有相应的最小值和最大值,范围基于键盘的适用性。例如,如果键盘0的适合度为10,键盘1的适合度为20,键盘2的适合度为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)个操作才能完成。

下一个是快的:

首先要弄清楚键盘的最低和最高安装是什么。然后生成一个介于(最低适配度)和(最高适配度)之间的随机数,并杀死所有适配度高于生成数的键盘。这是有效的,但不能保证只杀死一半的键盘。它与“轮盘赌”选择的机制也有些不同,因此它甚至可能不适用。

所以问题是,什么是有效的实现?

这本书第36页有一个比较有效的算法( Link ,但问题是,只有当你只做一次或几次轮盘选择时,它才是有效的。有没有什么有效的方法可以同时进行许多轮盘选择?

1 回复 | 直到 16 年前

j_random_hacker 17 年前

首先,听起来你好像在说 不适应 如果你想“扼杀”你的选择(很可能是一个键盘高的得分)。

我认为没有必要维护两个数组。我认为最简单的方法是维护一个单一的分数数组,然后迭代该数组以做出选择:

/* 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 */
        }
    }
}

对于n个键盘,每次选择/更新都需要O(n)个时间。