Вернуться в библиотеку

МОДЕЛИРОВАНИЕ РЕАЛЬНЫХ ВЕРОЯТНОСТНЫХ ПРОЦЕССОВ НА БАЗЕ КЛЕТОЧНЫХ АВТОМАТОВ С ОГРАНИЧЕНИЯМИ

Автор: Плотников Д.Ю., Малеваный Е.Ф.
Источник: Электронный архив ДонНТУ, http://ea.donntu.ru...

Аннотация

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

Постановка задач исследования

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

Решение задачи и результаты исследований

Первыми разработками на факультете, связанными с моделированием клеточных автоматов и компьютерной игрой "Жизнь" стали программы, разработанные Аноприенко А.Я. и Коноплевой А.П. [2]. Авторами для решения данной задачи были созданы две версии программы. Первая написана на языке Borland C++ Builder. Вторая версия ориентирована на Web-технологии и представляет собой Flash-приложение. Для краткого анализа программ с целью определения их основных достоинств и различий рассмотрим примеры их использования на конкретных задачах. Для простоты введем определения: Life Flash – Web-ориентированное приложение и просто Life – Windows-программа. При запуске Life мы видим окно, которое изображено на рисунке 1. Можно выполнить следующие действия:
- создание проекта;
- сохранение;
- загрузка.

При создании нового проекта необходимо задать тип фона – белая сетка или любое изображение формата Bitmap, что очень полезно для большей наглядности моделирования. Следующим шагом будет создание поля, размер которого 64*64 клетки. Элементы поля можно выбирать из трех типов: точки, которые будут участвовать в моделировании; преграды (ограничения), сквозь которые не смогут пройти клетки, а также обычный ластик, чтобы изменить уже созданное поле.

Рисунок 1 – Интерфейс программы Life

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

Продемонстрируем наглядно на примере модели распространения лавы в вулкане. Рисунок 2 состоит из 3-х частей: верхняя часть – исходное состояние, левая нижняя половина – выполнение стандартного алгоритма игры, правая нижняя – нового. Сверху – расположение точек до запуска, снизу – через 505 тактов. На рисунках не показаны ограничения, визуализация которых может быть включена как одна из опций. Как можно заметить, результат моделирования стандартного алгоритма не дает нам представления о том, что происходит в вулкане, что нельзя сказать о новом, разработанном нами.

Рисунок 2 – Распространение лавы в вулкане

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

Рисунок 3 – Модель распространения инфекции по Европе

Можно заметить, что хотя процесс и вероятностный, он все-таки отражает один из возможных вариантов реального распространения инфекции. Быстрее всего инфекция распространилась по остальной территории России. Затем она проникла в приграничные страны. Еще один крупный очаг заболеваемости возник в Турции. Возможно, это объясняется тем, что очень многие русские туристы отдыхают именно в этой южной стране. Государства Западной Европы, в свою очередь, проводят жесткий приграничный контроль. Это объяснят то, что на территории этих стран инфекция еще не успела добраться. Хотя спустя более продолжительный промежуток времени это все равно будет неизбежным.

Рисунок 4 – Модель распространения инфекции по миру

Поскольку в настоящее время быстрыми темпами развиваются Web-технологии, авторами была разработана онлайн-верися программы Life Flash. Благодаря этому любой исследователь, да и просто обычный человек, имея доступ к интернету, может быстро и удобно промоделировать интересующие его процессы. Главное преимущество приложения Life Flash над Life – удобство в использовании (его не нужно скачивать и устанавливать, достаточно просто запустить с сайта). Однако есть и существенный недостаток – оно работает медленней, чем Windows-приложение. Ведется активная разработка, в ходе которой Life Flash станет самым мощным программным продуктом для онлайн моделирования, как и Life – среди Windows приложений. Интерфейс Life Flash изображен на рисунке 5.

Рисунок 5 – Интерфейс программы Life Flash

Выводы

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

Список литературы

1. Тофоли Т., Марголус Н. Машины клеточных автоматов // Издательство “Мир” Москва, 1991. – 280 с.

2. Аноприенко А.Я., Коноплева А.П. Опыт применения гиперкодов в моделировании клеточных автоматов // Научные труды Донецкого национального технического университета. Серия "Проблемы моделирования и автоматизации проектирования динамических систем" (МАП-2007). Выпуск 6 (127): Донецк: ДонНТУ, 2007. С. 220-227.