|
§ 24. Имитационные модели в электронной таблице
Основные темы параграфа:
♦ что такое имитационная модель;
♦ пример имитационного моделирования в электронных таблицах.
Что такое имитационная модель
В предыдущем параграфе вы познакомились с примером реализации в
электронной таблице математической модели. Сейчас рассмотрим пример
реализации другого типа модели, которая называется имитационной моделью.
Об имитационных моделях говорилось в § 9. Вспомним данное там определение:
Имитационная модель воспроизводит поведение сложной системы,
элементы которой могут вести себя случайным образом. Иначе говоря,
поведение которых заранее предсказать нельзя.
Пример имитационного моделирования в электронных таблицах
Как и в предыдущем параграфе, пример возьмем из класса моделей, описывающих эволюцию популяций.
Пусть на определенном пространстве случайным образом расселяются
живые организмы. В дальнейшем происходит процесс смены поколений: в
каких-то местах расселения жизнь сохраняется, в каких-то исчезает. Эти
процессы протекают в соответствии с законами эволюции. Законы эволюции в
описании модели представляются в виде формальных правил. Цель
моделирования — проследить изменения в расселении живых организмов со
сменой поколений.
Сначала рассмотрим простейший вариант задачи: жизненное
пространство одномерное. Это значит, живые организмы расселяются вдоль
линии. Будем считать жизненное пространство ограниченным, т. е.
рассмотрим отрезок. Отрезок разделяется на ячейки, в пределах каждой из
которых может поселиться один организм. Договоримся, что самые крайние
ячейки не заселяются. Они определяют границу жизненного пространства.
На рис. 4.3 показано первоначальное расселение организмов на
поле, состоящем из 20 ячеек. Организмы поселились в ячейках с номерами
5, 8 и 12. Ячейки 1 и 20 всегда должны быть пустыми.
Теперь сформулируем законы эволюции. В следующем поколении в
пустой ячейке жизнь может либо появиться, либо нет. В живой ячейке жизнь
может либо сохраниться, либо исчезнуть. На состояние данной ячейки
влияют ее ближайшие соседи: два соседа слева и два соседа справа. Если
ячейка была живая, и число живых соседей не превышает двух, то в
следующем поколении в этой ячейке жизнь сохранится, иначе жизнь исчезнет
(погибнет от перенаселения). Если в ячейке жизни не было, но среди ее
соседей есть 1, 2 или 3 живые ячейки, то в следующем поколении в этой
ячейке появится жизнь. В противном случае ячейка останется пустой.
Следует учитывать, что у ячеек, расположенных у края, число
соседей меньше других. У ячейки номер 2 соседи: 1, 3 и 4. Но ячейка 1
всегда пустая. У ячейки номер 3 из четырех соседей живыми могут быть не
больше трех (2,4,5). Аналогичная ситуация у крайних правых ячеек.
То, что сказано выше, есть модельное описание процесса эволюции
популяции. Формализуем это описание. Распределение живых организмов по
ячейкам будем кодировать
последовательностью из нулей и единиц. Ноль обозначает пустую ячейку,
единица — живую. Например, расселение, отображенное на рис. 4.3,
кодируется следующим образом:
00001001000100000000
Обозначим буквой n номер ячейки, а значение двоичного числа, соответствующего этой ячейке в текущем поколении, обозначим R(n). В рассматриваемом примере R(5) = R(8) = R(12) = 1. Все остальные значения ячеек равны нулю.
Значения кода в n-й ячейке для следующего поколения будем обозначать S(n). Внимательно проанализировав сформулированные выше правила эволюции, приходим к следующей формуле:
Если 1 < R(n - 2) +R(n - 1) + R(n) + R(n + 1) + R(n + 2) < 3,
то S(n) = 1, иначе S(n) = 0.
Эта формула работает для значений n от 3 до 18. Всегда: S(1) = S(20)
= 0. Для ячеек с номерами 2 и 19 в данной сумме нужно убрать по одному
слагаемому. Но можно поступить иначе, чтобы оставить справедливой данную
формулу для всех ячеек жизненного пространства. Для этого к отрезку
добавим по одной фиктивной ячейке справа и слева. Их номера будут,
соответственно, 0 и 21. В этих ячейках, как и в ячейках 1 и 20, всегда
будут храниться нули. Тогда написанную формулу можно применять для n от 2 до 19.
Итак, модель построена и формализована. Однако имитационной
моделью она станет только в результате реализации с помощью какого-то
программного компьютерного средства. В качестве такого средства выберем
табличный процессор.
Моделью жизненного пространства будет строка электронной таблицы.
Первая строка — первое поколение, вторая строка — второе поколение и т.
д. Тогда номера ячеек будут идентифицироваться именами столбцов
таблицы. Ячейка номер 0 — столбец А, ячейка 1 — столбец В и т. д.,
ячейка 21 — столбец F.
В первой строке выставляем единицы в ячейках, заселенных в первом
поколении. Это будут ячейки F1, I1, М1. Незаполненные ячейки по
умолчанию приравниваются к нулю.
Теперь в ячейки второй строки нужно записать формулы. Сделать это
достаточно один раз. Например, в ячейку С2 занести следующую формулу:
ЕСЛИ(И(А1 + В1 + С1 + D1 + Е1 >=1;
А1 + В1 + С1 + D1 + Е1 <= 3); 1; 0)
Далее, копируя эту формулу во все остальные ячейки второй строки с
D2 по Т2, получаем картину распределения живых организмов во втором
поколении.
Чтобы получить третье поколение, достаточно скопировать вторую
строку (блок С2:Т2) в третью строку (блок СЗ:ТЗ). Так можно продолжать
сколько угодно.
На рис. 4.4 показаны результаты имитационного моделирования
процесса эволюции исходного расселения живых организмов вплоть до 10-го
поколения. Все очень наглядно. Обратите внимание, как драматично
развивались события! В шестом поколении наступило состояние
перенаселения, В результате в седьмом поколении вымерли все организмы,
кроме крайних. Их спасло свободное пространство слева и справа. От них
пошла новая волна жизни!
Рассмотренная задача является упрощенным (одномерным) вариантом
известной модели Дж. Конуэя, которая называется «Жизнь». В этой модели
эволюция популяции живых организмов происходит в двумерном пространстве.
Рассматривается прямоугольная область, разделенная на квадратные
ячейки. Тогда у каждой внутренней ячейки имеется 8 соседей. Судьба жизни
в ячейке также зависит от состояния соседних клеток. Но теперь правила
эволюции такие: если клетка живая и в ее окружении более трех живых
клеток, то она погибает от перенаселения; если же живых соседей меньше
двух, то она погибает от одиночества. В пустой клетке в следующем
поколении зарождается жизнь, если у нее есть ровно три живых соседа.
Попробуйте самостоятельно получить имитационную модель для этой
задачи в среде электронной таблицы. Последовательность действий будет
аналогичной рассмотренной в примере. По-прежнему для перехода к новому
поколению нужно использовать метод копирования диапазона. Но только
теперь придется копировать не линейный диапазон, а прямоугольный.
Коротко о главном
Рассмотренная имитационная модель эволюционного типа позволяет
проследить за изменениями в расселении живых организмов со сменой
поколений.
Удобство применения электронной таблицы для имитационного
моделирования заключается в простоте реализации вычислительного
алгоритма и наглядности представления результатов.
Вопросы и задания
1. Для каких задач используется метод компьютерного имитационного моделирования?
2.
В чем отличие эволюционной задачи, решавшейся методом математического
моделирования в § 23, от задачи, решавшейся в данном параграфе методом
имитационного моделирования?
3. Проведите вычислительный эксперимент
на линейной имитационной модели для различных вариантов исходного
расселения организмов. Ответьте на вопросы:
1) Возможно ли такое расселение, при котором все организмы в конце концов вымрут?
2) Не ведет ли любое расселение в конечном итоге к одной и той же последовательности поколений?
3) Что меняется с изменением размера жизненного пространства?
4*.
Постройте в электронной таблице двумерную модель Дж. Конуэя «Жизнь».
Проведите вычислительный эксперимент с разными вариантами
первоначального расселения организмов.
5*. Решая предыдущую задачу, попробуйте найти такие первоначальные расселения, которые:
1) обречены на гибель;
2) не меняются со сменой поколений;
3) ведут к периодической смене повторяющихся конфигураций расселения.
Тренировочный тест к главе 4 "Табличные вычисления на компьютере". Самоконтроль по теме "Табличные вычисления на компьютере". Подготовка к итоговому тестированию.
Итоговый тест к главе 4 "Табличные вычисления на компьютере". Многовариантная генерация тестов для итогового контроля по темам "Представление чисел. Электронные таблицы"
|
