Как организовать выбор колеса рулетки для несортированной популяции в генетическом алгоритме?

Question

Мой вопрос связан с этим: выбор колеса рулетки в генетическом алгоритме. Население должно быть отсортировано в первую очередь? Если мы не сортируем население, как организовать для него выбор колеса рулетки? Конечно, мы должны искать линейным способом сейчас. У вас есть какие-нибудь фрагменты кода на C++ или Java для этого случая?

Answer 1

Население вообще не нужно сортировать - ключом к выбору рулетки является то, что вероятность того, что данный человек будет выбран для размножения, пропорциональна его пригодности.

Допустим, у вас несортированная популяция со следующими особенностями:

[12, 45, 76, 32, 54, 21]

Для выбора рулетки вам нужно выбрать случайное число в диапазоне от 0 до 240 (сумма пригодности населения). Затем, начиная с первого элемента в списке, вычитайте пригодность каждого индивидуума, пока случайное число не станет меньше или равно нулю. Итак, в приведенном выше случае, если мы случайным образом выберем 112, мы сделаем следующее:

Step 1: 112 - 12 = 100. This is > 0, so continue.
Step 2: 100 - 45 = 55.  This is > 0, so continue.
Step 3: 55 - 76 = -21.  This is <= 0, so stop.

Поэтому мы выбираем человека № 3 для размножения. Обратите внимание, что это не требует сортировки населения вообще.

Итак, в псевдокоде это сводится к:

let s = sum of population fitness
let r = random number in range [0, s].
let i = 0.
while r > 0 do:
    r = r - fitness of individual #i
    increment i
select individual #i - 1 for reproduction.

Обратите внимание, что - 1 в последней строке, чтобы противодействовать increment i это делается в течение последней итерации цикла (потому что, хотя мы нашли нужного человека, он увеличивается независимо).