#Введение

Случайно встретил на просторах интернета этот занимательный видос, и мне он настолько понравился, что я решил поделиться им с русским зрителем: перевести и озвучить. Результат опубликовал на ютуб:

Далее я приведу ссылки и немного подробнее расскажу о том, как это работает, расскажу какие идеи у меня возникли после его просмотра.

#Ссылки

• Оригинал видео на сайте archive.org.
• Страница на сайте Карла Симса об этом проекте.
• Научная статья об этой работе, её можно найти на странице выше.
• Немного дополненная статья для конференции SIGGRAPH. Крайне рекомендую прочитать, в ней нет никаких сложных формул, только идеи и результаты. Плюс в ней больше информации, чем в статье выше. Всё, кроме моих идей, далее основывается на этой статье.
• Видео, где тоже самое, что и в оригинальном видео рассказывает сам Карл. Никакой особо новой информации там нет, но на всякий случай пусть будет.
• Патент #5511158, где подробно рассказывается о том, как создавать и мутировать направленные графы, на основе которых строится тело и мозг существ.

#Эволюция

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

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

#1994 год, серьёзно?

Я тоже был невероятно удивлен! Получены отличные результаты, и удивительно, что в то время вообще могли помыслить об симуляции 3D существ. Я бы предпочел симулировать 2D ввиду ограниченной вычислительной мощности тех времён.

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

Согласно научной статье, программа вычислялась на суперкомпьютере CM-5, который, на минуточку, в 1993 году был первым в списке TOP500.

Так же в статье приведён пример времени работы программы: при размере популяции в 300 особей, обработка 100 поколений на 32 ядрах этого компьютера занимала 3 часа. Мне кажется, в 2019 наши домашние ПК могут работать с такой же скоростью для подобной программы.

К сожалению, далее Карл Симс, если изучить его сайт, не занимался этой темой.

Зато занимался чем-то подобным ранее:

#Устройство существа

У данных существ мозг и тело идейно связаны, поэтому нельзя объяснить принцип устройства одного без объяснения принципа устройства другого.

Существо состоит из жёстких кубоидов (параллелепипедов), соединенных шарнирами.

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

Ниже изображён пример генов и результирующих существ. Обратите внимание на то, что некоторые части могут строиться рекурсивно.

На данной картинке разные части подписаны для удобства, это лишь рукотворный пример.

Каждая вершина графа генетического материала содержит иформацию:

• Относительный размер параллелепипеда.
• Ограничения на рекурсивность данной части тела (если она ссылается сама на себя).
• Локальная нейронная сеть (в статье это называется вложенный граф).

Каждое ребро графа содержит информацию:

• Тип шарнира, связующего две части: закрепленный, свободный, вокруг определенной оси, и другие которые я не понял (revolute, twist, universal, bend-twist, twist-bend).
• Ограничения на вращение.
• В каком месте кубоида и под каким углом расположено соединение.

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

Итоговая нейросеть, которая получается объединением и копированием локальных нейросетей в одну конфигурацию вида я называю глобальной нейронной сетью.

#²Устройство мозга

Современные нейросети представляют собой жёсткую линейную архитектуру (в виде ацикличного ориентированного графа), и иногда рекуррентную архитектуру. В данной же работе никаких таких ограничений нет, и любой нейрон может связываться с любым другим нейроном, единственное условие - чтобы граф был связным. Части, не принадлежащие основному графу, удаляются сборщиком мусора.

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

В данной работе на каждую итерацию симуляции приходится две итерации движения сигнала в нейронной сети.

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

• +, *, /
• sum-threshold
• sign-of, abs
• min, max
• greater-than, if
• interpolate
• sin, cos, atan
• log, exp
• sigmoid
• integrate, differentiate
• smooth
• memory
• oscillate-wave, oscillate-saw

К сожалению я знаю о том, что делают эти функции не больше вашего, и нам остается только догадываться.

Некоторые функции не просто вычисляют ответ на основе своих входных данных, но ещё и хранят некоторое внутреннее состояние.

Аналогично обычным НС, здесь каждый вход умножается на какое-то число. На вход даже может подаваться константа.

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

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

#³Моя идея насчёт конечных автоматов

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

Таким образом можно эволюционировать не только нейросети, но и конечные автоматы, мне этот подход даже видется более перпективным.

Вдохновлялся этой статьёй про создание NPC на основе конечного автомата. Картинка оттуда для привлечения внимания:

#²Входные параметры

Не забываем что у каждой части тела есть своя локальная нейронная сеть.

У каждой локальной нейронной сети есть следующие входы для своей физической части:

• Угол наклона соединения - передается отдельным нейроном для каждого соединения.
• Сенсор касания - аналогично для каждой грани создаётся отдельный нейрон. Передаёт 1, если контакт есть, и -1, если нет.
• "Фотосенсор", для каждой части имеется своя копия. Передает нормализованный относительный вектор направления на источник света или зелёный куб. Название взято в кавычки, потому что настоящее явление света не симулируется, и существо видит свет, даже если по факту оно загорожено другими объектами.

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

Одним словом это называется сенсоры.

#²Выходные параметры

Далее каждая локальная нейронная сеть имеет выходы, чтобы управлять телом.

На выход каждому шарниру подается пара чисел, задающих силу вращения по разным осям. Для некоторых типов шарниров может подаваться и одно число (но это я уже сам додумал, на самом деле там это не уточняется).

Как я понял каждая часть направляет сигналы на те шарниры, которые соединяют эту часть с родительской.

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

Одним словом это называется эффекторы.

#³Моя идея о новых эффекторах

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

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

#²Взаимодействие локальный нейронных сетей

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

В итоге каждая часть будет двигаться единообразно, и такое существо можно легко расширить или уменьшить, или добавить ему пару хвостов. Аналогично можно добавить ноги к существу с 2 и более ногами.

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

Ниже на картинке показан пример из первой статьи. Он довольно простой. Взаимодействие локальных нейросетей между собой представлено через сенсор P1, который отправляет информацию локальным нейронным сетям.

Следующий пример взят из дополненной статьи для siggraph.

Пунктирной линией показана центральная нейронная сеть, не связанная ни с какой частью.

Обратие внимание, что в ней сенсор J1 подает сигнал на вход itp, а в глобальной нейронной сети, с несколькими частями, только один сенсор J1 смог послать свой сигнал на itp. Очевидно, что это проблема того, что максимум входов может быть 3. И просто обрезать случайные - не очень красивое решение. Как решаются такие проблемы в статье не говорится.

#²Моя идея взаимодействия локальных нейронных сетей

У меня появилась собственная идея как организовывать взаимодействие локальных нейронных сетей так, чтобы это было красиво, и чтобы подобных проблем не возникало.

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

То есть к каждой нейросети помимо собственных входных параметров (сенсоров)/собственных выходных параметров (эффекторов) добавляются входные/выходные параметры от/для других нейросетей. Какие именно нейросети могут отправлять/получать информацию, определяется генетическим графом.

Например, возьмем уже известный нам генетический граф и сгенерированное на его основе существо:

Тогда, согласно моей идее, для него получатся следующие локальные нейронные сети:

Здесь надо много рассказать про обозначения:

• Желтые нейроны - входные нейроны, получающие информацию от других локальных нейронных сетей.
• Красные нейроны - выходные нейроны отправляющие информацию на другие локальные нейронные сети.
• Голубые нейроны с надписью S - нейроны сенсоров.
• Фиолетовые нейроны с надписью E - нейроны эффекторов.

Здесь я обозначаю одним кружком сразу много нейронов, вектор нейронов, очевидно, что сенсоров у части тела много, я просто не стал их все рисовать, так как это сложно и мусорно. Если количество эффекторов и сенсоров вполе понятно, то вот количество нейронов для обмена информацией с каждой другой локальной нейросетью может задаваться генетически. Это может быть 0, 1, 2 или даже 10 чисел.

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

Так же я сделал так, чтобы родительская часть тела могла не только отправлять дочерним информацию, но и получать её от них.

А у локальной нейросети A так много входов и выходов, потому что ей надо общаться не только с двумя B, но и ещё с дочерней A и потенциально с родительской A.

В итоге после объединения локальных нейросетей получается такая глобальная нейросеть:

Заметьте, что некоторые нейроны в итоге ни с кем не соединились. Это нормально.

Так же здесь важно то, что Da, Db просто копируются в нужном количестве.

Правда в этой идее не нашлось места для центральной нейронной сети, которая не зависит от частей тела, и по идее должна выполнять основную, центральную, мыслительную деятельность.

Наверное, можно добавить её в виде ещё одних входных и выходных нейронов для A, и подключить её только к одной копии A:

#²Моя идея об объединении мозгов от разных задач

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

В общем идея состоит в:

• Чтобы сначала обучить две разных нейросети одного существа:
  • Одно стремится плыть максимально прямолинейно и быстро
  • Второе стремится поворачиваться на месте максимально неподвижно и быстро, чтобы достичь нужного угла
• А затем заставить эволюцию как-то объединить эти две нейросети, не модифицируя их, чтобы получить существо, которое комбинирует поведение движения по прямой и разворота для выполнения изначального действия достижения красной точки.

Кажется, в результате должно возникнуть красивое поведение, и само тело существа будет оптимизироваться под эффективное движение вперёд и разворот, оно, возможно, станет симметричным.

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

Обозначим нейросеть плавающего по прямой существа как 🏊, а разворачивающегося как ⚙️, тогда задача эволюции состоит в том, чтобы обучить нейросети Din и Dout на следующей диаграмме:

Наверняка существо научиться делать что-то вроде:

• Разворачивайся, пока твоё тело не будет направлено на цель
• Двигайся прямо

Может быть там даже возникнет поведение, позволяющее делать эти действия более-менее одновременно без ущерба ко времени достижения цели и длине траектории.

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

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

Может быть и в нашей эволюции гены являются этими строительными блоками?

Кстати, я уже давно придумывал идею о генах внутри нейронных сетей, и нарисовал её как-то так:

#Размножение

Согласно научной статье, в 40% случаях осуществляется простое копирование существа с применение мутации, в 30% случаях скрещивание под названием crossovers, и в 30% оставшихся случаев скрещивание под названием grafting (прививание).

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

А насчет скрещивания - тоже обращайтесь к статье, если интересно. Первый метод похож на обычное скрещивание битов, а второй на прививание ветки груши к яблоне.

Хотя лично я очень скепически отношусь к скрещиванию. Даже как-то высказывался об этом в твитере. Если цель скрещивания в получении генов, которые могут потенциально использоваться другими существами, или в том, чтобы гены эволюционировали, борясь между собой, как это описано в "Эгоистичном гене" Ричарда Докинза, то у меня придумываются совсем другие алгоритмы, созданные специально с этой целью, но никак не скрещивание.

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

#"Успешное поведение сильно зависит от противника."

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

Просто обычно симуляция эволюции представляет собой подобный график:

×1
png

Фитнес-функция --- это функция, которая оценивает эффективность решения особью поставленной задачи. Как видим из графика, в процессе эволюции значение этой функции растет, а затем сходится к какому-то пределу и далее не изменяется.

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

По моим предположениям одним из таких двигателей постоянно возрастающей сложности может стать соревновательная система, представленная в видео. В ней успех существа не зависит от среды, и не является какой-то статичной функцией, которая может к чему-то сойтись, нет, она зависит от постоянно меняющегося противника, который меняется в зависимости от своего оппонента!

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

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

Кстати, в научной статье показываются и обсуждаются различные соревновательные системы, как между существами одной популяции, так и между двумя:

#Future work

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

К сожалению, учитывая ту информацию, что я нагуглил, ничего путного из этого не вышло. :(

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

#Маленькая размерность

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

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

#Заключение

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

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