Генетические алгоритмы или как учебник по биологии может помочь в функциональной оптимизации. Генетический алгоритм — наглядная реализация
Эволюционный процесс представляется как способность «лучших» хромосом оказывать большее влияние на состав новой популяции на основе длительного выживания из более многочисленного потомства. Основные этапы эволюционного поиска следующие:
1. Конструируется начальная популяция. Вводится точка отсчета поколений t = 0. Вычисляется приспособленность каждой хромосомы в популяции, а затем средняя приспособленность всей популяции.
2. Устанавливается t= t+1. Производится выбор двух родителей (хромосом) для реализации оператора кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.
3. Формируется генотип потомков. Для этого с заданной вероятностью производится оператор кроссинговера над генотипами выбранных хромосом. Далее с вероятностью 0,5 выбирается один из потомков P i (t) и сохраняется как член новой популяции. После этого к P i (t) последовательно применяется оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохраняется как P k (t).
4. Определяется количество хромосом для исключения их из популяции, чтобы ее размер оставался постоянным. Текущая популяция обновляется заменой отобранных хромосом на потомков P k (t).
5. Производится определение приспособленности (целевой функции) и пересчет средней приспособленности всей полученной популяции.
6. Если t = t заданному, то переход к 7, если нет, то переход к 2.
7. Конец работы.
Данный алгоритм известен как упрощенный «репродуктивный план Д. Холланда». Заметим, что в практических задачах вместо понятия «приспособленность» используют понятие «целевая функция».
Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Предварительно ПГА случайно генерирует популяцию последовательностей – хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем производится копирование последовательности хромосом и перестановка их частей. Далее ПГА реализует множество простых операций к начальной популяции и генерирует новые решения.
ПГА состоит из трех операторов:
репродукция;
кроссинговер;
Репродукция – процесс, в котором хромосомы копируются пропорционально значению их ЦФ. Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для попадания в следующую генерацию. Рассматривая эволюцию Ч. Дарвина, можно отметить, что оператор репродукции (ОР) является искусственной версией натуральной селекции - «выживание сильнейших». Он представляется в алгоритмической форме различными способами. Самый простой – создать модель «колеса рулетки», в которой каждая хромосома имеет поле, пропорциональное значению ЦФ.
Рассмотрим пример Д. Гольдберга: необходимо найти значение максимума функции f(x)=x 2 на целочисленном интервале . Традиционными методами можно изменять значения переменной x, пока не получим максимальное значение f(x).
Для объяснения и реализации ПГА построим следующую таблицу:
|
Номер хромосом |
Хромосома (двоичный код) |
Десятичный код |
Значение ЦФ |
Значение ЦФ, в процентах |
В столбце 2 табл. расположены 4 хромосомы (представленные в двоичном коде), сгенерированные случайным образом. Значение ЦФ для каждой хромосомы (столбец 4) определяется как квадрат значения десятичного кода двоичного числа, которое приведено для хромосом во втором столбце таблицы. Тогда суммарное значение ЦФ всех хромосом равно 890. Для селекции хромосом используется оператор репродукции на основе колеса рулетки. На рисунке поля колеса рулетки соответствуют значению ЦФ каждой хромосомы в процентах. В одной генерации колесо рулетки вращается, и после останова ее указатель определяет хромосому, выбранную для реализации следующего оператора. Очевидно, не всегда хромосома с большим значением ЦФ в результате ОР будет выбрана для дальнейших преобразований.
Колесо рулетки для примера
На основе реализации ОР выбираются хромосомы для применения ОК. Оператор кроссинговера, как правило, выполниться в 3 шага, одним из ОК описанным выше. Точка разрыва kвыбирается случайно между 1 и числом равным длине хромосомы минус единица, то есть в интервале (1, L-1). Длина хромосомы L – это число значащих цифр в ее коде. В рассматриваемом примере таблицы длина каждой хромосомы равна пяти (L=5). На основе ОК создаются две новые хромосомы, путем обмена их частей между позициями (k+1) и L соответственно.
Например, рассмотрим хромосомы 1 и 2 из начальной популяции. Пусть k=1. Тогда получим:
P 1 0 | 1 1 0 0 До применения оператора кроссинговера
P 2 1 | 0 0 0 0,
-----------------
P 1 0 0 0 0 0 После применения оператора кроссинговера
P 2 1 1 1 0 0.
Работа ПГА начинается с репродукции. Хромосомы для следующей генерации выбираются путем вращения колеса рулетки. В примере колесо рулетки вращается 4 раза. Это число соответствуют мощности начальной популяции.
Величину отношения
называют вероятностью выбора копий
(хромосом) при реализации оператора
репродукции и обозначают:
где f i (x)значение ЦФ i-й хромосомы в популяции,
sum f(x)суммарное
значение ЦФ всех хромосом в популяции.
Величину
также
называют нормализованной вероятностью
выбора. Ожидаемое число копий
i-й хромосомы после реализации ОР определяются по формуле:
где
число анализируемых
хромосом, причемN G
включается вN.
Ожидаемое число копий хромосомы P i , переходящее в следующее поколение, также иногда определяют на основе выражения:
.
где
среднее значение
ЦФ по всей популяции.
Тогда для рассматриваемого примера, ожидаемое число копий для первой хромосомы из таблицы равно 0,164=0,64 копий, для второй0,294=1,16 копий, для третьей0,054 = 0,2 и наконец для четвертой0,54=2. Используя модель «бросание монеты» можно определить число полученных копий. Например, (см. столбец 7 таблицы) хромосомы P 1 и P 2 получают 1 копию, хромосома P 4 – 2 копии, и хромосома 3 не получает копий. Сравнивая этот результат с ожидаемым числом копий, получаем то, что «лучшие» хромосомы дают большее число копий, «средние» остаются и «плохие» удаляются после реализации оператора репродукции.
|
Начальная популяция |
Значение f i (x)/sum |
Ожидаемое число копий |
Число полученных копий |
|||
|
Суммарное значение ЦФ (sumf(x)) | ||||||
|
Среднее значение ЦФ
| ||||||
|
Max значение ЦФ | ||||||
Для рассматриваемого примера построим таблицу. В столбце 2 приведен вид 4 хромосом после выполнения оператора репродукции. В столбце 3 приведены списки пар хромосом, которые выбраны случайным образом для реализации оператора кроссинговера. В столбце 4 указан номер позиции для точки разреза хромосом. В столбце 5 приведен вид 4 хромосом после выполнения оператора кроссинговера. В столбце 6 приведены значения десятичного кода двоичного числа каждой хромосомы столбца 5. В столбце 7 приведено значение f(x) для каждой из 4 хромосом новой популяции. В строке 5 приведено суммарное значение ЦФ хромосом новой популяции, в строке 6 –среднее значение их ЦФ, а в строке 7- максимальное значение ЦФ хромосомы из новой популяции.
|
Популяция после оператора репродукции |
выбранные случайно |
Новая популяция | ||||
|
| ||||||
Применяя к популяции полученной после реализации оператора репродукции (столбец 2 табл.) оператор кроссинговера, получим новую популяцию хромосом (5 столбец таблицы). В принципе оператор кроссинговера можно применять любое число раз. После проведения одной генерации ПГА улучшились все показатели: среднее и максимальное значение ЦФ.
Далее, согласно схеме выполнения ПГА, реализуется оператор мутации. Существует большое количество видов операторов мутации. Заметим, что эти операторы соответствуют перестановкам элементов внутри заданного множества. Очевидно, что при небольшой длине хромосомы L (порядка 1020) можно выполнить полный перебор за приемлемое время и найти наилучшие решения. При увеличении L до 50200 и выше, полный перебор произвести затруднительно, и необходимы другие механизмы поиска. Здесь как раз и приходит на помощь направленно-случайный поиск, который реализуется на основе ПГА.
Отметим, что глобальный максимум можно было найти еще на этапе реализации кроссинговера. Для этого необходимо было увеличить пространство поиска. Например, если в столбце 5 табл. выбрать хромосомы P 2 и P 4 и между ними выполнить оператор кроссинговера (точка ОК выбрана случайно и равна 3), то получим:
P 2: 1 0 1 | 1 1 (ЦФ-23)
P 4: 1 1 1 | 0 0 (ЦФ-28)
P 2 : 1 0 1 0 0 (ЦФ-20)
P 4 : 1 1 1 1 1 (ЦФ-31).
Решение P 4 , полученное в результате применения ОК случайным образом, является наилучшим результатом (глобальным оптимумом).
Как отмечалось выше, в генетических алгоритмах можно выделять два основных механизма воспроизводства хромосом:
потомки являются точными копиями родителей (неполовое воспроизводство без мутации);
потомки имеют «большие» отличия от родителей.
В генетических алгоритмах в основном используют комбинации этих механизмов. Отметим, что в инженерных задачах начальная популяция может выбираться любым образом, например, моделированием «бросания монеты» (орел = 1, решка = 0). Тогда оператор репродукции выполняется через моделирование движения колеса рулетки. Оператор кроссинговера в задачах вычислительного характера обычно выполняется через двоичное декодирование двух положений монеты. Часто применяют другие типы ОК и другие технологии его выполнения. Вероятность ОК допускается равной Рr(ОК) = 1.0 и меньше, вероятность ОМ допускается равной Рr(ОМ) = 0.01 и больше. В общем случае вероятность применения оператора мутации зависит от знаний о решаемой задаче.
Приведем другой стандартный тип генетического алгоритма, описанный Л.Девисом:
Инициализация популяции хромосом.
Оценка значения каждой хромосомы в популяции.
Создание новых хромосом посредством скрещивания текущих хромосом; применение операторов мутации и рекомбинации.
Устранение хромосом из популяции, чтобы освободить место для новых хромосом.
Оценка значений новых хромосом и вставка их в популяцию.
Если время, заданное на реализацию алгоритма, закончено, то останов и возврат к наилучшей хромосоме, если нет, то переход к 3.
Конец работы алгоритма.
Сравнивая описание ПГА Д. Гольдберга, Д. Холланда и Л. Девиса, видно, что в них реализована одна основная идея моделирования эволюции с некоторыми модификациями. Однако заметим, что эти изменения могут существенно влиять на окончательное качество решения.
Приведем пример модифицированного ПГА:
1. Создание начальной популяции решений.
2. Моделирование популяции (определение ЦФ для каждой хромосомы).
3. Пока не проведено необходимое число генераций или не закончилось время, заданное на реализацию алгоритма или не найдено оптимальное значение ЦФ (если оно известно):
а) выбор элементов для репродукции;
Применение:
б) оператора кроссинговера для создания потомков;
в) оператора мутации;
г) оператора инверсии;
д) оператора транспозиции;
е) оператора транслокации;
ж) оператора сегрегации;
з) оператора удаления вершин;
и) оператора вставки вершин;
к) рекомбинация родителей и потомков для создания новой генерации;
л) оператора редукции.
4. Реализация новой генерации.
Новые модификации ГА могут строиться путем объединения, например, пунктов «б – л» или их частичного устранения, или их перестановок, а также на основе применения адаптационных принципов управления эволюционным поиском.
Введение в аксиоматическую теорию генетических алгоритмов
Сформулируем описание генетических алгоритмов в виде научной теории. Отметим, что способ построения научной теории, в основе которой используются исходные положения, называемые аксиомами, а все остальные предложения теории получаются как логические следствия аксиом, называется аксиоматический метод .Аксиома - положение принимаемое без доказательств в качестве исходного, отправного для данной теории. Основным в нем является метод интерпретаций. Тогда для генетических алгоритмов можно построить следующую базовую теорию.
Пусть каждому исходному понятию и отношению аксиоматической теории ГА поставлен в соответствие некоторый конкретный математический объект. Совокупность таких объектов называется полем интерпретации . Всякому утверждению U теории ГА ставится в соответствие некоторое высказывание U* об элементах поля интерпретации, которое может быть истинным или ложным. Тогда можно сказать, что утверждение U теории ГА соответственно истинно или ложно в данной интерпретации. Поле интерпретации и его свойства сами обычно являются объектом рассмотрения другой теории ПГА, которая в частности может быть аксиоматической. Этот метод позволяет доказывать суждения типа: если теория ГА непротиворечива, то непротиворечива и теория ПГА.
Пусть теория ГА проинтерпретирована в теории ПГА таким образом, что все аксиомы A i теории ГА интерпретируются истинными суждениями A i * теории ПГА. Тогда всякая теорема теории ГА, то есть всякое утверждение А, логически выведенное из аксиом A i в ГА, интерпретируется в ПГА некоторым утверждением A * , выводимым в ПГА из интерпретаций A i * аксиом A i и, следовательно, истинным.
Метод интерпретаций позволяет также решать вопрос о независимости систем аксиом: для доказательства того, что аксиома А теории ГА не зависит от остальных аксиом этой теории, то есть не выводима из них, и, следовательно, необходима для получения всего объема данной теории, достаточно построить такую интерпретацию ГА, в которой аксиома А была бы ложна, а все остальные аксиомы этой теории истинны. Уточнением понятия аксиоматической теории является понятие формальной системы . Это позволяет представлять математические теории как точные математические объекты и строить общую теорию или метатеорию таких теорий. Всякая формальная система строится как точно очерченный класс выражений – формул, в котором некоторым точным образом выделяется подкласс формул, называемых теоремами данной формальной системе. При этом формулы формальной системы непосредственно не несут в себе содержательного смысла. Их можно строить из произвольных знаков и символов. Общая схема построения произвольной формальной системы ГА такова:
Алфавит – перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.
Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории ГА:
Язык системы ГА: аппарат алгебры логики; теория множеств; теория графов, теория алгоритмов, основные положения биологии и теории систем.
построение моделей эволюций;
конструирования популяций;
построения ЦФ;
разработки генетических операторов;
репродукции популяций;
рекомбинации популяций;
редукции;
адаптации.
Последовательность элементарных символов считается формулой тогда и только тогда, когда она может быть построена с помощью правил образования.
Аксиомы системы ГА. Выделяется некоторое множество конечных формул, которые называются аксиомами системы. В ГА существует большое число наборов аксиом. Например, базовый набор аксиом следующий:
Популяция конструируется случайным образом.
Выполнение оператора репродукции производится на основе «колеса рулетки».
Обязательное использование операторов кроссинговера и мутации.
Размер популяции после каждой генерации остается постоянным.
Размер популяции меняется.
Число копий (решений), переходящих в следующую генерацию меняется.
Целевая функция определяется на основе принципа «Выживание сильнейших».
Правила вывода ГА. Фиксируется конечная совокупность предикатов П 1 , П 2 ,…, П k на множестве всех формул системы. Пусть П (x 1 ,…,x ni +1) – какой-либо из этих предикатов (n i 0) если, для данных формулF 1 ,…,F ni +1 утверждение П (F 1 ,…,F ni +1) истинно, то говорят, что формулаF ni +1 непосредственно следует из формулF 1 ,…,F ni +1 по правилу П i .
Заданием 1,2,3 исчерпывается задание формальной системы ГА как точного математического объекта. При этом степень точности определяется уровнем точности задания алфавита, правил образования и правил вывода. Выводом системы ГА называется всякая конечная последовательность формул, в которой каждая формула либо является аксиомой системы ГА, либо непосредственно следует из каких-либо предшествующих ей (этой последовательности) формул по одному из правил вывода П i системы.
Всякую конкретную математическую теорию ГА можно перевести на язык подходящей формальной системы таким образом, что каждое ложное или истинное предложение теории ГА выражается некоторой формулой системы. Метод интерпретаций позволяет устанавливать факт относительной непротиворечивости, то есть доказывать суждения типа: «если теория ГА непротиворечива, то непротиворечива и теория ПГА». В общем случае, проблема непротиворечивости не решена и является одной из основных в математике.
Предлагается ряд основных стратегий взаимодействия методов эволюционного и локального поиска:
«поиск – эволюция»;
«эволюция – поиск»;
«поиск – эволюция - поиск»;
«эволюция – поиск - эволюция».
Заметим, что иерархически можно строить стратегии такого типа любого уровня сложности. Например, «эволюция – поиск – эволюция - поиск – эволюция - поиск» и т.д. Отметим, что такое построение зависит от наличия вычислительных ресурсов и времени, заданного на получения окончательного решения.
В первом случае любым из описанных алгоритмов поиска или их комбинаций определяется одно или пара альтернативных решений задачи. На основе этих решений строится популяция, к которой применяется одна из схем эволюции. Далее процесс продолжается итерационно до достижения критерия остановки.
Во втором случае конструируется популяция и реализуется одна из схем эволюции. Лучшее решение анализируется и улучшается (если это возможно) одним из алгоритмов поиска. Далее процесс выполняется, как в первом случае. В остальных случаях процесс поиска результатов выполняется аналогично.
Выводы
Генетические алгоритмы - поисковые алгоритмы, основанные на механизмах натуральной селекции и натуральной генетики. Они являются мощной стратегией выхода из локальных оптимумов. Она заключается в параллельной обработке множества альтернативных решений, концентрируя поиск на наиболее перспективных из них. Причем периодически в каждой итерации можно проводить стохастические изменения в менее перспективных решениях.
Существует четыре основных отличия ГА от оптимизационных методов:
прямое преобразование кодов;
поиск из популяции, а не из единственной точки;
поиск через элементы (слепой поиск);
поиск, использующий стохастические и модифицированные операторы, а не детерминированные правила.
Использование ГА при решении инженерных задач позволяет уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.
Глава 1. Генетические алгоритмы
1.1 Естественный отбор в природе
1.2 Представление объектов. Кодирование признаков
1.3 Основные генетические операторы
1.4 Схема функционирования генетического алгоритма
Глава 2. Задачи оптимизации
2.1 Задачи, решаемые с помощью генетических алгоритмов
2.2 Математическая постановка задачи оптимизации
2.3 Решение Диофантова уравнения
2.4 Пути решения задач оптимизации
2.5 Задача коммивояжера
Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам
3.1 Обоснование выбора программного обеспечения
3.2 Описание программной реализации
Заключение
1.1. Естественный отбор в природе
“XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?..”
Ключевую роль в эволюционной теории играет естественный отбор. Его суть состоит в том, что наиболее приспособленные особи лучше выживают и приносят больше потомков, чем менее приспособленные. Заметим, что сам по себе естественный отбор еще не обеспечивает развитие биологического вида. Поэтому очень важно понять, каким образом происходит наследование, то есть как свойства потомка зависят от свойств родителей.
Основной закон наследования интуитивно понятен каждому - он состоит в том, что потомки похожи на родителей. В частности, потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. Чтобы понять, на чем основано это сходство, нужно немного углубиться в построение естественной клетки - в мир генов и хромосом .
Почти в каждой клетке любой особи есть набор хромосом, несущих информацию об этой особи. Основная часть хромосомы - нить ДНК, определяющая, какие химические реакции будут происходить в данной клетке, как она будет развиваться и какие функции выполнять. Ген - это отрезок цепи ДНК, ответственный за определенное свойство особи, например за цвет глаз, тип волос, цвет кожи и т.д. При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.
При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов . Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.
1.2. Представление объектов. Кодирование признаков
Из биологии мы знаем, что любой организм может быть представлен своим фенотипом, который фактически определяет, чем является объект в реальном мире, и генотипом, который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе . Таким образом, для решения задач нам необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.
В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.
Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма . Значения кодов Грея рассмотрены в таблице ниже:
Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит
Генетические алгоритмы (ГА) — это стохастические, эвристические оптимизационные методы, впервые предложенные Джоном Холландом в 1975 году. Они основываются на идее эволюции с помощью естественного отбора. Кроме более быстрого нахождения экстремума, к положительным свойствам генетических алгоритмов можно отнести и нахождение «глобального» экстремума. В задачах, где целевая функция имеет значительное количество локальных экстремумов, в отличие от градиентного метода, генетические алгоритмы не «застревают» в точках локального экстремума, а позволяют найти «глобальный» минимум.
Генетические алгоритмы работают с совокупностью особей – популяцией , где каждая особь представляет возможное решение данной проблемы. Она оценивается мерой ее «приспособленности» согласно тому, насколько «хорошо» соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность «воспроизводить» потомство с помощью «перекрестного скрещивания» с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.
Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что наследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.
ГА оперирует следующей терминологией:
- Хромосома – решение рассматриваемой проблемы, носитель наследственной информации. Совокупность хромосом (значений параметров целевой функции) характеризует особь. Хромосома состоит из генов .
- Гены – элементы кодирования наследственной информации (параметров целевой функции). В качестве генов чаще всего выступает битовое кодирование информации.
- Особь – набор хромосом (совокупность параметров, для которой ищется значение целевой функции).
- Приспособленность особи – значение целевой функции для данного набора параметров по отношению к требуемому значению.
ГА производит над особями следующие действия
Вначале ГА-функция генерирует определенное количество возможных решений (особей), а затем вычисляет для каждого приспособленность – близость к истине. Эти решения дают потомство (производится операция кроссовера). Более приспособленные решения имеют больший шанс к воспроизводству, а «слабые» особи постепенно «отмирают». Таким образом, происходит процесс эволюции. На определенных этапах данного процесса происходят спонтанные изменения генов (мутации и инверсии). Полезные изменения, приводящие к увеличению приспособленности особи, дают свое потомство, в то время как «бесполезные» изменения «отмирают». После скрещивания, мутаций и инверсий снова определяется приспособленность особей нового поколения. Процесс повторяется до тех пор, пока не найдено решение или не получено достаточное к нему приближение.
В качестве примера применения генетического алгоритма рассмотрим задачу численного поиска решения, рассмотренную в этой статье .
Целевая функция будет иметь вид
В качестве функции кроссовера будем использовать операцию нахождения среднего арифметического двух рассматриваемых точек. Для скрещивания выбираются несколько точек с наилучшим решением (со значением целевой функции, наиболее близким к нулю).
Мутацией будет являться операция генерации нового случайного числа рассматриваемой популяции.
Инверсия будет изменять значение хромосомы на некоторую небольшую величину, таким образом осуществляя поиск в окрестностях точки с наилучшим решением.
Реализация на C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#define
_USE_MATH_DEFINES
#include
#include
#include
using
namespace
std;
double
func(double
x)
{
return
sin(M_PI * x / 180) - 1 / x;
}
double
mutation(double
x0, double
x1) // мутация: генерация случайной величины
{
const
int
NUM = 100000000;
return
fabs((double
)((rand() * NUM) % (int
)((x1 - x0)*NUM) + 1) / NUM) + x0;
}
double
inversion(double
x, double
eps) // инверсия: поиск в окрестностях точки
{
static int
sign = 0;
sign++;
sign %= 2;
if
(sign == 0) return
x - eps;
else
return
x + eps;
}
void
crossover(double
*x, double
eps, double
x0, double
x1) // кроссовер: среднее арифметическое
{
int
k = 99;
for
(int
i = 0; i < 8; i++)
for
(int
j = i + 1; j < 8; j++)
{
x[k] = (x[i] + x[j]) / 2;
k--;
}
for
(int
i = 0; i < 8; i++)
{
x[k] = inversion(x[i], eps); k--;
}
for
(int
i = 8; i < k; i++)
x[i] = mutation(x0, x1);
}
void
sort(double
*x, double
*y) // сортировка
{
for
(int
i = 0; i < 100; i++)
for
(int
j = i + 1; j < 100; j++)
if
(fabs(y[j]) < fabs(y[i])) {
double
temp = y[i];
y[i] = y[j];
y[j] = temp;
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
double
genetic(double
x0, double
x1, double
eps) // поиск решения с использованием ГА
{
double
population;
double
f;
int
iter = 0;
for
(int
i = 0; i < 100; i++) // Формирование начальной популяции
{
population[i] = mutation(x0, x1);
f[i] = func(population[i]);
}
sort(population, f);
do
{
iter++;
crossover(population, eps, x0, x1);
for
(int
i = 0; i < 100; i++)
f[i] = func(population[i]);
sort(population, f);
} while
(fabs(f) > eps && iter<20000);
cout <<
iter <<
" iterations"
<<
endl;
return
population;
}
int
main()
{
srand(time(NULL
));
cout <<
genetic(1.0, 10.0, 0.000001);
cin.get();
return
0;
}
Результат выполнения
Применение генетических алгоритмов не всегда дает лучший результат по сравнению с другими методами. Однако этот метод имеет бесспорное преимущество при решении многомерных задач поиска глобального экстремума, содержащих значительное количество локальных экстремумов.
Выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить к следующему экспонату ко второй части, где описывается создание на основе ГА бота для программистской игры Robocode. Это, по последним сведениям разведки, еще не встречалось на хабре.
Часть первая. Жизнь и творчество генетического алгоритма.
Начнем издалека. Есть некоторый набор задач, которые требуют решения. Наша цель - найти действия, которые смогут преобразовать Дано (начальные условия задач) в Ответ (целевое состояние).Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо, нас наебали, все расходимся. Например, при решении квадратного уравнения ответ (значения x1, x2) получаются из начального условия (коэффициентов a, b, c) путем применения формулы, которую мы все учили в школе. А что делать в более печальном случае, когда нужной формулы в учебнике нету? Можно попробовать с помощью мозгового штурма решить одну из задач. Аналитически. Численными методами. Силой отчаянного перебора функций. Через некоторое время послышатся мечтательное студенческое «хоть бы оно само решилось». Ага, тут-то мы и вылезаем из-за занавесок. Итак, цель - написать программу, которая бы находила функцию (программу), получающую на вход исходные данные и возвращающую годные циферки. Сила метапрограммирования, в бой!
Хм, как же мы будем добиваться такой цели? Принесем у костра жертву богам рекурсии: напишем программу, которая напишет программу, которая бы находила функцию (программу)... Нет, во второй раз такое не прокатит. Лучше мы возьмем пример у природы, кинув наш взор на такие явления, как механизм эволюции, естественный отбор. Всё как в жизни: наши программы будут жить, спариваться, давать потомство и погибать под гнетом более приспособившихся особей, передавая свои лучшие качества потомкам. Звучит безумно, но стоит приглядеться.
Бог нашего мира программ - это наша задача. Программы должны верить в нее, спариваться ради нее, ставить в нее честь свечки в церкви и жить с единственной целью - найти смысл жизни решение этой задачи. Наиболее приспособившийся к среде (приблизившийся к решению задачи) становится альфа-самцом, выживает и дает крепкое потомство. Лузер, который просидел всю жизнь за онлайн играми не познал успеха в решении задачи, имеет совсем маленькие шансы дать потомство. Генофонд будет очищаться от вклада этих прыщавых товарищей, а всё общество программ будет идти к светлому будущему решенной задачи. Что же, в общих чертах уже понятно, теперь нужно разобраться с нюансами: во-первых, как вы себе представление спаривание программ? во-вторых, откуда мы возьмем первое поколение программ? в-третьих, по какому признаку мы будем определять приспособленность особей и как она будет влиять на скрещивание? в-четвертых, стоит определиться с условиями окончания работы алгоритма, когда всю эту оргию останавливать.
Искусство спаривания программ
Думаю, многие из нас иногда испытывают жгучее желание применить к программам насильственное действие сексуального характера. Тут мы вынуждены заранее предупредить, что у нас такие межвидовые девиации не поощряются. У нас всё как завещала католическая церковь: программа с программой, только после брака… и партнеров не меняют, даже если тот томный парень купил тебе коктейль в баре. Хотя нет, вру, многоженство гаремного типа процветает. Да, и еще, несмотря на применение ниже таких слов как «отец» или «сын», программы у нас гермафродиты. Ну и инцест тоже… Тьфу, и я еще о церкви говорил *facepalm*. Ладно, об этом позже.Вопрос скрещивания программ не так уж прост. Случайный обмен функциями, строками или переменными приведет к жирному потоку страшных слов в ваш адрес от компилятора/интерпретатора, а никак не новую программу. То есть необходимо найти способ скрестить программы корректно . Умные дяди нашли выход. А умные мальчики и девочки, изучавшие строения компиляторов, тоже уже догадались. Да-да, это синтаксическое дерево .
Сразу же умерю пыл: у нас борода еще не очень густая, поэтому будем использовать самые простые типы программ. Желающие могут отправиться в долину несметного богатства программирования, а нас тут всё просто - программа состоит из выражений, в свою очередь состоящих из простых функций с некоторой арностью, переменных и констант. Каждое выражение считает по одному из возвращаемых программой значений.
Например: некоторая особь-программа square из двух выражений, пытающаяся (не особо удачно) решить квадратное уравнение:
function square(a, b, c){
x1 = min(sin(b)*(a+1), 0);
x2 = 3 + exp(log(b*a));
return {x1, x2};
}
С представлением определились, теперь надо разобраться с хранением. Так как вокруг этих самых программ еще предстоит множество плясок, в том числе передача их из одной часть системы в другую (которые, вообще говоря, в моем случае вообще были написаны на разных языках), то хранение нашей особи в виде дерева не очень-то удобное. Для представления более удобным способом (идеально - набор строк над некоторым конечным алфавитом) нашу особь-программу-набор_деревьев придется научиться кодировать/раскодировать.
Вроде как дерево, а вроде и нет
Итак, надо представить дерево в виде строки. Тут нас выручит сила karva-деревьев. Для начала стоит определиться с набором функций, переменных и констант, которые могут попасться в дереве. Переменные и константы соответствуют листьям дерева и будут называться терминалами, функции - остальным (внутренним) узлам дерева, именуются нетерминалами. Так же стоит обратить внимание на то, что функции могут иметь разное количество аргументов, посему такие знания («арность», - тихо пробежало слово по губам знатоков) нам очень даже понадобятся. В итоге получается таблица кодировки, например, такая:Здесь n, +, *, if - функции; 2 - константа; a и b - переменные. В реальных задачах таблица поувесистей, с таким набором и квадратное уравнение не решить. Также надо иметь ввиду тот факт, что во избежании деления на нуль и других сценариев апокалипсиса все функции должны быть определены на всём множестве вещественных чисел (ну, или какое вы там множество используете в задаче). А то придется сидеть на карауле, отлавливать логарифмы от нуля и потом разбираться, что с этим делать. Мы люди не гордые, мы пойдем легким путем, исключая подобные варианты.
Так вот, с помощью такой таблицы гонять функции из дерева в строку и обратно не проблема. Например, пришла нам такая строка на расшифровку:
По таблице идентифицируем каждый элемент, вспоминаем также и про арность:
Теперь при помощи арности расставляем ссылки на аргументы функций:
Прошу обратить внимание на то, что последние 3 элемента списка оказались никому не нужны, и их значения никак не влияют на результат функции. Это получилось из-за того, что количество задействованных элементов списка, количество узлов дерева постоянно плавает в зависимости от их арностей. Так что лучше набрать про запас, чем потом мучиться с некорректным деревом.
Теперь если его потянуть вверх за первый элемент, то у нас в руке будет болтаться дерево выражения:
Значение функции можно вычислить рекурсивным обходом по дереву, она у нас оказывается такой:
У меня глаза от папы такие
Возвращаемся к самому горячему - к скрещиванию. Операции скрещивания программ мы ставим следующие условия: во-первых, две скрещивающиеся особи дают два потомка (т.е. размер популяции постоянный); во-вторых, в результате скрещивания потомки должны в определенной мере обладать характеристиками обеих родителей (т.е. яблоко не должно укатываться уж очень далеко от яблони). Мы теперь узнали, как программа будет представляться - это набор строк или деревьев. Соответственно, и скрещивать их можно как строки или как деревья.Скрещивание деревьев представляет собой обмен случайно выбранными ветками. Скрещивание строк можно реализовать несколькими способами: одноточечная рекомбинация (кусочное склеивание), двуточечная рекомбинация, поэлементный обмен и др. Их можно описать длинными сложноподчиненными предложениями с деепричастными оборотами, но и одного взгляда на схемку достаточно, чтобы смекнуть, что к чему:
Стоит только заметить, что места склейки в рекомбинации выбираются случайно, так же как и в поэлементном скрещивании обмен совершается с некоторой вероятностью. Скрещивание деревьями в плане наследственности выглядит перспективней, но реализуется сложнее.
Эй, эта девушка со мной!
С самой интимной частью процесса разобрались (многие уже почувствовали через эту статью, насколько скудна личная жизнь автора). Теперь от взаимоотношения между парой особей перейдем к социальным основам.Особи делятся на поколения. Новое поколение состоит из детей особей предыдущего поколения. Получается, есть текущее поколение сыновей и дочерей, поколение отцов и матерей, бабушек и дедушек, прабабушек и так далее до нулевого поколения - прародителей всего гордого народа. Каждая особь нового поколения после рождения пытается решить задачу, ее действия оценивает некоторая божественная функция пригодности, и в зависимости от ее оценок деятельности юнца особь получает некоторые шансы на воспроизведение потомства, то есть попадания в класс лучших представителей поколения, выбранных для продолжения рода. Наш мир суров и жесток, и по всем канонам антиутопий (или согласно идеям фюрера, как хотите) ни к чему не пригодные родители-пенсионеры после выполнения своей миссии рождения потомства отправляются в путешествие на газенвагене, освобождая жилплощадь паре своих чад. Дети идут по стопам родителей, и так из поколения в поколение.
Та самая функция приспособленности (или фитнесс-функция), которая выдает квоты на спаривание, должна адекватно оценивать способность особи решать задачу, и выдавать числовое выражение этой приспособленности (чем больше значение - тем лучше приспособленность). Например, в случае того самого квадратного уравнения это может быть мера того, насколько значение левой стороны уравнения близко к нулю при подставленных значениях x1, x2, вычисленных программой-особью.
Функция приспособленности выдает каждой особи поколения некоторое число, показывающее ее полезность, приспособленность. Это значение будет влиять на процедуру отбора (селекции): чем больше у особи это значение, тем больше у нее вероятность найти пару для скрещивания (и даже не одну). На практике, после вычисления приспособленности для всех особей поколения мы нормируем эти значения (чтобы сумма приспособленностей особей равнялась 1) и для каждого из мест для поцелуев бросается жребий (случайное число от 0 до 1), определяющий счастливчика. Альфа-самец может получить себе несколько мест, неудачник ничего не получит и так и останется в одиночестве с потертым календариком 1994 года с Памеллой. Такой способ селекции называется «отбором методом рулетки», и схематично это выглядит как-то так:
Существуют и другие способы селекции, но все они придерживаются общего правила: чем больше у особи приспособленность, тем больше она должна участвовать в скрещивании. Также в процесс можно включить опцию элитизма, когда лучший представитель поколения получает за заслуги перед Отечеством премию в виде дополнительных лет жизни: он переходит в следующее поколение без изменений, хотя и может параллельно наделать детей. Это позволяет нам не потерять очень удачное решение, которое может разрушиться в процессе скрещивания.
Тут же упомянем и мутацию. Это операция случайным образом с некоторой маленькой вероятностью меняет фрагмент особи, что позволяет разнообразить генофонд. Полезная вещь, вдруг такая мутация лактозу расщепить поможет! А если нет, и еще одна рука лишняя - то уж помучайся с ней до конца дней своих, потомство дать все равно шансов маловато.
Сотворения мира и Апокалипсис
Как переходить от поколения к поколению выяснили, теперь вопрос следующий - «а что стало первопричиной, с чего все началось?». В отличие от этого вашего мира, у нас для объяснения таких вещей не надо придумывать уловки типа «большого взрыва» или «7 дней». Тут ответ предельно ясен - всё началось с нулевого поколения, которое было сотворено случайным образом. Да-да, просто генерируем рандомом строки/деревья. Единственное требование - корректность особи, а насколько она ущербна - никого не волнует, отбор сделает свое дело.Существует же наш мир настолько долго, насколько нам надо. Мы или задаем планку удовлетворяющей нас приспособленности, и при появлении достаточно крутой особи останавливаем процесс, или проверяем, насколько особи поколения сильно различаются друг от друга. Логично, что если всё поколение состоит из однояйцевых близняшек, то дальнейшее спаривание возбуждает не даст ничего нового генофонду, а на одну мутацию надеяться наивно. Также можно установить ограничение по времени.
Эй, ты! Харошш парить мозг! Что в итоге-то?
Сделаем паузу в этом увлекательном словоблудии и оглянемся назад (ну т.е. наверх). Если подводить итоги, то генетический алгоритм выглядит так:Мы учимся представлять решение задачи в виде особи генетического алгоритма - списка фиксированной длины над некоторым алфавитом. После этого подбираем функцию приспособленности, которая могла бы оценивать особей, и генерируем случайным образом нулевое поколение. Тут начинается круговорот свободной любви: вычисляется приспособленность особей поколения, по этим данным формируются пары (лузеры выкидываются, а альфа-самцы не ограничиваются одной парой), оставшиеся спариваются, рожают пару детишек (к которым еще и мутация приложилась) и накладывают на себя руки. Так продолжается до тех пор, пока не найдется избранный, или изменения перестают нас радовать, или нам все это дело надоело. Ну и как же я обойдусь без схемки:
Часть вторая. Роль генетического алгоритма в образе бота Robocode.
Что-то первая часть затянулась, мы все утомились, поэтому не будем повторяться. Также опустим некоторые особенности реализации.Узнать что такое Robocode можно тут: habrahabr.ru/blogs/programmers_games/59784 (картинки утеряны правда). Если коротко - эта программистская игра, изначально созданная для изучения особенностей языка Java, которая позволяет участникам создавать своих ботов-роботов и устраивать между ними бои. Каждый участник пишет код на Java, который управляет небольшим танком, и сражается с другими такими же танками.
Перед нами стоит следующая задача: разработка при помощи генетического алгоритма автоматизированную системы управления ботом-танком. Робот должен создаваться и модифицироваться автоматически, т.е. в ходе своей эволюции «подстраиваться» под конкретного и заранее выбранного соперника в боях 1 на 1.
Как представить решение задачи в виде особи
Сначала определим возможности танка. Список основных действий, которые может совершить робот во время боя, ограничивается четырьмя пунктами: повернуть пушку, повернуть корпус, выстрелить, передвинуться. Пятое действие, поворот радара, мы исключили из рассмотрения, реализовав его тривиально - постоянное вращение (таким образом, танк будет всегда обладать актуальной информацией о положении врага).Очевидно, что для успешного ведения боя эти действия должны совершаться не хаотично, а зависеть от обстановки (состояния) на поле битвы: от положения танков, их скоростей, энергии и остальных параметров. Таким образом, процесс управления танком сводится к совершению вышеописанных действий на основе состояния боя. Закон, который определяет поведение танка (его действия) на основе обстановки на поле боя, мы будем именовать функцией управления, и именно она будет особью нашего генетического алгоритма.
Так как функция управления должна возвращать 4 значения (энергия выстрела, угол поворота башни, угол поворота корпуса, перемещение танка), то, как объяснялось в прошлой части, она будет состоять из четырех выражений, т.е. из четырех строк/деревьев.
Для составления таблицы кодирования необходимо определиться с набором базовых функций, переменных и констант.
Функции:
+(x, y) = x + y
++(x, y, z) = x + y + z
n(x) = -x
*(x, y) = x * y
**(x, y) = x * y * z
min(x, y) = x > y? y: x
s(x) = 1/(1+exp(-x))
if(x, y, z, w) = x > y? z: w
Переменные:
x, y - координаты танка соперника относительно нашего танка;
dr - расстояние, которое осталось «доехать» нашему танку;
tr - угол, на который осталось повернуться нашему танку;
w - расстояние от нашего танка до края поля;
dh - угол между направлением на танк соперника и пушкой нашего танка;
GH - угол поворота пушки нашего танка;
h - направление движения танка соперника;
d - расстояние между нашим танком и танком соперника;
e - энергия танка соперника;
E - энергия нашего танка.
Ну и константы: 0.5, 0, 1, 2, 10
Функция приспособленности
Опишем, как была выбрана функция приспособленности. Результаты боя «Robocode» формирует на основе множества нюансов. Это не только количество побед, но и всевозможные очки за активность, за выживаемость, за попадание в соперника и т.д. В итоге «Robocode» ранжирует роботов по параметру «total scores», который учитывает все вышеописанные тонкости. Его мы и будем использовать при подсчете приспособленности особи: итоговая приспособленность будет равняться доле в процентах очков нашего танка от суммы очков обеих танков, и принимает значение от 0 до 100. Соответственно, если значение приспособленности больше 50, то наш робот набрал больше очков, чем соперник, следовательно, сильнее его. Заметим, что согласно такой системе подсчета, первое место далеко не всегда занимает тот, кто победил в большинстве раундов боя. Ну тут мы разводим руками с фразой про мотороллер: создатели определили критерии, мы им следуем.Вообще говоря, вычисление приспособленности особи включает в себя проведение серии боев! Т.е. такой, казалось бы, незначительный пункт, как просчет приспособленности, состоит из таких плясок с бубном:
1) Наша система сохраняет закодированные хромосомы особи в файл chromosome.dat;
2) Для каждой особи запускается среда «Robocode», которая организовывает поединок. На вход ей мы подаем файл формата.battle, описывающий условия боя - список сражающихся танков, размеры поля, количество раундов и прочее;
3) Для битвы Robocode загружает танки, наш робот-оболочка считывает файл chromosome.dat с закодированным поведением, интерпретирует его в набор действий и ведет согласно им бой;
4) Среда Robocode по окончании поединка записывает результат битвы в файл results.txt и на этом завершает свою работу;
5) Наша система подбирает этот файл, парсит и выделяет из него значения total score нашего танка и соперника. Путем нехитрой арифметики получаем значение приспособленности.
Как наши их, да?
Подведем итоги нашего конструкторского бюро. Наша система состоит из двух частей (программ). Первая из них на основе генетического алгоритма собирает особь и сохраняет ее в виде набора строк, а вторая (код робота) интерпретирует ее (перерабатывая в дерево выражения) и осуществляет управление танком (вычисляя рекурсивным обходом значение деревьев выражений при заданных переменных, то есть текущем состоянии боя). Первая программа написана на языке СИ, вторая - на языке Java.При реализации генетического алгоритма число особей в популяции было выбрано равным 51 (25 пар + одна элитная особь). Один шаг эволюции (смена популяции) занимает около дюжины минут, следовательно, в сумме дело затягивается на несколько часов.
В качестве результата продемонстрируем итоги создания соперника роботам Walls и Crazy: 
В первом случае мы остановили процесс после достижения одной из особей приспособленности рубежа 70, во втором нам было достаточно, что средняя приспособленности особей поколения превышает 50.