Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Пример выбора одного человека

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

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

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

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

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

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

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

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

Недавно был представлен очень простой алгоритм, основанный на «стохастическом принятии». [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 = 10previous_probability = 0,0[1] = предыдущая_возможность + (фитнес / сумма_фитнесс) = 0,0 + (1/10) = 0,1previous_probability = 0,1[2] = предыдущая_возможность + (фитнес / сумма_фитнесс) = 0,1 + (2/10) = 0,3previous_probability = 0,3[3] = предыдущая_возможность + (фитнес / сумма_фитнесс) = 0,3 + (3/10) = 0,6previous_probability = 0,6[4] = предыдущая_возможность + (фитнес / сумма_фитнесс) = 0,6 + (4/10) = 1,0

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

random_number # от 0,0 до 1,0если random_number <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 конец, если

См. Также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]