Jump to content

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

Пример выбора одного человека

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

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

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

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

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

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

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

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

В 2011 году был представлен очень простой алгоритм, основанный на «стохастическом принятии». [3] Алгоритм случайным образом выбирает человека (скажем, ) и принимает выбор с вероятностью , где – максимальная приспособленность популяции. Определенный анализ показывает, что стохастическая приемочная версия имеет значительно лучшую производительность, чем версии, основанные на линейном или бинарном поиске, особенно в приложениях, где значения пригодности могут меняться во время прогона. [4] Хотя этот алгоритм обычно работает быстро, некоторые распределения приспособленности (например, экспоненциальные распределения) могут потребовать итерации в худшем случае. Этот алгоритм также требует больше случайных чисел, чем двоичный поиск.

Псевдокод

[ редактировать ]

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

См. также

[ редактировать ]
  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. ^ Быстрый пропорциональный выбор
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 79ca76fb0852644f6b926a00d98aebba__1687020180
URL1:https://arc.ask3.ru/arc/aa/79/ba/79ca76fb0852644f6b926a00d98aebba.html
Заголовок, (Title) документа по адресу, URL1:
Fitness proportionate selection - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)