Пропорциональный выбор по пригодности

Пропорциональный отбор по пригодности , также известный как отбор по принципу рулетки или отбор по принципу вращающегося колеса , представляет собой метод отбора , используемый в эволюционных алгоритмах для отбора потенциально полезных решений для рекомбинации . ^[1]

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

${\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), будет использование метода псевдонимов .

В 2011 году был представлен очень простой алгоритм, основанный на «стохастическом принятии». ^[2] Алгоритм случайным образом выбирает особь (например, ) и принимает выбор с вероятностью , где — максимальная приспособленность в популяции. Определенный анализ показывает, что версия стохастического принятия имеет значительно лучшую производительность, чем версии, основанные на линейном или бинарном поиске, особенно в приложениях, где значения приспособленности могут меняться во время выполнения. ^[3] Хотя поведение этого алгоритма обычно быстрое, некоторые распределения приспособленности (например, экспоненциальные распределения) могут потребовать итераций в худшем случае. Этот алгоритм также требует больше случайных чисел, чем бинарный поиск.${\displaystyle я}$${\displaystyle f_{i}/f_{M}}$${\displaystyle f_{M}}$${\displaystyle O(n)}$

Например, если у вас есть популяция с приспособленностями [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 /

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

сумма_пригодности = 10предыдущая_вероятность = 0.0[1] = предыдущая_вероятность + (приспособленность / сумма_приспособленности) = 0,0 + (1 / 10) = 0,1предыдущая_вероятность = 0,1[2] = предыдущая_вероятность + (приспособленность / сумма_приспособленности) = 0,1 + (2 / 10) = 0,3предыдущая_вероятность = 0,3[3] = предыдущая_вероятность + (приспособленность / сумма_приспособленности) = 0,3 + (3 / 10) = 0,6предыдущая_вероятность = 0,6[4] = предыдущая_вероятность + (приспособленность / сумма_приспособленности) = 0,6 + (4 / 10) = 1,0

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

random_number # Между 0,0 и 1,0если случайное_число < 0,1 выберите 1 иначе если random_number < 0.3 # 0.3 − 0.1 = 0.2 вероятность выберите 2 иначе если random_number < 0.6 # 0.6 − 0.3 = 0.3 вероятность выберите 3 иначе если random_number < 1.0 # 1.0 − 0.6 = 0.4 вероятность выберите 4 конец, если

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

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

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