Эффективное внедрение пропорционального фитнесу выбора рулетки

В настоящее время я пишу алгоритм оптимизации раскладки клавиатуры на 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 этой книги приведен довольно эффективный алгоритм (Link), но проблема в том, если вы делаете выбор рулетки только один или несколько раз. Есть ли какой-либо эффективный способ одновременного выбора нескольких вариантов рулетки?


c genetic-algorithm keyboard-layout roulette-wheel-selection
person Michael Dickens    schedule 14.08.2009    source источник
comment
Переформатируйте блок кода как код и исправьте ссылку на Google Книги.   -  person j_random_hacker    schedule 14.08.2009

Ответы (1)


arrow_upward
1
arrow_downward

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

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

/* 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 клавиатур.

person j_random_hacker    schedule 14.08.2009