Введение

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

где — число индивидов в популяции. Это можно представить как рулетку в казино. Обычно каждой из возможных опций выбора на основе их значения пригодности присваивается часть колеса. Этого можно достичь, разделив пригодность решения на общую пригодность всех решений, тем самым нормализуя их до 1. Затем производится случайный выбор, аналогичный вращению колеса рулетки. Хотя вероятность исключения кандидатов с более высокой пригодностью будет меньше, все же существует шанс, что они могут быть исключены, поскольку вероятность их выбора меньше 1 (или 100%). Это отличается от менее сложного алгоритма отбора, такого как усеченный отбор, который исключает фиксированный процент самых слабых кандидатов. При пропорциональном отборе существует вероятность того, что некоторые более слабые решения могут пережить процесс отбора. Это связано с тем, что, хотя вероятность выживания более слабых решений невелика, она не равна нулю, что означает, что они все еще могут выжить; это преимущество, поскольку есть шанс, что даже слабые решения могут обладать некоторыми признаками или характеристиками, которые могут оказаться полезными после процесса рекомбинации. Аналогию с рулеткой можно представить, вообразив колесо рулетки, в котором каждое возможное решение представляет собой сектор на колесе; размер секторов пропорционален вероятности выбора решения. Выбор N хромосом из популяции эквивалентен игре в N игр на колесе рулетки, поскольку каждый кандидат выбирается независимо. Другие методы отбора, такие как стохастическая универсальная выборка или турнирный отбор, часто используются на практике. Это связано с тем, что они имеют меньший стохастический шум, или они быстры, просты в реализации и обеспечивают постоянное давление отбора. Наивная реализация выполняется путем первоначального построения кумулятивного распределения вероятностей (CDF) по списку индивидов, используя вероятность, пропорциональную пригодности индивида. Выбирается равномерное случайное число из диапазона [0,1), и обратное значение CDF для этого числа дает индивида. Это соответствует падению шарика рулетки в сектор индивида с вероятностью, пропорциональной его ширине. "Сектор", соответствующий обратному значению равномерного случайного числа, можно найти быстрее всего, используя двоичный поиск по элементам CDF. Выбор индивида занимает O(log n) времени. Более быстрая альтернатива, генерирующая индивидов за O(1) времени, — использование метода псевдонимов. В 2011 году был представлен очень простой алгоритм, основанный на "стохастическом принятии". Алгоритм случайным образом выбирает индивида (скажем, ) и принимает выбор с вероятностью , где — максимальная пригодность в популяции. Некоторые анализы показывают, что версия со стохастическим принятием имеет значительно лучшую производительность, чем версии, основанные на линейном или двоичном поиске, особенно в приложениях, где значения пригодности могут изменяться во время выполнения. Хотя поведение этого алгоритма обычно быстрое, некоторые распределения пригодности (например, экспоненциальные распределения) могут потребовать итераций в худшем случае. Этот алгоритм также требует больше случайных чисел, чем двоичный поиск.