Схема работы классического генетического алгоритма

ГА имеет три важнейших оператора: оператор селекции, оператор кроссовера и оператор мутации (рис. 5.1).

Схема работы классического генетического алгоритма

Рис. 5.1. Схема работы классического генетического алгоритма

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

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

Отметим, что существуют различные варианты реализации оператора кроссовера, в частности двухточечный и равномерный кроссовер.

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

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

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

где paf — вероятность селекции /-й особи при селекции; fitZ - фитнес-функция /-й особи; /= 1, 2, F — индекс особи (F— размер популяции); а = 1, 2, SJ? — итерация (эпоха) генетического алгоритма (приводящая к обновлению популяции).

Отметим, что вероятность оператора мутации обычно задается экзогенно.

Особое значение в ГЛ имеет функция приспособленности особи к популяции, или фитнес-функция. Существуют различные способы ее вычисления в зависимости от задачи. В общем случае с помощью ГЛ выполняют поиск решения в миогоэкстремальпых задачах с ограничениями.

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

где A/f. — значение i-й целевой функции (i = 1, 2, ..., Г) вычисленной для /-й особи; р, — весовой коэффициент, определяющий предпочтения по отношению к /-м целевым функциям (как правило, О < Р,- < 1, экз.[1]); а, — коэффициент нормализации значений i-й целевой функции (a > 1, экз.); Q” — невязка ограничений, т.е. оценка декартова расстояния /-й особи от границы области допустимых значений (ОДЗ) (QJ >0 ); V, — оператор, определяемый для i-й целевой функции, V. е {(min),(шах)}, где V,- = (min) и V,- = (max) соответственно означает, что требуется минимизировать или максимизировать значения i-й целевой функции (экз.).

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

где Vf — оператор, определяемый для i-й целевой функции, V. е {(min),(шах),(=).(>),(<)} (экз.); Zi левая или правая часть ограничения (экз.).

Отметим, что размер популяции F является фиксированным. Наименее приспособленные особи через определенное количество поколений выталкиваются из популяции. При этом используются так называемые правила отбраковки.

Правила отбраковки (выталкивания особей из популяции) нацелены на обеспечения выживания наилучших решений (выталкивания наихудших из популяции). Отметим, что на каждой итерации ГА (а) мы ограничиваемся количеством генерируемых особей (/а <и) для недопущения неконтролируемого «рассыпания» алгоритма.

В качестве правил отбраковки обычно выбирается требование на выполнение одного из следующих условий:

  • • существенное нарушение модельных ограничений;
  • • устойчивое демонстрирование «слабости» данной /-й особи (фитнес-функции особи) с течением итераций ГА, т.е. fitvf~n <... < < fitf°~2 < fitf-x < fit'j5 и, как следствие, выталкивание ее из популяции, в силу ограниченности размера популяции (I7).

Отметим, что, как правило, рекомендуется 10%-ная замена неперспективных особей (элиминирование) в популяции более перспективными, отбираемыми селективным методом.

Критерием остановки генетического алгоритма будет выполнение критерия сходимости (стабилизация приспособленности популяции по отношению к эпохам).

  • [1] Здесь и далее в книге так обозначаются экзогенные, т.е. внемодельные переменные.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >