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

Часть 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 с.;


Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • На B-52 испытали новую гиперзвуковую ракету
  • Б-52 — знаменитый североамериканский бомбардировщик стратегического назначения. Минобороны США планирует оснастить этот самолет новейшим комплексом
  • Две погасшие звезды слились воедино и образовали одну, которая «ожила»
  • Можно ли из двух мертвых тел создать одно живое? Оказывается, это реально, если речь идет о звездах. Астрономы открыли такую редкую звезду, которая
  • Трансгенные грибы могут истреблять разносчиков малярии и других москитов
  • Ученые из США и Буркина-Фасо провели эксперименты, доказавшие эффективность нового средства от москитов. Это генномодифицированный гриб вида
  • Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
  • По сети гуляет видео, где несколько десятков летательных аппаратов ВМС Соединенных Штатов Америки демонстрируют слаженный взлет. Этот завораживающий
  • Ученые нашли окаменелость, которая сохранила целую стаю рыбок
  • В Америке нашли окаменелость, в которой «законсервирована» целая стайка рыбок. Они застыли в процессе движения, которое, как считают ученые, было
Последние комментарии
Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
Сколько раз я задавал вопрос про аварийную посадку конвертоплана,но так и не получил ответа. Если у него двигатели не повернутся вверх,то как он
5 необъяснимых для науки загадок
Ваша цитата: "Масса - это сконцентрированная Энергия. Энергия - это не сконцентрированная Масса".   Мой комментарий: Чтобы увеличить (в общем случае
Исследование показало: рождение ребенка старит женщину на 11 лет, а бездетные люди живут меньше
Корреляция в данном случае заключается в том что работает программа размножения. Программа размножения с точки зрения системы не дать умереть виду,
Сколько придется лететь со скоростью света до ближайшей звезды?
Ни какого замедления времени и ни какого сокращения расстояния не происходит при полёте в Космосе со скоростью близкой к скорости света, а тем более
Сколько придется лететь со скоростью света до ближайшей звезды?
Ближайшая звезда к нам, это Солнце. Расстояние порядка 150 млн. км. (Астрономическая единица). Несложные арифметические действия и "вуаля", получаем
Мы в социальных сетях
Статистика
3  
Всего статей 2003
1  
Всего комментариев 333
2  
Пользователей 118