bigpo.ru
добавить свой файл
  1 2 3 4 5

1.4 Игра Конвея «Жизнь»



Игра «Жизнь» — клеточный автомат, придуманный английским математиком Джоном Конвеем (John Horton Conway) в 1970 году. Описание этой игры было опубликовано в октябрьском выпуске (1970) журнала Scientific American, в рубрике «Математические игры» Мартина Гарднера (Martin Gardner).




Рис. 1 – Устойчивые конфигурации в модели Конуэя «Жизнь»




Игра "Жизнь" относится к категории так называемых моделирующих игр - игр, которые в той или иной степени имитируют процессы, происходящие в реальной жизни.

Действие игры происходит на некой плоскости, разделенной на клетки. Каждая клетка окружена 8 такими же клетками (окрестность Мура). Каждая клетка может находиться в двух состояниях - живом или мертвом, т. е. пустом. 




На состояние любой клетки оказывают влияние состояние соседних клеток. Во времени эти состояния дискретно в соответствии с некоторыми правилами или ГЕНЕТИЧЕСКИМИ ЗАКОНАМИ КОНВЕЯ, состоящими из 2 пунктов:



1) ВЫЖИВАНИЕ ИЛИ ГИБЕЛЬ. Если живая клетка имеет меньше 2 или более 3 соседей в окрестности из 8 клеток то в следующем поколении она умирает (моделирование реальных условий - недостатка питания или перенаселенности), в противном случае она выживает;
2) РОЖДЕНИЕ. В пустой клетке появляется живая клетка, если у исходной клетки ровно 3 соседа.



Гибель и рождение всех организмов происходит одновременно. Возникающие в игре ситуации очень похожи на реальные процессы, происходящие при зарождении, развитии и гибели живых организмов
Основная идея игры состоит в том, чтобы, начав с какого нибудь простого расположения живых клеток, проследить за эволюцией исходной позиции под действием упоминавшихся ГЕНЕТИЧЕСКИХ ЗАКОНОВ КОНВЕЯ, которые управляют рождением, гибелью и выживанием клеток.



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


Действие игры происходит на плоскости, разделенной на клетки. Каждая клетка окружена 8 такими же клетками (так называемая окрестность Мура) и может находиться в двух состояниях - живом или мертвом (быть пустой). Гибель и рождение всех организмов происходит одновременно. На состояние любой клетки оказывают влияние только состояния соседних с ней клеток. Во времени эти состояния дискретно изменяются в соответствии со следующими правилами (генетическими законами Конвея).

Выживание или гибель. Если живая клетка имеет менее 2 или более 3 соседей в окрестности из 8 клеток, то в следующем поколении она умирает (моделирование реальных условий - недостатка питания или перенаселенности), в противном случае она выживает.

Рождение. В пустой клетке появляется новая живая клетка, если у нее ровно 3 соседа.


Правила


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


Состояние клеток дискретно (обычно 0 и 1, хотя могут быть автоматы и с большим числом состояний).

Соседями является ограниченное число клеток, часто это ближайшие клетки.

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

Клеточный автомат является тактируемой системой, т. е. смена состояний клеток происходит одновременно.

Клеточные автоматы предоставляют большую свободу в выборе структуры и правил развития системы. Это позволяет моделировать на их основе и решать с их помощью самые разнообразные задачи.


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


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


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


В компьютерных реализациях игры чаще всего используют поверхность тора. Каждая клетка на этой поверхности может находиться в двух состояниях: быть живой или быть мёртвой. Клетка имеет восемь соседей. Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:

  1. пустая (мёртвая) клетка ровно с тремя живыми клетками-соседями оживает;

  2. если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседок меньше двух или больше трёх) клетка умирает (от «одиночества» или от «перенаселённости»).


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


Эти простые правила приводят к огромному разнообразию форм, которые могут возникнуть в игре.


Компьютерная реализация


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


Фигуры

Вскоре после опубликования правил игры, было обнаружено несколько интересных шаблонов (вариантов расстановки живых клеток в первом поколении), в частности: r-пентамино и глайдер (glider).


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


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

К настоящему времени более-менее сложилась следующая классификация фигур:

  • Устойчивые фигуры: фигуры, которые остаются неизменными

  • Периодические фигуры: фигуры, у которых состояние повторяется через некоторое число поколений

  • Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с некоторым смещением

  • Ружья: фигуры, у которых состояние повторяется, но дополнительно появляется двигающаяся фигура

  • Паровозы: двигающиеся фигуры, которые оставляют за собой следы в виде устойчивых или периодических фигур

  • Пожиратели: устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами


Райский сад

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


  1. Популяционные исследования.


Можно считать, что теоретические популяционные исследования ведут свою историю с работ Леонардо из Пизы (Фибоначчи; 1202 г.), т.е. имеют 800-летнюю историю, но лишь вторая четверть ХХ века справедливо может быть названа «золотым веком теоретической экологии» в рамках популяционного подхода (The Golden Age.., 1978; Гиляров, 1998). Имеется ряд обзорных работ, наиболее полно описывающих и становление, и теоретические основы популяционной экологии (например, Harper, 1977; Гиляров, 1990, и др.). Популяция, как и любая сложная система, характеризуется динамикой, структурой, взаимодействием компонент и системными (групповыми) свойствами-характеристиками. При этом чаще всего оперируют такими параметрами (Розенберг и др., 1999), как плотность популяции (средняя и экологическая), рождаемость и смертность (максимальная, экологическая и удельная), возрастной состав, виталитет (Злобин, 1989), половая структура, устойчивость (в т.ч. надежность, упругость, живучесть и пр.; см. Розенберг, 1986; Краснощеков, Розенберг, 1992) и др.


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

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


Математические модели динамики биологических популяций — наиболее разработанный раздел математической экологии: многочисленные исследования, проводимые в этой области, обобщены в целом ряде монографий, обзор и соответствующие ссылки на которые можно найти в работах Э. Пилу (Pielou, 1974, 1977), Ю.М. Свирежева и Д.О. Логофета (1978), Г.С. Розенберга (1984), А.Д. Базыкина (1985), Ю.П. Фролова и Г.С. Розенберга (2002), Э.В. Ивантера и А.В. Коросова (2003) и многих других.

Прежде чем перейти к рассмотрению конкретных моделей процессов в популяциях, подчеркнем одно обстоятельство. Численность или общая биомасса популяции всегда конечны, и на динамику этих параметров в той или иной степень всегда оказывают влияние случайные факторы. Таким образом, формально модели динамики популяций должны быть стохастическими и зачастую дискретными (в частности, для описания динамики численности популяции необходимо иметь дело с целочисленными величинами); однако на практике исследователь чаще всего строит детерминированные и непрерывные модели. При этом он предполагает, что количество особей (или биомасса) в популяции в целом или в отдельных ее группах (возрастных, половых и пр.) настолько велико, что отказ от целочисленности не приводит к заметным ошибкам. Поскольку при возрастании численности популяции имеет место сходимость по вероятности этой случайной численности к своей средней величине (Свирежев, Логофет, 1978), то поведение популяции высокой численности (биомассы) удовлетворительно описывается детерминированной динамикой средних величин. Кроме того, целью построения экологической теории в рамках аналитических моделей является объяснение лишь основных механизмов моделируемых явлений и тенденций развития экосистем, что также позволяет описывать их детерминировано, например, в виде систем дифференциальных уравнений. Наконец, выбор того или иного математического аппарата для построения аналитической модели «...во многом зависит от уровня интеллектуального эстетизма» (Налимов, 1971, с. 15), т.е. исследователь, лучше знакомый с дифференциальными уравнениями, будет строить непрерывную и детерминированную модель, а с теорией вероятностей — стохастическую.

Действительно, в самом широком плавне вопрос формализации основных теоретических конструкций современной экологии неизбежно упирается в выбор соответствующего аппарата математического моделирования. Правда, обсуждение роли моделирования в экологических исследованиях (особенно при создании экологической теории) встречает как резкий пессимизм и критицизм (например, Pielou, 1981; Simberloff, 1981), так и преувеличенный оптимизм (Yodzis, 1989). Эта ситуация, фактически, отражает то сложившееся в экологии положение, согласно которому существующая методология математического моделирования за последние 25–30 лет не смогла убедить практиков в постулируемых широких возможностях моделирования, а теоретиков-модельеров во многом привела к потери связи с практиками (современная «математическая экология» — это в большей степени раздел математики, чем экологии; примером могут служить формализация сукцессии и моноклимакса или описание структурной устойчивости фитоценозов марковскими моделями).


Анализ методов моделирования, используемых в экологических исследованиях (см. обзор Розенберг, 1984), позволяет предложить для формализации экологических концепций построение аналитических («концептуальных», «стратегических», «феноменологических») моделей, которые претендуют на выполнение объяснительной функции теории (они понятны, управляемы и позволяют проведение полного анализа). Это исключает использование как эмпирикостатистических и самоорганизующихся регрессионных моделей (получение корреляций и построение регрессий мало что дает для объяснения), так и сложных имитационных моделей (поведение таких моделей не может быть исследовано полностью). Построение аналитической модели — это решение задачи «об упрощении» — «...в будущем теоретик систем должен стать экспертом по упрощению» (Эшби, 1966. С. 177). Желание понять (объяснить) сложные, запутанные системы подразумевает их упрощение посредством абстракции до тех пор, пока их можно будет «охватить одним взглядом». Но на этом пути есть опасность «выплеснуть с водой ребенка» и уйти от реальности в сторону теоретизирования с той или иной степенью приближения к этой реальности.

Подтверждая вышеизложенные положения, В. Гримм (Grimm, 1994. Р. 646) называет модели, связанные с концепцией экологической ниши: поток теоретических работ вызвал и поток экспериментальных исследований. Это позволяет Гримму различать модели «свободного стиля» (англ. free-style models) — модели высокого уровня общности с отсутствием требования контролируемости, и модели, «ориентированные на образец» (англ. pattern-oriented models), — меньшая общность и получение поддающихся проверке прогнозов. Выбор «образца» из реальных экологических систем автоматически ограничивает общность модели и в то же время увеличивает ее прогностическую силу: классические модели В. Вольтерра (1976) «хищник — жертва» и конкуренции — это модели «фристайла», модели системы «зайцы — рыси» (Gilpin, 1973) и конкуренции Trifolium repens и T. fragiferum (Розенберг, 1984, с. 207) — модели «ориентированные на образец».

Реалистичность такого деления подтверждает и высказывание Ю.М. Свирежева (1976, с. 250): «...целью Вольтерра являлось не точное описание какой-либо конкретной ситуации, а исследование общих свойств этих систем».

Системология для построения теории сложных систем использует дедуктивный подход (движение от общего к частному), опирающийся на три основных принципа (Флейшман, 1982; Розенберг, 1984). В соответствии с первым принципом (формирования законов) постулируются осуществимые модели, из которых в виде теорем выводятся законы сложных систем. Второй принцип (рекуррентного объяснения) задает вывод свойств систем данного уровня исходя из постулируемых свойств элементов — систем непосредственно нижестоящего уровня и связей между ними. Третий принцип (минимаксного построения моделей) указывает, что теория должна состоять из простых моделей систем, каждая из которых хотя бы в минимальной (min) степени отражает нарастающий (max) уровень сложности поведения систем. Иными словами, рекомендуется строить простые модели сложных систем, структура и поведение которых оптимальны в некотором смысле.

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

Теория потенциальной эффективности сложных систем представляет собой один из наиболее интересных инструментов моделирования структуры и динамики популяций и последовательно разрабатывается Б.С. Флейшманом (1971, 1982), основополагающие результаты которого и будем использовать при построении законов теоретической экологии на популяционном уровне. Ниже укажем лишь общую форму предельного закона потенциальной эффективности, которая в раз- личных ситуациях будет «нагружаться» разным экологическим содержанием.

Взаимодействие системы А со средой В можно представить как серию обменов некоторого количества расходуемых ресурсов U на некоторое количество потребляемых ресурсов V; Флейшман такой обмен называет U;V-обменом (примером может служить увеличение фитомассы растительного сообщества V при внесении минеральных удобрений U). Таким образом, система А характеризуется параметрами U и V, и ее целью A0 можно считать наиболее выгодный U;V-обмен, т.е. система стремится получить больше, отдавая при этом меньше (для каждого фиксированного U система путем изменения своей структуры и поведения стремится максимизировать V). При стохастическом подходе к моделированию сложных систем (тот факт, что для экологических систем стохастическая составляющая структуры и поведения играет большую и важную роль, сейчас ни у кого не вызывает сомнений) целесообразно говорить о некоторой вероятности PU;V-достижения системой А своей цели A0 .


3. Состояние проблемы

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


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


Следующий этап развития математического моделирования связан с проблемой неинтегрируемости системы трех взаимодействующих тел. Многочисленные попытки свести эту систему к интегрируемой оказались бесплодными и были прекращены Брунсом и Пуанкаре в конце XIX века, доказавшими невозможность подобного преобразования. Открытие целого класса неинтегрируемых систем привело Пуанкаре к созданию качественной теории дифференциальных уравнений (теории динамических систем) для их исследования. Так как для неинтегрируемых систем невозможно получить аналитического решения, то объектом исследования теории динамических систем становятся качественные свойства решений, а не сами решения. Основным понятием новой теории стало понятие фазового пространства. Фазовое пространство состоит из точек, представляющих различные состояния системы, а его преобразования определяются динамикой системы. Фазовое пространство можно разбивать на области в зависимости от того, куда, в конце концов, попадают траектории начинающиеся в них. Множества в фазовом пространстве, «притягивающие» траектории, получили название аттракторов.


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


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


Сегодня в математическом моделировании нелинейных процессов происходит становление новой парадигмы – парадигмы сложности. Ее появление вызвано нарастающей потребностью в создании моделей «сложных» систем – биологических, социальных, экономических, политических, исторических. Эта потребность не была полностью удовлетворена уже имеющимися инструментами моделирования, что повлекло за собой создание широкого междисциплинарного направления исследований, призванного синтезировать подходы нелинейной динамики, теории динамического хаоса и вычислительного эксперимента. Характерными свойствами объектов моделирования в новой парадигме становятся: необратимость эволюции, редкие катастрофические события, высокая гетерогенность и адаптивность взаимодействующих элементов системы. Результаты исследований, проведенных в рамках парадигмы сложности, уже вылились в ряд важных приложений, таких как искусственные нейронные сети в области управления и предсказания, генетические алгоритмы в области оптимизации.


Одно из основных теоретических течений в парадигме сложности – это искусственная жизнь. Исследования в области искусственной жизни являются продолжением пионерских работ по теории самовоспроизводящихся автоматов, игр автоматов и компьютерного моделирования эволюции. С момента своего возникновения, искусственная жизнь тесно связана с синергетикой и нелинейной динамикой, не случайно первый сборник статей в этой области вышел в журнале Phisyca D «Nonlinear Phenomena». И сегодня синергетика, как междисциплинарный подход, и искусственная жизнь, как одно из направлений математического моделирования, широко используют представления о самоорганизации и динамических системах, и имеют общее направление движения. Методы искусственной жизни активно используются в работах по моделированию эволюции когнитивных способностей животных, в областях эволюционной роботики и эволюционных вычислений.


Модели искусственной жизни относятся к классу многоагентных (“multi-agent”, “agent-based”) компьютерных моделей. Принципиальным их отличием от других многоагентных моделей является обязательное наличие эволюции свойств агентов через наследование со случайными мутациями. Таким образом, метод искусственной жизни изначально является стохастическим, и его можно рассматривать, как подмножество методов Монте-Карло.


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


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


4. Искусственная жизнь, как метод моделирования эволюции


Эволюционная теория оказала и продолжает оказывать значительное влияние не только на биологию, но и на другие области науки. Больцман утверждал, что при разработке термодинамики он пытался построить теорию аналогичную дарвиновской, но только в физике. В философской теории познания дарвинизм привел к эволюционной эпистемологии, а в экономике – к эволюционной экономике.


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


Эволюционная теория нашла свое применение и в исследованиях человеческого общества. В современных социальных науках сформировалось целое направление, прошедшее путь от «Агрессии» Лоренца и «Социобиологии» Уилсона до современных теорий коэволюции генов и культуры.


Математизация эволюционной теории началась в области генетики популяций в начале 20-го века. Вопрос, на который должна была ответить теория, можно сформулировать так: Каковы будут изменения в генетическом составе популяции при данной стратегии размножения и заданных постоянных значениях приспособленности для каждого гена?


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


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


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


Основное уравнение эволюционной теории игр – уравнение репликации:

Это уравнение эквивалентно уравнению Лотки-Вольтерры [31,32], которое используется для моделирования экологических взаимодействий. Ни уравнение репликации, ни уравнение Лотки-Вольтерры не требует введения понятия приспособленности. В первом случае эволюция определяется матрицей выигрышей, а во втором – скоростью воспроизведения вида и матрицей его взаимодействий с другими видами. Это наводит на мысль о том, что понятие приспособленности не является необходимым при моделировании эволюционной динамики. Следовательно, исследование модели сводится к анализу возможных путей ее эволюционного движения от одного относительно устойчивого динамического режима к другому [33,34]. Несмотря на это, обычной практикой остается использование понятия приспособленности при рассмотрении любых эволюционных моделей, включая эволюционную теорию игр и уравнение Лотки-Вольтерры.


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


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


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


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


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


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


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


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


Применение искусственной жизни позволяет подвергнуть теоретические эволюционные концепции более жесткому тесту. Так, в исследованиях эволюции кооперации, базирующихся на наиболее распространенном сегодня подходе теории игр, репертуар возможных взаимодействий между агентами очень беден, обычно агент может выбрать одно из двух действий – кооперироваться или не кооперироваться с текущим партнером. Искусственная жизнь позволяет смоделировать эволюцию популяции с гораздо более широкими и естественными возможностями для взаимодействия агентов, что дает гораздо более широкий спектр стратегий поведения агентов. Исследование такой модели кооперации позволило увидеть не только конкуренцию малого количества заранее заданных кооперативных и эгоистических стратегий поведения (единицы стратегий), но сам сценарий возникновения кооперативных стратегий (всего возможно более 101000 различных стратегий) и то, какие из кооперативных стратегий будут отобраны эволюцией.


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


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


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


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


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

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

В игре Конвея Жизнь, рассматривается бесконечная плоская решётка квадратных ячеек-клеток. Время в этой игре дискретно (t=0, 1, 2, ...). Клетка может быть живой или мёртвой.

Изменение её состояния в следующий момент времени t+1 определяется состоянием её соседей в момент времени t (соседей у клетки восемь, четверо имеют с ней общие рёбра, а четверо только вершины). Основная идея состоит в том, чтобы, начав с некоего расположения клеток, проследить за эволюцией исходной позиции под действием «генетических законов» Конуэя, которые управляют рождением, гибелью и выживанием клеток. Конуэй тщательно подбирал свои правила и долго проверял их на «практике», добиваясь, чтобы они по возможности удовлетворяли трём условиям:


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

• В то же время должны существовать такие начальные конфигурации, которые

заведомо обладают способностью беспредельно развиваться.

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


Следствием этих требований явились следующие правила игры «Жизнь»:


1. Выживание. Каждая клетка, имеющая две или три соседние живые клетки, выживает и переходит в следующее поколение.


2. Гибель. Каждая клетка, у которой больше трёх соседей, погибает из-за перенаселённости. Каждая клетка, вокруг которой свободны все соседние клетки

или же занята всего одна клетка, погибает от одиночества.


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


Зададимся вопросами:

Какие основные типы структур (то есть конфигураций,

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


Первая закономерность – свойство локализации – структуры, разделённые двумя «мёртвыми» (пустыми) клетками не влияют друг на друга.

Вторая закономерность – система клеток, которую описывает игра «Жизнь»,

развивается необратимо. В самом деле, конфигурация в момент времени t полностью определяет будущее (состояние в моменты t+1, t+2 и так далее). Но восстановить прошлое системы по её настоящему не удаётся. Картина здесь такая же, как в одномерных отображениях, только прообразов у данной конфигурации может быть бесконечно много. (Докажем это утверждение: воспользуемся свойством локализации и расположим вокруг данной конфигурации множество локализованных одиночных клеток или их пар так, чтобы они не влияли на неё и друг на друга. Понятно, что все они исчезнут на следующем шаге, никоим образом не повлияв на будущее системы).

Здесь мы можем заметить признаки нелинейных диссипативных структур: эти структуры определяли поведение системы при t стремящемся к бесконечности в случае различных начальных данных.

Третья закономерность – как показывают длительные наблюдения за

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

симметрией, обнаруживают тенденцию к переходу в симметричные формы.

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

Условимся классифицировать конфигурации клеток по следующим

параметрам:


• По количеству клеток в комбинации: единичная клетка, дуплет (2 клетки в

комбинации), триплет (3 клетки) и т.д.

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

Теперь рассмотрим типичные структуры, появляющиеся в игре «Жизнь».

Простейшими являются стационарные, то есть не зависящие от времени структуры (сам Конуэй называет их «любителями спокойной жизни»). Их примеры показаны на рисунке 1. С помощью этих стационарных структур можно получить множество других. В самом деле, если мы имеем такую структуру, то конфигурация, полученная поворотом на 90О, также будет стационарной. Конфигурации в нижних рядах показывают, как можно достраивать определённые структуры до любых размеров.

Используя свойство локализации можно строить «большие» стационарные структуры из «малых»-элементарных.






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