Приветствую вас еще раз, дорогие читатели!
Эта статья выкладывается в разгар сессии, так что я могу пропасть из комментариев.
1. Первое знакомство
2. Симуляция и простейший бот
Сегодня разберёмся с настройками симуляции и посмотрим на простейшего бота (или робота, как вам будет удобно). Нет, я не буду досконально рассматривать интерфейс программы – это будет вашим домашним заданием:-) И да, само понятие «генетический алгоритм» четко расписано в Википедии, поэтому опустим это объяснение.
2.1. Настройки симуляции.
Начнём с настроек симуляции. Дабы сохранить в Вас желание познавать что-то большее, чем просто кучу вкладок с непонятными настройками, спрячу эту неотформатированную часть статьи под спойлер.
- Выбрать в меню «File» пункт «New simulation»;
- Нажать соответствующую кнопку на панели инструментов;
- Нажать клавишу F1.
Рассмотрим содержимое вкладок в появившемся окне Simulation Settings. Сразу оговорюсь, что многие настройки представляются сомнительными – либо не работают, либо никак не действуют на симуляцию (а не одно ли это и тоже?). Некоторые такие функции я опущу, некоторые рассмотрю.
Вкладка «Species» (Рис. 1):
Рисунок 1
Native Species — список с загруженными кодами ДНК (ботами). Для управления списком можно использовать кнопки:
Add — позволяет рассматривать новые разновидности для добавления в список (попросту, добавить файл кода ДНК).
Duplicate – позволяет дать свойства выбранного бота другому боту.
Delete species — удаление ДНК из моделирования.
Comments – показывает комментарии из заголовка кода ДНК.
Разновидности начальных свойств (раздел Species starting properties):
Skin — рисунки на поверхности особей. Эти рисунки не имеют никакого значения, но когда робот видоизменяется, рисунок также видоизменяется, таким образом можно иметь представление о генетической разности между двумя ботами.
Change — случайное изменение начального рисунка.
Colour – задает начальный цвет бота, однако он тоже может измениться с мутациями.
Starting position — определяет начальную позицию для рода на поле моделирования.
Individuals – количество ботов одной разновидности в начале симуляции.
Starting energy — количество энергии каждой особи при старте.
Vegetable (autotroph) — с этой отметкой все особи разновидности накапливают энергию. Это должно способствовать воспроизведению новой энергии в симуляции. Автотрофы (организмы, рост и размножение которых не зависит от внешних источников органических соединений) работают подобно растениям, формируя основу пищевой цепочки. Такие особи будут всегда присутствовать в симуляции. Мутация не может изменить такую особь.
Fixed in place – боты данной разновидности не двигаются на поле моделирования. Является симуляцией растений. Мутация не может изменить особи данного вида.
Disable Vision – отключает глаза у ботов.
Disable Voluntary Movement – отключает случайные движения бота, которые позволяют им избежать зацикливания на поле моделирования (этот процесс ещё называют броуновским движением).
Disable Reproduction – отключает размножение.
Virus Immune – данный вид особей никогда не будет заражён вирусами.
Disable Mutation – отключает мутации ДНК.
Mutation rates (Рис. 2) — открывает окно определения начальных мутационных коэффициентов для данной разновидности. Имеется много различных мутационных коэффициентов, много типов мутаций ДНК. Много непонятных букв, может кто и разберёт — это предназначено для более тонкой настройки мутации и в большинстве случаев остаётся неизменным.
Рисунок 2
На вкладке «General» (Рис. 3) настраиваются следующие параметры:
Рисунок 3
Field Controls — размеры поля моделирования
Waste –задаёт пороговое значение количества мусора для всех ботов на поле моделирования. При установленном значении «-1» сброс мусора не производится.
Graphing – время обновления графиков (в циклах)
Population control – раздел, в котором можно регулировать популяцию на поле моделирования: задавать предел количества особей, в том числе автотрофов, количество энергии у автотрофов, период её восполнения, соотношение «энергия/тело», режим смены дня и ночи при достижении определенного количества суммарной энергии в поле моделирования и многое другое.
Вкладка «Physics and Costs» (Рис. 4) регулирует физику мира ботов и стоимость каждой операции ботов.
Рисунок 4
Раздел «Physics» имеет следующие настройки:
The Big Blue Screen Acts Like A – выбор типа поля моделирования. Оно может быть представлено жидкостью или плоской поверхностью, также имеет более продвинутые настройки при нажатии кнопки «Custom Physics» (Рис. 5): свойства жидкости, её плотность и скорость течения, гравитация мира, статический и кинетический коэффициенты, коэффициент броуновского движения;
Рисунок 5
Movement Efficiency – устанавливает модель движения ботов: биологический, механический и идеальный;
Brownian Movement – тип броуновского движения: бактерия или животное;
Vertical Gravity – тип вертикальной гравитации: Земля или Луна;
Max Velocity — максимальная скорость ботов;
Collision Elasticity – регулировка упругости столкновения ботов.
Раздел «Costs and Retuned Shots» (Рис. 6) содержит следующие настройки:
Costs – стоимость каждой операции бота. Либо отключена, либо задаётся в соответствии со стандартной стоимостью в лиге F1 (о лигах расскажу чуть позже), либо настраивается вручную при нажатии кнопки «Custom Simulation Costs». В появившемся окне «Costs» настраиваются стоимости команд ДНК, его изменения, ограничения и стоимость в зависимости от количества прожитых циклов.
Рисунок 6
Shot Energy Exchange Method – определяет количество энергии, которое может затратить бот для стрельбы. Может ограничиваться определенным числом либо быть пропорционально общему количество энергии бота. По умолчанию, бот может использовать всю свою энергию для стрельбы.
Вкладка «Mutations» (Рис. 7) содержит настройки мутации:
Рисунок 7
Disable All Mutations – отключить все мутации
Current Multiplier – устанавливает коэффициент мутации от 1/32x до 32x.
Oscillation Frequency – частота случайного изменения коэффициента мутации (фиксированно 1/16x и 16x в рамках выбранного коэффициента). Случайное изменение применяется через выбранное количество циклов.
Scripts – набор скриптов, действующих на ботов. Составляются самостоятельно по принципу «условие — ячейка ДНК – действие». Так, скрипт «If Robot gains Sysvar — pain — then Pause and highlight robot» означает «Если бот получил Боль, то приостановить симуляцию и выбрать данного бота». Условие задается как «бот получил», «бот потерял», «ДНК содержит» и «ДНК не содержит». Ячейка ДНК – это переменная, использующаяся при вычислении в ДНК. Действие задается как «Приостановить симуляцию и выбрать бота», «Убить бота» и «Сделать снимок».
Вкладка «Restart and League» (Рис. 8) содержит настройки рестарта симуляции и участия в лигах. Лиги – это соревнования между разработчиками ботов. Есть 4 основные лиги, которые отличаются правилами, начальными условиями и настройками мира. Так, лига F1 не имеет правил поведения ботов в мире, а лига F2 запрещает объединившимся ботам питаться и атаковать, а также отключает мутацию и избавляет мир от вирусов. Рестарт симуляции сводится к одному условию – начать заново, если все боты мертвы.
Рисунок 8
Вкладка «Internet» (Рис. 9) содержит настройки Интернет-режима, в котором разработчики ботов могут подключиться друг к другу и использовать одно поле моделирования. Является экспериментальной реализацией режима «Player versus Player», существующего во многих сетевых играх. В планах проверить работу этого режима. Как говорится, stay tuned!
Рисунок 9
Вкладка «Recording» (Рис. 10) имеет настройки сохранения текущей симуляции или ДНК лучших ботов через заданное время, а также создание базы данных, в которую заносится каждый бот, когда-либо существовавший в симуляции.
Рисунок 10
Чтобы загрузить или сохранить настройки симуляции, нужно нажать на кнопки «Load Settings» или «Save Settings» соответственно. Кнопка «Paused/Unpaused» переключает режим старта симуляции: начать симуляцию сразу либо не запускать ее. Кнопка «Start new» начнет симуляцию, а кнопка «Change» изменит свойства уже запущенной симуляции.
2.2. Простейший бот
Итак, мы подошли вплотную к рассказу о написании бота. В данной статье я не буду рассматривать строение ДНК целиком (припасу на будущее). Других ботов Вы можете посмотреть в папке «Robots» в директории программы.
Так что же представляет из себя обычный бот в системе Darwinbots. А вот что:
' How does it work?
cond
start
100 *.nrg 1000 sub sgn 0 floor 500 *.body sub sgn 0 floor mult .strbody mult store 100 500 *.nrg sub sgn 0 floor .fdbody mult store 200 *.shell sub 0 floor 200 ceil 200 *.shell sub sgn abs .mkshell mult store 10 *.venom sub 0 floor 10 ceil *.venom 10 sub sgn abs .strvenom mult store *.tiepres *51 *.tiepres sub sgn abs *.tiepres sgn mult .deltie mult store *51 *.refeye sgn -1 mult 1 add *.refeye *.myeye sub sgn abs *.eye5 35 sub 0 floor sgn mult mult .tie mult store *51 *.tie sgn *.tiepres *51 sub sgn abs -1 mult 1 add add sgn .tienum mult store -1 *.tie sgn *.tiepres *51 sub sgn abs -1 mult 1 add add sgn .tieloc mult store -1000 *.tie sgn *.tiepres *51 sub sgn abs -1 mult 1 add add sgn .tieval mult store 1 *.robage sgn 1 sub abs .tie mult store .mkshell *.vloc sgn -1 mult 1 add .vloc mult store -100 *.venval sgn 1 add .venval mult store 999 rnd 1 add *51 sgn -1 mult 1 add 51 mult store 200 *.aim add *.refeye *.myeye sub sgn abs -1 mult 1 add .setaim mult store *.maxvel *.vel sub 0 floor *.robage sgn *.refeye *.myeye sub sgn abs mult .up mult store *.refxpos *.refypos angle *.robage sgn *.refeye *.myeye sub sgn abs *.eye5 sgn mult mult .setaim mult store *.refveldx *.refeye *.myeye sub sgn abs *.eye5 sgn mult .dx mult store *.refeye *.myeye sub sgn abs -1 mult 1 add 50 mult inc 0 *50 30 sub 0 floor sgn .refeye mult store 0 *50 30 sub 0 floor sgn 50 mult store *.refshell 1 sub 0 floor sgn 3 mult 5 sub *.refeye sgn mult 1 sub *.refeye *.myeye sub sgn abs *.eye5 35 sub 0 floor sgn mult .shoot mult store *.shoot 3 add sgn 10 mult 0 floor *.refeye sgn 30 mult add *.refshell 1 sub 0 floor sgn 20 mult sub *.shoot sgn abs .shootval mult store 50 *.body 250 sub sgn 0 floor *.nrg 2000 sub sgn 0 floor *.eye5 30 sub 0 floor sgn -1 mult 1 add mult mult .repro mult store *.thisgene -1 mult 3 add abs *.genes 1 sub sgn .delgene mult store
stop
end
Удивлены сложности кода? На самом деле, этот бот написан пользователем под ником Shen в качестве эксперимента. Какого – скоро сами поймёте. На самом деле, это хороший пример углублённого изучения возможностей кода ДНК.
Итак, приступаем!
Код бота ДНК составляется из одного или нескольких генов, которые выполняются все вместе за один цикл симуляции. Гены представлены условиями, которые задаются следующими конструкциями:
Cond
<одно или более условий>
Start
<операции внутри гена>
Stop
или
Сond
<одно или более условий>
Else
<операции внутри гена>
Stop
Команда «Start» выполняет операции, если все условия верны, а команда «Else“ — если все условия ложны. Пример условия: a b > (если ‘а’ больше ‘b’, то условие верно). Могут использоваться следующие операции сравнения: = (равно), != (не равно), %= (приближённо равно — возвращает истину, если первое число отличается от второго не более, чем на 10%), !%= (выдает противоположный результат предыдущего сравнения), > (больше), < (меньше), >= (больше или равно), <= (меньше или равно), ~= (использует три числа, возвращает истину, если второе число больше первого на третье число процентов), !~= (выдает противоположный результат предыдущего сравнения). Принцип действия всех операций описан в разделе «Operators» официального сайта. На сайте хитровырезанная система навигации, поэтому нужный раздел придется искать догло и упорно.
Как вы уже, наверное, заметили, для записи операций используется обратная польская запись. Отличительной особенностью обратной польской нотации является то, что все аргументы (или операнды) расположены перед знаком операции. В общем виде запись выглядит следующим образом:
Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами. Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность её операндов и её знак, после чего выражение вычисляется дальше по тому же правилу. Результатом вычисления выражения становится результат последней вычисленной операции. Нувыпонели. Пример: нужно вычислить выражение (a+b)*(c+d). Обратная польская запись и, соответственно, код будет следующим:
a b add
c d add mult
Подробнее в статье на Википедии.
Гены оперируют с указателями памяти или числами. Например, 110 * или *110 означает «возврат значения из ячейки 110». Половина генетической памяти предопределена, чтобы функционировать в качестве свойств бота. Эта область памяти называется Sysvars (или Системные переменные). Например, ячейки от 501 до 509 содержат расстояния объектов в поле видимости каждого глазка бота и могут быть использованы операциями как *501…*509, так и *.eye1…*.eye9. Ячейки 1 (.up), 2 (.dn), 3 (.sx), 4 .(dx), 5 (.aimdx), 6 (.aimsx) и 11 (.maxvel) хранят скорость передвижения в разных направлениях, вокруг оси и максимальную скорость, зависящую от веса бота. Каждая системная переменная имеет название и номер, поэтому к ним можно обращаться по-разному. Свободные для использования ячейки указаны в разделе «Free Variables», а список системных переменных — в разделе «Sysvar»
Операции генов могут изменять значения ячеек памяти, например: 10 .up store или 10 1 store означают «задать скорость движения вперёд равной 10». Этот же результат будет, если выполнить операцию 5 5 add 1 store. Операция .up inc эквивалентно операции *.up 1 add .up store (извлечь значение из ячейки .up (10), прибавить единицу, записать в .up). Соответственно, операция .up dec означает «уменьшить скорость движения вперед на 1». Пример готового кода ДНК представлен ниже.
' комментарий обозначается апострофом в начале строки
' Gene 1 Movement
cond
*.nrg 100 > 'условие – пока энергия больше 100…
start
10 .dn store '…бот двигается назад со скоростью 10
stop
end 'конец кода ДНК
Создание бота. Выбор модели поведения и разработка генов.
Для данной статьи рассмотрим бота, который будет обладать большинством необходимых в мире ботов операций. ДНК будет состоять из четырёх генов: «Поиск пищи», «Поедание пищи», «Избегать объединения» и «Размножение».
Полный код ДНК представлен под спойлером ниже, взят с официального сайта проекта. Представленный ниже текст будет переводом обучащей статьи, включающей некоторые дополнения от себя.
' Gene 1 Food Finder
cond
*.eye5 0 >
*.refeye *.myeye !=
start
*.refveldx .dx store
*.refvelup 30 add .up store
stop' Gene 2 Eat Food
cond
*.eye5 50 >
*.refeye *.myeye !=
start
-1 .shoot store
*.refvelup .up store
stop' Gene 3 Avoiding Family
cond
*.eye5 0 =
*.refeye *.myeye = or
start
314 rnd .aimdx store
stop' Gene 4 Reproduce
cond
*.nrg 20000 >
start
10 .repro store
stopend
Итак, давайте разбирать по генам.
Ген «Поиск пищи»
' Gene 1 Food Finder
cond
*.eye5 0 >
*.refeye *.myeye !=
start
*.refveldx .dx store
*.refvelup 30 add .up store
stop
Для удобства записи бота, которого мы «выделим» и чей ДНК будем рассматривать, назовём «нашим». Это не отменяет тот факт, что ботов с одинаковым кодом может быть несколько.
Рассмотрим условия в этом гене. Значение eye5 будет больше нуля, если другой бот находится прямо перед нашим (в поле зрения пятого, центрального глазка). Таким образом, данный код позже заставит нашего бота атаковать только тогда, когда враг находится прямо «под носом». Строка *.refeye *.myeye!= является классической распознающей системой, используемой ботами с начала разработки программы. Если другие боты не имеют такого же количества глаз, как у нашего, то он является не родственником, а пищей. Практически так же, как в реальном мире:-).
Переходим к операциям. Refveldx и Refvelup возвращают скорость любого бота, попавшего в поле зрения нашего. Значения являются относительными. Операция *.refveldx .dx store позволит нашему боту двигаться в бок со скоростью движения бота, попавшего в поле зрения. Это позволит нашему подопытному не стать жертвой бота, крутящегося вокруг и стреляющего по всем сторонам. Операция *.refvelup 30 add .up store заставит нашего бота двигаться вперед на 30 единиц скорости быстрее, чем враг, чтобы догнать добычу. Естественно, скорость не будет больше, чем значение ячейки .maxvel, то есть максимальной скорости в зависимости о веса. Операции этого гена также могут быть записаны следующим образом:
*.refvelup .up store
*.up 30 add .up store
Ген «Поедание пищи»
' Gene 2 Eat Food
cond
*.eye5 50 >
*.refeye *.myeye !=
start
-1 .shoot store
*.refvelup .up store
stop
Разберём условия. Как и в предыдущем гене, наш бот будет реагировать только на бота, попавшего в поле зрения пятого глазка. Однако в этом гене поиск будет проходить на целых 50 единиц расстояния вперёд. Если бот приблизится на расстояние, меньшее 50, то это будет сигналом к атаке. Второе правило осталось неизменным и взято из первого гена. Причиной указывания одной и той же операции распознавания является особенностью выполнения кода ДНК: все гены выполняются последовательно за один цикл, каждый следующий ген может использовать только значения ячеек памяти и не может обратиться к результатам выполнения прошлого гена, если они не были записаны в память.
Рассмотрим реакцию бота на выполнение всех условий. В этом коде, как уже стало видно, нет операции движения. Это тоже следствие последовательного выполнения кода ДНК – скорость бота была записана ранее, поэтому наш бот будет двигаться именно с ней, если, конечно, в следующем гене скорость не изменят. Строка -1 .shoot заставит бота стрелять в выбранную им цель столько раз, сколько ему потребуется. Строка *.refvelup .up store заставит бота снизить скорость и начать двигаться со скоростью своей цели. Это важная операция, поскольку столкновения ботов могут привести к потери времени и энергии.
Ген «Избегать объединения»
' Gene 3 Avoiding Family
cond
*.eye5 0 =
*.refeye *.myeye = or
start
314 rnd .aimdx store
stop
Это условие немного сложнее предыдущего. Здесь используется логический оператор or (или). Ячейка .eye5 равно нулю, если никого не видно. Распознавание вернёт булево «false», если перед глазами вдруг появится особь, аналогичная нашей. Тут в силу вступает оператор or. С помощью него общее условие для выполнения будет верным, если одно из входящих в него условий будет верным – либо если никого не будет рядом, либо если рядом «свой». Ну тут, думаю, понятнее некуда.
Если условие сработало, то бот начнет крутиться вправо на случайные углы от 0 до 314 градусов. Этой операцией наш бот сможет более рационально осматривать окрестности мира в поисках пищи. В принципе, можно поставить любое значение угла (даже не случайное), однако слишком маленький угол приведёт к ухудшению способности к поиску пищи.
Также этот ген является классическим методом избегания ботом объединения с другими, если, конечно, не стандартом. Про объединения расскажу в следующих статьях.
Ген «Размножение»
' Gene 4 Reproduce
cond
*.nrg 20000 >
start
10 .repro store
stop
Последний ген задает правила размножения бота.
Кратко этот ген можно объяснить так: если энергия бота больше 20000, то создается новое поколение бота со стартовым количеством энергии, равным 10% от энергии родителя. Конечно, потомку можно отдать и 50%, однако есть риск потерять оба поколения. С этим же риском можно связать уменьшение необходимого количества энергии для размножения. Чем быстрее бот размножается, тем меньше энергии он может отдать потомку.
Вывод
Данный бот является отличным пособием для изучения основ генетического алгоритма программы Darwinbots, так как содержит в себе основные функции особи. Однако этот бот не является совершенным — при определённых обстоятельствах он обречён на гибель, как и любой другой бот. Это открывает разработчику возможность совершенствовать своих ботов, пробовать запускать их в лиги либо в Интернет-режиме, выявлять сильные и слабые стороны и дальше совершенствовать. Боты, написанные специально для участия в лигах, могут содержать в себе больше 20 генов с несколькими десятками операций, могут содержать всего два гена с огромным количеством условий и операций, а могут и вовсе иметь один ген, в котором безусловно выполняется куча операций (конечно, не совсем безусловно — применяются логические операторы. Такой бот был в первом примере.) – все зависит от стратегии разработчика. В ДНК можно использовать огромное количество системных переменных, которые отвечают почти за каждый аспект жизни бота, начиная от широты зрения и сброса мусора и заканчивая свойствами внутри объединённой особи и счётчиком общее количество особей на поле моделирования. Если у вас появится желание, я попробую разобрать сложного бота в одной из следующих статей.
Программа Darwinbots не ставит ограничений по сложности кода, однако чем сложнее бот, тем больше ресурсов компьютера понадобится для вычисления следующих циклов. Разработчики рекомендуют запускать симуляцию на свободном компьютере и оставить на одну-две недели, предварительно настроив симуляцию на сохранение лучших особей. Таким образом, можно изучить несколько поколений ботов и дождаться глобального естественного отбора.
На официальном форуме проекта можно задать любой интересующий вопрос, и на него с радостью ответят. К сожалению некоторых, для этого нужно иметь хотя бы начальные знания английского языка.
Надеюсь, эта обширная статья была более увлекательной, чем вводная. Уверен, что многие после этой статьи будут пробовать писать своих ботов. Возможно, даже устроим небольшой парад ботов в комментариях. Но это в будущем, если программа заинтересует читателей.
Как всегда, в комментариях я принимаю ваши пожелания по поводу содержания следующих статей. Спишемся!
Источники:
1. Единственная лабораторная работа по программе во всем Рунете, с нее я и начал работу над курсовой;
2. Официальный сайт проекта Darwinbots;
3. Википедия.
Автор: cjmaxik
