Эффективная реализация фитнес-пропорционального выбора “Рулетки”

Question

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

С помощью функции выбора рулетки вы выбираете представителей населения на основе модели рулеточного колеса.Составьте круговую диаграмму, где площадь среза участника по отношению ко всей окружности равна отношению пригодности участника к общей численности населения.Как вы можете видеть, если точка на окружности круга выбрана случайным образом, то те члены популяции с более высокой физической подготовкой будут иметь более высокую вероятность быть выбранными.Это гарантирует, что происходит естественный отбор .

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

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

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

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 (n) времени для n клавиатур.