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


Гость, оставишь комментарий?
Имя:*
E-Mail:


 
Свежее новое
  • Подопытные животные могут вздохнуть с облегчением? Вскоре их заменит искусственный интеллект
  • Исследователи разработали систему искусственного интеллекта, которая может быть использована для тестирования побочных эффектов применения различных
  • Робот поможет в ремонте вашего автомобиля
  • Когда Джейми Людольф столкнулся с непростым автомобильным ремонтом, он обратился к сервисный центр, но сегодня в автосалоне в Атланте, он может
  • Компания HUAWEI стремится захватить трон компаний из Силиконовой долины в сфере производства чипов для нужд AI
  • Китайский технологический гигант Huawei успешно реализует свою стратегию по захвату рынка производства чипов, который принадлежит представителям
  • Ежегодный форум по системам искусственного интеллекта RAIF 2018 состоится 23 октября 2018 в конгресс-парке «Рэдиссон Ройал Москва»
  • 23 октября в конгресс-парке «Рэдиссон Ройал Москва» состоится второй ежегодный форум по системам искусственного интеллекта — RAIF 2018 (The Russian
  • Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
  • Технологическая Сингулярность (ТС), т.е. взрывное развитие технического прогресса, а значит и взрывное развитие экономики России, предполагает в
Последние комментарии
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
У нас очень странный народ, если что не понимает, то обязательно надо сунуть в морду. Зачем? А не лучше ли поинтересоваться, почему именно так? У
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Господин Чернов. Поясню. Любой инструмент, даже прозаическая кофемолка, проходят процедуру стендовых испытаний. Сертификат соответствия
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
     " И странная картина получается в коридорах власти ". Странная картина  получается, если полагать, что власть эта поставлена для решения задач
Как работает Любовь? Квантовая связь нейронной активности Людей
Спасибо за статью, но удивило, что ни в статье, ни в перечне литературы не упоминаются исследования и четкие выводы о структуре воды как
Искусственный интеллект против команды профессиональных геймеров в DOTA 2. Кто победит?
Офигенно, крутая инаф.
Мы в социальных сетях
Статистика
1  
Всего статей 1526
0  
Всего комментариев 62
0  
Пользователей 51