кодирование в генетическом алгоритме

Кодирование в генетическом алгоритме

Рассмотрим математическую модель поставленной задачи. Дан вектор X с размерностью 256, который представляет собой закодированное изображение известного распознаваемого символа. Также есть вектор Y с размерностью 10, который отражает требуемый результат распознавания, указывающий принадлежность символа к эталонному образцу. Необходимо найти весовую матрицу W, элементами которой являются вещественные числа в отрезке [0; 1], чтобы выполнялось равенство:

Необходимо осуществить настройку весовой матрицы W с помощью генетического алгоритма. В рамках решаемой задачи рассматриваемая матрица имеет следующую размерность: количество строк равняется 10, что представляет собой все символы, описывающие арабские цифры; количество столбцов определяется размером знакоместа, отводимого под каждый символ, 256 столбцов.

С точки зрения очевидности и простоты понимания следует каждый столбец матрицы весов рассматривать в качестве хромосомы, что приведет к наличию 256 хромосом, которые в совокупности будут отражать каждую особь. Однако при практической реализации гораздо удобнее использовать более простую структуру, хотя и менее наглядную. Это связано с тем, что довольно тяжело реализовать операции кроссинговера и мутации при наличии нескольких хромосом. Каждая особь в разрабатываемом генетическом алгоритме можно представить в виде только одной хромосомы, что значительно упростит программную реализацию на ЭВМ. Этого можно достичь следующим способом. Хромосома будет начинаться с первого столбца матрицы весов, и каждый следующий столбец будет просто добавляться в конец уже существующей «единой» хромосомы. Данный метод проиллюстрирован на рисунке 1.

Рис. 1. Преобразование весовой матрицы W в вектор весов Vw.

Классический генетический алгоритм состоит из ряда наиболее важных этапов. Фактически данные этапы можно расположить в хронологическом порядке.

Все описанные этапы являются абсолютно справедливыми в рамках решаемой задачи 3. Практическая реализация первого шага любого генетического алгоритма в большинстве случаев представляет собой не что иное, как инициализацию случайным образом. Каждому гену любой хромосомы присваивается случайное значение из интервала допустимых значений. Соответственно, при настройке весовой матрицы W каждый ген получит генетическую информацию в виде случайного значения в отрезке [0; 1]. Программная реализация подобного метода инициализации является самой простой и имеет свои достоинства и недостатки. Достоинства заключаются в следующем.

Оценка приспособленности особей в популяции заключается в вычислении значения функции пригодности для каждого члена популяции. И чем выше это значение, тем больше особь отвечает требованиям решаемой задачи. В рамках решаемой задачи весовая матрица есть часть нейронной сети, которая осуществляет распознавание образов. И соответственно генетический алгоритм выполняется на стадии обучения нейронной сети. Иными словами, необходимо привести весовую матрицу к такому виду, при котором ошибка распознавания эталонного образа будет минимальной. Таким образом, функция пригодности оценивает ошибку распознавания каждого эталонного образа, и чем меньше ошибка, тем выше значение функции пригодности. Задача состоит в минимизации ошибки распознавания. Для этого необходимо сравнить полученный вектор Y′ с эталонным образцом Y.

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

Отсюда вытекает, что чем выше значение функции пригодности, тем больше будет размер сектора на «колесе рулетки». Очевидно, что чем больше сектор, тем выше вероятность «победы» соответствующей особи. И, как следствие, вероятность выбора определенной особи оказывается пропорциональной значению ее функции приспособленности. Использование метода «рулетки» часто приводит к преждевременной сходимости алгоритма, которая заключается в том, что в популяции начинают доминировать лучшие особи, но не оптимальные. Спустя несколько поколений популяция практически полностью будет состоять из копий наиболее лучших особей. Однако весьма маловероятно, что достигнутое решение будет оптимальным, так как исходная популяция генерируется случайным образом и представляет собой лишь малую часть пространства поиска. Чтобы предотвратить преждевременную сходимость генетического алгоритма, используется масштабирование функции приспособленности. Масштабирование функции пригодности позволяет исключить ситуацию, когда средние и лучшие особи начинают формировать одинаковое число схожих потомков в следующих поколениях, что является крайне нежелательным явлением. Следует отметить, что масштабирование также предупреждает случаи, когда, несмотря на значительную неоднородность популяции, среднее значение функции приспособленности мало отличается от максимального. Итак, масштабирование функции приспособленности есть не что иное, как преобразование ее вида. Выделяют три основных преобразования: линейное, степенное и сигма-отсечение. В разработанном алгоритме используется преобразование сигма-отсечение.

, (2)

Также можно в определенной степени модифицировать данный метод селекции или строить селекцию на основе синтеза сразу нескольких методов.

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

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

На рис. 2 изображен процесс получения новых особей с использованием упорядоченного кроссинговера. Имеются две родительские хромосомы: Vw1 и Vw2. Генетическим материалом являются вещественные числа от 0 до 1. Упорядоченный кроссинговер работает следующим образом. Изначально случайным образом определяется «разрезающая точка». На следующем этапе первый потомок New_Vw1 наследует левую часть родительской хромосомы Vw1. Заполнение оставшихся генов новой хромосомы осуществляется за счет информации, хранящейся у второго родителя Vw2. Алгоритм просматривает хромосому Vw2 с самого начала и осуществляет извлечение генов, которые отличаются от генов, уже находящихся в потомке, более чем на величину e = 0,02. Малая величина e задается в алгоритме для определения «родства» генов. С каждым последующим шагом, а в особенности на завершающих этапах алгоритма, имеет смысл уменьшать значение этой величины для достижения более точных результатов. Аналогичная процедура выполняется при получении второго потомка New_Vw2. Второй потомок New_Vw2 наследует левую часть родительской хромосомы Vw2. Заполнение оставшихся генов получаемой хромосомы осуществляется за счет информации, находящейся у второго родителя Vw1.

Рис. 2. Принцип работы упорядоченного кроссинговера.

Алгоритм производит анализ хромосомы Vw1 с первого гена и осуществляет упорядоченное извлечение генов, которые отличаются от генов, уже находящихся в потомке, более чем на величину e = 0,02. В результате работы каждого оператора скрещивания в популяции появляются две новые особи. Чтобы контролировать количество операций кроссовера используется коэффициент скрещивания K_k, определяющий долю производимых на каждой итерации потомков. Количество потомков определяется следующей формулой:

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

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

Рис. 3. Случайная мутация на основе приращения.

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

Оператор мутации применяется к потомкам особей, получаемых после операции скрещивания. Особи с мутациями остаются в популяции до начала этапа «формирование новой популяции». Количество мутирующих особей определяется формулой:

, (4)

,

Рис. 4. Классический многоточечный оператор мутации.

Следующим этапом разработанного генетического алгоритма является формирование новой популяции. Насколько сильно выросла численность популяции, определяется общим коэффициентом мутации K_m и коэффициентом скрещивания K_k. В общем виде текущая численность популяции вычисляется по следующей формуле:

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

Таким образом, в результате работы генетического алгоритма получен набор весовых коэффициентов, обеспечивающих корректную работу нейронной сети. Также стоит отметить тот факт, что использование специального оператора мутации позволило сократить время обучения сети. Для обучения было выбрано обучающее множество из 180 элементов. Время обучения на этом множестве с помощью описанного генетического алгоритма с использованием мутации на основе приращения, нечеткой сети Ванга-Менделя составило 2 мин. 50 сек., обучение с использованием алгоритма с применением классического многоточечного оператора мутации длилось 3 мин. 10 сек., а применение гибридного оператора мутации позволило сократить время обучения до 1 мин. 20 сек. Таким образом, полученный генетический алгоритм позволяет сократить время поиска наилучшего решения в рамках поставленной задачи.

Источник

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

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

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

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

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

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

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

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

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

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

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

Пусть P = (p₁, p₂, …, p_n) и Q = (q₁, q₂, …, q_n) – две особи популяции, выбранные для проведения кроссовера, причём приспособленность первой особи лучше, чем приспособленность второй.

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

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

где

Арифметический кроссовер – получение двух новых особей H = (h₁, h₂, …, h_n) и G = (g₁, g₂, …, g_n) из родительских путём вычисления значений генов по соотношениям:

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

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

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

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

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

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

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

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

На первом этапе из популяции случайно выбирается одна из особей X = (x₁, x₂, …, x_n) для изменения и замены, а также ещё три – H = (h₁, h₂, …, h_n), G = (g₁, g₂, …, g_n) и F = (f₁, f₂, …, f_n) – для формирования мутантной особи. Значения генов (m_i) мутантной особи (M) определяются с использованием расчётного соотношения:

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

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

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

Источник

Генетический алгоритм

Материал из MachineLearning.

Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Содержание

Постановка задачи

Для функции приспособленности в пространстве поиска требуется найти (или ).

Описание алгоритма

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

Иные обозначения

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

Встречаются такие обозначения:

Применение генетических алгоритмов

Генетические алгоритмы применяются для решения следующих задач:

Подробное описание алгоритма

Кодирование пространства поиска

В ГА часто используют следующие типы кодирования компонент пространства поиска:

Начальная популяция

Оценка приспособленности

Оператор отбора (селекции)

На этом этапе отбирается оптимальная популяция для дальнейшего размножения. Обычно берут определённое число лучших по приспособленности. Имеет смысл также отбрасывать «клонов», т.е. особей с одинаковым набором генов.

Оператор скрещивания

Оператор мутаций

Критерии останова

Эвристики

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

Плоидность

Мета ГА

Простейший пример ГА

Подбор ключа 2048 бит

Эффективность генетических алгоритмов

Холланд недвусмысленно пишет[1], что при прочих равных условиях ГА будет работать хуже, чем специальный алгоритм, рассчитанный на конкретную задачу (тип признаков, целевую функцию). Например, полный перебор конечного небольшого пространства или любой эффективных алгоритм спуска будет всегда эффективнее чем ГА. Тем не менее, в ситуации, когда о задаче ничего a priori не известно, можно полагаться на результат работы простейшего генетического алгоритма как некого приближения.

Существуют некоторый класс функций (Hyperplane-defined functions, Holland), с которым за приемлемое время[2] справляются только генетические алгоритмы.

Тестовые функции

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

Мнения

Конвергенция с генетикой и синтетической теории эволюции

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

Нейронные сети и эволюционное моделирование

ИНС и ГА часто пытаются применять в тандеме, т.к. и те и другие имеют корни из биологии. Тем не менее (см. выше об эффективности ), во-первых алгоритм обратного распространения ошибки настройки ИНС работает значительно (на порядок) быстрее в простых случаях. А во-вторых, настройка нейронной сети в биологии происходит методом, который, скорее всего, значительно разнится с генетическим подходом.

Аналогия с другими алгоритмами

В случае отключённого кроссинговера ГА начинает вести себя по образу случайного поиска. Также у ГА есть аналогия со случайным поиском с адаптацией. Во многих стохастических алгоритмах можно найти аналогию с ГА.

Источник