Автор работы: Пользователь скрыл имя, 08 Октября 2015 в 22:27, реферат
Математические модели типа «клеточных автоматов» в последнее время широко применя-ются для моделирования систем типа «реакция-диффузия». Кроме того, модели клеточных авто-матов применяются при моделировании процессов в нанотехнологиях, при моделировании до-рожного движения. Математические модели теории перколяции («просачивания») также можно отнести к моделям типа клеточных автоматов.
Система клеток, которую описывает игра «Жизнь», развивается необратимо. В самом деле, конфигурация в момент t полностью определяет будущее (состояние в моменты t +1, t +2 и т. д.). Но восстановить прошлое системы по ее настоящему не удается.
В игре «Жизнь» существуют конфигурации, которые могут передвигаться по плоскости. Одной из них является «планер». (Внизу на рис. 6 стационарная структура поставлена в качестве точки отсчета). Через каждые четыре шага он повторяет себя, сдвигаясь на одну клетку вниз и вправо. Некоторые конфигурации могут передвигаться не вдоль диагоналей, а по прямой. Таков, например, «корабль», показанный вверху на рис. 6
Рис. 6. Подвижные структуры «планер» и «ко- Рис. 7. Начальная конфигурация «резонанс» из
рабль» в начале эволюции. Момент време- 5 клеток
ни t = 1
Столкновение двух планеров или планера со стационарами может приводить к их «анни-гиляции». Иногда при столкновении может рождаться целый набор семафоров и стационаров
Обратим внимание на две закономерности. Если в конфигурации возникла симметрия (например, относительно вертикальной или горизонтальной оси), то далее в процессе эволюции она сохра-няется. Если конфигурация все время локализована в квадрате со стороной N , то она является набором стационаров и циклов, период которых не превышает 2N .
Обратим внимание на конфигурацию, показанную на рис. 7. Возникающие при эволюции клетки занимают все большую часть плоскости, рождается несколько планеров, причем это со-общество будет развиваться далее. Ни одна из других конфигураций, состоящих из пяти клеток, не приводит к такому сложному поведению.
Как правило, эволюция взятых наугад конфигураций приводит к появлению наборов ста-ционаров, семафоров, планеров. При этом общее число «живых» клеток при t → ∞ оказывается ограниченным. Однако при некоторых начальных данных ситуация может качественно менять-ся. Такое поведение характерно для ряда биологических систем, в частности, эволюционных процессов. Маловероятное событие может качественно изменить поведение системы, привести к появлению новых видов. Именно поэтому «клеточные автоматы» (к этому классу моделей принадлежит игра «Жизнь») находят применение в экологических моделях, при моделировании морфогенеза, в других биологических задачах
Чем большую площадь занимает сообщество, тем сложнее оно может себя вести.
Рис. 8. «Катапульта» в момент а) t = 1; б) t = 128
Поэтому большой интерес вызывают неограниченно растущие в пространстве конфигура-ции. Одну из них, называемую «катапультой», или «планерным ружьем«, предложил в 1970 г. Р. Госпер-младший.
Катапульта через каждые 30 шагов повторяет себя и выпускает планер. Планерное ружье заполняет пространство потоком планеров. Есть еще более сложные сообщества клеток, которые могут двигаться, оставляя за собой большой набор семафоров и стационаров. Одно из них — «паровоз», показанный на рис. 9. Поиск таких конфигураций требует применения специальных алгоритмов.
«Райские сады»
В последнее время среди любителей игры «жизнь» появилось новое увлечение — поиски «райских садов», или «садов Эдема». Так называется конфигурация клеток, которая не может быть получена ни при какой начальной конфигурации клеток «жизни».
Другим примером нетривиального характера эволюции простых начальных данных служит исследование Г. Г. Малинецким и М. С. Шакаевой двумерного обобщения автомата
Легко видеть, что окрестности Неймана соответствует явная разностная схема с шаблоном, соединяющим центры квадратов на рис. 10а, а окрестности Мура — на рис. 10б. (Конечно, только для этапа «предиктора» (6)). Можно убедиться, что для гладкого начального распределения обе разностные схемы устойчивы в случае k < 1/4 ( k — аналог числа Куранта; k = τD/h2 , схема на рис. 10а монотонна при k < 1/4 а на рис. 10б — при k < 1/8 ). Изменение α от 0 до 1 в формуле (6) соответствует k ∈ [0, 1/4] для схемы на рис. 10а, k ∈ [0, 1/8] для схемы на рис. 10б. Читателям, знакомым с основами теории разностных схем, предоставляем проверить это в качестве простого упражнения. Остальным следует обратиться к Приложению 1
Таким образом, случай схемы с рис. 10а (окрестность Неймана) «ближе» к области немо-нотонности, и, как можно ожидать, она будет более «урожайна» на существование различного рода структур.
Численный эксперимент, результаты которого приведены в [Малинецкий, Шакаева, 1992; Малинецкий, Шакаева, 1991], показывает, что в случае окрестности Неймана в довольно уз-кой области параметров (α, M) могут существовать аналоги «планеров» в игре «Жизнь»: в эксперименте фиксируется два вида «планеров».
Первый вид существует при M = 6, α ∈ [0, 41, 0, 43] и повторяет себя через каждые 7 вре-менных шагов, смещаясь на две клетки по вертикали вниз. Начальное распределение показано на рис. 11. В «розовых» клетках значение функции равно 1, в «голубых» — М. Второй вид (M = 6, α ∈ [0, 35, 0, 40]) перемещается за четыре временных шага на одну клетку вниз.
При M = 6, α = 0, 45 «планер» превращается в «паровоз» (подвижную структуру, остав-ляющую след из «дыма», изчезающего за конечное число тактов). При столкновении «планеров» между собой и с устойчивыми структурами могут наблюдаться достаточно сложные структуры, в том числе, спиральные волны. Последние в этом случае можно получить и в результате взаимо-действия растущей структуры со стационарным циклом периода 3. При этом спиральные волны существуют также в ограниченном диапазоне значений α, M ( α = 0, 35, M = 6 — конфигурация рис. 7 дает спиральную волну, при M = 8 волн нет). Данные волны по своей природе отличают-ся от волн в «стандартных» возбудимых средах: в этой модели они обусловлены перемещением границ областей постоянной концентрации, внутри которых концентрация меняется по циклу периода 3 [Малинецкий, Шакаева, 1992].
Рис. 11. Конфигурация «Планер, повторяющая себя за 7 временных шагов» в момент t = 1
Таким образом, класс моделей клеточных автоматов способен демонстрировать разнооб-разное поведение и является сравнительно легко моделируемым (на ЭВМ) объектом. Класс мо-делей позволяет получить качественные характеристики процессов. Клеточные автоматы могут служить также для имитационного моделирования течений вязкой жидкости и МГД-течений. К недостаткам относится слабая изученность класса моделей.
В последнее время появляются и более сложные конструкции клеточных автоматов. В ка-честве примера укажем работу [Gontar, 1993], где строится и анализируется автомат для моде-лирования периодических химических реакций типа реакции Белоусова–Жаботинского. В цити-руемой работе для анализа свойств клеточного автомата строится теория, основанная на анализе размерности и Π-теореме [Седов, 1988]. Для анализа свойств клеточного автомата построены дискретные аналоги автомодельных решений.
Теория клеточных автоматов в настоящее время разработана очень слабо, и основным способом их изучения является численный эксперимент.
Другие автоматы типа «Жизни»
Первые описания игры «Жизнь» на русском языке содержится в книгах Мартина Гардне-ра [Гарднер, 1988; Гарднер, 1972]. В 1980–2010 годах в разных странах разными авторами созда-ны «жизнеподобные» клеточные автоматы. Математические теории и численный эксперимент в области таких автоматов привели к возникновению не только многочисленных специализи-рованных Интернет-ресурсов, но и специализированных научных журналов. Адреса некоторых ресурсов приведены в Приложении 2.
Так, в двумерном пространстве все автоматы типа «Жизни» определены только на шаблоне типа «окрестности Мура». Правила перехода на следующий слой могут быть записаны в канони-ческой форме B3/S23. В первой части записи правила послойного перехода (B от слова «born» — «рождение») указывается то число соседей в окрестности Мура, при котором происходит рож-дение новой клетки. S (save) — число соседей, при котором клетка остается живой. Во всех остальных случаях клетка переходит в состояние 0 — «смерть», и эти правила не записываются стандартной нотацией.
Все автоматы типа «Жизнь» рассматривают клетки, находящиеся в двух состояниях, правила перехода зависят только от числа соседей в окрестности Мура.
Обобщение игры Дж. Конвея «Жизнь» на случай пространства произвольной размерности
и трехмерный клеточный автомат У. Ооно–М. Кохомото
Здесь α ∈ [0, 1], N — число точек в окрестности Aij . Их количество может быть различ-ным. Если в окрестность θ(i, j, n) включены те ячейки, которые имеют с данной общие грани (их 6), назовем окрестность трехмерной окрестностью Неймана; если включены те ячейки, что имеют с данной общие грани и общие ребра (их 14), то назовем окрестность окрестностью Неймана–Мура. Можно включить в окрестность θ(i, j, n) все ячейки, имеющие с данной об-щие грани, ребра или вершины. В этом случае окрестность из 26 ячеек назовем трехмерной окрестностью Мура.
Остановимся на некоторых недостатках данного клеточного автомата. Модель второ-го этапа (химических реакций), очевидно, условна. Это — достоинство предлагаемой моде-ли, позволяющее сократить количество операций и уменьшить требования к точности их выполнения.
Первый этап моделирует диффузию. Если в окрестности Неймана нет очевидных способов улучшения автомата на данном этапе, то для окрестностей типа Мура есть почти очевидные дефекты описания диффузии.
Модификации автомата Кохомото–Ооно в окрестности Мура для трехмерного случая
Для линейного уравнения диффузии все пространственные направления равноправны. Для этого достаточно убедиться, что уравнение
Отсюда следует, что диффузионные потоки во всех направлениях в модель должны входить равноправно. Между тем, для рассматриваемой модели правил перехода клеточного автомата по-токи из тех ячеек, которые имеют с данной общее ребро или общую вершину, точно такие же, как и потоки из ячеек, имеющих с данной общую грань. Это приводит к неравноправному уче-ту диффузионных потоков. В эвклидовой метрике расстояние между центрами соседних клеток неодинаково, следовательно, при равноправии пространственных направлений, веса у диффузи-онных потоков должны учитывать тип соседства (общая грань, ребро или вершина). Будем рас-сматривать автомат, реализованный на окрестности Мура в трехмерном случае, как более общий случай. Сужение правил перехода автомата при выборе окрестности Мура–Неймана будет сразу
следовать из рассмотрения. Очевидно, что расстояние между центрами фиксированной ячейки и ячеек, имеющих с ней общее ребро, в 2 раз больше, чем расстояние до центров тех ячеек,
которые имеют с данной общую грань. Если ячейка имеет с данной лишь общую вершину, то расстояние между центрами увеличится в 3 раз. Соответственно, во столько же раз уменьшим и диффузионные потоки. После необходимых тривиальных преобразований для правил перехода получим следующую краткую запись.
где учтено, что у данной клетки 6 соседей, имеющих с ней общую грань (расстояние √между центрами ячеек равно 1), 12 соседей имеют с данной общее ребро (поток уменьшается в 2 раз, вес значения функции в данной ячейке уменьшается вдвое) и 8 соседей имеют с данной общую вершину. При этом поток уменьшается в 3 раз, вес значения функции в данной ячейке умень-шается втрое. Параметры, характеризующие подвижность молекул, в этих двух записях правил перехода связаны очевидным соотношением
β(6 + 12 · 1/2 + 8 · 1/3) = α.
Отметим, что и двумерные модифицированные клеточные автоматы в окрестности Мура, и, тем более, трехмерные варианты пока не исследованы.
Список литературы.
http://www.vlad-utenkov.narod.
http://www.dissercat.com/
http://dic.academic.ru/dic.
https://ru.wikipedia.org/wiki/
http://uvd45.ru/2-kurs/
http://cinref.ru/razdel/
http://refdb.ru/look/1427299-
http://ancient.hydro.nsc.ru/