Комментарии 49
Очень интересно. Спасибо за статью.
О! Отличная статья. А не подскажите, реально ли на сегодня создать подобие модели простейшего живого существа? В принципе если представить память(компьютера) как жизненное пространство, а процессорное время как питательная среда, должно что-то само развивающееся получиться.
Когда включаешь-выключаешь гены, тултипы остаются и мешают.
Так… «Волостая окружность», «пальцастая гантелька», записал :)
Да, по-моему, названия шедевральны.
А вообще алгоритм очень интересен и наглядность программы радует. Сам занимаюсь КА.
Спасибо автору за утренний позитив!
А вообще алгоритм очень интересен и наглядность программы радует. Сам занимаюсь КА.
Спасибо автору за утренний позитив!
Это не я :-) Большую часть названий придумала моя пятилетняя дочка, которая была использована «в тёмную» в качестве альфа тестера. Она ведь думала, что играет. Кроме «странной фигуры 1 и 2», т.к. ничего странного она в этих «кустах» не нашла :-)
А не поделитесь программкой? Уж очень хочется самому потыкать :)
НЛО прилетело и опубликовало эту надпись здесь
Это самое интересное! Мозг частенько выламывает. Ну и, возможно, кто-нибудь найдёт ошибки в реализации.
Пока могу предложить следующее: сегодня-завтра добавлю кнопку загрузки хромосомы из xml (xaml) файла и выложу вместе с примером такого файла. На «настольной» версии я так и делаю, так как удобного интерфейса по редактированию генов не придумал.
Единственное, в сильверлайт версии не отображается в виде текста текущее и предыдущее состояние узла — не совсем удобно «отлаживать» код (генетический).
Пока могу предложить следующее: сегодня-завтра добавлю кнопку загрузки хромосомы из xml (xaml) файла и выложу вместе с примером такого файла. На «настольной» версии я так и делаю, так как удобного интерфейса по редактированию генов не придумал.
Единственное, в сильверлайт версии не отображается в виде текста текущее и предыдущее состояние узла — не совсем удобно «отлаживать» код (генетический).
а как самому писать гены?
Захватывающе, как в шахматы! :-) Ответил тут: habrahabr.ru/blogs/algorithm/107387/#comment_3386428
Возиться с программой очень занимательно, особенно отрезать куски от графов и смотреть как они вырастают заново
Автор молодец, что тут скажешь.
Желаю успехов в дальнейших планах!
Желаю успехов в дальнейших планах!
Криминально интересно, спасибо!
Люди, сильверлайт не нужен, остановитесь пока не поздно!
Люди, сильверлайт не нужен, остановитесь пока не поздно!
По поводу сильверлайта: так было легче всего, практически без переделок, «опубликовать» готовое десктопное C#|WPF приложение. Понятно, что у половины народу пока не получиться «пощупать», но тратить время на другую технологию не хотелось. Совсем не против, если кто-нибудь сделает на SVG или Flash — уверен, можно сделать не хуже.
крутяк
Отличная работа! Спасибо!
Браво! Весьма занимательно.
Усложнять правила для атвоматов не стоит, как показал дяденька Вольфрам, поведения произвольной сложности (универсальности в вычислительном смысле) можно достичь с минимальным набором и сложностью правил, лишь бы автомат с таким набором был способен показывать поведения класса 4. А дальше уже GA создадут нужный генотип.
Да, как раз и есть желание нащупать необходимый минимум операций.
Правда, от идеалов может быть придётся и отступить: в конце концов, и в современные процессоры регулярно добавляют всё новые и новые расширения (SSE, раньше FPU и прочие) для удобства «программирования» и/или из-за архитектурных соображений, а не сводят всё к машине Тьюринга.
В GUCA, например, условие по предыдущему состоянию добавил лишь для удобства «программирования» графов (сокращает количество кода и время на отладку), но отключив это условие при поиске решений генетическим алгоритмом, заметил что GA находит решение примерно за тоже самое время, что и с дополнительным правилом.
Правда, от идеалов может быть придётся и отступить: в конце концов, и в современные процессоры регулярно добавляют всё новые и новые расширения (SSE, раньше FPU и прочие) для удобства «программирования» и/или из-за архитектурных соображений, а не сводят всё к машине Тьюринга.
В GUCA, например, условие по предыдущему состоянию добавил лишь для удобства «программирования» графов (сокращает количество кода и время на отладку), но отключив это условие при поиске решений генетическим алгоритмом, заметил что GA находит решение примерно за тоже самое время, что и с дополнительным правилом.
Я считаю, что это направление очень перспективное. Поздравляю!
эх под бубунтой 64 в хроме — пустой экран(
Интересно!
> Соединение узла с ближайшим не соединённым узлом, находящимся в состоянии X
А ближайший узел определяется по топологии графа или геометрически?
> Соединение узла с ближайшим не соединённым узлом, находящимся в состоянии X
А ближайший узел определяется по топологии графа или геометрически?
Ближайший узел определяется по топологии, причём узел не должен находится на расстоянии более чем 2-3 ребра (задаётся глобальным параметром) — это чтобы обеспечить условие локальности… и производительности тоже. Если узла «поблизости» нет, то соединение не происходит.
Просто иначе топология графа будет зависеть от конкретных параметров геометрической или физической модели, управляющей разворачиванием графа на плоскости (или в пространстве).
Например, если замедлить «внутриклеточные» процессы в «странной фигуре 1», то она вытянется вдоль и концевые узлы будут далеко друг от друга, а если ускорить «метаболизм» (или замедлить среду обитания сделав её вязкой) — то новорождённые узлы не будут успевать отойти друг от друга на большое расстояние.
То, что граф в демонстрационном приложении отображается на плоскости, не должно вводить в заблуждение о механизме его происхождения — можно запросто изменить «отображалку» на 3D-версию и выглядеть тот же самый граф в пространстве будет заметно по другому. А такие приложения графов, как нейронная сеть, вряд ли должны зависеть от параметров отображения графов для зрителей.
Конечно, можно и даже любопытно «наворачивать» и/или параметризовать правила используя и другие меры (геометрические), и на самом деле, в известной нам жизни так и происходит (грубо говоря, выделяются гормоны — сиськи растут). Да и при росте организмов в известной нам жизни, геометрия именно трёхмерного мира, без условно, определяет «упаковку» и взаимное расположение делящихся клеток относительно друг друга.
Но это задача уже следующего уровня, мне кажется. Для небольших многоклеточных организмов «близкодействие» весомее «дальнодействия».
Просто иначе топология графа будет зависеть от конкретных параметров геометрической или физической модели, управляющей разворачиванием графа на плоскости (или в пространстве).
Например, если замедлить «внутриклеточные» процессы в «странной фигуре 1», то она вытянется вдоль и концевые узлы будут далеко друг от друга, а если ускорить «метаболизм» (или замедлить среду обитания сделав её вязкой) — то новорождённые узлы не будут успевать отойти друг от друга на большое расстояние.
То, что граф в демонстрационном приложении отображается на плоскости, не должно вводить в заблуждение о механизме его происхождения — можно запросто изменить «отображалку» на 3D-версию и выглядеть тот же самый граф в пространстве будет заметно по другому. А такие приложения графов, как нейронная сеть, вряд ли должны зависеть от параметров отображения графов для зрителей.
Конечно, можно и даже любопытно «наворачивать» и/или параметризовать правила используя и другие меры (геометрические), и на самом деле, в известной нам жизни так и происходит (грубо говоря, выделяются гормоны — сиськи растут). Да и при росте организмов в известной нам жизни, геометрия именно трёхмерного мира, без условно, определяет «упаковку» и взаимное расположение делящихся клеток относительно друг друга.
Но это задача уже следующего уровня, мне кажется. Для небольших многоклеточных организмов «близкодействие» весомее «дальнодействия».
Очень интересная статья и, вообще, тема. Сразу же закралась мысль, нельзя ли сделать самовоспроизводящийся «организм». Возможно, все решилось бы добвалением нового действия «разорвать связь» в конечный автомат. Потом решил почитать, как именно это реализовано у природы. Пошел смотреть в гугл как воспроизводится ДНК. Оказалось совсем не похоже на то, что у Вас. Там напрочь отсутствует конечный автомат. Вся репликация проходит за счет связей между элементами.
Идея хорошая… Рад, что подобные идеи приходят не только в мою голову — есть с кем обсудить :-).
Как раз такая операция введена («отсоединения от узла X обозначим –X»). И, если у Вас в браузере отображается демонстрационное приложение, Вы и сами можете понаблюдать как она работает — в «волосатой окружности» и её гибриде, а также в шестиугольнике. Чтобы рассмотреть подробности — лучше замедлить процесс, установив флажок «Slow down...»
Более того, если бы в демонстрационном приложении, отрезанные «осколки» графа не удалялись бы автоматически, то можно было бы увидеть, что «осколки» иногда тоже начинают расти и жить.
Ничто не мешает «запрограммировать» граф таким образом чтобы после его «разворачивания» из начального зародыша (узла в состоянии А), он на определённой стадии отстреливал от себя один или несколько таких же зародышей. Тогда будет цепная реакция.
Что касается ДНК — я как раз стремился абстрагироваться от подробностей конкретной реализации жизни на нашей планете, сконцентрировавшись именно на принципах образования формы (морфогенеза). Единственное что роднит GUCA с ДНК, так это буквы сокращений нуклеиновых оснований её РНК-отпечатка (G, U, С, A -гуанин, урацил, цитозин, аденин).
Насколько я понял, клетка устроена не проще аэробуса и ДНК/РНК могут кодировать уйму туч самых разных белков и прочих деталек, участвующих в сложных многоходовках химических/механических процессов. Если уж проводить аналогию, то состояние в клеточном автомате — это макросостояние клетки — определённый её химический/электростатический состав с определённым набором уже извлечённых из генома белков/ферментов. Клетки взаимодействуют с соседними и в зависимости от этого взаимодействия, а также от текущего состояния извлекают из генома другие вещества (белки/гены), которые меняют её исходное состояние на другое или запускают операцию деления… или смерти. И так далее… Пока не съедят :-)
Как раз такая операция введена («отсоединения от узла X обозначим –X»). И, если у Вас в браузере отображается демонстрационное приложение, Вы и сами можете понаблюдать как она работает — в «волосатой окружности» и её гибриде, а также в шестиугольнике. Чтобы рассмотреть подробности — лучше замедлить процесс, установив флажок «Slow down...»
Более того, если бы в демонстрационном приложении, отрезанные «осколки» графа не удалялись бы автоматически, то можно было бы увидеть, что «осколки» иногда тоже начинают расти и жить.
Ничто не мешает «запрограммировать» граф таким образом чтобы после его «разворачивания» из начального зародыша (узла в состоянии А), он на определённой стадии отстреливал от себя один или несколько таких же зародышей. Тогда будет цепная реакция.
Что касается ДНК — я как раз стремился абстрагироваться от подробностей конкретной реализации жизни на нашей планете, сконцентрировавшись именно на принципах образования формы (морфогенеза). Единственное что роднит GUCA с ДНК, так это буквы сокращений нуклеиновых оснований её РНК-отпечатка (G, U, С, A -гуанин, урацил, цитозин, аденин).
Насколько я понял, клетка устроена не проще аэробуса и ДНК/РНК могут кодировать уйму туч самых разных белков и прочих деталек, участвующих в сложных многоходовках химических/механических процессов. Если уж проводить аналогию, то состояние в клеточном автомате — это макросостояние клетки — определённый её химический/электростатический состав с определённым набором уже извлечённых из генома белков/ферментов. Клетки взаимодействуют с соседними и в зависимости от этого взаимодействия, а также от текущего состояния извлекают из генома другие вещества (белки/гены), которые меняют её исходное состояние на другое или запускают операцию деления… или смерти. И так далее… Пока не съедят :-)
а исходников поиграться не дадут?
НЛО прилетело и опубликовало эту надпись здесь
Огромное спасибо за статью. Я и сам давно интересуюсь генетическими алгоритмами и вообще эволюцией. Мне очень понравилась идея о размножении графов. Здесь уже пахнет Искусственной Жизнью. Остается только добавить движение и взаимодействие между особями. Я бы с большим удовольствием сам поэкспериментировал с живыми графами. Очень хочется увидеть ваш код, чтобы не писать это все с нуля. Буду рад, если вы поделитесь ссылкой на исходники.
Подход и сами «живые» графы похожи на графы вычислительной Вселенной: habr.com/ru/post/518206. Скорее всего, они ими и являются, просто правила в другом формате записи.
«Странная фигура 1» демонстрирует распад физического пространства на несвязанные области, ака чёрные дыры или разбег галактик. А «Кокошник» в своей внутренней структуре действительно должен быть искривлён гравитацией из-за энергии, поддерживающей структуру этого 2D пространства.
«Странная фигура 1» демонстрирует распад физического пространства на несвязанные области, ака чёрные дыры или разбег галактик. А «Кокошник» в своей внутренней структуре действительно должен быть искривлён гравитацией из-за энергии, поддерживающей структуру этого 2D пространства.
Да видел, спасибо. Возможно, как не раз бывало в истории науки, междисциплинарный подход поможет выработать более компактную модель мира и эволюционные биологи, программисты помогут физикам найти нужное правило на графах, а математики с физиками подскажут биологам как работает эволюция сложных систем.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
«Живые графы» — выращивание графов на клеточных автоматах с примерами на Silverlight