Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Простейшие клеточные автоматы в математическом моделировании процессов Шакаева, Милана Салаватовна

Диссертация, - 480 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Шакаева, Милана Салаватовна. Простейшие клеточные автоматы в математическом моделировании процессов : диссертация ... кандидата физико-математических наук : 05.13.16.- Москва, 1995.- 127 с.: ил. РГБ ОД, 61 95-1/1007-3

Введение к работе

Актуальность темы. Основной задачей при изучении

пространственно-временного поведения многих систем в природе является математическое моделирование их временной эволюции. Для эё решения традиционно использовались дифференциальные уравнения з частных производных. Можно условно выделить три этапа в ізучении эволюции физических систем. Первый этап заключается в юпытке описать явление с помощью уравнений путей различных допущений и предположений относительно явления. В редких случаях кино найти аналитическое решение полученных уравнений. Чаще гсего в нашей власти лишь провести анализ динамики только для достаточно простых моделей. И вот тогда для их решения приходится прибегать к численным методам. Второй этап, таким образом, заключается в "переводе" дифференциальных уравнений в чзстных фонзводных в 'конечно-разностные. На этом этапе непрерывное іространство и время заменяются на дискретные, непрерывные функции - на сеточные, производные - на разности между значениями зеточных функций в соседних узлах пространственно-временной эешетки ( путем "обрывания" рядов. представляющих собой разложения непрерывных функций ). Решение полученной системы сонечпо - разностных уравнений имеет, спадовательно, некоторую тогрешюсть, называемую погрешностью дискретизации. И далее, так сак решать "вручную" конечно-разностныэ уравнения тоже не под зилу из-за большого объема вычислений, их решают с помощью ЭВМ. 1а третьем этапе осуществляется проекция действительных величин іа машинное слово, имеющее конечное количество разрядов. Что вызывает еще и погрешность округления. А не существует ли менее школьного пути моделирования явлений природы?

Обычно на первом этапе . при выводе уравнений в частных іроизводньїх мы переходим от законов для физически малого объема іутем усреднения ( интегрирования ) к уравнениям, описывающим макроскопические изменения в системе. Но иногда переход к «прерывному описанию затруднен из-за "дискретности" задачи і когда переменные, характеризующие явление, имеют малое соличество значении или когда существует "порог" при изменении теременной ). Например, если в "физически малом объеме" почти 5сегда оказывается одна или ни одной частицы, то переходить к

понятию плотности p=lin N(r)/v, где ы - число частиц в объеме V,

v-»o просто неразумно. Плотность будет почти всегда нулевой и только

изредка очень большой.

Далее, осуществив переход из микромира, который сам по себе

дискретен ( на молекулярном уровне-) в макромир с непрерывными

величинами, мы на втором этапе опять возвращаемся на дискретный

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

модели?

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

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

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

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

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

Отметим основные достоинства использования клеточных автоматов для моделирования физических процессов:

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

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

  3. упрощается анализ разрывных решений ( по сравнению с традиционными конечно-разностными схемами );

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

  5. связь с физической реальностью : благодаря своей "микроскопической природе", модели клеточных автоматов могут демонстрировать явления, имеющие место в реальных системах, но которые не могут быть получены из макроуравнений, - те 'явления, которые теряются в результате аппроксимации при переходе от физической модели к непрерывным уравнениям ( например, явления, связанные с микроскопическими флуктуациями );

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

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

Естественно, автоматы имеют не толко достоинства, но и недостатки. Среди них:

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

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

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

Цель и задачи исследования. Широкое применение клеточные

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

  1. Каков?! простейшие типы упорядоченности в системе "реакция-диффузл-ч", описывающей колебательные химические реакции? I качестве базовой модели здесь был выбран клеточный аЕток*. предложенный У. Ооко и М. Кохмото. Как поведение автомата завис.' от параметров? Как повлияет на поведение модели увеличение чиг .; градаций концентрации?

  2. Каковы простейшие типы упорядоченности в колебательнг і реакции, протекающей на поверхности, при ее описании с помоги-простейшего двумерного клеточного автомата?

  3. Какова точность решения уравнения диффузии с помещыс v.r [г глы: автоматов? Как соотносится "автоматный" алгоритм j традиционно: схемой Монте-Карло? Каковы простейшие типы упорядоченности клеточном автомате, моделирующем образование осадка в систем типа "реакция-диффузия" ( неустойчивость Ли^еганга )?

  4. Каковы простейшие дискретные модели, дозволяющие имитироват

развитие иерархической организации?

Метод,ы_исследования. Для решения поставленных задач применялся численный эксперимент, методы теории вероятностей, теории динамических систем, теории автоматов.

ЗіїНЦая_новизна. В работе при исследовании одномерной модели обнаружены новые типы качественного поведения системы. В частности, аннигиляция волн при столкновении друг с другом. Это говорит о том, что волны могут вести себя не только как солитоны ( этот факт был обнаружен У. Ооно и М. Кохмото ), но и подобно автоволнам. Обнаружены пространственно-локализованные структуры, которые могут играть роль счетчика приходящих к ним волн, а таое явление "фазового перехода" ( когда одна "фаза" со временем полностью вытесняется другой ).

При исследовании двумерной модели, являющейся обобщением автомата У. Ооно и М. Кохмото, были обнаружены спиральные волны. Последние отличаются от ранее наблюдавшихся волн в возбудимы:; средах. Кроме того, были найдены движущиеся локализованные в пространстве объекты типа "планеров" в игре "Жизнь".

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

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

Полученные результаты могут быть использованы при решении прикладных задач в Институте прикладной математики. Московском государственном университете, Институте математического

моделирования, Институте радиоэлектроники, Ярославском государственном университете. Институте математического моделирования в биологии < Путино ), В Государственном комитете по высэему образованию и других организациях.

Апро^ацня_р_аботы. Основные результаты работы были доложены на международной конференции "математика. Компьютер. Образование" ( Носква-Пущино, 1995г. ). на Московском научном семинаре "Современные проблемы синергетики", а также на научных семинарах факультета ВмиК МГУ им. М. В. Ломоносова ( кафедра вычислительных методов ).

Публикации. По теме диссертации опубликовано восемь работ. перечисленных в конце автореферата.

СтеНТуез 8Е25ЕТаШ!8- Диссертация состоит из введения,

четырёх глав и списка литературы, включающего 59 наименований. Объем работы составляет 127 страниц.

Похожие диссертации на Простейшие клеточные автоматы в математическом моделировании процессов