Новое поведение в не цикличном мире

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

Всем спасибо 🙂

Advertisements

Ошибка!

В предыдущих постах, я упоминал о том, что искомая программа сгенерированна и задача поиска 90% решений найдена. Но это не так 🙂 Я проанализировал код, который подобрал решения для 56 записей из 60 и пришел к выводу, что он не выполняет свою функцию… После небольшой отладки, я понял, что решение было найдено, но оно полностью зависело от рантайма в момент выполнения этого кода моей виртуальной машиной. Под рантаймом я понимаю состояние памяти организмов, и конкретные числа полученные функцией Math.random(). Помимо этого, я нашел несколько критических ошибок: например, лучшие организмы не всегда с большей вероятностью давали потомство. Короче говоря, мне таки удалось получить работоспособную программу да еще и в 3х вариантах 🙂 Вуаля:

// winner 1 -------------------
v1 = v1 & v0
v0 = +!v2
v1 = v1 | v3
v0 = v1 > v3
v1 = v3 >> v1
if (v1 < v0) {
    v2 = 6
}
v0 = 4
v1 = 2
v0 = v3 >> v2

// winner 2 -------------------
if (v1 > v3) {
    v0 = org.toMem(v1)
    v3 = v3 << v2
}
v2 = v0 << v1
v1 = org.toMem(v0)
v0 = v0 < v2
if (v2 > v3) {
    if (v0 < v3) {
        v2 = 3
        v0 = v2 & v1
    }
}

// winner 3 -------------------
v3 = v3 + v3
v1 = v0 & v1
v1 = v1 - v3
v1 = v1 >> v0
v2 = v1 >>> v3
v3 = 8
v0 = 3
v2 = v0 + v2
v1 = +!v0
v0 = v3 >> v2

В данном случае нужно сделать небольшую оговорку. Данные победители нашли 14 решений из 15 исходных. Я специально уменьшил выборку, чтобы ускорить процесс.

Update на 06.08.2017:

v3 = v3 + v3
if (v3 > v1) {
    v0 = 5
    v3 = v0 & v3
    v2 = v1 >>> v0
    v0 = 2
    if (v2 != v0) {
        if (v2 == v3) {
            v1 = +!v0
            v3 = 9
            v3 = v3 << v3
            v0 = v0 - v3
            v3 = 15
            v2 = v0 << v3
            v0 = v2 < v1
        }
    }
}

53 из 60 – это 88.3% 🙂

Теперь я спокоен 🙂

Практическое применение ГА (финал)

Итак, друзья, jevo.js достиг своего финиша, подобрав 56 решений для 60 блоков данных. 90% успеха – это заданный мной барьер. Так что, задача решена успешно 🙂 Код ниже:

v1 = 385938
if (v0 > v0) {
  v2 = +!v3
  v3 = +!v3
  v0 = 675503
  v1 = +!v1
  v3 = org.fromMem()
  v3 = 497086
  v1 = org.toMem(v2)
  v3 = v2 & v0
  v1 = +!v2
  v0 = org.toMem(v2)
  v1 = org.fromMem()
  v0 = org.toMem(v3)
}
v2 = v1
v2 = v3 & v1
v1 = org.fromMem()
v3 = +!v2
v0 = +!v3
if (v3 > v3) {
  v0 = org.fromMem()
  v2 = org.fromMem()
  v3 = +!v3
  v1 = +!v3
  v1 = org.fromMem()
  if (v2 != v2) {
    v2 = org.toMem(v1)
    v0 = v3 + v1
    v2 = org.fromMem()
    v2 = org.toMem(v0)
    v1 = org.fromMem()
    v3 = v1 != v1
    v3 = +!v0
    v3 = org.fromMem()
    v3 = +!v2
    v3 = v3 + v1
    v3 = +!v0
    if (v1 == v2) {
      v3 = +!v1
      v3 = v0
      v2 = org.toMem(v1)
    }
    v3 = org.toMem(v1)
    v3 = org.toMem(v1)
  }
}

Переход на JavaScript

Как бы необычно это не звучало, но я решил портировать на JS весь код проекта jevo. JavaScript уже достаточно созрел для такого рода проектов. И тому есть несколько причин:

  1. в языке появились генераторы (легкие потоки)
  2. я нашел способ создания “псевдо бесконечного” цикла
  3. есть все, что нужно: дебаггер, сборщик мусора, профайлер,…
  4. в JS на много проще работать с AST (здесь это просто текст)
  5. он медленнее, но менее, чем на порядок
  6. я его хорошо знаю 🙂

Исходный код в процессе переноса и лежит здесь.

Рождение условного поведения 2

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

code-escape

модификация условного поведения

В строке 2, организм проверяет кто находится над ним. Функция Creature.idUp() возвращает идентификатор организма, находящегося над текущим. Если над нами ничего нет, то возвращается 0. Окей, переменная var_33 теперь равно нулю или идентификатору недруга. Далее, в строке 9 мы проверяем, что в переменной var_33. Если там 0, то и var_2 будет 0. Но если там идентификатор организма, то var_2 будет равна 127. И от этого значения зависит то, зайдем ли мы в цикл в строке 14 и будем ли мы “убегать” в противоположную сторону или нет 🙂 Если описать это простыми словами то получается вот что: “если над тобой кто-то есть – убегай вниз”. Не знаю как Вы, но я в восторге от этого 😀

P.S. список всех 80 лучших организмов вы можете найти здесь.

И еще раз, с новым годом!

Рождение условного поведения

Сегодня отличный день знаете ли 🙂 Отличный он, потому что в одной из популяций (6 дней работы алгоритма) родился организм с экстраординарными способностями. Такой себе мальчик-индиго 🙂 Анализируя код двадцатки лучших, я заметил, что у одного из них аномально много вызовов редких функций energyLeft(), energyDown() и idLeft().

Это странно, так как такие штуки редко поддерживаются отбором. Когда я начал разбираться, то наткнулся на интересную конструкцию:

code-2

Обратите внимание на строки от 70 до 84. Что Вы там видите? Это то самое условное поведение, которого я так долго ждал! Итак, в двух словах, о том, что здесь происходит. Сначала наш организм проверяет есть ли что-то под ним с помощью функции Creature.energyDown() (строка 63). Она возвращает количество энергии (это может быть как обычная энергия, так и другой организм). И если это число не ноль (ноль – означает пусто), то организм входит в цикл, где он 7 раз откусывает от жертвы 127 энергетических единиц. Если же под ним ничего нет, то в цикл мы не заходим и выполнение кода продолжается. Эта хитрость дает ему возможность нападать на своих жертв предварительно поняв, что они рядом. Если быть совсем точным, то нужно отметить, что количество энергии под ним должно быть больше 127. Но это не играет большой роли, так как в строке 84 все равно происходит откусывание снизу…

Стоит так же отметить, что появлению такого условного поведения предшествовал ряд событий. А именно:

  • Приоритет на добавление мутаций. В строке 90, Вы можете заметить массив чисел: 98, 38, 30,... – это коэффициенты которые влияют на частоту появления определенных мутаций. Первое число (98) определяет, как часто новый код будет добавляться в код нашего организма. Само число больше, чем все остальные. А это значит, что добавления будут более часты, нежели, например модификация (38) или удаление (30) кода.
  • Высокий процент мутаций при делении. В той же 90-й строке Вы можете заметить число 47.4821. Это процент мутаций при делении организма (при получении потомства). По сути – это означает, что при делении будет внесено столько мутаций сколько строк кода содержит организм поделенное на 2. То есть, если организм состоит из 88 строк, то будет внесено 44 мутации. И большинство из них будут вставками нового кода (мы это выяснили из предыдущего пункта).
  • Высокий коэффициент мусора. В данной популяции коэффициент мусора составляет 0.2. Это означает, что организм может хранить 80% мусорного кода без потери энергии. Это одно из новшеств, которое было добавлено в версии 1.1-rc1. Что дает мусор? Как ни странно, мы не до конца понимаем зачем в наших ДНК хранится столько мусора (по разным оценкам от 80% до 40%). Некоторые эксперименты на мышах, показывают, что он используется ими для реакции на экстремальное изменение окружающей среды. В нем, могут хранится нужные случайные мутации… По всей видимости в нашем (в цифровом организме) случае все произошло именно так.

Именно по этим важным причинам, данный организм случайно получил в подарок эту последовательность операций 🙂 Для желающих изучить все детали, привожу полный листинг нашего альфа-самца:

code

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

Всех с Новым Годом! 🙂

Пост 6. Видео материалы.

Добрый вечер друзья. Давненько я не находил времени для очередного поста. Был занят: программировал и играл в хоккей 🙂 Сегодня я хочу поделиться с Вами видео материалами, которых у меня накопилось, за последний год с лишним, некоторое множество. Они полезны тем, кто хочет изучить тему эволюционного программирования и генетического алгоритма немного глубже. Ссылки расставлены сверху-вниз по тому, как по моему мнению нужно знакомиться с материалом. Единственная разница между этим постом и постом 1 – этот более полный. Итак:

Bio evolution – сборник ссылок на лекции Александра Маркова по эволюционной биологии. Они важны, так как эволюционная биология и генетика лягли в основу при разработке принципов эволюционного программирования.
http://macroevolution.livejournal.com/206803.html
GA – видео, объясняющие суть генетического алгоритма.

AI – видео по искусственному интеллекту связанному с ГА и ЭП от Криса Адами.

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

Polyworld – интерактивная OpenGL программа (несколько устаревшая) по разведению цифровых организмов. Похожая на Avida, но имеет 2D виртуальный мир, используя который можно вживую посмотреть, чем именно занимаются организмы, как они охотятся, развиваются, едят и т.д. Использует нейронные сети вместе с генетическим алгоритмом.

Всем хорошего вечера 🙂

Пост 5. О чем говорят цифры…

Всем привет!

Окей, этот выпуск будет немного неформатный, по той причине что у меня появились первые данные 🙂 В прошлый раз, мы говорили о языке julia и о том, как писать простые программы с его использованием. Сегодня – поговорим о реальных результатах и уже в следующий раз, продолжим с julia. Что я имею ввиду, когда говорю о данных? “Данные” – это различные характеристики (возраст популяции, размер кода организмов, количество мутаций, количество циклов в коде и т.д.) тестируемой популяции, которые изменяются со временем. Таким образом, их можно визуализировать в виде графиков.

Если в двух словах говорить о том, как были получены эти данные и связанные с ними графики, то дело происходило так: сначала создавалась “пустая” (без кода) популяция из 250 особей. У каждого организма такой популяции было 7000 юнитов энергии. Далее они размножались и мутировали, а отбор делал свое грязное дело (убивал организмы (10 штук), количество энергии которых было минимальным). Каждые 5 секунд система делала срез данных куда входили следующие поля:

fields

Давайте, я поясню детальней что означают эти поля. Сверху-вниз:

  • Вероятностные коэффициенты. Определяют, как часто в коде появятся мутации добавления, изменения и удаления кода (первые 3 числа). Последние 3 числа определяют: количество мутаций при клонировании, период дополнительных мутаций и количество доп. мутаций после этого периода. Все эти параметры так же могут мутировать у каждого организма по отдельности
  • Количество функций в коде организма
  • Количество вызовов этих функций
  • Фактическое количество мутаций применяемое после клонирования
  • Период, после которого применяются дополнительные мутации
  • Количество дополнительных мутаций применяющихся после периода доп. мутаций
  • Количество энергии организма
  • Количество операторов for в коде организма
  • Количество операторов if в коде организма
  • Количество вызовов функции getEnergy() (аналог примитивного зрения)
  • Количество обращений к внутренней памяти организма
  • Количество вызовов функции eatXXX() (еда)
  • Количество вызовов функции stepXXX() (движение)
  • Количество строк кода организма
  • Количество организмов в текущей популяции
  • Текущий IPS (Iterations Per Second)
  • Количество энергии в “мире” доступной для поедания
  • Возраст популяции

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

2016-08-16 (500000) code-lines-charts
увеличить

Начнем с того, что по горизонтали у нас “возраст популяции”. Что это значит? Это значит, что в самом левом углу (где ноль) популяция начала существование, а в самом правом (где значение 500000) – она находится сейчас. Сами числа определяют количество умерших организмов с момента рождения популяции и до выбранного момента. В некотором смысле – этот параметр означает “текущее поколение” и он напрямую связан со временем. Чем больше число, тем дольше существует популяция…

Видите этот синий график сверху? Это количество строк кода у самых лучших организмов популяции. Вообще, все эти графики строятся на основе “лучших из лучших” организмов. Такой себе показ “альфа самцов” 🙂 (в этом месте должны проснуться феминистки). Для нас важно то, что всреднем, синий график растет. Это означает, что организмы увеличивают размер своего кода, при этом затраты энергии тоже увеличиваются. Важно помнить, что увеличение количества строк кода – задача вполне тривиальная. А вот увеличение кол-ва строк одновременно с увеличивающейся потерей энергии – нет. Все это означает, что удлинение кода происходит с одновременным увеличением его эффективности. В нашем случае – это способность “находить” больше энергии для пропитания, чем твои предки. Таким образом отбор работает в сторону тех организмов, которые мутируют в направлении более эффективного кода. Затраты увеличиваются, потому что каждая дополнительная строка кода приравнивается к одному юниту энергии. То есть, чем больше код организма, тем больше энергии он тратит с течением времени. Даже в том случае, если он ничего не делеат (просто итост на месте) – энергия все равно тратится. Это обстоятельство – один из факторов, который заставляет систему стремиться к увеличению потребления энергии. Давайте взглянем на код одного из лучших организмов (приблизительное поколение: 500000):

final-cut

Что мы здесь видим? Во-первых, сверху (строки 2-66) распологаются объявления функций и переменных. Далее, можно заметить вызов функции func_232() целых 5 раз. Видимо для жизни организма она играет центральную роль (у всех его “родственников” она тоже присутсвует). Заглянув внутрь нее, мы видим, что это по-сути микс движения и пожирания всего, что вокруг. Менее важной является функция func_296(). Она вызывается только раз (строка 130) и служит для дополнительного передвижения организма. Далее – интересней. Обратите внимание на строку 166. Там происходит вызов функции func_254(), но сама функция не определена в коде. Что это означает? Это означает, что текущий лучший организм содержит логическую ошибку (одна из предыдущих мутаций удалила эту функцию), которая ведет к исключению в строке 166. То есть, далее, код не выполнится. Строки 167-174, никогда не будут выполнены. По сути – это баласт, за который забирается дополнительная энергия. Разумеется, со временем отбор конечно же вычистит его, но на момент сбора данных это не мешало нашему подопытному кролику быть лучшим в популяции себеподобных. В остальном, там нет ничего интересного. Весть код – это смесь отностельно оптимального движения и поедания всего, что находится вокруг организма.

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

Окей, что еще? Чуть ниже, можно увидеть зеленый график – это количество функций. О них мы уже говорили выше. Это обычные функции (оператор function), которые программисты используют для абстрагирования. Я не учил организмы, как их использовать. Они сами “поняли”, что функции – это более оптимальный выбор нежели просто линейный код. Давайте я объясню. Обратите внимание на фиолетовый график – он тоже растет. Хоть и не так быстро, но все же растет. Оба, они показывают, как часто организм использует функции для изменения своего поведения. Количество вызовов функции всегда больше количества самих функций. Это логично. Ведь, если Вам нужно сделать 50 шагов. Вы можете вызвать 50 раз функцию stepXXX() или написать функцию с 10 вызовами stepXXX() внутри и вызвать её 5 раз. Такой код будет занимать 15 строк. Видите разницу? 50 против 15. Второй вариант короче, а значит, тратит меньше энергии. А, значит, более экономный и выживет с большей вероятностью. Именно так и просходит – оптимальные программы имеют больший шанс на выживание, а значит и на то, что именно их потомство “продолжит их дело”.

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

2016-08-16 (500000) energy-charts

увеличить

Обратите внимание – первые 50000 особей активно увеличивали потребление энергии. После наступил медленный рост с перепадами, вплоть до самого конца (до 500000 поколения). Среднее увеличение показывает отдельная линия в центре графика (полином, построенный по данным энергии). Она передает сглаженное совокупное трендовое значение всего графика. Именно на её основе, мы делаем вывод о росте этого параметра.

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

Давайте подведем итог:

  • рассматриваемое поколение (приблизительно 500000) “научилось” писать относительно оптимальный код используя функции
  • общий график потребления энергии растет
  • общий график размера кода тоже растет
  • количество таких операторов как: for, if, getEnergy,… растет медленно
  • основная логика организмов (как минимум на текущий момент) – это “есть” и “двигаться”. Именно на эти параметры направлен отбор
  • эволюция сложного поведения процесс очень медленный и неверояно затратный (относительно CPU time). Результаты полученные в этой статье собирались 6 дней постоянной работы при 12% загрузки CPU

Всем спасибо, я спать 🙂