Фитнес пропорциональный отбор - Fitness proportionate selection

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

При пропорциональном выборе пригодности, как и во всех методах отбора, функция приспособленности присваивает приспособленность возможным решениям или хромосомам . Этот уровень пригодности используется для связывания вероятности выбора с каждой отдельной хромосомой. Если это приспособленность особи в популяции, ее вероятность быть выбранной равна ${\ displaystyle f_ {i}}$${\ displaystyle i}$

${\ displaystyle p_ {i} = {\ frac {f_ {i}} {\ Sigma _ {j = 1} ^ {N} f_ {j}}},}$

где - количество особей в популяции. ${\ displaystyle N}$

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

Хотя вероятные решения с более высокой пригодностью будут исключены с меньшей вероятностью, все же существует вероятность того, что они могут быть исключены, поскольку их вероятность выбора меньше 1 (или 100%). Сравните это с менее сложным алгоритмом выбора, таким как выбор с усечением , который устранит фиксированный процент самых слабых кандидатов. При отборе, пропорциональном пригодности, есть шанс, что некоторые более слабые решения могут выжить в процессе отбора. Это потому, что даже несмотря на то, что вероятность того, что более слабые решения выживут, мала, она не равна нулю, что означает, что они все еще могут выжить; это преимущество, потому что есть шанс, что даже слабые решения могут иметь некоторые особенности или характеристики, которые могут оказаться полезными после процесса рекомбинации.

Аналогию с колесом рулетки можно представить, представив колесо рулетки, в котором каждое возможное решение представляет собой карман на колесе; размеры карманов пропорциональны вероятности выбора решения. Выбор N хромосом из популяции эквивалентен игре в N игр на колесе рулетки, поскольку каждый кандидат выбирается независимо.

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

Наивная реализация выполняется сначала путем создания кумулятивного распределения вероятностей (CDF) по списку лиц с использованием вероятности, пропорциональной приспособленности человека. Выбирается единообразное случайное число из диапазона [0,1), и инверсия CDF для этого числа дает индивидуальное значение. Это соответствует падению шарика рулетки в корзину человека с вероятностью, пропорциональной его ширине. «Бункер», соответствующий инверсии однородного случайного числа, может быть найден наиболее быстро с помощью двоичного поиска по элементам CDF. Чтобы выбрать человека, требуется время O (log n) . Более быстрой альтернативой, которая генерирует людей за время O (1), будет использование метода псевдонима .

Недавно был представлен очень простой алгоритм, основанный на «стохастическом принятии». Алгоритм случайным образом выбирает индивидуума (скажем ) и принимает выбор с вероятностью , где - максимальная приспособленность в популяции. Определенный анализ показывает, что версия стохастического принятия имеет значительно лучшую производительность, чем версии, основанные на линейном или двоичном поиске, особенно в приложениях, где значения пригодности могут изменяться во время выполнения. Хотя поведение этого алгоритма обычно быстрое, некоторые распределения пригодности (например, экспоненциальные распределения) могут потребовать итераций в худшем случае. Этот алгоритм также требует больше случайных чисел, чем двоичный поиск. ${\ displaystyle i}$${\ displaystyle f_ {i} / f_ {M}}$${\ displaystyle f_ {M}}$${\ Displaystyle О (п)}$

Псевдокод

Например, если у вас есть популяция с приспособленностями [1, 2, 3, 4], то сумма будет (1 + 2 + 3 + 4 = 10). Следовательно, вы хотите, чтобы вероятности или шансы были [1/10, 2/10, 3/10, 4/10] или [0,1, 0,2, 0,3, 0,4]. Если бы вы визуально нормализовали это значение между 0,0 и 1,0, оно было бы сгруппировано, как показано ниже, с [красный = 1/10, зеленый = 2/10, синий = 3/10, черный = 4/10]:

0.1 ]

0.2 \
0.3 /

0.4 \
0.5 |
0.6 /

0.7 \
0.8 |
0.9 |
1.0 /

Используя приведенные выше примеры чисел, вот как определить вероятности:

sum_of_fitness = 10
previous_probability = 0.0

[1] = previous_probability + (fitness / sum_of_fitness) = 0.0 + (1 / 10) = 0.1
previous_probability = 0.1

[2] = previous_probability + (fitness / sum_of_fitness) = 0.1 + (2 / 10) = 0.3
previous_probability = 0.3

[3] = previous_probability + (fitness / sum_of_fitness) = 0.3 + (3 / 10) = 0.6
previous_probability = 0.6

[4] = previous_probability + (fitness / sum_of_fitness) = 0.6 + (4 / 10) = 1.0

Последний индекс всегда должен быть 1.0 или близок к нему. Тогда вот как случайным образом выбрать человека:

random_number # Between 0.0 and 1.0

if random_number < 0.1
    select 1
else if random_number < 0.3 # 0.3 − 0.1 = 0.2 probability
    select 2
else if random_number < 0.6 # 0.6 − 0.3 = 0.3 probability
    select 3
else if random_number < 1.0 # 1.0 − 0.6 = 0.4 probability
    select 4
end if

Смотрите также

• Выбор на основе вознаграждения
• Стохастическая универсальная выборка
• Выбор турнира

Ссылки

внешние ссылки

• Реализация C (.tar.gz; см. Selector.cxx) WBL
• Пример выбора колеса рулетки
• Схема реализации версии O (1)