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

в 10:30, , рубрики: evo, qt, qt4, Алгоритмы, естественный отбор, игра жизнь, искусственный интеллект, метки: , , , ,

Приветствую вас, читатели!
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

Поделиться

* - обязательные к заполнению поля