32. Основные понятия га (Егор)

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

Популяция – это конечное множество особей

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

Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение.

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

33. Стратегии отбора для га (Егор)

Рассмотрим различные стратегии отбора родителей.

Панмиксия. Это самый простой оператор отбора. В соответствии с дан¬ной стратегией каждому члену популяции сопоставляется случайное целое число на отрезке [1; п], где п - количество особей в популяции. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффек¬тивность алгоритма, реализующего такой подход, снижается с ростом чис¬ленности популяции.

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

Ранговый отбор. Для каждой особи её вероятность попасть в промежу¬точную популяцию пропорциональна её порядковому номеру в отсортиро¬ванной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.

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

Аутбридинг. Использует понятие схожести особей, однако в этой стра¬тегии брачные пары формируются из максимально далёких особей.

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

Стратегии формирования нового поколения. Существует 2 основных типа формирования нового поколения после кроссовера и мутации:

- дети замещают родителей;

- новое поколение составляется из совокупности и детей, и их родителей.

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

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

Метод отжига (Больцмана). Вероятность отбора зависит от управляю¬щего параметра Т. Обычно вероятность попадания в новую популяцию вы¬числяется по следующей формуле: [нераспознанная формула]

где /(г) и /(j) - значения целевой функции г -й и j -й особей. Эти номера выбираются случайно. Если значение р окажется больше случайного числа на интервале (0; 1), то в новую популяцию попадёт особь /((), иначе f(j). Данный метод используется для узкого класса задач.