Небольшой видео ролик о новой версии construct 0.2.1 с распределенными вычислениями «под капотом».
Uncategorized
Новое поведение в не цикличном мире
Совсем небольшая новость о том, что может появиться за одну ночь работы алгоритма. Небольшое пояснение: обратите внимание, как ловко организмы обошли ограничения мира. Под ограничениями я подразумеваю невозможность двигаться за пределы мира и возвращаться в него с другой стороны. Каждый раз, когда организм доходит до границы, он делает разворот и бежит в противоположном направлении с небольшой корректировкой траектории (добавляется диагональное движение). Код здесь.
Всем спасибо 🙂
Ошибка!
В предыдущих постах, я упоминал о том, что искомая программа сгенерированна и задача поиска 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)
}
}
Новые записки о jevo.js
Переход на JavaScript
Как бы необычно это не звучало, но я решил портировать на JS весь код проекта jevo. JavaScript уже достаточно созрел для такого рода проектов. И тому есть несколько причин:
- в языке появились генераторы (легкие потоки)
- я нашел способ создания «псевдо бесконечного» цикла
- есть все, что нужно: дебаггер, сборщик мусора, профайлер,…
- в JS на много проще работать с AST (здесь это просто текст)
- он медленнее, но менее, чем на порядок
- я его хорошо знаю 🙂
Исходный код в процессе переноса и лежит здесь.
Рождение условного поведения 2
В предыдущей статье, я познакомил вас с первым организмом получившим так называемое «условное поведение» в результате нескольких случайных мутаций. Как оказалось, этим дело не закончилось 🙂 Данный поведенческий шаблон оказался очень удобен для последующих изменений. Что это значит? Это значит, что на его основе можно делать новые виды условного поведения. Немного позже, я нашел другой организм, который содержал тот же код (смотри предыдущую статью), но с некоторыми модификациями. Смотрите:
модификация условного поведения
В строке 2, организм проверяет кто находится над ним. Функция Creature.idUp() возвращает идентификатор организма, находящегося над текущим. Если над нами ничего нет, то возвращается 0. Окей, переменная var_33 теперь равно нулю или идентификатору недруга. Далее, в строке 9 мы проверяем, что в переменной var_33. Если там 0, то и var_2 будет 0. Но если там идентификатор организма, то var_2 будет равна 127. И от этого значения зависит то, зайдем ли мы в цикл в строке 14 и будем ли мы «убегать» в противоположную сторону или нет 🙂 Если описать это простыми словами то получается вот что: «если над тобой кто-то есть — убегай вниз». Не знаю как Вы, но я в восторге от этого 😀
P.S. список всех 80 лучших организмов вы можете найти здесь.
И еще раз, с новым годом!
Рождение условного поведения
Сегодня отличный день знаете ли 🙂 Отличный он, потому что в одной из популяций (6 дней работы алгоритма) родился организм с экстраординарными способностями. Такой себе мальчик-индиго 🙂 Анализируя код двадцатки лучших, я заметил, что у одного из них аномально много вызовов редких функций energyLeft(), energyDown() и idLeft().
Это странно, так как такие штуки редко поддерживаются отбором. Когда я начал разбираться, то наткнулся на интересную конструкцию:
Обратите внимание на строки от 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%). Некоторые эксперименты на мышах, показывают, что он используется ими для реакции на экстремальное изменение окружающей среды. В нем, могут хранится нужные случайные мутации… По всей видимости в нашем (в цифровом организме) случае все произошло именно так.
Именно по этим важным причинам, данный организм случайно получил в подарок эту последовательность операций 🙂 Для желающих изучить все детали, привожу полный листинг нашего альфа-самца:
Еще один примечательный факт, касающийся этих важных мутаций — они были поддержаны отбором. Просмотрев список из 80 лучших организмов, я нашел их в коде у многих из них. В общем, буду держать вас в курсе 😉
Всех с Новым Годом! 🙂
Небольшой комикс :)
Хочу поблагодарить Oksana Broshnivska за создание небольшой статьи и комикса со мной.
Пост 6. Видео материалы.
Добрый вечер друзья. Давненько я не находил времени для очередного поста. Был занят: программировал и играл в хоккей 🙂 Сегодня я хочу поделиться с Вами видео материалами, которых у меня накопилось, за последний год с лишним, некоторое множество. Они полезны тем, кто хочет изучить тему эволюционного программирования и генетического алгоритма немного глубже. Ссылки расставлены сверху-вниз по тому, как по моему мнению нужно знакомиться с материалом. Единственная разница между этим постом и постом 1 — этот более полный. Итак:
Bio evolution — сборник ссылок на лекции Александра Маркова по эволюционной биологии. Они важны, так как эволюционная биология и генетика лягли в основу при разработке принципов эволюционного программирования.
http://macroevolution.livejournal.com/206803.html
GA — видео, объясняющие суть генетического алгоритма.
AI — видео по искусственному интеллекту связанному с ГА и ЭП от Криса Адами.
Avida — от части, конкурирующая программа, которая разрабатывается Чарлзом Офрия из Мичиганского университета. Так же, эмулирует виртуальный мир цифровых организмов (программ), которые используют ассемблеро-подобный язык для жизни и функционирования в памяти. Помимо видео материалов, советую послушать интервью, где Чарлз объясняет многие детали своего проекта.
Polyworld — интерактивная OpenGL программа (несколько устаревшая) по разведению цифровых организмов. Похожая на Avida, но имеет 2D виртуальный мир, используя который можно вживую посмотреть, чем именно занимаются организмы, как они охотятся, развиваются, едят и т.д. Использует нейронные сети вместе с генетическим алгоритмом.
Всем хорошего вечера 🙂
construct 