Использование клеточных автоматов для моделирования онтогенеза

Игра в жизнь

«Жизнь» Конвея — самый популярный из двумерных (да и трехмерных) клеточных автоматов. Эта модель отдаленно напоминает копошение бактерий в чашке Петри, и обладая Тьюринг полнотой, может послужить основой для чего угодно: моделирования мышления, компьютеров (архитектуры тетриса) и самой себя.

играбельно

Множество энтузиастов находят все новые структуры: осцилляторы, глайдеры, корабли (на гусеничном ходу!) и фабрики. То есть, вся прелесть здесь заключается в том, что на основе простых правил можно создавать сложные структуры, откуда возникает соблазн попытаться распространить данную модель на фундаментальные законы Естества. В частности С. Вольфрам балует нас подобными высказываниями. Вопрос, на сколько это правдоподобно и, главное, полезно, всегда вызывает споры, так что, не будем на нем заостряться. Лучше реализуем «Жизнь» использующую преобразования Фурье.

Жизнь без Фурье и не жизнь вовсе

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

За основу использовался алгоритм из хабровской статьи

Приятные бонусы этого подхода — это сравнительно быстрая отработка БПФ в силу его отполированности, и закольцованность граничных условий (действо происходит как бы на поверхности тора). Собственно, теперь можно обобщить «жизнь» непрерывным случаем.

Гладкая жизнь

• Репозиторий проекта
• Доступное объяснение
• Дисер с доскональными исследованиями

Вот так в общем виде выглядит модель:

Состояние теперь описывается не 1 и 0, а сигмоидой, соседи учитываются в некотором радиусе, а еще понадобится решать дифуры.

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

Класс Rule

ДанныеФункции

• Конструктор. На вход поступает константное беззнаковое целое число типа size_t. Это число проверяется на принадлежность числовому отрезку . Если проверка пройдена успешно, то оно разбивается на двоичные разряды, сохраняемые во внутренний вектор типа bool. Иначе генерируется исключение out_of_range.
• Оператор взятия индекса. Он принимает целое беззнаковое число типа size_t. Если число входит в числовой отрезок , то возвращается элемент вектора типа bool находящийся по данному индексу. Иначе снова генерируем исключение out_of_range. Данное число есть окрестность клетки. Этой окрестности правило перехода сопоставляет состояние клетки посередине в будущем поколении.

Влияние на развитие наук

Хотя игра состоит всего из двух простых правил, тем не менее она более сорока лет привлекает пристальное внимание учёных. Игра «Жизнь» и ее модификации повлияла (в ряде случаев взаимно) на многие разделы таких точных наук как математика, информатика, физика

Это, в частности:

• Теория автоматов,

• Теория алгоритмов,

• Теория игр и математическое программирование,

• Алгебра и теория чисел,

• Теория вероятностей и математическая статистика,

• Комбинаторика и теория графов,

• Фрактальная геометрия,

• Вычислительная математика,

• Теория принятия решений,

• Математическое моделирование.

Кроме того, многие закономерности, обнаруженные в игре, имеют свои аналогии в других, подчас совершенно «нематематических» дисциплинах. Вот список наук, теории которых имеют интересные точки соприкосновения с феноменами «Жизни»:

• Кибернетика. Сама игра является удачной попыткой Конвея доказать существование простых самовоспроизводящихся систем.

• Биология. Внешнее сходство с развитием популяций примитивных организмов впечатляет.

  

  

  

  

  

  

  

  

  

  

• Физиология. Рождение и смерть клеток аналогичны процессу возникновения и исчезновения нейронных импульсов, которые и формируют процесс мышления. А также аналогичны созданию импульсов в нервной системе многоклеточных организмов.

• Астрономия. Эволюции некоторых сложных колоний удивительным образом схематично повторяют этапы развития спиралевидных галактик.

• Физика твёрдого тела. Теория автоматов вообще и игра «Жизнь» в частности используются для анализа «явлений переноса» — диффузии, вязкости и теплопроводности.

• Квантовая физика. Поведение «жизненных» ячеек (рождение новых и взаимное уничтожение) во многом напоминают процессы, происходящие при столкновении элементарных частиц.

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

• Электротехника. Правила игры используются для моделирования самовосстанавливающихся электрических цепей.

• Химия. Конфигурации, подобные строящимся в игре, возникают во время химических реакций на поверхности, в частности в опытах М. С. Шакаевой возникают движущиеся молекулярные конструкции аналогичные «жизненному» планеру. Также предпринимаются попытки объяснить периодические химические реакции с помощью многомерных клеточных автоматов. Самоорганизацией элементарных частиц также занимается супрамолекулярная химия.

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

• Философия. Приведённый список примеров снова наводит на мысль, что всё во Вселенной развивается по одним и тем же нескольким фундаментальным законам, пока ещё не познанным человеком.

Возможно, эта игра связана и с другими научными явлениями, в том числе и с теми, о которых современной науке пока неизвестно. Также возможно, что не открытые на сегодня законы Природы и Общества станут более понятными благодаря «Жизни» и ее модификациям.

Применение клеточных автоматов для математического моделирования динамических процессов

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

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

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

Разумеется, этот подход не является панацеей и имеет наряду с достоинствами ряд серьезных недостатков

Поэтому тем более важно выяснить, какова «экологическая ниша» таких моделей, в частности, в газовой динамике

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

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

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

Одной из первых удачных попыток такого рода был «НРР-газ» (названный по первым буквам фамилий своих создателей). Поле этого клеточного автомата представляет собой ортогональную решетку (2-х или 3-х мерную). Возможные состояния клетки соответствуют наличию в ней частиц, движущихся параллельно осям координат (не более одной частицы на каждое направление). На каждом временном шаге частица перемещается на одну клетку. Столкновения частиц считаются абсолютно упругими.

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

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

Этого недостатка лишен автомат «ТИР-газ», поле которого — гексагональная решетка, образованная равносторонними треугольниками. Более высокий порядок симметрии обеспечивает выполнение уравнения Навье-Стокса для этого клеточного автомата. С другой стороны, особая структура поля несколько усложняет его реализацию на компьютере и замедляют вычисления.

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

Одним из существенных недостатков всех этих моделей является их принципиальная изотермичность.

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

Подробнее в автореферате диссертации «Применение клеточных автоматов для математического моделирования динамических процессов» 

Суть работы

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

элементарному клеточному автомату

1. Это просто. Алгоритм работы элементарного клеточного автомата прост для понимания и реализации.
2. Это быстро. Даже моя (не самая удачная) реализация работает достаточно быстро (убедимся в этом, закончив работу).

1. Разбиваем входную строку на символы
2. Код каждого символа разбиваем на двоичные разряды
3. Записываем эту вереницу единиц и нулей в поле клеточного автомата
4. Просчитываем эволюцию клеточного автомата с помощью правила перехода состояний и в какой-то момент возвращаем вызывающей стороне текущее состояние поля
5. Преобразуем это состояние обратно в код символа
6. «Запихиваем» символ в выходную строку

Моделирование неоднородных динамических систем

Также кандидат физико-математических наук Мамзин Е. А. в 2011 году предложил метод клеточных автоматов в качестве высокопроизводительного средства вычисления и развития численных методов.

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

В настоящее время наибольшее применение клеточные автоматы нашли в задачах моделирования гидро- и газодинамических, эволюционных, поведенческих, колебательных и различных вероятностных процессов, что обусловлено сравнительной простотой их реализации, предрасположенностью к распараллеливанию и большими перспективами дальнейшего использования. Вопросам применения клеточных автоматов посвящены исследования многих отечественных и зарубежных учёных. Среди них МалинецкийГ.Г., Шакаева М.С., Лобанов А.И., Биндера К., von Neumann J., Martin O.,Toffoli T., Margolus N., Wolfram S., Moore F., Cipra B., Gacs P., Gardner M.,Gutowitz H. и др.

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

Класс Field

Данные

• Правило перехода состояний. Экземпляр класса Rule, хранящий правило перехода состояний. Интерфейс класса описан выше.
• Текущее состояние поля. Экземпляр класса std::vector<bool>, хранящий текущее состояние всех клеток поля. Вектор инициализируется двоичными разрядами кодируемого символа в конструкторе и изменяется при вызове оператора (), в котором и происходит кодирование.
• Вспомогательное поле. Вспомогательный экземпляр класса std::vector<bool>, хранящий состояние всех клеток поля. Используется при просчёте следующего поколения клеток. Можно было бы определять его прямо в операторе (), но этот оператор используется довольно часто, поэтому практичней определить вектор отдельно.
• Размер поля. Константа типа size_t, хранящая размер поля клеточного автомата, равна 8, так как на данный момент поддерживается лишь кодировка ASCII.

Функции

• Конструктор. Принимает константную ссылку на объект типа Rule и константу типа unsigned char. Так как конструктор класса Rule не объявлен explicit, мы можем передавать вместо ссылки целое число — номер правила перехода, записанный в виде кода Вольфрама (см. ссылку в начале). Переданный символ разбивается на двоичные разряды, записываемые по порядку в вектор, который хранит текущее состояние поля.
• Оператор (). Здесь и происходит кодирование символа. Просчитывается следующее поколение (для каждой клетки смотрим её окрестность и с помощью правила перехода узнаём состояние клетки посередине в следующем поколении). Поле замкнуто в кольцо, поэтому отдельно считаем состояние клеток по краям поля. После этого поле обратно переводится в десятичную систему счисления, при этом мы получаем код символа, который и возвращаем из функции.

Немного тестов

Для зашифровки всех символов кодировки Unicode с использованием правила 110 понадобилось на моей системе 645 000 тиков или приблизительно 0.645 секунды (средние значения для 10 запусков).

Для зашифровки одного символа кодировки Unicode с использованием правила 110 понадобилось 80 тиков или приблизительно 0.00008 секунды (средние значения для 10 запусков).

Все символы Unicode с использованием всех 256 правил были зашифрованы за 133500000 тиков или приблизительно 134 секунды (средние значения для 10 запусков).

Но самое странное, что выдаются верные результаты! Проверял вручную, лично зашифровав некоторые числа.

Заключение

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

Тьюрмиты

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

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

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

На rosetta code есть довольно хитрая реализация, где направление муравья задается комплексным числом:

Поначалу, поведение агента кажется хаотичным. Но потом появляется магистраль — система выходит на стационар. Прекраснейший пример рождения порядка из кажимого хаоса!

Но самый смак начинается если расширить состояние ячейки за пределы одного бита:

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

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

и еще ряд интересных правил:

Магистрали довольно частое явление

Мозг в ящике — довольно стабильная структура. Здесь результат тридцати миллиардов шагов:

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

Эпилог

К слову о жизни. Немало интереса вызывают самовоспроизводящиеся структуры, а ля циклы Лэнгтона

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

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

Ну и напоследок самокопирующаяся структура созданная Тэдом Коддом на спор за пинту пива