Генетические алгоритмы в искусственных интеллектуальных системах. Введение.Основы генетических алгоритмов

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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.

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

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

Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).

Конечно, эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.

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

Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название "репродуктивный план Холланда" и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

Представление объектов

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

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

Кодирование признаков, представленных целыми числами

Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма. Значения кодов Грея рассмотрены в таблице ниже:

Таблица 1. Соответствие десятичных кодов и кодов Грея

Двоичное кодирование			Кодирование по коду Грея
Десятичный код	Двоичное значение	Шестнадцатеричное значение	Десятичный код	Двоичное значение	Шестнадцатеричное значение
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Таким образом, при кодировании целочисленного признака мы разбиваем его на тетрады и каждую тетраду преобразуем по коду Грея.

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

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

Кодирование признаков, которым соответствуют числа с плавающей точкой

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

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

Рассмотрим вышеописанную последовательность действий на примере:

Допустим, что значения признака лежат в интервале . При кодировании использовалось разбиение участка на 256 интервалов. Для кодирования их номера нам потребуется таким образом 8 бит. Допустим значение гена: 00100101bG (заглавная буква G показывает, что используется кодирование по коду Грея). Для начала, используя код Грея, найдем соответствующий ему номер интервала: 25hG->36h->54d. Теперь посмотрим, какой интервал ему соответствует… После несложных подсчетов получаем интервал . Значит значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.

Кодирование нечисловых данных

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

Определение фенотипа объекта по его генотипу

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому . В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит

0010

1010

1001

0100

1101

теперь мы можем определить значения признаков

Признак	Значение гена	Двоичное значение признака	Десятичное значение признака
Признак 1
Признак 2
Признак 3
Признак 4
Признак 5

Основные генетические операторы

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

из популяции выбираются две особи, которые будут родителями;
определяется (обычно случайным образом) точка разрыва;
потомок определяется как конкатенация части первого и второго родителя.

Рассмотрим функционирование этого оператора:

Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.

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

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

000

1111111

000

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

Схема функционирования генетического алгоритма

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

Инициировать начальный момент времени $t=0$. Случайным образом сформировать начальную популяцию, состоящую из $k$ особей. $B_0 = \{A_1,A_2, \dots, A_k\}$
Вычислить приспособленность каждой особи $F_{Ai} = fit(A_i)$ , $i=1…k$ и популяции в целом $F_t = fit(B_t)$ (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
Выбрать особь $A_c$ из популяции $A_c = \mbox Get(B_t)$
С определенной вероятностью (вероятностью кроссовера $P_c$) выбрать вторую особь из популяции $A_{c1} = \mbox Get(B_t)$ и произвести оператор кроссовера $A_c = \mbox {Crossing}(A_c, A_{c1})$.
С определенной вероятностью (вероятностью мутации $P_m$) выполнить оператор мутации $A_c = \mbox {mutation}(A_c)$.
С определенной вероятностью (вероятностью инверсии $P_i$) выполнить оператор инверсии $A_c = \mbox {inversion}(A_c)$.
Поместить полученную хромосому в новую популяцию $\mbox {insert} (B_{t+1},A_c)$.
Выполнить операции, начиная с пункта 3, $k$ раз.
Увеличить номер текущей эпохи $t=t+1$.
Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Теперь рассмотрим подробнее отдельные этапы алгоритма.

Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой . При использовании такого метода вероятность выбора хромосомы определяется ее приспособленностью, то есть $P_{Get(Ai)} ~ Fit(A_i)/Fit(B_t)$. Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор . Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма , которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.

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

Выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить к следующему экспонату ко второй части, где описывается создание на основе ГА бота для программистской игры 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.

После созерцания промыть глаза спиртом

Если кто не боится плакать кровавыми слезами в конвульсиях от созерцания быдлокодинга (особенно волосы начнут шевелиться от кода робота - у нас с java взаимная ненависть), то прикрепляю

В последнее время все больше «ходят» разговоры про новомодные алгоритмы, такие как нейронные сети и генетический алгоритм. Сегодня я расскажу про генетические алгоритмы, но давайте на этот раз постараемся обойтись без заумных определений и сложных терминах.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.

Щепотка истории

Как говорит Википедия: «Отец-основатель генетических алгоритмов Джон Холланд, который придумал использовать генетику в своих целях аж в 1975 году». Для справки в этом же году появился Альтаир 8800, и нет, это не террорист, а первый персональный компьютер. К тому времени Джону было уже целых 46 лет.

Где это используют

Поскольку алгоритм самообучающийся, то спектр применения крайне широк:

Задачи на графы
Задачи компоновки
Составление расписаний
Создание «Искусственного интеллекта»

Принцип действия

Генетический алгоритм - это в первую очередь эволюционный алгоритм, другими словами, основная фишка алгоритма - скрещивание (комбинирование). Как несложно догадаться идея алгоритма наглым образом взята у природы, благо она не подаст на это в суд. Так вот, путем перебора и самое главное отбора получается правильная «комбинация».
Алгоритм делится на три этапа:

Скрещивание
Селекция (отбор)
Формирования нового поколения

Если результат нас не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

Количество поколений (циклов) достигнет заранее выбранного максимума
Исчерпано время на мутацию

Более подробно о шагах

Создание новой популяции . На этом шаге создается начальная популяция, которая, вполне возможно, окажется не кошерной, однако велика вероятность, что алгоритм эту проблему исправит. Главное, чтобы они соответствовали «формату» и были «приспособлены к размножению».
Размножение . Ну тут все как у людей, для получения потомка требуется два родителя. Главное, чтобы потомок (ребенок) мог унаследовать у родителей их черты. При это размножаются все, а не только выжившие (эта фраза особенно абсурдна, но так как у нас все в сферическом вакууме, то можно все), в противном случае выделится один альфа самец, гены которого перекроют всех остальных, а нам это принципиально не приемлемо.
Мутации . Мутации схожи с размножением, из мутантов выбирают некое количество особей и изменяют их в соответствии с заранее определенными операциями.
Отбор . Тут начинается самое сладкое, мы начинаем выбирать из популяции долю тех, кто «пойдет дальше». При этом долю «выживших» после нашего отбора мы определяем заранее руками, указывая в виде параметра. Как ни печально, остальные особи должны погибнуть.

Практика

Вы успешно прослушали «сказку» про чудо-алгоритм и вполне возможно заждались, когда мы его начнем эксплуатировать наконец, хочу вас обрадовать, время настало.
Давайте рассмотрим на примере моих любимых Диофантовых уравнений (Уравнения с целочисленными корнями).
Наше уравнение: a+2b+3c+4d=30
Вы наверно уже подозреваете, что корни данного уравнения лежат на отрезке , поэтому мы берем 5
случайных значений a,b,c,d. (Ограничение в 30 взято специально для упрощения задачи)
И так, у нас есть первое поколение:

(1,28,15,3)
(14,9,2,4)
(13,5,7,3)
(23,8,16,19)
(9,13,5,2)

Для того чтобы вычислить коэффициенты выживаемости, подставим каждое решение в выражение. Расстояние от полученного значения до 30 и будет нужным значением.

|114-30|=84
|54-30|=24
|56-30|=26
|163-30|=133
|58-30|=28

Меньшие значения ближе к 30, соответственно они более желанны. Получается, что большие значения будут иметь меньший коэффициент выживаемости. Для создания системы вычислим вероятность выбора каждой (хромосомы). Но решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и исходя из этого вычислять проценты. (P.S. 0.135266 - сумма обратных коэффициентов )

(1/84)/0.135266 = 8.80%
(1/24)/0.135266 = 30.8%
(1/26)/0.135266 = 28.4%
(1/133)/0.135266 = 5.56%
(1/28)/0.135266 = 26.4%

Далее будем выбирать пять пар родителей, у которых будет ровно по одному ребенку. Давать волю случаю мы будем давать ровно пять раз, каждый раз шанс стать родителем будет одинаковым и будет равен шансу на выживание.
3-1, 5-2, 3-5, 2-5, 5-3
Как было сказано ранее, потомок содержит информацию о генах отца и матери. Это можно обеспечить различными способами, но в данном случае будет использоваться «кроссовер». (| = разделительная линия)

Х.-отец: a1 | b1,c1,d1 Х.-мать: a2 | b2,c2,d2 Х.-потомок: a1,b2,c2,d2 or a2,b1,c1,d1
Х.-отец: a1,b1 | c1,d1 Х.-мать: a2,b2 | c2,d2 Х.-потомок: a1,b1,c2,d2 or a2,b2,c1,d1
Х.-отец: a1,b1,c1 | d1 Х.-мать: a2,b2,c2 | d2 Х.-потомок: a1,b1,c1,d2 or a2,b2,c2,d1

Есть очень много путей передачи информации потомку, а кросс-овер - только один из множества. Расположение разделителя может быть абсолютно произвольным, как и то, отец или мать будут слева от черты.
А теперь сделаем тоже самое с потомками:

Х.-отец: (13 | 5,7,3) Х.-мать: (1 | 28,15,3) Х.-потомок: (13,28,15,3)
Х.-отец: (9,13 | 5,2) Х.-мать: (14,9 | 2,4) Х.-потомок: (9,13,2,4)
Х.-отец: (13,5,7 | 3) Х.-мать: (9,13,5 | 2) Х.-потомок: (13,5,7,2)
Х.-отец: (14 | 9,2,4) Х.-мать: (9 | 13,5,2) Х.-потомок: (14,13,5,2)
Х.-отец: (13,5 | 7, 3) Х.-мать: (9,13 | 5, 2) Х.-потомок: (13,5,5,2)

Теперь вычислим коэффициенты выживаемости потомков.

(13,28,15,3) - |126-30|=96(9,13,2,4) - |57-30|=27
(13,5,7,2) - |57-30|=22
(14,13,5,2) - |63-30|=33
(13,5,5,2) - |46-30|=16
Печально так как средняя приспособленность (fitness) потомков оказалась 38.8, а у родителей этот коэффициент равнялся 59.4. Именно в этот момент целесообразнее использовать мутацию, для этого заменим один или более значений на случайное число от 1 до 30.
Алгоритм будет работать до тех, пор, пока коэффициент выживаемости не будет равен нулю. Т.е. будет решением уравнения.
Системы с большей популяцией (например, 50 вместо 5-и сходятся к желаемому уровню (0) более быстро и стабильно.
Код
На этом простота заканчивается и начинается чудесный C++...
Класс на C++ требует 5 значений при инициализации: 4 коэффициента и результат. Для вышепривиденного примера это будет выглядеть так: CDiophantine dp(1,2,3,4,30);
Затем, чтобы решить уравнение, вызовите функцию Solve(), которая возвратит аллель, содержащую решение. Вызовите GetGene(), чтобы получить ген с правильными значениями a, b, c, d. Стандартная процедура main.cpp, использующая этот класс, может быть такой:
#include "" #include "diophantine.h" void main() { CDiophantine dp(1,2,3,4,30); int ans; ans = dp.Solve(); if (ans == -1) { cout << "No solution found." << endl; } else { gene gn = dp.GetGene(ans); cout << "The solution set to a+2b+3c+4d=30 is:\n"; cout << "a = " << gn.alleles << "." << endl; cout << "b = " << gn.alleles << "." << endl; cout << "c = " << gn.alleles << "." << endl; cout << "d = " << gn.alleles << "." << endl; } }
Сам класс CDiophantine:
#include #include #define MAXPOP 25 struct gene { int alleles; int fitness; float likelihood; // Test for equality. operator==(gene gn) { for (int i=0;i<4;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class CDiophantine { public: CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d. int Solve();// Solve the equation. // Returns a given gene. gene GetGene(int i) { return population[i];} protected: int ca,cb,cc,cd;// The coefficients. int result; gene population;// Population. int Fitness(gene &);// Fitness function. void GenerateLikelihoods(); // Generate likelihoods. float MultInv();// Creates the multiplicative inverse. int CreateFitnesses(); void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {} int CDiophantine::Solve() { int fitness = -1; // Generate initial population. srand((unsigned)time(NULL)); for(int i=0;i 25) break; } temppop[i] = Breed(parent1, parent2);// Create a child. } for(i=0;i
Статья основана на материалах Википедии и сайта