Эффективная реализация фитнес-пропорции «Рулетка» Выбор

Question

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

с выбором рулетки вы выбираете членов населения на основе 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).

Следующая быстро один:

Первая цифра, что самые низкие и самые высокие приспособленности для клавиатур. Затем создайте случайное число между (наименьшая пригодность) и (наивысшая пригодность) и убейте все клавиатуры с физической пригодностью выше, чем сгенерированный номер. Это эффективно, но не гарантированно убить только половину клавиатуры. Он также имеет несколько другую механику от выбора «колеса рулетки», поэтому он может даже не применяться.

Итак, вопрос в том, что такое эффективная реализация?

На странице 36 этой книги есть несколько эффективный алгоритм (Link), но проблема в том, что он эффективен только в том случае, если вы делаете выбор в рулетке только один или несколько раз. Есть ли эффективный способ сделать много вариантов рулетки параллельно?

Answer 1

С одной стороны, это звучит, как вы говорите о непригодности очков, если вы хотите, чтобы «убить» ваш выбор (который, вероятно, будет клавиатурой с высоких баллов).

Я не вижу необходимости поддерживать два массива. Я думаю, что самый простой способ, чтобы сохранить единый массив оценок, которые вы затем перебирать, чтобы сделать выбор:

/* 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 (п) для п клавиатуры.