Часть 9. Генетические алгоритмы вещественного кодирования

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

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

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

Мутация в генетических алгоритмах вещественного кодирования проводится в заданном проценте (доле) от всех генов особей текущего поколения популяции (например, μ = 0,2). Таким образом, количество мутаций, приходящихся на одно поколение популяции, вычисляется по соотношению:

(1) Генетические алгоритмы вещественного кодирования

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

(2) Генетические алгоритмы вещественного кодирования,

где α – случайное двоичное значение (0 или 1); Δ – случайное вещественное число из интервала (0, σ], где σ – параметр, близкий по величине к ожидаемому стандартному отклонению от нормального распределения. Для увеличения скорости работы алгоритма последний параметр целесообразно устанавливать постоянной величиной в настройках, а не вычислять для каждого поколения популяции.

При необходимости установить разные вероятности для мутаций с понижением и повышением значения переменной можно использовать соотношение для вычисления параметра α для (2) вместо его случайной генерации:

(3) Генетические алгоритмы вещественного кодирования,

где β – случайное вещественное число из интервала [0, 1); γ – параметр, определяющий соотношение между вероятностями понижения и повышения значения переменной в результате мутации.

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

Наиболее важными генетическими операторами вещественного кодирования следует считать разновидности вещественного кроссовера.

Пусть P = (p1, p2, …, pn) и Q = (q1, q2, …, qn) – две особи популяции, выбранные для проведения кроссовера, причём приспособленность первой особи лучше, чем приспособленность второй.

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

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

H = (h1, h2, …, hn),

где

Арифметический кроссовер – получение двух новых особей H = (h1, h2, …, hn) и G = (g1, g2, …, gn) из родительских путём вычисления значений генов по соотношениям:

(4) ,

где λ – константа (для постоянного арифметического кроссовера) или переменная, зависящая от количества пройденных эпох (для непостоянного арифметического кроссовера).

В процессе линейного кроссовера создаются три потомка H = (h1, h2, …, hn), G = (g1, g2, …, gn) и F = (f1, f2, …, fn):

(5)

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

Дискретный кроссовер – получение новой особи, хромосома которой составлена из случайным образом взятых генов двух или большего количества родительских хромосом.

Расширенный кроссовер сводится к созданию потомка:

H = (h1, h2, …, hn),

где hi генерируется случайным образом из интервала Генетические алгоритмы вещественного кодирования; Di – расстояние между соответствующими генами родительских хромосом, определяемое по соотношению:

(6) Генетические алгоритмы вещественного кодирования

Эвристический кроссовер учитывает приспособленности родительских особей. Значения генов дочерней особи определяются по соотношению:

(7) Генетические алгоритмы вещественного кодирования

где α – случайное вещественное число из интервала от нуля до единицы.

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

На первом этапе из популяции случайно выбирается одна из особей X = (x1, x2, …, xn) для изменения и замены, а также ещё три – H = (h1, h2, …, hn), G = (g1, g2, …, gn) и F = (f1, f2, …, fn) – для формирования мутантной особи. Значения генов (mi) мутантной особи (M) определяются с использованием расчётного соотношения:

(8) ,

где α – параметр метода дифференциальных эволюций, обычно лежащий в пределах (0, 2].

На втором этапе некоторые значения генов исходной родительской особи X с заданной вероятностью β заменяются значениями генов мутантной особи M, находящихся в соответствующих позициях. Для полученной в результате такого скрещивания особи рассчитывается значение функции приспособленности, и, если оно лучше, чем у исходной особи X, та заменяется на новую.

По материалам учебного пособия:
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.;

Добавить комментарий


Защитный код
Обновить