bigpo.ru
добавить свой файл
1 2 ... 4 5
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО «Самарский государственный архитектурно-строительный университет»

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники


Отчётная работа

по Методологии научных исследований

на тему

«Исследование закономерностей эволюции видов на базе эволюционной модели Конуэя "Жизнь"


СТУДЕНТА ГИП-104 Поляков В.











Подпись, дата


Расшифровка подписи








ВЫПОЛНИЛ: студент ГИП-104





Поляков В.







студент




/ /







Модуль сдан в библиотеку кафедры ПМ и ВТ













Модуль размещен на портале ФИСТ













ПРОВЕРИЛ:




Пиявский С.А.







ОЦЕНКА




/ /



Самара 2007 г.


Глава 1.


  1. Проблема и актуальность её решения.




    1. Клеточные автоматы и сферы их применения.


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

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

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


Кле́точный автома́т (КА) — набор клеток, образующих некоторую периодическую решетку с заданными правилами перехода, определяющими состояние клетки в следующий момент времени через состояние клеток, находящимися от нее на расстоянии не больше некоторого, в текущий момент времени. Как правило, рассматриваются автоматы, где состояние определяется самой клеткой и ближайшими соседями. В качестве решетки обычно рассматривается кубическая решетка. Один из самых интересных примеров клеточного автомата — игра «Жизнь».


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


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

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

Таким образом, вычислительная система может оперировать своей материальной частью, модифицировать, расширять себя и строить себе подобных . Хотя системы этого класса и были придуманы Джоном фон Нейманом, такая параллельная архитектура получила название «не-фон-неймановской», так как последовательную архитектуру он создал раньше. Если сравнивать клеточные автоматы и обыкновенные дифференциальные уравнения (ОДУ), то одно из основных отличий первых от вторых заключается в локальности правил, с помощью которых описывается динамика системы. В случае применения ОДУ мы пользуемся некоторыми правилами изменения усредненных по всей системе величин – средних (например, концентраций). При этом изначально полагают, что такие правила существуют. В случае КА существование таких обобщенных правил необязательно. Достаточно знать законы развития системы на микро- или мезо-уровне в небольших пространственных областях (ячейках), из которых состоит макросистема. Важно лишь, что эти локальные правила одинаковы для всех ячеек. Другим отличием КА от дифференциальных уравнений (ДУ) является использование не только дискретных, но и, как правило, целочисленных переменных. Дискретность переменных позволяет рассматривать большой класс разрывных недифференцируемых функций. Следует отметить, что дискретные свойства КА заметно уменьшаются при работе с большими значениями переменных, но никогда не исчезают. Всегда существует минимальный дискретный шаг изменения переменной. В случае же численного решения ОДУ или ДУ в частных производных можно уменьшать шаг дискретности до сколь угодно малых величин.


1.2 Основные свойства классической модели клеточных автоматов.


Основные правила:


• Локальность правил. На новое состояние клетки могут влиять только элементы её окрестности и, возможно, она сама;


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


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


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


1.3 Классификация клеточных автоматов


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

Клеточные автоматы с памятью можно получить, предположив, что функция F зависит, например, также от состояния элемента в еще более ранний момент времени. Подвижные КА характеризуются возможностью изменения положения клетки в решетке во время эволюции системы. В неподвижных КА положение клетки во время эволюции остается постоянным. Иногда используются правила, записанные в виде обыкновенных дифференциальных уравнений (класс КА-ОДУ). В этом случае состояния ячеек задаются набором переменных, значения которых способны принимать любые действительные числа. Для таких автоматов дифференциальные уравнения решаются для каждой ячейки отдельно на протяжении фиксированного отрезка времени, при этом каждая ячейка может иметь различные начальные условия. Этот класс КА очень плотно прилегает к ДУ в частных производных. КА, в которых состояния ячеек в последующий момент времени определяются на основе некоторых вероятностей, называются вероятностными КА (ВКА).

В классических ВКА правила переходов имеют абстрактный характер и не связаны однозначно с реальными процессами, происходящими в моделируемой системе. В таких автоматах при моделировании процесса для каждой ячейки датчиком случайных чисел генерируется случайное число Q (0 < Q < 1), которое сравнивается с вероятностью w реализации этого процесса. Если Q < w, то процесс реализуется. К таким КА относятся метод реакционного решеточного газа, метод прямого стимулирования Монте-Карло и метод вероятностного КА с применение процедуры Монте-Карло. В ВКА вместо функции F необходимо задать набор вероятностей изменения состояния клетки. которые показывают, какой будет вероятность перехода i-го элемента из состояния в n-й момент времени в состояние в последующий n+1-й момент времени при условии, что состояния его ближайших соседей в n-й момент времени принимали определенные значения.


Модели типа КА-ОДУ занимают промежуточное состояние между КА и ВКА, а также между простыми КА и ДУ в частных производных. Основной идеей КА-ОДУ является разбиение моделируемой области на равновеликие ячейки и решение системы ОДУ независимо в каждой ячейке с различными начальными условиями. В некоторых моделях пространственное расположение ячеек несущественно, а в других количество соседних ячеек и размерность пространства играют решающую роль (случаи распространения волн или образования стационарных пространственных структур в неперемешиваемой среде). В моделях КА-ОДУ предполагается, что клетка содержит очень большое число частиц, позволяющее применять ОДУ и непрерывные функции. Это обстоятельство оставляет только один способ для моделирования диффузии, а именно простое усреднение концентрации по соседним ячейкам.


Для решения наиболее трудных задач типа "реакция – диффузия – конвекция" с учетом флуктуаций был разработан метод вероятностного клеточного автомата с применением процедуры Монте-Карло (ВКА-МК или просто ВКА). Клеточный автомат представляет собой регулярную решетку, состоящую из N2=N0 элементарных ячеек. Форма решетки может быть не только квадратной, но и прямоугольной с сильно вытянутыми ячейками. Каждая ячейка характеризуется набором целых чисел: числом молекул соответствующего сорта в данной ячейке (например, nA, nB, nC в случае трех сортов молекул A, B и C) и своими целочисленными координатами (например, i и j). Ячейке приписывается также определенный объем Vm и линейный размер l=(Vm)1/3. Объем Vm используется при задании вероятностей протекания химических реакций в ячейках. Все ячейки считаются гомогенными.

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

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

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


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


следующая страница >>