Клеточные автоматы. Часть III. Применение клеточных автоматов.


Клеточные автоматы. Часть III. Применение клеточных автоматов.

Теория клеточных автоматов, связанная с именами фон Неймана и Конрада Цузе, имеет фундаментальное значение для всей науки и многообразное прикладное применение. Начиная с работ Т. Тоффоли и Н. Марголуса 80-х гг. [Тоффоли и др. 1991], клеточные автоматы (КА) стали использоваться в моделях физико-химических процессов. К середине 90-х гг. клеточно-автоматное моделирование проникло [Pintoetal. 2007] в гуманитарные науки при изучении мультиагентных cистем в урбанистике (толпа, транспортная пробка). Обзорная статья [Ванаг, 1999] В. Ванага по вероятностным КА еще раз легитимизировала для отечественных исследователей клеточные автоматы как метод математического моделирования. Последнее десятилетие ознаменовалось бумом публикаций в самых разных разделах науки, связанных с КА-моделями [Лобанов, 2010]; одновременно с этим продолжает развиваться и математическая теория клеточных автоматов (на русском языке см. монографию В. Аладьева [Аладьев, 2009]).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

Степанцов М.Е.

 

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

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

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

 

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

 

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

 


Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • Как искусственный интеллект помогает в изучении иностранного языка ?
  • Технологии стали неотъемлемой частью нашей жизни. Они развиваются так быстро, что люди не успевают за ними. Мы не можем отрицать его силу или
  • Mail.Ru Group запустили чемпионат по искусственному интеллекту Mini AI Cup #3!
  • На конец лета выпало событие, которое наверняка заинтересует многих любителей поразмышлять о будущем разумных машин. Неделю назад, 30 августа,
  • Искусственный интеллект против команды профессиональных геймеров в DOTA 2. Кто победит?
  • Искусственный интеллект уже подтвердил, что может легко расправится со своими соперниками людьми, играя с ними в шахматы, Го или покер. Как он
  • Обработку разведданных с дронов США поручат искусственному интеллекту
  • Как известно, большинство частных компаний избегают использовать свой потенциал при разработке систем искусственного интеллекта для оборонных целей.
Последние комментарии
Теория и Практика Технологической Сингулярности и Искусственного Интеллекта
На сегодня развитие IT в США значительно опережает состояние в России, где нет своего компьютера, нет своей операционной системы, нет своей
Как работает Любовь? Квантовая связь нейронной активности Людей
про квантовые коммуникации прочитал - интересно. Спасибо. Про любовь - не увидел. Жалко.
Топ 10 компаний, занимающихся разработкой искусственного интеллекта
Спасибо, перечень интересный, но знакомый. Единая проблема всех ИИ-разработчиков - не понимание того, что сознание - это не статистика, а пойти по
Теория и Практика Технологической Сингулярности и Искусственного Интеллекта
Технологическая сингулярность по мнению Вернора Винджа будет развиваться следующим образом: 1. Компьютеры обретут сознание, и возникнет мощный ИИ; 2.
Теория и Практика Технологической Сингулярности и Искусственного Интеллекта
Может ли технологическая сингулярность, т.е. взрывное ускорение научно-технического прогресса, появиться только в России или необходимо, чтобы она
Мы в социальных сетях
Статистика
0  
Всего статей 1511
1  
Всего комментариев 49
1  
Пользователей 48