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


 
Свежее новое
  • Искусственный интеллект смог визуализировать 2D изображения.
  • Ученые из Вашингтона разработали модель, которая способна воссоздавать движения человека на фотографиях и картинах. Она создает для него 3D модель и
  • Искусственный интеллект, робот Вера, получил 226 млн рублей
  • ФРИИ и Кировский завод вкладывают 226 миллионов рублей в представителя «Сколкова» — компанию «Стафори», создавшую робота-рекрутера. Искусственный
  • В Москве состоялся финал PicsArt AI Hackathon, с самым крупным призовым фондом в истории
  • 30 ноября-2 декабря, в Москве прошел крупнейший хакатон в сфере искусственного интеллекта и компьютерного зрения - PicsArt AI Days. На хакатон было
  • В следующем году в Москве, заработает видеоконтроль, способный обнаружить преступников
  • Как рассказал в своем сообщении Сергей Собянин, новая система будет способна анализировать записи с видеокамер. Быстрая обработка данных позволит
  • В Москве пройдет один из крупнейших хакатонов в мире в сфере искусственного интеллекта
  • PicsArt, ведущая творческая платформа для создания контента и визуализации историй в социальных сетях с более чем 100 миллионами активных
Последние комментарии
Каким был первый робот в мире? Происхождение слова "Робот"
Восхищения нет предела делу ваших рук и идей. Хочется склонить голову перед вашим трудом, хотя твердо придерживаюсь Библии (не поклоняться идолам)
Как работает Любовь? Квантовая связь нейронной активности Людей
Я думаю, когда начнется квантовое взаимодействие мржду человеком и ИИ это и будет началом конца.
Как работает Любовь? Квантовая связь нейронной активности Людей
Как вы считаете, возможно ли образование квантовых взаимодействий между человеком и ИИ? 
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
А почему бы сразу СИИ не запустить в другую галактику, может там нет коррупции, воровства, плебейства и прочей муры, которая не только мешает
Искусственный Интеллект. Концепция развития и внедрения Искусственного Интеллекта (Искусственной Аналитики)
Согласен. проблема ИИ не в наборе задач. Главная проблема - познание процесса мышления как феномена физиологии головного мозга человека.
Мы в социальных сетях
Статистика
0  
Всего статей 1539
0  
Всего комментариев 74
0  
Пользователей 64