有效地实现适合度的“轮盘赌".选拔 [英] Efficient Implementation of Fitness-Proportionate "Roulette" Selection

问题描述

我目前正在用C语言编写键盘布局优化算法(例如Peter Klausler设计的一种算法)，并且我想实现此处所述的适应性比例选择(

I am currently writing a keyboard layout optimization algorithm in C (such as the one designed by Peter Klausler) and I want to implement a fitness-proportionate selection as described here (PDF Link):

通过轮盘选择，您可以选择 人口的基础上 轮盘模型.做个馅饼 图表，成员所在的区域 切片与整个圆之比 成员适合度总数 人口.如你所见 在圆的圆周上是 随机选择那些人群 健身度更高的成员将拥有一个 被拣选的可能性更高. 这样可以确保自然选择 地方.

With roulette selection you select members of the population based on a roullete wheel model. Make a pie chart, where the area of a member’s slice to the whole circle is the ratio of the members fitness to the total population. As you can see if a point on the circumfrence of the circle is picked at random those population members with higher fitness will have a higher probability of being picked. This ensures natural selection takes place.

问题是，我看不到如何有效地实现它.我想到了两种方法:一种不可靠，另一种很慢.

The problem is, I don't see how to implement it efficiently. I've thought of two methods: one is unreliable, and the other is slow.

首先，慢一点:

对于长度为N的键盘池，创建一个长度为N的数组，其中数组的每个元素实际上包含两个元素，一个最小值和一个最大值.每个键盘都有对应的最小值和最大值，其范围取决于键盘的适用性.例如，如果键盘零的适应度为10，键盘一的适应度为20，而键盘二的适应度为25，则如下所示: 代码:

For a keyboard pool of length N, create an array of length N where each element of the array actually contains two elements, a minimum and a maximum value. Each keyboard has a corresponding minimum and maximum value, and the range is based on the fitness of the keyboard. For example, if keyboard zero has a fitness of 10, keyboard one has a fitness of 20, and keyboard two has a fitness of 25, it would look like this: Code:

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;

(在这种情况下，较低的适应性会更好，因为这意味着需要更少的精力.)

(In this case a lower fitness is better, since it means less effort is required.)

然后生成一个随机数.无论该数字落入哪个范围，相应的键盘都会被杀死"，并替换为其他键盘的后代.根据需要重复多次.

Then generate a random number. For whichever range that number falls into, the corresponding keyboard is "killed" and replaced with the offspring of a different keyboard. Repeat this as many times as desired.

与此有关的问题是它非常慢.需要O(N ^ 2)个操作才能完成.

The problem with this is that it is very slow. It takes O(N^2) operations to finish.

接下来是快速的:

首先弄清楚键盘的最低和最高适用性是什么.然后在(最低适用性)和(最高适用性)之间生成一个随机数，并杀死适用性高于所生成数字的所有键盘.这是有效的，但不能保证只杀死一半的键盘.与轮盘赌"选择相比，它的机制也有些不同，因此它甚至可能不适用.

First figure out what the lowest and highest fitnesses for the keyboards are. Then generate a random number between (lowest fitness) and (highest fitness) and kill all keyboards with a fitness higher than the generated number. This is efficient, but it's not guaranteed to only kill half the keyboards. It also has somewhat different mechanics from a "roulette wheel" selection, so it may not even be applicable.

问题是，什么是有效的实现?

So the question is, what is an efficient implementation?

本书第36页有一种效率较高的算法(

There is a somewhat efficient algorithm on page 36 of this book (Link), but the problem is, it's only efficient if you do the roulette selection only one or a few times. Is there any efficient way to do many roulette selections in parallel?

推荐答案

一方面，如果您想取消"您的选择，这听起来像是您在谈论不健康分数(这是可能是具有高分数的键盘).

For one thing, it sounds like you are talking about unfitness scores if you want to "kill off" your selection (which is likely to be a keyboard with high score).

我认为不需要维护两个数组.我认为最简单的方法是维护一个分数数组，然后反复进行选择:

I see no need to maintain two arrays. I think the simplest way is to maintain a single array of scores, which you then iterate through to make a choice:

/* 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)时间.

Each selection/update takes O(n) time for n keyboards.

这篇关于有效地实现适合度的“轮盘赌".选拔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！