Генетические алгоритмы — выбор родителей

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

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

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

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

Рассмотрим круговое колесо. Колесо делится на n пирогов , где n — количество особей в популяции. Каждый человек получает часть круга, которая пропорциональна его значению пригодности.

Возможны две реализации пропорционального выбора фитнеса —

Выбор колеса рулетки

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

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

Для реализации мы используем следующие шаги:

• Рассчитать S = сумма дел.

• Генерация случайного числа от 0 до S.

• Начиная с верхней части населения, продолжайте добавлять сферы к частичной сумме P, пока P <S.

• Индивидуум, для которого P превышает S, является выбранным индивидуумом.

Рассчитать S = сумма дел.

Генерация случайного числа от 0 до S.

Начиная с верхней части населения, продолжайте добавлять сферы к частичной сумме P, пока P <S.

Индивидуум, для которого P превышает S, является выбранным индивидуумом.

Стохастическая универсальная выборка (SUS)

Стохастическая универсальная выборка очень похожа на выбор колеса рулетки, однако вместо одной фиксированной точки мы имеем несколько фиксированных точек, как показано на следующем рисунке. Поэтому все родители выбираются всего за один оборот колеса. Кроме того, такая схема поощряет выбор подходящих людей хотя бы один раз.

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

Выбор турнира

В отборе турниров K-Way мы выбираем K человек из популяции случайно и выбираем лучших из них, чтобы стать родителями. Тот же процесс повторяется для выбора следующего родителя. Турнирный отбор также чрезвычайно популярен в литературе, поскольку он может работать даже с отрицательными значениями пригодности.

Выбор ранга

Выбор ранга также работает с отрицательными значениями пригодности и в основном используется, когда люди в популяции имеют очень близкие значения пригодности (это обычно происходит в конце цикла). Это приводит к тому, что каждый человек имеет почти равную долю пирога (как в случае соразмерного выбора пригодности), как показано на следующем изображении, и, следовательно, каждый человек, независимо от его соответствия относительно друг друга, имеет приблизительно одинаковую вероятность выбора в качестве родитель. Это, в свою очередь, приводит к потере давления отбора по отношению к более приспособленным людям, что делает ГА плохим выбором родителей в таких ситуациях.

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

Случайный выбор

В этой стратегии мы случайным образом выбираем родителей из существующего населения. Не существует давления отбора в отношении более приспособленных людей, и поэтому этой стратегии обычно избегают.