В настоящее время я пишу алгоритм оптимизации раскладки клавиатуры на C (например, разработанный Питером Клауслером), и я хочу реализовать пропорциональный выбор, как описано здесь (PDF Ссылка):

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.

Проблема в том, что я не вижу, как это эффективно реализовать. Я думал о двух методах: один ненадежный, а другой медленный.

Во-первых, медленный:

Для пула клавиатуры длиной N создайте массив длины N, где каждый элемент массива фактически содержит два элемента, минимальное и максимальное значение. Каждая клавиатура имеет соответствующее минимальное и максимальное значение, а диапазон зависит от пригодности клавиатуры. Например, если для клавиатуры «ноль» пригодность 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 этой книги есть несколько эффективный алгоритм (Ссылка на сайт), но проблема в том, что это эффективно, только если вы выбираете рулетку только один или несколько раз. Есть ли эффективный способ сделать много выборов рулетки параллельно?