Когда писалась эта статья, хабрапоиск по словосочетанию «Генетический алгоритм» выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить
Часть первая. Жизнь и творчество генетического алгоритма.
Начнем издалека. Есть некоторый набор задач, которые требуют решения. Наша цель — найти действия, которые смогут преобразовать Дано (начальные условия задач) в Ответ (целевое состояние).
Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо,
Хм, как же мы будем добиваться такой цели?
Бог нашего мира программ — это наша задача. Программы должны верить в нее, спариваться ради нее, ставить в нее честь свечки в церкви и жить с единственной целью — найти
Искусство спаривания программ
Думаю, многие из нас иногда испытывают жгучее желание применить к программам насильственное действие сексуального характера. Тут мы вынуждены заранее предупредить, что у нас такие межвидовые девиации не поощряются. У нас всё как завещала католическая церковь: программа с программой, только после брака… и партнеров не меняют, даже если тот томный парень купил тебе коктейль в баре. Хотя нет, вру, многоженство гаремного типа процветает. Да, и еще, несмотря на применение ниже таких слов как «отец» или «сын», программы у нас гермафродиты. Ну и инцест тоже… Тьфу, и я еще о церкви говорил *facepalm*. Ладно, об этом позже.
Вопрос скрещивания программ не так уж прост. Случайный обмен функциями, строками или переменными приведет к жирному потоку страшных слов в ваш адрес от компилятора/интерпретатора, а никак не новую программу. То есть необходимо найти способ скрестить программы корректно. Умные дяди нашли выход. А умные мальчики и девочки, изучавшие строения компиляторов, тоже уже догадались. Да-да, это синтаксическое дерево.
Сразу же умерю пыл: у нас борода еще не очень густая, поэтому будем использовать самые простые типы программ. Желающие могут отправиться в долину несметного богатства программирования, а нас тут всё просто — программа состоит из выражений, в свою очередь состоящих из простых функций с некоторой арностью, переменных и констант. Каждое выражение считает по одному из возвращаемых программой значений.
Например: некоторая особь-программа square из двух выражений, пытающаяся (не особо удачно) решить квадратное уравнение:
function square(a, b, c){
x1 = min(sin(b)*(a+1), 0);
x2 = 3 + exp(log(b*a));
return {x1, x2};
}С представлением определились, теперь надо разобраться с хранением. Так как вокруг этих самых программ еще предстоит множество плясок, в том числе передача их из одной часть системы в другую (которые, вообще говоря, в моем случае вообще были написаны на разных языках), то хранение нашей особи в виде дерева не очень-то удобное. Для представления более удобным способом (идеально — набор строк над некоторым конечным алфавитом) нашу особь-программу-набор_деревьев придется научиться кодировать/раскодировать.
Вроде как дерево, а вроде и нет
Итак, надо представить дерево в виде строки. Тут нас выручит сила karva-деревьев. Для начала стоит определиться с набором функций, переменных и констант, которые могут попасться в дереве. Переменные и константы соответствуют листьям дерева и будут называться терминалами, функции — остальным (внутренним) узлам дерева, именуются нетерминалами. Так же стоит обратить внимание на то, что функции могут иметь разное количество аргументов, посему такие знания («арность», — тихо пробежало слово по губам знатоков) нам очень даже понадобятся. В итоге получается таблица кодировки, например, такая:
| Нетерминалы | Терминалы | ||||||
|---|---|---|---|---|---|---|---|
| № | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| значок | n | + | * | if | 2 | a | b |
| арность | 1 | 2 | 2 | 4 | 0 | 0 | 0 |
| значение | -{a1} | {a1}+{a2} | {a1}*{a2} | if {a1}>{a2}? {a3}: {a4} | 2 | a | b |
Здесь n, +, *, if — функции; 2 — константа; a и b — переменные. В реальных задачах таблица поувесистей, с таким набором и квадратное уравнение не решить. Также надо иметь ввиду тот факт, что во избежании деления на нуль и других сценариев апокалипсиса все функции должны быть определены на всём множестве вещественных чисел (ну, или какое вы там множество используете в задаче). А то придется сидеть на карауле, отлавливать логарифмы от нуля и потом разбираться, что с этим делать. Мы люди не гордые, мы пойдем легким путем, исключая подобные варианты.
Так вот, с помощью такой таблицы гонять функции из дерева в строку и обратно не проблема. Например, пришла нам такая строка на расшифровку:
По таблице идентифицируем каждый элемент, вспоминаем также и про арность:
Теперь при помощи арности расставляем ссылки на аргументы функций:
Прошу обратить внимание на то, что последние 3 элемента списка оказались никому не нужны, и их значения никак не влияют на результат функции. Это получилось из-за того, что количество задействованных элементов списка, количество узлов дерева постоянно плавает в зависимости от их арностей. Так что лучше набрать про запас, чем потом мучиться с некорректным деревом.
Теперь если его потянуть вверх за первый элемент, то у нас в руке будет болтаться дерево выражения:
Значение функции можно вычислить рекурсивным обходом по дереву, она у нас оказывается такой:
У меня глаза от папы такие
Возвращаемся к самому горячему — к скрещиванию. Операции скрещивания программ мы ставим следующие условия: во-первых, две скрещивающиеся особи дают два потомка (т.е. размер популяции постоянный); во-вторых, в результате скрещивания потомки должны в определенной мере обладать характеристиками обеих родителей (т.е. яблоко не должно укатываться уж очень далеко от яблони). Мы теперь узнали, как программа будет представляться — это набор строк или деревьев. Соответственно, и скрещивать их можно как строки или как деревья.
Скрещивание деревьев представляет собой обмен случайно выбранными ветками. Скрещивание строк можно реализовать несколькими способами: одноточечная рекомбинация (кусочное склеивание), двуточечная рекомбинация, поэлементный обмен и др. Их можно описать длинными сложноподчиненными предложениями с деепричастными оборотами, но и одного взгляда на схемку достаточно, чтобы смекнуть, что к чему:
Стоит только заметить, что места склейки в рекомбинации выбираются случайно, так же как и в поэлементном скрещивании обмен совершается с некоторой вероятностью. Скрещивание деревьями в плане наследственности выглядит перспективней, но реализуется сложнее.
Эй, эта девушка со мной!
С самой интимной частью процесса разобрались (многие уже почувствовали через эту статью, насколько скудна личная жизнь автора). Теперь от взаимоотношения между парой особей перейдем к социальным основам.
Особи делятся на поколения. Новое поколение состоит из детей особей предыдущего поколения. Получается, есть текущее поколение сыновей и дочерей, поколение отцов и матерей, бабушек и дедушек, прабабушек и так далее до нулевого поколения — прародителей всего гордого народа. Каждая особь нового поколения после рождения пытается решить задачу, ее действия оценивает некоторая божественная функция пригодности, и в зависимости от ее оценок деятельности юнца особь получает некоторые шансы на воспроизведение потомства, то есть попадания в класс лучших представителей поколения, выбранных для продолжения рода. Наш мир суров и жесток, и по всем канонам антиутопий (или согласно идеям фюрера, как хотите) ни к чему не пригодные родители-пенсионеры после выполнения своей миссии рождения потомства отправляются в путешествие на газенвагене, освобождая жилплощадь паре своих чад. Дети идут по стопам родителей, и так из поколения в поколение.
Та самая функция приспособленности (или фитнесс-функция), которая выдает квоты на спаривание, должна адекватно оценивать способность особи решать задачу, и выдавать числовое выражение этой приспособленности (чем больше значение — тем лучше приспособленность). Например, в случае того самого квадратного уравнения это может быть мера того, насколько значение левой стороны уравнения близко к нулю при подставленных значениях x1, x2, вычисленных программой-особью.
Функция приспособленности выдает каждой особи поколения некоторое число, показывающее ее полезность, приспособленность. Это значение будет влиять на процедуру отбора (селекции): чем больше у особи это значение, тем больше у нее вероятность найти пару для скрещивания (и даже не одну). На практике, после вычисления приспособленности для всех особей поколения мы нормируем эти значения (чтобы сумма приспособленностей особей равнялась 1) и для каждого из мест для поцелуев бросается жребий (случайное число от 0 до 1), определяющий счастливчика. Альфа-самец может получить себе несколько мест, неудачник ничего не получит и так и останется в одиночестве
Существуют и другие способы селекции, но все они придерживаются общего правила: чем больше у особи приспособленность, тем больше она должна участвовать в скрещивании. Также в процесс можно включить опцию элитизма, когда лучший представитель поколения получает за заслуги перед Отечеством премию в виде дополнительных лет жизни: он переходит в следующее поколение без изменений, хотя и может параллельно наделать детей. Это позволяет нам не потерять очень удачное решение, которое может разрушиться в процессе скрещивания.
Тут же упомянем и мутацию. Это операция случайным образом с некоторой маленькой вероятностью меняет фрагмент особи, что позволяет разнообразить генофонд. Полезная вещь, вдруг такая мутация лактозу расщепить поможет! А если нет, и еще одна рука лишняя — то уж помучайся с ней до конца дней своих, потомство дать все равно шансов маловато.
Сотворения мира и Апокалипсис
Как переходить от поколения к поколению выяснили, теперь вопрос следующий — «а что стало первопричиной, с чего все началось?». В отличие от этого вашего мира, у нас для объяснения таких вещей не надо придумывать уловки типа «большого взрыва» или «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 взаимная ненависть), то прикрепляю исходники сего проекта. Разрабатывался и проверялся он под Linux (последняя убунта) с Robocode 1.7.2.2. Робота зовут Hulk (потому что жертва мутации). Остальное он расскажет вам сам (при помощи ридми).
Напоследок прошу прощения за научное невежество и каламбуры, меня в детстве с тумбочки уронили. Сам всё время опасаюсь, что меня выловят, посадят на пароход и пустят по Волге. Оглядываюсь.
upd: описанные выше способ — самый простой и примитивный. Для того, чтобы построенный робот был действительно конкурентоспособен для реальных боев robocode, необходима продолжительная работа напильником: тщательный подбор базовых элементов (функций, переменных и констант), вероятностей, способов скрещивания, отбора и мутации… с соответствующим временем на оценку каждого варианта. Поэтому в комментариях разумно встречаются предложения по улучшению бота, которые желающие могут проделать.
