Генетические алгоритмы - отбор родителей
Отбор родителей - это процесс выбора родителей, которые спариваются и рекомбинируют для создания потомков для следующего поколения. Отбор родителей очень важен для скорости конвергенции ГА, поскольку хорошие родители подталкивают людей к лучшим и более подходящим решениям.
Однако следует позаботиться о том, чтобы одно чрезвычайно подходящее решение не захватило всю совокупность за несколько поколений, так как это приводит к тому, что решения находятся близко друг к другу в пространстве решений, что приводит к потере разнообразия. Maintaining good diversityв популяции чрезвычайно важен для успеха ГА. Этот захват всего населения одним чрезвычайно подходящим решением известен какpremature convergence и является нежелательным состоянием в ГА.
Пропорциональный отбор по фитнесу
Пропорциональный отбор по фитнесу - один из самых популярных способов родительского отбора. В этом случае каждый человек может стать родителем с вероятностью, пропорциональной его приспособленности. Следовательно, у более приспособленных особей больше шансов спариться и передать свои особенности следующему поколению. Следовательно, такая стратегия отбора применяет давление отбора к более подходящим особям в популяции, со временем развивая лучших особей.
Рассмотрим круглое колесо. Колесо делится наn pies, где n - количество особей в популяции. Каждый человек получает часть круга, пропорциональную его значению приспособленности.
Возможны две реализации пропорционального отбора по пригодности:
Выбор колеса рулетки
При выборе колеса рулетки круговое колесо делится, как описано ранее. На окружности колеса выбирается фиксированная точка, как показано, и колесо вращается. Область колеса, которая находится перед фиксированной точкой, выбирается в качестве родительской. Для второго родителя процесс повторяется.
Понятно, что у более сильного человека больше возможностей на колесе и, следовательно, больше шансов приземлиться перед фиксированной точкой при вращении колеса. Поэтому вероятность выбора индивидуума напрямую зависит от его приспособленности.
Для реализации мы используем следующие шаги -
Вычислите S = сумма тонкости.
Создайте случайное число от 0 до S.
Начиная с верхушки популяции, продолжайте добавлять тонкости к частичной сумме P, пока P <S.
Индивидуум, для которого P превышает S, является выбранным человеком.
Стохастическая универсальная выборка (SUS)
Стохастическая универсальная выборка очень похожа на выбор колеса рулетки, однако вместо одной фиксированной точки у нас есть несколько фиксированных точек, как показано на следующем изображении. Таким образом, все родители выбираются одним вращением колеса. Кроме того, такая установка поощряет выбор наиболее подходящих людей хотя бы один раз.
Следует отметить, что методы пропорционального выбора пригодности не работают в случаях, когда приспособленность может принимать отрицательные значения.
Выбор турнира
В отборе турниров K-Way мы случайным образом выбираем K человек из популяции и выбираем лучших из них, чтобы они стали родителями. Тот же процесс повторяется для выбора следующего родителя. Выбор турнира также чрезвычайно популярен в литературе, поскольку он может работать даже с отрицательными значениями пригодности.
Выбор ранга
Выбор ранга также работает с отрицательными значениями пригодности и в основном используется, когда люди в популяции имеют очень близкие значения приспособленности (обычно это происходит в конце пробега). Это приводит к тому, что каждый человек имеет почти равную долю пирога (как в случае выбора, пропорционального пригодности), как показано на следующем изображении, и, следовательно, каждый человек, независимо от того, насколько он подходит друг другу, имеет примерно одинаковую вероятность быть выбранным в качестве родитель. Это, в свою очередь, приводит к потере давления отбора в сторону более приспособленных людей, заставляя GA делать плохой выбор родителей в таких ситуациях.
Здесь мы убираем понятие фитнес-ценности при выборе родителя. Однако каждый человек в популяции оценивается в соответствии с его физической подготовкой. Выбор родителей зависит от ранга каждого человека, а не от пригодности. Люди с более высоким рейтингом предпочтительнее, чем лица с более низким рейтингом.
| Хромосома | Ценность фитнеса | Ранг |
|---|---|---|
| А | 8.1 | 1 |
| B | 8.0 | 4 |
| C | 8,05 | 2 |
| D | 7,95 | 6 |
| E | 8,02 | 3 |
| F | 7,99 | 5 |
Случайный выбор
В этой стратегии мы случайным образом выбираем родителей из существующей популяции. В отношении более подготовленных специалистов отсутствует давление отбора, поэтому этой стратегии обычно избегают.