Пользователь
0,2
рейтинг
28 октября 2012 в 14:30

Разработка → Evo, часть 2 — о скрещивании

Приветствую вас, хабражители!

В продолжение поста «Аналог игры «Жизнь» — Evo» хотелось бы дать более подробное описание команд «языка генов», который используется в Evo, и поделиться своими соображениями по методам скрещивания особей в этой игре.

Генетический код


Генетический код особей в Evo представляет собой последовательность байт практически неограниченной длины. При этом каждый байт трактуется как команда для клеточного автомата. У автомата 2 ленты: команд и памяти. Соответственно есть два указателя cmd_ptr и mem_ptr. В качестве ОЗУ животного используется переменная data, размерностью в 1 байт (8 бит).
На текущий момент есть следующие команды:
  • 9 команд управления исполнением «генетического» кода:
    1. nop — ничего не делать
    2. move_cmd_left — передвинуть указатель команд влево
    3. move_cmd_right — передвинуть указатель команд вправо
    4. jump_to — сдвинуть указатель команд вправо на Х позиций (следующий за командой байт трактуется как signed char, то есть отрицательные значения сдвинут указатель влево)
    5. jump_to_ifz — то же, что и jump_to, но при условии, что значение data == 0
    6. jump_to_ifnz — то же, что и jump_to, но при условии, что значение data != 0
    7. start — то же, что и nop, просто метка для начала какого-то обособленного куска (начало функции)
    8. restart — сбрасывает значение cmd_ptr в 0
    9. end — конец функции, заставлет искать дальше по ленте метку start, с которой продолжить выполнение (если метки нет, то cmd_ptr=0)
  • 8 команд, позволяющих живности осмотреться вокруг себя (результаты сохраняются в ОЗУ живности, в переменной data):
    1. eye_up_distance — получить значение дистанции до ближайшего объекта вверх
    2. eye_down_distance — получить значение дистанции до ближайшего объекта вниз
    3. eye_left_distance — получить значение дистанции до ближайшего объекта влево
    4. eye_right_distance — получить значение дистанции до ближайшего объекта вправо
    5. touch_up — получить значение типа ближайшего объекта вверх
    6. touch_down — получить значение типа ближайшего объекта вниз
    7. touch_left — получить значение типа ближайшего объекта влево
    8. touch_right — получить значение типа ближайшего объекта вправо
  • 10 команд управления памятью живности:
    1. move_mem_left — сдвинуть указатель mem_ptr влево
    2. move_mem_right — сдвинуть указатель mem_ptr влево
    3. save_to_mem — сохранить в текущую ячейку содержимое ОЗУ живности (data)
    4. load_from_mem — загрузить значение из текущей ячейки в ОЗУ живности (data)
    5. add_mem — прибавить к data значение текущей ячейки памяти
    6. sub_mem — вычесть из data значение текущей ячейки памяти
    7. set_mem_ptr — установить mem_ptr равным значению ОЗУ
    8. data_clear — очитстить ОЗУ
    9. data_inc — инкрементировать значение в ОЗУ
    10. data_dec — декрементировать значение в ОЗУ
  • 12 команд для действий, которые живность может делать (передавать сигналы объекту World):
    1. action_move_left — живность двигается влево
    2. action_move_right — живность двигается влево
    3. action_move_up — живность двигается влево
    4. action_move_down — живность двигается влево
    5. action_eat_left — живность пытается съесть объект слева
    6. action_eat_right — живность пытается съесть объект слева
    7. action_eat_up — живность пытается съесть объект слева
    8. action_eat_down — живность пытается съесть объект слева
    9. action_wait — живность ждёт, пропуск хода
    10. action_suicide — живность самоуничтожается
    11. action_split — живность делится клонированием
    12. action_split_mutate — живность делится клонированием, но с некоторыми мутациями


Пример программы


В принципе такого набора команд достаточно, чтобы делать циклы и ветвления. Другой вопрос, что описывать алгоритмы на таком языке не так удобно, как на С++, например.
Но для примера покажу Вам программу, которая заставляет живность двигаться по квадратной спирали:
      start
         action_split
         load_from_mem //load from var1
         move_mem_right //save var2
         data_dec
         save_to_mem

      move_mem_right //save to var3
      data_dec
      save_to_mem
         //right
             action_move_right
             data_dec
         jump_to_ifnz
         AnimalCommand(-3)
         //up
         load_from_mem
         data_dec
         save_to_mem
             action_move_up
             data_dec
         jump_to_ifnz
         AnimalCommand(-3)
         //left
         load_from_mem
         data_dec
         save_to_mem
             action_move_left
             data_dec
         jump_to_ifnz
         AnimalCommand(-3)
         //down
         load_from_mem
         data_dec
         save_to_mem
             action_move_down
             data_dec
         jump_to_ifnz
         AnimalCommand(-3)
         //dec var2
         move_mem_left
         load_from_mem
         data_dec
         save_to_mem
         jump_to_ifnz
         AnimalCommand(-33)
         move_mem_left // restore var1
     end;
  

В память же загружаются 3 значения: 10, 0, 0. Алгоритм пояснять не буду. По-моему всё довольно очевидно.
Этот код вы можете найти в mainwindow.cpp:117.

О мутациях


Мутации в игре сейчас реализованы так. По желанию организма размножиться клонированием с мутацией создается клон. Клон подвергается мутациям в количестве от 0 до 9 (на усмотрение великого рандома). Для каждой мутации великий рандом выбирает один из 4 вариантов:
  • 1 произвольный байт кода заменяется на произвольное значение
  • к ДНК прибавляется произвольный байт
  • от ДНК откусывается байт в произвольной позиции
  • в ДНК в произвольную позицию вставляется произвольный байт (свежий коммит)


О скрещивании


Теперь перейдём к размышлениям о том, как нам скрещивать два организма. Их код может быть разной длины, они могут иметь разную память.
  • Первое, что напрашивается на ум, это просто слепить 2 ДНК в одну большей длины. Но в таком случае вторая часть алгоритма может не функционировать вовсе, или же работать крайне редко. Что ж, хорошо — будет фактически рецессивным геном.
  • Можно взять скажем 3 произвольных точки на каждом ДНК и собрать новую по принципу: кусок 0-1 от первой ДНК, 1-2 от второй, 2-3 от первой, 3-4 от второй. Причём куски могут быть и нулевой длины.
  • Можно искать метки start|end и лепить новую ДНК, просто собирая воедино функции от разных организмов. Это заставит живности пытаться как-то структурировать код.
  • Есть вариант брать в цикле по байту от каждого организма пока ДНК их не кончится. Получится некий такой Франкинштейн, но свойства его будут весьма интересны.

Вот пожалуй и все варианты, которые сходу приходят мне в голову. Над наследованием памяти ещё не думал.
А! Вот ещё о чем забыл. Как вы считаете, что лучше?
  1. По истечению Х раундов брать Y самых-самых и скрещивать их. При этом убить всю популяцию, мир заселить этими Y особями и их потомками.
  2. Каждые Х раундов брать Y (от 2 до 5, скажем) самых сильных и скрещивать их, добавляя их потомство в популяцию.
  3. Третий вариант — тот который придумаете вы и напишете в комментариях.

Размышлений на тему не густо, конечно, но я надеюсь на богатое воображение хабражителей.
Спасибо. Жду отзывов.
Владимир @icoz
карма
45,0
рейтинг 0,2
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (28)

  • 0
    Если посмотреть на биологические аналоги, при скрещивании происходит обмен генами: блоками порядка 10^3-10^4 «инструкций». То есть, программу нужно делить на большие слабо связанные модули и при скрещивании обмениваться ими.

    К сожалению, биологические геномы содержат от 3*10^6 до 10^11 инструкций (нуклеотидных пар).
    Поскольку меньше не встречается, видимо есть нижний предел сложности, под которым размножающийся в сложных условиях организм «не заведётся».

    Так что апгредим железо для эмулятора, да ищем индусов, которые напишут эти гигантские гигабайты кода.
    • 0
      Мощно.
      Пока в программе жестко задана длина генома при генерации равной 1500 байтам.
      Можно это тоже параметром сделать и вывести на форму для ввода.
      Но интересно наблюдать как мелкие куски будут объединяться во что-то большее.
  • 0
    Искусственная жизнь исследовалась в академических кругах в прошлом веке, сейчас мода прошла.
    В начале 90-х меня поразила статья в каком-то науч-поп журнале («Техника-молодёжи», возможно), где описывался симулятор TIERRA Томаса Рея. Якобы он достиг конкуренции между организмами и т.п.

    А визуализация «бульона» (по тем годам) была просто шикарной:
    tierra.jpg

    Попробуйте отыскать старые статьи, хотя возможно в интернет они не перенесены никем.
    • +2
      Хм. Бесспорно интересно. Статья в википедии.
      Причем у него даже были паразиты, симбионты… Молодец.
      Другой вопрос, что он ученый, которым этим занимался, а я делал программу «just for fun».
      Ни на какую академичность не претендую. Просто нравится наблюдать за живностью.
  • 0
    Я бы вынес в геном для начала параметры «конфигурации», а не поведения — дальность и четкость зрения, чуткость обоняния, слуха. Потом бы уже занялся параметрами поведения — реакция на объекты,.

    И, кстати, я бы животных сделал не императивными, а событийными. И вместо своего сомнительного байткода запилил туда, скажем, Lua. Или Erlang?.. Вот тут надо подумать, у меня не продумана модель взаимодействия «актормир».
    • 0
      Понятно, что лучше событийная модель лучше. Только она и сложнее насколько? Если какой-нибудь язык запиливать, то автоматическая генерация уже не получится — надо будет, чтобы человек писал.
      • 0
        Я как раз об этом — первоначальные блоки поведения писать самому, а в геноме оставить лишь их активаторы. Скажем, «хищник-травоядное». Позже можно допилить до decision network, частично передаваемой потомству.
        «Скрещивать» программы поведения мне кажется не самой интересной идеей. Слишком упрощенной.

        Насчет сложности событийной модели — ну, тут как посмотреть. Код поведения станет явно лаконичнее, хотя, конечно, симуляция несколько усложнится. Самая ресурсоемкая задача — выбор получателей события. Это нужно прямо сильно оптимизировать — событий много, получатели определяются исходя из расстояния до источника события…
        • +1
          Так для обеспечения разнообразия требуется написание очень большого количества «первоначальных блоков поведения». Я думаю не меньше нескольких десятков.
          И здесь выбор все равно весьма ограничен.
          В моем же варианте, лучше доработать набор команд для упрощения образования циклов и ветвлений, что позволит живностям проще создавать более сложные алгоритмы.
          Суть была в том, чтобы с использованием минимума кода получить максимум фана и веселья.

          Хоть идея ваша беспорно правильна, но в моем случае она неприменима.
  • 0
    Было бы интересно добавить к живности характеристики вроде силы и тд. Получится РПГ в вакууме.
    • 0
      Поясните. Не очень понял.
      То есть не просто одно животное съело другое? Надо несколько раз укусить?
      • 0
        Ну да.У одного животного благодаря сильной ДНК больше жизни, у другого- больше силы и т.д.
        Конечно, это сильно замедлит расчеты.Но их как раз можно было бы рассчитывать на GPU.
        • 0
          А как определить какая ДНК сильнее?
          Если строить ДНК не по принципу кода, а набором характеристик, таких как:
          1) скорость движения
          2) сила атаки
          3) количество жизни
          4) наличие брони
          ну и т.д., то все организмы будут банально стремиться к увеличению всех этих параметров
          • 0
            можно ввести понятие боевой опыт. То есть чем больше убил тем хитрее становится тем больше урона за укус наносит. А понятие здоровья может браться из фитнесса.
            • 0
              Надо пересмотреть само понятие фитнесс-функции.
              Т.к. сейчас здоровее будет тот, кто дольше прожил. А это неправильно.
              Надо вводить в рассмотрение большее количество факторов.
        • +2
          Тогда уж заодно по карте разбросать магические предметы.
          Например, «Адамантовый меч погибели одноклеточных» => +5 к повреждению организмов с короткой программой.
  • +1
    Мне кажется, результат fitness-функции не должен зависеть напрямую от времени жизни особи. Если вы сделаете размножение через скрещивание, то первыми в приоритете будут те, кто тупо дольше жил, даже если на поле уже существуют более приспособленные особи, так как последние могли просто не успеть съесть достаточно травы. Если разница во времени их рождения будет в несколько сотен тысяч раундов, то средний по показателям организм уже, возможно, никто и не обойдет, и он так и будет размножаться, а новые более приспособленные организмы будут умирать.
    В общем, если оставить расчет fitness таким, какой он есть, то предложенный вами второй вариант не подходит, по моему мнению. Только полное убийство всей популяции, через X раундов.

    Еще хотелось бы, чтобы вы сделали ограничения по краям (просто камнями застроить, например), а то сейчас они все ходят лишь в одну сторону. С ограничием такие организмы бы упирались в стену и умирали, а чтобы выжить им пришлось находить более сложные алгоритмы перемещения.
    • 0
      Отлично! Я не подумал об этом! Спасибо.
      В ближайшее время надеюсь реализовать.
  • 0
    Есть смысл примерить на эту задачу язык PUSH (видел реализацию на sf.net), он придуман как раз для таких вещей. И обязательно вставить кроссовер, обычный или двухточечный, организмы смогут обмениваться информацией, сходимость к фитнессу резко повышается. В некоторых вариантах мутации становятся вообще ненужными, т.к. имитируются кроссовером со случайным геномом.
    Вообще это задачки для классического ГП. Ваш подход ближе к AIMGP или решению en.wikipedia.org/wiki/Santa_Fe_Trail_problem

    А вот кстати один древний проект alife с 3д визуализацией
    www.framsticks.com/
    куча видео, проект очень старый.
    Когда-то вел список таких, интересовался темой, сейчас посмотрел — почти все дохлое.

    Вообще тема древняя но по прежнему интересная.

    Мне когда-то было интересно прикрутить генетику к вот этому: sodaplay.com/
    Там организмы более живенькие.

    А если сделать фенотип организма L-системой, то будет и живенько и красиво.
    • 0
      Крайне интересно.
      А вот язык PUSH — это круто! Можно по аналогии что-то сделать. (Хочется своё же!)
      sourceforge.net/projects/push-evolve/
      faculty.hampshire.edu/lspector/push.html
      faculty.hampshire.edu/lspector/push3-description.html
      • 0
        PUSH достаточно серьезно проработан под эти задачи.
        Например такая деталь — в обычном языке случайно сгенерированный цикл приведет к долгому выполнению программы или зависанию.
        А в PUSH циклы реализуются по обходу стека.
        Вообще достаточно интересный язык, я только первую версию ковырял, сейчас уже третья.
        • 0
          Да, займусь более подробным изучением на досуге.
          Может и сделаю что-то подобное.
  • +1
    Выбор родителей для скрещивания делается так.
    Берется N случайных особей и из них выбирается с лучшим фитнессом.
    N по традиции обычно равно 7.
    :-)

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

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

    Если надо сылок накидать — пишите, но основные моменты были исследованы в схемах с tree-based genomes а у вас геном линейный, там есть отличия в параметрах.
    Например для генома-дерева кроссовер совсем по другому выглядит и сходится быстрее.
    • 0
      Класс! Ссылки в студию!

      Скажите, а вы этим просто интересовались или работаете/работали в данной области? Хватка чувствуется.
      • +2
        Работаю, деньги за это получаю.
        Собственно стало скучно просто применять очередной паттерн проектирования в очередной типовой задаче, вот в какой-то момент и мигрировал в эту область.
        Ну и ленив я, зачем писать программы, когда программы могут написать все за меня.
        :-)

        По ссылкам — дальше много буков.

        Во первых надо различать GP (генетическое программирование) и GA (генетические алгоритмы).
        Ваш случай — GP и это самый интересный вариант.

        Сам я его изучал по вот этой книжке.

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

        Быстрый поиск нашел ее на здесь
        Надеюсь не умрет от хабраэффекта.

        Первые 70 страниц можно пропустить.
        Но можно и не пропускать.

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

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

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

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

        Потом есть такой метод как AIMGP, на его основе делались первые автономные роботы-трейдеры, вот тут автор сделал такую конторку www.tradingsystemlab.com/introgeneticprograms.aspx
        Когда она открылась, лицензия на одного клиента стоила емнип 60 килобаксов

        Там суть похожа, но геном — это линейная последовательность ассемблерных команд, с рядом ограничений против зацикливания.
        Т.е. примерно как у вас реализовано.
        Ссылку не дам, искать надо по «Nordin AIMGP formal description», но в открытом доступе чего-то не нашел.

        Есть еще такая штука как Grammatical Evolution.
        Достаточно привлекательная, ей задается грамматика языка и она по ней строит правильные программы и проверяет их.
        Но чего-то она у меня не показала столь хороших результатов как первый вариант, я ее тоже наваял и несколько пожалел о потраченном времени.
        Есть в википедии даже.

        Ну и есть over9000 модификаций, каждый придумывает свою версию, Cartesian GP (CGP), Stronlty typed GP (STGP), в общем там свои тараканы.

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

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

        Хотя вот есть например такое издание как jasss.soc.surrey.ac.uk/JASSS.html специализирующееся на Agent Based Modeling (ABM)
        Со своими фреймворками и симуляторами.
        Например вас наверное заинтересует вот такая публикация jasss.soc.surrey.ac.uk/14/2/5.html

        Названия статей там говорят сами за себя

        Nonlinear Dynamics of Crime and Violence in Urban Settings
        jasss.soc.surrey.ac.uk/15/1/2.html
        Это с псевдокодами симуляции и картинками примерно как у вас.

        A Virtual Laboratory for the Study of History and Cultural Dynamics
        jasss.soc.surrey.ac.uk/14/4/19.html

        Sympathy and Punishment: Evolution of Cooperation in Public Goods Game
        jasss.soc.surrey.ac.uk/14/4/20.html
        Это почему общество основанное на кооперации не выживает если состоит из классов производителей и воров
        Но выживает если появляются менты, наказывающие воров и получающие за это мзду от кооператоров.
        :-)

        A Computational Model of Worker Protest
        jasss.soc.surrey.ac.uk/14/3/1.html

        В общем интересный такой журнальчик, после его статей можно свой оккупай начинать.
        :-)

        Тоже рекомендую.

        Это я к тому привел, чтобы вы не думали, что то, что вы написали — просто игрушка.
        На похожих игрушках просчитываются многие реальные серьезные вещи.
        • 0
          Может быть стоит статейку по этому поводу накатать?
          Тем более, что объем комментария уже на пост тянет…

          За инфу огромное спасибо. Буду удовлетворять своё любопытство.
          • 0
            Статейку писать сложно, у меня тут уже лежит недописанная статейка по искусственным иммунным системам, добавлять еще сверху в очередь задач бессмысленно.
            Хроническая нехватка времени, увы.

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

            Вроде в книжках по AI были описания разных типов ГП, но обычно они очень поверхностные и недостаточны для полной реализации.
  • +1
    Я требую продолжения!
    • 0
      Не вы один!

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.