Специальные задачи линейного и нелинейного программирования

Теория клеточных автоматов имеет сравнительно небольшую, но достаточно продуктивную историю, основные этапы которой детально изложены в работе [11], в которой особое внимание уделено фундаментальным свойствам клеточных автоматов: параллельности и локальности.
Клеточный автомат состоит из конечной совокупности объектов (ячеек), как правило, образующих регулярную решетку. Другими словами, если не использовать строгие математические термины, это — совокупность ячеек, определенным образом соединенных между собой и образующих равномерную сетку (решетку). При этом состояние каждой i-й ячейки (клетки) в момент времени t характеризуется некоторым числом a(i, t) или набором чисел. Совокупность состояний всех клеток решетки называется состоянием решетки. В модели клеточного автомата каждое состояние решетки соответствует некоторому моменту времени, которое изменяется дискретно по шагам (итерациям).
Состояние решетки меняется в соответствии с некоторым законом, который называется правилом клеточного автомата. Правила определяют, какое состояние должно быть у клетки в следующий момент времени, в зависимости от состояний ее и некоторых других клеток в текущий момент времени.
Теоретически клеточные автоматы могут иметь любую размерность, однако чаще всего рассматривают одномерные и двумерные клеточные автоматы. В случае двумерного клеточного автомата решетка реализуется двумерным массивом и каждая клетка нумеруется упорядоченной парой чисел (a, b). В этом случае у каждой клетки ближайшими соседями
считаются либо клетки, имеющие с исходной общую сторону (окрестность фон Неймана), таких клеток будет 4, либо имеющие с исходной общую вершину (окрестность Мура), таких клеток будет 8.
Классическая модель клеточного автомата имеет следующие свойства:
• сеть клеточного автомата является однородной, т. е. правила изменения состояний для всех клеток одинаковы;
• множество состояний каждой клетки конечно;
• на клетку могут повлиять лишь клетки из ее окрестности, ближайшие соседи;
• состояния всех клеток меняются единовременно, в конце итерации.
В модели клеточного автомата каждая клетка изменяет свое состояние, взаимодействуя с ограниченным числом клеток, как правило, ближайшего окружения. Однако имеется возможность одновременного (параллельного) изменения состояния всех клеток, всей решетки на основе общего правила клеточного автомата. Это свойство позволяет при моделировании связывать процессы, происходящие на микроуровне, с изменениями процессов, про¬текающими на макроуровне. Это важнейшее свойство клеточных автоматов, которое позволяет их успешно использовать для моделирования систем, в которых значительную роль играют пространственные взаимодействия между элементами. Они хорошо зарекомендовали себя при моделировании динамики жидкости и газа в различных средах, в пограничных зонах, при моделировании систем, состоящих из большого числа частиц, взаимодействующих друг с другом нелинейно, при описании возникновения коллективныхявлений — турбулентности, упорядочения, хаоса, нарушения симметрии, фрактальности и других.
В последние годы клеточные автоматы находят свое применение при мо-делировании социальных явлений как чисто теоретические модели для ка-чественного анализа процессов, так и для численного прогнозирования. Не-которые примеры клеточных автоматов, применяемых в задачах социологии, приведены в работе [9].
Результаты фундаментальных исследований в области клеточных автоматов представлены в работе [23], в которой сделан акцент на
возможности использования клеточных автоматов при моделировании физических, био-логических и вычислительных систем, в силу простоты реализации моделей, точности математических вычислений и способности моделей к моделированию сложных систем.
В целом у моделей клеточных автоматов достаточно много положительных качеств, которые, несомненно, влияют на активность их использования в различных областях науки. Однако есть и определенные негативные моменты, сдерживающие развитие этого направления математического моделирования, среди которых следует отметить слабую общую теоретическую базу клеточных автоматов, недостаточную разработку вопросов сходимости вычислительных экспериментов, вопросов устойчивости полученных численных решений.
В настоящее время существует достаточно много различных классификаций клеточных автоматов, из которых наиболее известна классификация Вольфрама, основанная на анализе возможной сложности поведения клеточного автомата. Классифицировать клеточные автоматы можно по разным признакам, в частности, по правилам изменения состояния клеток можно разделить автоматы на детерминированные и вероятностные. В детерминированных клеточных автоматах состояние каждой клетки в момент времени t + 1 определяется однозначно состоянием этой клетки и ее ближайших соседей в момент времени t.
Вероятностный клеточный автомат, описывающий диффузию инноваций, представлен в работе [6]. Каждой клетке соответствует агент, который может принять инновацию. Клетка может находиться в двух состояниях: S: — новинка принята, S0 — новинка не принята, состояние S: не может быть изменено. Автомат принимает или не принимает новинку, ориентируясь на мнение восьми или четырех ближайших соседей в окрестности данной клетки (окрестность Мура или Неймана). В зависимости от количества n приверженцев новинки существует пороговая функция P(n) — вероятность ее принятия. Для каждой клетки автомата на каждом шаге
(такте) генерируется случайное число х, определяется количество соседей п, принявших инновацию, проверяется неравенство х < P(n), если оно
выполняется, клетка принимает инновацию, то есть переходит в состояние Sr
Подобный автомат может быть использован для моделирования диффузии локальных инноваций в рамках одного города или района. Вероятностный клеточный автомат хорошо моделирует диффузию инноваций для сетевого маркетинга.


Купить