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

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

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

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

где $N$ это количество особей в популяции.

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

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

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

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

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

В 2011 году был представлен очень простой алгоритм, основанный на «стохастическом принятии». ^[3] Алгоритм случайным образом выбирает человека (скажем, $i$ ) и принимает выбор с вероятностью $f_{i}/f_{M}$ , где $f_{M}$ – максимальная приспособленность популяции. Определенный анализ показывает, что стохастическая приемочная версия имеет значительно лучшую производительность, чем версии, основанные на линейном или бинарном поиске, особенно в приложениях, где значения пригодности могут меняться во время прогона. ^[4] Хотя этот алгоритм обычно работает быстро, некоторые распределения приспособленности (например, экспоненциальные распределения) могут потребовать $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 или близок к нему. Тогда вот как случайным образом выбрать человека:

случайное_номер # От 0,0 до 1,0 если  случайное_число < 0,1    выберите  1  иначе, если  случайное_число < 0,3 # 0,3 − 0,1 = вероятность 0,2    выберите  2  иначе, если  случайное_число < 0,6 # 0,6 - 0,3 = вероятность 0,3    выберите  3  иначе, если  случайное_число < 1,0 # 1,0 − 0,6 = вероятность 0,4    выберите  4  конца, если

См. также

Ссылки

^ Бэк, Томас, Эволюционные алгоритмы в теории и практике (1996), стр. 120, Оксфордский университет. Нажимать
^ Бликль, Тобиас; Тиле, Лотар (1996). «Сравнение схем отбора, используемых в эволюционных алгоритмах». Эволюционные вычисления . 4 (4): 361–394. дои : 10.1162/evco.1996.4.4.361 . ISSN 1063-6560 . S2CID 42718510 .
^ А. Липовски, Выбор колеса рулетки посредством стохастического принятия (arXiv:1109.3627) [1]
^ Быстрый пропорциональный выбор

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

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

[1] Бэк, Томас, Эволюционные алгоритмы в теории и практике (1996), стр. 120, Оксфордский университет. Нажимать

[2] Бликль, Тобиас; Тиле, Лотар (1996). «Сравнение схем отбора, используемых в эволюционных алгоритмах». Эволюционные вычисления . 4 (4): 361–394. дои : 10.1162/evco.1996.4.4.361 . ISSN 1063-6560 . S2CID 42718510 .

[3] А. Липовски, Выбор колеса рулетки посредством стохастического принятия (arXiv:1109.3627) [1]

[4] Быстрый пропорциональный выбор

[1]

[2]

[3]

[4]