автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование новых типов самоорганизации и возникновения поведенческих стратегий

ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ им. М.В. КЕЛДЫША РОССИЙСКОЙ АКАДЕМИИ НАУК

На правах рукописи

БУРЦЕВ Михаил Сергеевич

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

05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена в Институте прикладной математики им. М.В. Келдыша Российской академии наук

Научные руководители: доктор физ.-мат. наук

Редько Владимир Георгиевич доктор физ.-мат. наук, профессор Малинецкий Георгий Геннадьевич Официальные оппоненты: доктор физ.-мат. наук, академик РАН

Бугаев Александр Степанович доктор физ.-мат. наук, профессор Смолянинов Владимир Владимирович

Ведущая организация: Институт системного программирования РАН

Защита диссертации состоится « 0.% » —_2005 г.

на заседании диссертационного совета Д002.024.02 при Институте прикладной математики им. М.В. Келдыша РАН по адресу: Москва, Миусская пл., д. 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им. М.В. Келдыша РАН

Автореферат разослан 2005 г.

Ученый секретарь диссертационного совета к.ф.-м.н.

У«/-

Г.В. Устюгова

I. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Исследования в рамках искусственной жизни являются продолжением пионерских работ по теории самовоспроизводящихся автоматов [1], игр автоматов [2] и компьютерного моделирования эволюции [3]. С момента своего возникновения, искусственная жизнь тесно связана с синергетикой и нелинейной динамикой, не случайно первый сборник статей в этой области вышел в журнале Phisyca D "Nonlinear Phenomena" [4]. И сегодня, синергетика и искусственная жизнь, широко использующая представления о самоорганизации и динамических системах, имеют общее направление движения [5,6]. Методы искусственной жизни активно используются в работах по моделированию эволюции когнитивных способностей животных [7], в областях эволюционной роботики и эволюционных вычислений [8].

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

- кооперироваться или не кооперироваться с текущим партнером. Искусственная жизнь позволяет смоделировать эволюцию популяции с гораздо

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

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

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

1. Построение и исследование эволюционной компьютерной модели возникновения кооперации агентов.

2. Моделирование социальной эволюции в примитивных сообществах охотников-собирателей и ранних земледельцев.

3. Разработка компьютерной модели эволюции целенаправленного поведения.

4. Разработка и формальное описание некоторого класса и конкретной модели искусственной жизни.

5. Разработка методов измерения и визуализации динамики эволюционных компьютерных моделей.

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

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

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

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

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

Предложена и исследована оригинальная модель эволюции целенаправленного поведения основанного на мотивациях

На основе формализма теории автоматов разработан новый способ описания конкретных моделей искусственной жизни и их классов

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

Практическая ценность Полученные результаты используются в Институте прикладной математики им М В Келдыша РАН, Институте оптико-нейронных технологий РАН и Центре цивилизационных и региональных исследований РАН

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

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

Апробация работы Основные результаты работы докладывались на конференциях "Биосфера и человечество" (Обнинск, 2000), 8-й Международной конференции "Математика Компьютер Образование" (Пущино, 2001), 3-й, 4-й и 7-й Научно-технической конференции "Нейроинформати-ка" (Москва, 2001, 2002, 2005), Международной конференций "Искусственные интеллектуальные системы" (IEEE AIS, Геленджик, 2002), 8-ой Национальной конференции по искусственному интеллекту с междуна-

родным участием (Коломна, 2002), 4-й Международной конференции "European conference on Artificial Life" (Дортмунд, 2003), Международной конференции "Математическое моделирование социальной и экономической динамики" (Москва, 2004), 3-ей Международной конференции "Иерархия и власть в истории цивилизаций" (Москва, 2004), на международных школах "Summer University Complex Systems course" (Будапешт, 2001) и "Complexity in Social Sciences" (Баеза, 2003), на семинарах Института проблем передачи информации РАН, Института системного программирования РАН, Института оптико-нейронных технологий РАН, Института нормальной физиологии им. П.К. Анохина РАМН, Института высшей нервной деятельности РАН, Центрального экономико-математического института РАН, Института прикладной математики им. М.В. Келдыша РАН.

Публикации. По результатам выполненной работы имеется 26 публикации (см. список публикаций).

Структура диссертации. Диссертация состоит из введения и четырех глав, изложенных на 120 страницах, содержит 29 рисунков, 14 таблиц и библиографию из 181 наименования.

II. СОДЕРЖАНИЕ РАБОТЫ

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

Приводится краткое изложение содержания диссертации.

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

Модели искусственной жизни концептуально близки к моделям коллективного поведения автоматов, что позволяет позаимствовать стиль описания из теории автоматов [2].

Рассмотрим популяцию $ агентов 2i, эволюционирующую в среде U. Поведение отдельного агента 2С задается следующим образом:

(p(0 = ®(s(0), (1)

f(t) = F( ср(0), (2)

здесь ф - вектор внутренних состояний агента 2С; s - вектор входных переменных; f - выходная переменная. В уравнениях (1) и (2) переменная t имеет смысл времени и принимает целочисленные значения t = 1,2,... Значения входных переменных s определяются текущим состоянием, ок-

ружающей агента среды. Будем считать, что выходная переменная /принимает п дискретных значений /1,/, ■ ■ ■ и называть эти значения действиями. Так если в момент времени I выходная переменная принимает некоторое значение _Д0 ~/к мы будем говорить, что в момент Г агент ЗГ произвел действие/.

Определим зависимость внутреннего состояния <р,({) агента 2С от входных переменных ¡з(/) как взвешенную сумму, тогда выражение (1) принимает вид:

ф(0 = \VsC0, (3)

где W - матрица весов, компоненты которой могут принимать значения из некоторого ограниченного интервала [-^шах^пшх]- Для удобства в работе рассматриваются агенты, у которых число внутренних состояний равно числу возможных действий п, что позволяет определить (2) следующим образом:

ЛО =/ь к = ш^тах^ХО.' = 1,2,...,п. (4)

Последовательное применение (3) и (4) аналогично функционированию простой искусственной нейронной сети.

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

Коэффициент Ат,- имеет отрицательное значение, если действие приводит к уменьшению ресурса агента, и положительное в противном случае.

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

Для обеспечения воспроизводства популяции в репертуаре действий агента имеется действие "делиться"/;. Если агент Жр (родитель) совершает действие то в популяцию добавляется новый агент 2С0 (потомок). Матрица весов потомка формируется на основе матрицы весов родителя следующим образом:

где ^ - случайная величина, имеющая равномерное распределение на интервале Выражение (6) задает мутационный процесс с амплитудой мутаций Будем называть матрицу \¥ - генотипом агента 2Г, отдельный элемент матрицы Щ- - геном. Стратегией поведения агента 2Т или его фенотипом будем называть отображение из пространства входных в пространство выходных переменных (действий), задаваемое (1) и (2).

Взаимодействие между агентами определяется топологией среды и. Основу 11 составляет ограниченное множество дискретных клеток, в которых могут находиться агенты 2Г. Топология [/накладывает ограничения на возможные переходы агентов между клетками. Для того чтобы смоделировать эволюцию популяции на плоскости, в предложенной модели клетки среды были помещены в узлы двумерной прямоугольной сетки, натянутой на тор. Таким образом, за один такт времени агент мог переместиться в одну из четырех соседних клеток среды К

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

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

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

Кооперативное поведение животных хорошо вписывается в эволюционную теорию, если кооперирующиеся особи принадлежат разным видам, и взаимоотношения между ними носят характер симбиоза. Но кооперация также широко распространена и между особями одного вида, несмотря на то, что они занимают одну и ту же экологическую нишу, и, следовательно, конкуренция между ними максимальна. Этот феномен ставит серьезную проблему перед теорией естественного отбора. Решение, объясняющее возможность возникновения кооперации между генетически родственными организмами, было предложено В. Гамильтоном [9] Оно заключается в том, что кооперация возможна, если выполнено условие:

гЬ>с,

где г - мера генетической близости, Ь - выигрыш объекта кооперативного поведения, а с - затраты самого животного.

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

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

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

В предложенной модели популяция $ агентов И помещалась в клеточную среду, в клетках которой с некоторой вероятностью появлялся ресурс, необходимый агентам для совершения действий. Для того чтобы агенты могли отличать родственников, каждому агенту был приписан вектор-маркер т, значения которого наследовались с мутациями от агента-родителя Пр. Компоненты вектора ш принимали целочисленные значения из некоторого интервала {-М^МтсЛ- Вектор s значений входных переменных агента формировался на основе информации о локальном окружении, значении внутреннего ресурса г и евклидовом расстоянии между собственным маркером ш и маркером соседа по клетке. Значения выходной переменной/, определяющей действия агента и соответствующих коэффициентов изменения внутреннего ресурса агента, использовавшиеся при моделировании, приведены в таблице 1.

Эволюционный алгоритм, изложенный в первой главе, был несколько модифицирован. В геном g агента 2Т, содержащий матрицу весов были добавлены два бинарных вектора I и О, кодировавших наличие компонент в векторе входных переменных s и значений выходной переменной / Компоненты векторов I и О подвергались мутациям малой величины при делении агента Ир, таким образом, существовала малая вероятность, что потомок будет иметь набор входных переменных и действий несколько отличный от соответствующего набора родителя. Мутации векторов в модели интерпретировались, как аналог биологических макромутаций. Изменения значений компонент векторов I и О приводили к тому, что при формировании матрицы весов потомка в матрицу родителя добавлялись или удалялись столбцы или строки соответственно.

Таблица 1

действие изменение внутреннего ресурса г*

/о отдыхать А г = -ко

Л поворачиваться налево Аг = -к,

л поворачиваться на право I ЕГ II

л потреблять ресурс Дл = *з

А двигаться на одну клетку вперед Аг = -к4

А делиться Аг = -к5

Л отнять ресурс у соседа Аг = кб, если у соседа достаточно ресурса, Аг = -кв, в противном случае

* при моделировании коэффициенты к, были заданы в соответствии со следующими равен скг — 7к\, к4 = к; = 2кг, кв — ц и е н тк3 являлся параметром в се-

рии экспериментов. При делении (/=/{) после изменения энергии родителя (Аг — половина его ресурса передается потомку.

Компьютерные эксперименты проводились с четырьмя вариантами модели (см. таблицу 2).

Таблица 2

1 У агентов отсутствует входная переменная, связанная со значением родственности, т.е. агенты не могут узнавать родственников. Выходная переменная/не может принимать значение /б, т е агенты не могут нападать друг на друга.

2 У агентов отсутствует входная переменная, связанная со значением родственности, но выходная переменная / может принимать значение /в, т.е. агенты могут нападать друг на друга

3 Агенты могут отличать родственников и нападать друг на друга. Если в матрице весов потомка XV" в результате макромутаций появляются новые веса, то их значение выбирается случайным образом из интервала

4 Агенты могут отличать родственников и нападать друг на друга. Если в матрице весов потомка в результате макромутаций появляются новые веса, то их значение приравнивается нулю. Такая реализация генетического алгоритма приводит к большей летальности макромутаций, т.е. эволюция становится более "консервативной".

В каждом эксперименте начальная популяция состояла из агентов Ж, которые имели одинаковые геномы g{I;O;W}. Геном агента начальной популяции был задан таким образом, что агент мог получать информацию, о наличии ресурса в текущей клетке, клетке по направлению "вперед", и совершать только три действия: потреблять ресурс, двигаться вперед и делиться.

С моделью была проведена серия экспериментов. Для каждого из вариантов модели (см. табл. 2), при различных значениях эффективности потребления ресурса кз, производился расчет трех версий, отличавшихся начальным значением генератора случайных чисел, все остальные параметры были зафиксированы. В каждом эксперименте эволюция длилась 5-107 тактов, что значительно больше характерного времени перехода модели в стационарный режим с постоянной численностью популяции или в динамический режим с регулярными колебаниями численности.

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

потребления ресурса к

Для первого варианта модели (см. табл. 2), в котором агенты не могут отнимать ресурс друг у друга, точки ложатся на прямую. Это значит, что максимальная численность популяции растет прямо пропорционально эффективности потребления ресурса Л^1 = №тах х кз- Типичная динамика численности популяции для первого варианта модели приведена на рис. 2а.

Зависимость полученная в экспериментах с вариантом модели,

в котором агенты могут нападать друг на друга, но не могут отличать родственников (вариант 2 из табл. 2), распадается на два участка (рис. 1). Для тех значений к л', для которых максимальная численность популяции мень-

ше числа клеток в среде Ыс (Ыс = 900 во всех экспериментах) ЫвтаЛкз) ^ Не, т.е. одна клетка не способна "прокормить" одного агента, численность поп у ]№2(кз)=№та1(кз) = №1(кз)-я значений кг, для которых выполняется условие Л'яиаХ^з) > Ас, численность популяции Л^2 (¿з) = Ыс. Пример динамики численности популяции для последнего случая {Ы$таЖкз) -> приведен на рис. 26. Независимость установившейся численности Ы$2 от кг для Л^тохС^з) >Л'с вызвана тем, что в популяции доминирует стратегия поведения, в соответствии с которой два агента, находящиеся в одной клетке, нападают друг на друга и продолжают бороться, пока один из них не погибнет.

в 2500

5

В

а

5

>> 2000

V 1000

линия максимальной численности популяции, Л^тот

2Ыс

-УГ

±

X

Кс

........-¡¿-'-Щ.....УХ--0—-О.........О—-

¿3

¡2£з

.Л/д1, борьба невозмож-о на, маркеры отсутствуют

Ы^, борьба возможна, маркеры отсутствуют

Л^3, борьба возможна, маркеры присутствуют

ЛГ/, борьба возможна, маркеры присутствуют, консервативная эволюция

эффективность потребления ресурса, к3

Рис. 1. Зависимость установившегося значения численности популяции Л^' от эффективности потребления ресурса кг для различных вариантов модели (/ = 1,2,3,4)

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

2 2Ыс, совпадает с поведением второго варианта модели = При значениях к3, для которых 2:2Ыс числен-

ность популяции постоянно колеблется. Типичное поведение численности популяции во времени для этого случая приведено на рис. 2в. Кроме того, при увеличении ку, максимальная амплитуда колебаний численности растет (на рис. 1 интервалы колебаний численности для точек Л^3 показаны вертикальными пунктирными линиями). Причины, вызывающие колебания, будут рассмотрены ниже.

Компьютерные эксперименты с четвертым вариантом модели (см. табл. 2) показали, что Ы^(кц) = Л^3(£з) =Л^(Агз) для значений кг удов-

летворяющих у Л^Дз) ^ 2МС, и Л// (кг) = Л^1 (¿з) = (к3) я значений к% удовлетворяющих условию Щ^к}) £ 2Л^. Наиболее интересное поведение динамики численности популяции для этого варианта модели наблюдается при значениях кз, для которых Л^тги(£з) « 2Ые- В этом случае динамика численности популяции сначала соответствует второму варианту модели, а затем "переключается" в режим соответствующий первому варианту модели. Пример такого "переключения" представлен на рис. 2г.

Рис. 2. Динамика численности популяции для различных вариантов модели (см. таблицу 2). Для случаев а), б), г) эффективность потребления ресурса къ = 1000, для случая в) кг = 1250

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

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

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

Таблица 3

гдеа{0."отдыхать,поворачиваться", I "убегать", 2 "нападать"; 3 "делиться"}, г = 1,2,3,4

6000 1 Г„

40003000 -

1000 -

5 мо"

4 5 6

время, такты

МО"

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

Для удобства анализа разобьем всю эволюцию системы (рис. 3) на три периода: 1-ый с 0 по 6,5'106 такт, 2-ой с 6,5 106 по 7,5' 106 такт, 3-ий с 7,5106 по 107 такт времени. В течение первого периода численность популяции примерно равна числу клеток в среде, все агенты в популяции обладают той или иной агрессивной стратегией. Подавляющее большинство агентов следует стратегиям, заключающимся в избегании конкуренции с родственниками за ресурс и нападении на чужаков (стратегии типа "121212" - покинуть клетку, если в ней родственник, и напасть, если чужак). Второй период начинается с появления в популяции новой кооперативной стратегии

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

накопить ресурс больший г^, и, следовательно, при борьбе чужака с несколькими родственниками, вероятность выживания одного из родственников будет выше вероятности выживания чужака. Таким образом, если в первом периоде родственники кооперировались за счет избегания конкуренции за ресурс, то теперь они начинают кооперироваться за счет совместной обороны. Для совместной обороны выгодно иметь как можно больше родственников, что приводит к появлению и распространению быстро делящихся агентов (стратегии "123233" и "123333"), так как при делении половина ресурса родителя передается потомку, то средний по популяции ресурс быстро падает (см. врезку на рис. 3). В популяции начинают доминировать стратегии, когда агент не нападает на чужака, а пытается от него убежать (например, "113133"), при этом за счет высокой скорости деления ресурс таких агентов низок и нападение на них не выгодно Все это

приводит к вымиранию агентов с агрессивными стратегиями к концу второго периода.

В начале третьего периода численность популяции быстро достигает максимального для данного &з значения Л^та;с(£з). В третьем периоде агенты с агрессивными стратегиями отсутствуют, при этом в популяции присутствуют, как агенты с родственными стратегиями (например, "001033"), так и агенты, не отличающие родственников ("000033").

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

Наличие в модели возможности изменения поведения в зависимости от значения маркера партнера позволяет ввести пару новых стратегий1. В одну из них попадают агенты, избегающие конкуренции за ресурс с родственниками (малое расстояние между маркерами) и нападающие на чужаков. Примером такой стратегии может служить стратегия, закодированная в соответствии с таблицей 3 как «121212». В соответствии с поговоркой: «Ворон ворону глаз не выклюет», будем называть эту стратегию стратеги-

1 Названия стратегий предложены П.В. Турчиным.

ей «ворона». В природе у многих малых стайных птиц, например у скворцов, наблюдается кооперативная защита от хищника. Если провести аналогию с коллективной защитой в модели, то можно назвать агентов, придерживающихся подобной стратегии - «скворцами». Определения стратегий для исследуемой модели приведено в таблице 4.

Таблица 4

Название стратегии Определение

Голубь Отсутствие действия а2 ("нападать") для всех ситуаций приведенных в таблице 3.

Ястреб Агент не различает родственников и среди его действий присутствует аг ("нападать").

Буржуа Ни в одной из ситуаций агент не покидает клетки. Если в клетке появляется другой агент, то на него производится нападение.

Ворон Ни в одной из ситуаций агент не нападает на родственника, и хотя бы в одной ситуации нападает на не родственника.

Скворец При значении внутреннего ресурса г > 0,5гтах агент не покидает клетку с родственником (действия а0 «отдыхать» или аз «делиться»), и нападает на не родственника.

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

При низких значениях эффективности потребления ресурса ку < к$~ (см. рис. 1) ресурса, появляющегося в одной клетке, недостаточно для выживания одного агента, поэтому агенты вынуждены постоянно перемещаться в пространстве. Постоянное движение агентов приводит к тому, что конкуренция за ресурс между родственниками отсутствует, а, следовательно, отсутствует и вызываемое ей давление отбора. Но если агенты могут нападать друг на друга, то присутствует родственный отбор в сторону не нападения на родственников. Поэтому при кз<к}С в популяции частота агентов, способных дифференцировать свое поведение в отношении родственников, растет вместе с частотой агрессивных агентов (см. рис. 4а). Анализ стратегий показывает, что основная часть агрессивных агентов в этом интервале значений к$ являются воронами (см. рис. 46).

Когда одна клетка способна «прокормить» одного агента, но не двух, т.е. отдельный агент имеет тем большую вероятность вы-

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

одинаковыми шансами на выживание в поединке, то в популяции устанавливается «баланс сил» - доминирующей стратегией является стратегия буржуа. При этом в популяции присутствуют, как агенты, не различающие родственников, так и вороны. В модели при делении агента энергия распределяется поровну между родителем и потомком, что делает каждого из них неконкурентоспособным в сравнении с агентами из соседних клеток. Следовательно, если один из агентов после деления покидает клетку, он с большой вероятностью погибает. С другой стороны, если они оба остаются в клетке, то даже в случае ненападения друг на друга один из них погибает от недостатка ресурса (т.к. Аз < 2АзС). Отсюда можно сделать вывод, что д лАзС < Аз < 2АзС) р в сторону родственной кооперации будет слабее, чем для Аз < А3С, Ио при этом он все равно будет достаточно сильно действовать на популяцию. Результаты моделирования свидетельствуют в пользу этого предположения. На рис. 4а видно, что в отличие от первого интервала Аз < А3С, на котором численность различающих родственников агентов следует за численностью агрессивных агентов (т.е. практически все они вороны), на втором интервале АзС <Аз <2к}С наблюдается сильный разброс значений частоты родственных агентов от эксперимента к эксперименту (см. также точки для стратегии ворона на рис. 46).

эффективность потребления ресурса, к} эффективность потребления ресурса, к3

Рис. 4. Значения усредненной частоты агрессивных2 (кружки) и различающих родственников3 (треугольники) агентов в популяции (а) и значения усредненной частоты стратегий голубей (крестики), воронов (кружки) и скворцов (треугольники) (б) для различных значений эффективности потребления ресурса Аз- Частоты усреднялись по времени за период пребывания популяции в установившемся режиме. Линии проведены через средние значения.

2 Агрессивными считались агенты, которые совершали действие аг ("нападать") хотя бы в одной из ситуаций из таблицы 3.

3 Считалось, что агент отличает родственников, если хотя бы в одной из ситуаций из таблицы 3 действие в отношении родственника отличалось от действия в отношении не родственника.

При к-} > 2к$~ на эволюцию в популяции влияет несколько разнонаправленных факторов. За счет возможности кооперативной обороны скворцов, равновесие с высокой средней внутренней энергией по популяции, обычное для к$С <к^< 2кз~, становится неустойчивым. Наличие скворцов создает отбор в сторону понижения энергии агента, такое понижение происходит за счет появления стратегий со все большей скоростью размножения. При этом если средний внутренний ресурс для агентов некоторой стратегии опускается ниже величины нападение на агентов этой стратегии становится не выгодно, так как в соответствии с определением взаимодействия между хищником и жертвой (см. таблицу 1), изменение ресурса хищника в этой ситуации становится отрицательным. Это делает возможным существование в популяции значительной доли голубей (рис. 46). С другой стороны, конкуренция между голубями действует, как фактор отбора в сторону увеличения внутреннего ресурса, т.к. агент, имеющий больший запас энергии, имеет большее время на поиск ресурса. Все эти факторы приводят к сложной коэволюции стратегий голубей, воронов и скворцов. Высокая конкуренция как внутри, так и между стратегиями ведет к отбору кооперирующихся агентов. Результаты экспериментов показывают, что доля кооперирующихся агентов высока для всех реализаций (рис. 4а). При этом в отличие от первого интервала значений эффективности потребления ресурса кз < при к$ > практически все голуби различают родственников (разность значений для агрессивных и кооперирующихся агентов на рис. 4а примерно равна численности голубей на рис. 46).

Детальное исследование динамики стратегий для высоких значений потребления ресурса представляет отдельный интерес и может выступать в качестве предмета дальнейших исследований.

Третья глава посвящена моделированию социальной эволюции в примитивных сообществах охотников-собирателей и ранних земледельцев.

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

Будем считать, что агенту из модели, изложенной в предыдущей главе, будет соответствовать община охотников собирателей или ранних земле-

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

Для оценки адекватности описания моделью реальных сообществ использовались две характеристики:

1. Частота в популяции агрессивных агентов. Агрессивными будем называть таких агентов, которые совершают действие аг («нападать») хотя бы в одной из ситуаций, приведенных в таблице 3. Эта величина отражает количество агентов потенциально готовых совершать агрессивные действия.

2. Частота совершения действия /ц («отнять ресурс у соседа»). Дает оценку количества совершаемых агрессивных действий в популяции.

Зависимость этих характеристик от величины ресурсной базы приведены на рисунках 5а и 56 соответственно. Эти зависимости демонстрируют, что поведение модели четко различается в трех интервалах:

1 к}< кзС — скудя ресурсная база;

2 кзС < ¿з < 2&зС[овлетворительная ресурсная база;

3. к% > 2£зС —жарошая ресурсная база.

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

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

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

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

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

ческих обществах. Результаты моделирования находятся в соответствии с этой гипотезой в условиях скудной и хорошей ресурсной обеспеченности, но при промежуточных значениях параметра кг модель обладает «аномальным» поведением. Таким образом, результаты моделирования «предсказывают», что, несмотря на низкий уровень межобщинной агрессии при удовлетворительной ресурсной базе, агенты должны обладать развитыми возможностями совершения агрессивных действий. Оказывается, что это действительно имеет место у охотников собирателей Калахари. Охотники племени !кунг всегда носят с собой отравленные стрелы, убить человека при помощи которых для охотника не представляет особого труда. Более того, существуют нормы, оправдывающие убийство посягнувшего на чужую собственность (улей с медом) [11]. Предсказание модели, подтверждается и наблюдениями аборигенов западной пустыни Австралии, которые живут в экологических условиях аналогичных условиям ! кунг, и также демонстрируют низкий уровень агрессии. При этом у аборигенов присутствует институализация агрессии, проявляющаяся в виде создания отрядов тайных мстителей и ритуальных поединков [11].

эффективность потребления ресурса, кз эффективность потребления ресурса, кз

Рис. 5. Значения усредненной частоты агрессивных агентов (а) и действия /в (б) в популяции для различных значений эффективности потребления ресурса &з (частота усреднялась по времени за период пребывания популяции в установившемся режиме, линии проведена через средние значения)

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

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

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

служит рост плотности населения. Следовательно, для реальных сообществ высокий уровень межобщинной агрессии должен положительно коррелировать с плотностью населения. Исходя из похожей посылки, Тур-чин и Коротаев предложили модель внутренней конфликтности для обществ, у которых отсутствует государственность [12]. Эта модель предсказывает наличие слабо отрицательной корреляции агрессии с плотностью населения. Расчет рассматриваемой корреляции для представленной в работе модели дает значения лежащие в интервале (-0.3;-0 6).

Для того чтобы протестировать представленные модели посмотрим, как плотность популяции коррелирует с частотой конфликтов для примитивных обществ. Расчет корреляции между переменной отражающей частоту межобщинных конфликтов и плотностью населения для обществ, представленных в этнографической базе данных [13], дает результат г = -0,489 (р = 0,046), что согласуется с результатами расчета аналогичной корреляции полученными в работе [14]. Очевидно, что по результатам расчета корреляции предложенная в диссертационной работе модель является наиболее приемлемой.

Как показывают этнографические исследования, на межобщинный уровень агрессии влияет не только объем ресурсов, но и предсказуемость их доступности. Для догосударственных обществ корреляция между частотами стихийных бедствий (или неурожаев) и вооруженных столкновений составляет г = 0,631 (р = 0,046) [15]. Следовательно, увеличение вероятности появления ресурса в модели должно приводить к уменьшению показателей характеризующих агрессивность. Эксперименты с модифицированной моделью (вероятность увеличена в 10 раз) показывают, что агрессивность в модели падает в соответствии с наблюдаемой зависимостью, так при эффективности потребления ресурса кг = 1500 обе характеристики агрессивности (см. выше) уменьшаются примерно в 3 раза.

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

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

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

показано, что в процессе исследованных эволюционных процессов возникает естественная иерархическая структура целей и подцелей.

Модели, предложенные в главе, являются отправной точкой в программе по построению серии моделей когнитивной эволюции [7].

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

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

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

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

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

ПО ТЕМЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ СЛЕДУЮЩИЕ РАБОТЫ:

1. Burtsev M.S. Tracking the Trajectories of Evolution // Artificial Life 10(4), 2004. стр. 397-411.

2. Бурцев М.С., Гусарев Р.В., Редько ВТ. Исследование механизмов целенаправленного адаптивного управления // Известия Академии Наук. Теория и системы управления, т. 6. 2002. стр. 55-62.

3. Бурцев М.С., Гусарев Р.В., Редько ВТ. Модель эволюционного возникновения целенаправленного адаптивного поведения 1. Случай двух потребностей // Препринт ИПМ РАН № 43. М., 2000. 24 стр.

4. Бурцев М.С. Модель эволюционного возникновения целенаправленного адаптивного поведения. 2. Исследование развития иерархии целей // Препринт ИПМ РАН № 69. М, 2002. 15 стр.

5. Burtsev M.S. Measuring the Dynamics of Artificial Evolution // Lecture Notes in Computer Science, 2801 / 2003. Advances in Artificial Life. 2003. стр. 580-587.

6. Burtsev M.S., Red'ko V.G., Gusarev R.V. Model of Evolutionary Emergence of Purposeful Adaptive Behavior. The Role of Motivation // Advances in Artificial Life: 6th European Conference, ECAL 2001, Prague, Czech Republic, Proceedings. Springer-Verlag Heidelberg. 2001.

7. Red'ko V.G., Prokhorov D.V., Burtsev M.S. Theory of Functional Systems, Adaptive Critics and Neural Networks // Proceedings of IJCNN 2004. стр.1787-1792.

8. Burtsev M.S. Artificial Life Meets Anthropology: A Case of Aggression in Primitive Societies // Proceedings of ECAL 2005.

9. Редъко ВТ., Бурцев M.C., Гусарев Р.В. Проблема моделирования эволюционного происхождения интеллекта // Сб. труд. конф. "Биосфера и человечество". Обнинск, МРНЦ РАН. 2000. стр. 123-129.

Ю.Бурцев М.С., Гусарев Р.В., Редъко ВТ. Эволюционное возникновение целенаправленного поведения в модели искуственно жизни // Математика. Компьютер. Образование. Вып.8/ Тезисы. Пущино, 2001.

11.Бурцев М.С., Гусарев Р.В., Редъко ВТ. Нейросетевая модель эволюционного возникновения целенаправленного адаптивного поведения // Ш Всероссийская научно-техническая конференция "Нейроинформатика-2001". М., МИФИ. 2001. стр. 153-160.

12.Бурцев М.С. Формирование иерархии целей в модели искусственной эволюции // IV Всероссийская научно-техническая конференция "Ней, роинформатика-2002". М, МИФИ. 2002.

13.Бурцев М.С. Эволюционно-кибернетический подход к моделированию адаптивного поведения // 8-ая национальная конференция по искусственному интеллекту с международным участием. М., Физматлит. 2002. стр. 790-798.

ЫАиохин КВ., Бурцев М.С, Зарайская И.Ю., Лукашев А.О., Редъко ВТ. Проект "Мозг Анимата": разработка модели адаптивного поведения на основе теории функциональных систем // 8-ая национальная конференция по искусственному интеллекту с международным участием. М., Физматлит. 2002. стр. 781-789.

15.Бурцев М.С, Редъко ВТ. Влияние агрессии на эволюцию в многоагент-ной системе // Сб. трудов 9-ой Международной конференции "Проблемы управления безопасностью сложных систем". М., ИПУ. 2002.

16.Бурцев М.С Исследование эволюции адаптивного поведения в модели искусственной жизни // Труды Международных конференций "Искусственные интеллектуальные системы" (IEEE AIS'02) и "Интеллектуальные САПР" (CAD-2002). М., Физматлит. 2002. стр. 514-520.

17.Редъко ВТ., Крыжановский М.В., Бурцев М.С, Анохин КВ. Теория функциональных систем как концептуальная основа исследований ин-

теллектуального адаптивного поведения // Интеллектуальные и многопроцессорные системы - 2003. Таганрог, Издательство ТРТУ, 2003. Т.1. стр. 60-63.

^.Бурцев М.С Что такое Искусственная жизнь? // Труды XLVI научной конференции МФТИ "Современные проблемы фундаментальных и прикладных наук". Часть I. Радиотехника и кибернетика. Москва -Долгопрудный, МФТИ. 2003. стр. 17-19.

19Мосолов О.П., Редъко В.Г., Бурцев М.С, Мишин Н.А. Модель эволюционирующей многоагентной Интернет-системы // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник трудов П-го Международного научно-практического семинара. М., Физматлит. 2003. стр. 217-221.

ЮМосалов О.П., Бурцев М.С, Мишин Н.А., Редько В.Г. Модель много-агентной Интернет-системы, предназначенной для предсказания временных рядов. // V Всероссийская научно-техническая конференция "Нейроинформатика-2003". М, МИФИ. 2003. стр. 177-183.

2\.Редько В.Г., Мосолов 0.11., Мишин НА., Бурцев М.С. Многоагентные Интернет-системы - исследование процессов обучения и самоорганизации // Сб. трудов Первой Всероссийской научной конференции «Методы и средства обработки информации». М., МГУ. 2003. стр. 280-285.

ll.Burtsev M.S. Evolution of strategies in the Artificial Life model: an attempt of historical interpretation // тезисы Международной конференции "Математическое моделирование социальной и экономической динамики". М.:МГСУ,2004.

23 .Burtsev M.S. Does evolution of kinship organization lead to pacification? // тезисы 3-ей Международной конференции "Иерархия и власть в истории цивилизаций" М.: Иаф РАН, 2004.

24.Бурцев М.С Классическая и эволюционная причинность в моделях обучения // 9-ая национальная конференция по искусственному интеллекту с международным участием. Труды конференции. М., Физмат-лит. 2004.

25.Бурцев М.С. Эволюция кооперации в многоагентной системе // VII Всероссийская научно-техническая конференция "Нейроинформатика-2005". М., МИФИ. 2005.

26.Бурцев М.С. Метафизика Дарвина против метафизики Ньютона: два подхода к причинности в обучении // Всероссийская междисциплинарная конференция «Философия искусственного интеллекта». М., МИ-ЭМ. 2005.

СписокЛИТЕРАТУРЫ:

1. Нейман Дж. Теория самовоспроизводящихся автоматов. - М.: Мир, 1971.

2. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. -М.: Наука, 1969.

3. Кулагина О.С, Ляпунов А. А. К вопросу о моделировании эволюционного процесса// сб. "Проблемы кибернетики", вып. 16. М.: Наука, 1966.

4. Evolution, Games and Learning: Models for Adaptation in Machines and Nature // Physica D 22D (1-3), 1986.

5. Новое в синергетике. Взгляд в третье тысячелетие. Сборник статей под ред. Г.Г.Малинецкого, С.П.Курдюмова. - М.: Наука, 2002.

6. Куракин П.В., Малинецкий Г.Г. На пороге "субъективной" синергетики (синергетика II) // Синергетика. Труды семинара. Т.З, М., изд-во МГУ, 2000. С.242-250

7. Редъко ВТ. Эволюционная кибернетика. - М.: Наука, 2001.

8. Holland J.H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. -Cambridge, Massachusetts: MIT Press, 1992.

9. Hamilton W.D. The evolution of altruistic behavior // Am. Nat. 97, 1963. C. 354-356.

10Maynard Smith J. Evolution and the Theory of Games. Cambridge: Cambridge University Press, 1982.

11.Казанков А.А. Агрессия в архаических обществах. - М .: Иаф РАН, 2002.

Yl.Turchin P., Korotayev A. Population Dynamics and Internal Warfare: a Reconsideration // American Anthropologist (в печати).

13.Standard Cross-Cultural Sample Variables (Edited by William T. Divale, Daria Khaltourina and Andrey Korotayev) // World Cultures 13, 2002. (файлы STDS01-88.SAV)

\A.Nolan P.D. Toward an Ecological-Evolutionary Theory of the Incidence of Warfare in Preindustrial Societies // Sociological Theory V.21, N1, p.18-30, 2003.

15.Ember C.R., Ember M. Resource Unpredictability, Mistrust, and War: A Cross-Cultural Study // Journal of Conflict Resolution V.36, p.242-262, 1992.

Заказ № 982 Подписано в печать 26 05 05 Тираж 250 экз Уел п л 0,8 ООО "Цифровичок", тел (095) 797-75-76

/ ^»W..*»*,, -

I ¿*5лвот«ад S 11

содержание.

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

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

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

Задачи, решаемые в диссертационной работе.

Структура диссертации.

глава 1. моделирование эволюции.

1.1. Основные подходы к моделированию эволюции.

1.1.1. Классическая популяционная генетика.

1.1.2. Динамика популяций.

1.1.3. Модели молекулярной эволюции.

1.1.4. Эволюционная теория игр.

1.1.5. Макроэволюционные модели.

1.1.6. Искусственная жизнь.

1.2. Формализация некоторой модели искусственной жизни.

1.3. Методы анализа эволюционных многоагентных моделей.

глава 2. модель кооперации.

2.1 Теории и модели эволюции кооперативного поведения.

2.2 Моделирование родственного отбора при помощи искусственной жизни.

глава 3. кооперация у охотников-собирателей и ранних земледельцев. проверка модели.

3.1 Теории социальной эволюции.

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

ГЛАВА 4. МОДЕЛЬ ЭВОЛЮЦИИ АДАПТИВНОГО ПОВЕДЕНИЯ, ОСНОВАННОГО НА МОТИВАЦИЯХ.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ.

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

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

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

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

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

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

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

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

Одно из основных теоретических течений в парадигме сложности — это искусственная жизнь. Исследования в области искусственной жизни являются продолжением пионерских работ по теории самовоспроизводящихся автоматов [4], игр автоматов [5] и компьютерного моделирования эволюции [6]. С момента своего возникновения, искусственная жизнь тесно связана с синергетикой и нелинейной динамикой, не случайно первый сборник статей в этой области вышел в журнале PhisycaD «Nonlinear Phenomena» [7]. И сегодня синергетика, как междисциплинарный подход, и искусственная жизнь, как одно из направлений математического моделирования, широко используют представления о самоорганизации и динамических системах, и имеют общее направление движения [8,9]. Методы искусственной жизни активно используются в работах по моделированию эволюции когнитивных способностей животных [10], в областях эволюционной роботики и эволюционных вычислений [11].

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

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

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

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

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

Классическая теория игр [16,17], ориентированная на поиск статической оптимальной стратегии, сначала была применена в теоретической биологии для моделирования эволюции в популяции [18-20], а затем полученные результаты были использованы и для развития самой теории игр, но уже в направлении исследования динамики стратегий. Эта ветвь теории игр называется эволюционная теория игр [21] (см. раздел 1.1.4, стр.23) и посвящена динамической устойчивостью стратегий.

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

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

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

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

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

Основное уравнение эволюционной теории игр - уравнение репликации'. где х1 - частота /-ой стратегии, а,у - выигрыш /-ой стратегии при взаимодействии су'-ой стратегией (подробнее про уравнение репликации см. стр. 23). Это уравнение эквивалентно уравнению Лотки-Вольтерры [31,32] (подробнее про уравнение Лотки-Вольтерры см. раздел 1.1.2, стр.21), которое используется для моделирования экологических взаимодействий. Ни уравнение репликации, ни уравнение Лотки-Вольтерры не требует введения понятия приспособленности. В первом случае эволюция определяется матрицей выигрышей, а во втором - скоростью воспроизведения вида и матрицей его взаимодействий с другими видами. Это наводит на мысль о том, что понятие приспособленности не является необходимым при моделировании эволюционной динамики. Следовательно, исследование модели сводится к анализу возможных путей ее эволюционного движения от одного относительно устойчивого динамического режима к другому [33,34]. Несмотря на это, обычной практикой остается использование понятия приспособленности при рассмотрении любых эволюционных моделей, включая эволюционную теорию игр и уравнение Лотки-Вольтерры [35].

В развитии современной эволюционной теории можно проследить переход от вопросов, связанных с эволюцией популяции на заданном ландшафте приспособленности2, к вопросам о том, как зависит ландшафт приспособленности от взаимодействий между различными особями и внешних условий. Это нашло отражение в постепенном включении в эволюционную теорию сначала моделей родственного отбора3 [36-38], группового отбора4 [3840] и неслучайных взаимодействий5 [41-43], а затем пространственной структуры популяции [44,45].

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

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

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

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

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

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

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

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

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

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

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

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

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

• Отсутствие эффективных методов анализа результатов моделирования. И хотя в настоящее время начинают развиваться методы исследования динамики подобных моделей, например, эволюционные статистики [52], но потребность в новых эффективных методах анализа результатов остается высокой.

• Отсутствие желаемого объема опыта по прикладному моделированию и интерпретации результатов вычислительных экспериментов.

Задачи, решаемые в диссертационной работе

Проблемы и подходы, перечисленные в предыдущем разделе, определили следующие задачи данной работы:

1. Построение и исследование эволюционной компьютерной модели возникновения кооперации агентов.

2. Моделирование социальной эволюции в примитивных сообществах охотников-собирателей и ранних земледельцев.

3. Разработка компьютерной модели эволюции целенаправленного поведения.

4. Разработка и формальное описание некоторого класса и конкретной модели искусственной жизни.

5. Разработка методов измерения и визуализации динамики эволюционных компьютерных моделей.

Структура диссертации

Работа состоит из введения и четырех глав.

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

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

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

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

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

Основные результаты диссертации

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

1. Николис Г., Пригожий И. Самоорганизация в неравновесных системах. — М.: Мир, 1979.

2. Хакен Г. Синергетика. М.: Мир, 1980.

3. Пределы предсказуемости / Сб. статей под ред. Ю.А. Кравцова. М.: Цен-трком, 1997.

4. Нейман Дж. Теория самовоспроизводящихся автоматов. М.: Мир, 1971.

5. Цетлин M.JI. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969.

6. Кулагина О.С., Ляпунов А.А. К вопросу о моделировании эволюционного процесса// сб. «Проблемы кибернетики», вып. 16. М.: Наука, 1966.

7. Evolution, Games and Learning: Models for Adaptation in Machines and Nature // Physica D V.22D, N(1-3), 1986.

8. Новое в синергетике. Взгляд в третье тысячелетие. Сборник статей под ред. Г.Г.Малинецкого, С.П.Курдюмова. М.: Наука, 2002.

9. Куракин П.В., Малинецкий Г.Г. На пороге «субъективной» синергетики (синергетика II). Синергетика. Труды семинара. Т.З, С.242-250. М.: изд-во МГУ, 2000.

10. Эволюционная эпистемология и логика социальных наук: Карл Поппер и его критики. Под ред. Садовского В.Н. М.: Эдиториал УРСС, 2000.

11. Эволюция, культура, познание. М., 1996.

12. Nelson R.R., Winter S.G. An Evolutionary Theory of Economic Change. — London: Belknap Press, 1982.

13. The Economy as an Evolving Complex System // Anderson P.W., Arrow K.J., Pines, D. (eds.), Addison-Wesley, Reading, Mass., 1988.16. von Neumann J., Morgenstern O. Theory of Games and Economic Behaviour. Princeton: Princeton University Press, 1947.

14. Nash J. Non-cooperative games // Ann. Math. V.54, p.287-295, 1951.

15. Maynard Smith J. The theory of games and the evolution of animal conflicts // J. Theor. Biol. V.47, p.209-221, 1974.

16. Maynard Smith J. Evolution and the Theory of Games. Cambridge: Cambridge University Press, 1982.

17. Hofbauer J., Sigmund K. Evolutionary Games and Population Dynamics. — Cambridge: Cambridge University Press, 1998.

18. Hofbauer J., Sigmund K. Evolutionary game dynamics // Bull. Am. Math. Soc. V.40, N4, p.479-519, 2003.

19. Lorenz K. On Aggression. London: Methuen, 1966.

20. Wilson E.O. Sociobiology: The New Synthesis. Cambridge, MA: Harvard University Press, 1975.

21. Boyd R., Richerson P.J. Culture and the evolutionary process. Chicago: University of Chicago Press, 1985.

22. Sober E., Wilson D.S. Unto Others: The Evolution and Psychology of Unselfish Behavior. Cambridge, MA: Harvard University Press, 1998.

23. Richerson P. J., Boyd R., Henrich J. The Cultural Evolution of Human Cooperation // The Genetic and Cultural Evolution of Cooperation, P. Hammerstein ed., p.357—388. Cambridge MA: MIT Press, 2003.

24. Fisher R.A. The genetical theory of natural selection. Oxford: Clarendon Press, 1930.

25. Haldane, J. B. S. A mathematical theory of natural and artificial selection. Parts I-V // Transactions of the Cambridge Philosophical Society V.23, 19241927.

26. Wright S. Evolution in Mendelian populations // Genetics V.16, p.97-159, 1931.

27. Ariew A., Lewontin R. C. The Confusions of Fitness // Brit. J. Phil. Sci. V.55, p.347-363, 2004.

28. Lotka A. J. Undamped oscillations derived from the law of mass action // J. Am. Chem. Soc. V.42, p. 1595-1599, 1920.

29. Volterra V. Variozioni e fluttuazioni del numero d'individui in specie animali conviventi // Mem. Accad. Naz. Lincei V.2, p.31-113, 1926.

30. Crutchfield J.P. When Evolution is Revolution: Origins of Innovation // Evolutionary Dynamics: Exploring the Interplay of Selection, Neutrality, Accident, and Function / J. P. Crutchfield and P. Schuster eds. NY: Oxford University Press, 2003.

31. Burtsev M.S. Tracking the Trajectories of evolution // Artificial Life V.10, p.397-411,2004.

32. Page K.M., Nowak M.A. Unifying Evolutionary Dynamics // J. theor. Biol. V.219, p.93-98, 2002.

33. Hamilton W.D. The evolution of altruistic behavior // Am. Nat. V.97. p.354-356, 1963.

34. Hamilton W.D. The genetical evolution of social behavior, I and II // J. Theor. Biol. V.7, p. 1-52, 1964.

35. MaynardSmith J. Kin selection and group selection // Nature V.201, p. 11451147, 1964.

36. Wright S. Tempo and Mode in Evolution: A Critical Review // Ecology V.26, N.4, p.415-419,1945.

37. Wilson D.S. A theory of group selection // Proc. Nat. Acad. Sci. USA. V.72, N1, p.143-146,1975.

38. Trivers R. The evolution of reciprocal altruism // Q. Rev. Biol. V.46, p.35-57, 1971.

39. Nowak M.A. May R. M. Evolutionary games and spatial chaos //Nature V.359, p.826-829, 1992.

40. Brauchli K., KillingbackT., Doebeli M. Evolution of cooperation in spatially structured populations //J. theor. Biol. V.200, p.405-417, 1999.

41. Artificial Life // Langton C.G. ed. MA: The MIT Press, 1995.

42. Adami C. Introduction to Artificial Life. NY: Springer Verlag, 1998.

43. Axtell R. Why agents? On the varied motivations for agent computing in the social sciences // Center for Social and Economic Dynamics, Working Paper N17, 2000.

44. Lansing J.S. "Artificial Societies" and the Social Sciences // Artificial Life V.8, p.279-292,2002.

45. Raven M.J., Bedau M.A. A General Framework for Evolutionary Activity Statistics // Lecture Notes in Computer Science, 2801/2003. Advances in Artificial Life, p.676-685, 2003.

46. Ахромеева T.C., Курдюмов С.П., Малинецкий Г.Г., Самарский А.А. Нестационарные структуры и диффузионный хаос. -М.: Наука, 1992.

47. Эбелинг В., Энгелъ А., Файстель Р. Физика процессов эволюции. — М.: Эдиториал УРСС, 2001.

48. May R. М. Stability and Complexity in Model Ecosystems. Princeton, NJ: Princeton University Press, 2001.

49. Eigen M., Schuster P. Hypercycle-principle of natural self-organization. A. Emergence of hypercycle. //Naturwissenschaften V.64, p.541-565, 1977.

50. Эйген M, Шустер П. Гиперцикл. Принципы самоорганизации макромолекул. -М.: Мир, 1982.

51. Eigen М., Mccaskill J., Schuster P. The molecular quasispecies // Adv. Chem. Phys. У.15, p. 149-263. 1989.

52. Altmeyer S., Fuchslin R.M., McCaskill J.S. Folding Stabilizes the Evolution of Catalysts // Artificial Life V.10, p.23-38, 2004.

53. Sasaki A., Nowak M.A. Mutation landscapes // J. Theor. Biol. V.224, p.241-247, 2003.

54. Nowak M. A., SigmundK. Evolutionary Dynamics of Biological Games // Science V.303, p.793-799, 2004.

55. Hofbauer J. From Nash and Brown to Maynard Smith. Equilibria, Dynamics, and ESS I I Selection V.l, p.81-88,2000.

56. Maynard Smith J., Price G. R. The logic of animal conflicts // Nature V.246, N.15, 1973.

57. Gavrilets S., Arnqvist G., Friberg U. The evolution of female mate choice by sexual conflict // Proceedings of the Royal Society London В V.268, p.531-539, 2001.

58. Kauffman S.A., Johnsen S. Coevolution to the edge of chaos: Coupled fitness landscapes, poised states, and revolutionary avalanches // J. Theor. Biol. V.149, p.467-505, 1991.

59. Kauffman S.A. Origins of Order: Self-Organization and Selection in Evolution. Oxford: Oxford University Press, 1993.

60. Kauffman S.A. At Home in the Universe. Oxford: Oxford University Press, 1993.6S.BakP. How nature works: the science of self-organized criticality. NY: Springer-Verlag, 1996.

61. Newman M.E.J., Palmer R.G. Modelling Extinction. Oxford: Oxford University Press, 2003.

62. Harvey I. Artificial Evolution for Real Problems / In T. Gomi (Ed.), Evolutionary Robotics: From Intelligent Robots to Artificial Life (ER'97), AAI Books, 1997.

63. Sharpe O. J. Towards a Rational Methodology for Using Evolutionary Search Algorithms / Ph. D. Dissertation. University of Sussex, 2000.

64. Barnett L. Explorations in Evolutionary Visualisation / In Bilotta E., et al. (Eds.), ALife VIII Workshops, p.113-118. UNSW, 2002.

65. Layzell P. Visualising Evolutionary Pathways in Real-World Search Spaces / In Bilotta E., et al. (Eds.), ALife VIII Workshops, p. 149-154. UNSW, 2002.

66. Dopazo H., Gordon M.B., Perazzo R., Risau-Gusman S. A Model for the Emergence of Adaptive Subsystems // Bulletin of Mathematical Biology, V.65, p.27-56, 2003.

67. Wright S. The roles of mutation, inbreeding, crossbreeding, and selection in evolution // In Proceedings of the Sixth International Congress on Genetics, pp.355-366, 1932.

68. Bedau MA., Packard N.H. Measurement of evolutionary activity, teleology, and life / In C. G. Langton, C. Taylor, J. D. Farmer, and S. Rasmussen, (Eds.), Proceedings of Artificial Life II, p.431-461. Redwood City, CA: Addison-Wesley, 1992.

69. Bedau M.A., Snyder E., Packard N.H. A classification of long-term evolutionary dynamics / In C. Adami, R. Belew, H. Kitano, and C. Taylor, (Eds.), Proceedings of Artificial Life VI, p.228-237. Cambridge, MA: MIT Press, 1998.

70. Bedau M.A., Brown C.T. Visualizing evolutionary activity of genotypes I I Artificial Life V.5, p. 17-35, 1999.

71. Bedau M.A., Raven M.J. Visualizing Adaptive Evolutionary Activity of Allele Tokens and of Phenotypic Equivalence Classes of Alleles / In Bilotta, E., et al. (Eds.), ALife VIII Workshops, p. 119-130. UNSW, 2002.

72. Channon A.D. Passing the ALife test: Activity statistics classify evolution in Geb as unbounded / In J. Kelemen, P. Sosik (Eds.), Advances in Artificial Life, Proceedings of 6th European Conference, p.417-426. Prague, Czech Republic: Springer, 2001.

73. Pachepsky E., Taylor Т., Jones S. Mutualism promotes diversity and stability in a simple artificial ecosystem I I Artificial Life, N.8, p.5-24, 2002.

74. Малинецкий Г.Г., Потапов А.Б. Современные проблемы нелинейной динамики. М.: УРСС, 2000.

75. Eldredge N. Gould S.J. Punctuated equilibria: an alternative to phyletic gradualism // Models in Paleobiology, p.82-115. San Francisco, 1972.

76. Burtsev M.S. Measuring the Dynamics of Artificial Evolution // Lecture Notes in Computer Science, 2801/2003. Advances in Artificial Life, p.580-587, 2003.

77. Axelrod R., Hamilton W.D. The evolution of cooperation // Science V.211, p.1390-1396, 1981.

78. Wright S. Statistical genetics and evolution // Bulletin of the Amer. Mathematical Society V.48, p.223-246, 1942.

79. Levins R. Extinction / In Some mathematical questions in biology: lectures on mathematics in the life sciences // Amer. Math. Soc. V.2, p.75-108, 1970.

80. Eshel I. On the neighbor effect and the evolution of altruistic traits // Theor. Popul. Biol. V.3, p.258-277, 1972.

81. Boorman S.A., Levitt P.R. Group selection on the boundary of a stable population // Theor. Popul. Biol. V.4, p.85-128, 1973.

82. Levin B.R., Kilmer W.L. Interdemic selection and the evolution of altruism: a computer simulation study //Evolution. V.28, N4, p.527-545, 1974.

83. Gilpin M.E. The theory of group selection in predator prey communities. -Princeton University Press, Princeton N.J. 1975.

84. Wilson D.S. Structured demes and the evolution of group-advantageous traits // Amer. Natur. V.l 11, N977, p.157-185, 1977.

85. Gadgil M. Evolution of social behaviors through interpopulation selection // Proc. Natl. Acad. Sci. USA. V.72, p.l 199-1201, 1975.

86. Charnov E.L., Krebs J.R. The evolution of alarm calls: altruism or manipulation? // Amer. Natur. V.109, p.107-112, 1975.

87. Matessi C., Jayakar S.D. A model for the evolution of altruistic behavior // Genetics. V.47,p.l74, 1973.

88. Matessi C., Jayakar S.D. Conditions for the evolution of altruism under Darwinian selection // Theor. Popul. Biol. V.9, p.360-387, 1976.

89. Cohen D., Eshel I. On the founder effect and the evolution of altruistic traits //Theor. Popul. Biol. V.10, p.276-302, 1976.

90. Taylor P.D., Wilson D.S. A mathematical model for altruism in haystacks // Evolution. V.42, N1, p.193-196, 1988.

91. Tanaka Y. A quantitative genetic model of group selection // Amer. Natur. V.148, N4, p.660-683, 1996.

92. Silva A.T.C., Fontanari J.F. Deterministic group selection model for the evolution of altruism // Eur. Phys. J. B. V.7, p.385-392, 1999.

93. Silva A.T.C., Fontanari J.F. Stochastic group selection model for the evolution of altruism // Physica A. V.268, p.257-268, 1999.

94. Ono S., Misawaz K., Tsujiy K. Effect of Group Selection on the Evolution of Altruistic Behavior // J. theor. Biol. V.220, p.55-66,2003.

95. Cooper B., Wallace C. Group selection and the evolution of altruism // Oxford Economic Papers. V.56, p.307-330,2004.

96. Hauert C., Doebeli M. Spatial structure often inhibits the evolution of cooperation in the snowdrift game // Nature V.428, p.643-646, 2004.

97. Killingback T., Doebeli M., Knowlton N. Variable investment, the continuous prisoner's dilemma, and the origin of cooperation 11 Proc. R. Soc. Lond. B V.266, p. 1723-1728, 1999.

98. Irwin A. J., Taylor P.D. Evolution of altruism in stepping-stone populations with overlapping generations // Theor. Pop. Biol. V.60, p. 315-325, 2001.

99. Doebeli M., Knowlton N. The evolution of interspecific mutualisms // PNAS V.95, p.8676-8680, 1998.

100. Traulsen A., SchusterH.G. Minimal model for tag-based cooperation // Physical Review E. V.68, p.046129, 2003.

101. McNamara J.M., BartaZ., Houston A.I. Variation in behavior promotes cooperation in the Prisoner's Dilemma game //Nature V.428, p.745-748, 2004.

102. McNamara J.M., Gasson C.E., Houston A.I. Incorporating rules for responding into evolutionary games //Nature V.401, p.368-371, 1999.

103. Nowak M.A., SigmundK. Evolution of indirect reciprocity by image scoring //Nature V.393, p.573-577, 1998.

104. Taylor P.D., Day T. Stability in negotiation games and the emergence of cooperation//Proc. R. Soc. Lond. B. V.271, p.669-674, 2004.

105. Riolo R., Cohen M.D., Axelrod R. Evolution of cooperation without reciprocity//Nature V.414, p.441-443, 2001.

106. Cohen M.D., Riolo R L. Axelrod R. The role of social structure in the maintenance of cooperative regimes // Rationality Soc. V.13, p.5-32,2001.

107. Mitteldorf J., Wilson D.S. Population Viscosity and the Evolution of Altruism // J. theor. Biol. V.204, p.481-496, 2000.

108. Peck J.R. Friendship and the evolution of co-operation // J. theor. Biol. V.162, p.195-228, 1993.

109. Pepper J. W. Relatedness in trait group models of social evolution // J. theor. Biol. V.206, p.355-368, 2000.

110. Wade M.J. Soft selection, hard selection, kin selection, and group selection // Am. Nat. V. 125, N1, p.61-73, 1985.

111. Hamilton W.D. Altruism and related phenomena, mainly in social insects // Annual Review of Ecology and systematics V.3, p. 193-232, 1972.

112. Maynard Smith J. Models of evolution // Proc. of the Royal Soc. of London. Series B., V.219, N1216, p.315-325, 1983.

113. Boorman S.A., Levitt P.R. A frequency-dependent natural selection model for the evolution of social cooperation networks // Proc. Nat. Acad. Sci. USA. V.70, N1, p.187-189, 1973.

114. Boyd R., Richer son P.J. Effect of phenotypic variation on kin selection // PNAS V.77, N.12, p.7506-7509, 1980.

115. Charlesworth B. A note on the evolution of altruism in structured demes I I Amer. Natur. V.l 13, N4, p.601-605, 1979.

116. Maynard Smith J. The Evolution of Alarm Calls // Am. Nat. V.99, N904, p.59-63, 1965.

117. Michod R.E., Abugov R. Adaptive topography in family-structured models of kin selection // Science, New Series. V.210, N4470, p.667-669, 1980.

118. Queller D.C. A general model for kin selection // Evolution. V.46, N2, p.376-380, 1992.

119. SlatkinM., Wade M.J. Group selection on a quantitative character // PNAS V.75, N7, p.3531-3534, 1978.

120. Eshel L, Hamilton W.D. Parent-offspring correlation in fitness under fluctuating selection//Proc. R. Soc. Lond. B. V.222, p.1-14, 1984.

121. Axelrod R., Hammond R.A., Graf en A. Altruism via kin-selection strategies that rely on arbitrary tags with which then co-evolve I I Evolution. V.58, p.1833-1838, 2004.

122. Nowak M.A., Sasaki A., Taylor C., Fudenberg D. Emergence of cooperation and evolutionary stability in finite populations // Nature V.428, p.646-650, 2004.

123. Crumley C.L. A Dialectical Critique of Hierarchy / In Patterson, Th.C., and Gailey, Chr. W. (eds.), Power Relations and State Formation, p. 155-169. Washington DC: American Anthropological Association, 1987.

124. Beyond Chiefdoms: Pathways to Complexity in Africa / Mcintosh S.K. (ed.). Cambridge: Cambridge University Press, 1999.

125. Альтернативные пути к цивилизации. Сб. Под ред. H.H. Крадин, А.В.Коротаев, Д.М. Бондаренко, В.А.Лынша. М.: Логос, 2000.

126. Коротаев A.B. Социальная эволюция: факторы, закономерности, тенденции. -М.: Вост. лит., 2003.

127. Ciaessen H.J.M. Was the State Inevitable? / In Grinin, L.E., Carneiro, R.L., Bondarenko, D.M., Kradin, N.N., and Korotayev, A.V. (eds.) The Early State, Its Alternatives and Analogues, p.72-87. Volgograd: Uchitel Publishing House, 2004.

128. Levinson D., Malone M. Toward Explaining Human Culture. New Haven, CT: HRAF Press, 1980.

129. Капица С.П., Курдюмов С.П., Малинецкий Г.Г. Синергетика и прогнозы будущего. — М.: Наука, 1997.

130. Lenski G. Power and Privilege. Chapel Hill: University of North Carolina Press, 1966.

131. Nolan P., Lenski G. Human Societies: An Introduction to Macrosociology, 8th ed.-New York: McGraw-Hill, 1999.

132. Nielsen F. The Ecological-Evolutionary Typology of Human Societies and the Evolution of Social Inequality // Sociological Theory V.22, N2, p.292-314, 2004.

133. Hamilton W.D. Innate social aptitudes of man: An approach from evolutionary genetics / In: Biosocial Anthropology, ed. R. Fox, p. 115-132. New York: Wiley, 1975.

134. Wilson D.S. Humans Groups as Units of Selection // Science V.276, N5320, p.1816-1817, 1997.

135. Richerson P.J., Boyd R. The evolution of human ultrasociality / In: Indoc-trinability, Ideology, and Warfare: Evolutionary Perspectives, ed. I. Eibl-Eibesfeldt and F.K. Salter, p.71-95. New York: Berghahn, 1998.

136. Richerson P.J., Boyd R. Complex societies: The evolutionary origins of a crude superorganism // Hum. Nat.: Inter. Biosoc. Persp. V.10, p.253-289, 1999.

137. Henrich J., Boyd R. Why people punish defectors: Weak conformist transmission can stabilize costly enforcement of norms in cooperative dilemmas // J. Theor. Biol. V.208, p.79-89, 2001.

138. Henrich J. Cultural group selection, revolutionary processes and large-scale cooperation // J. Econ. Behav. Org. V.53, N1, p.3-35, 2004.

139. Cosmides L. The logic of social exchange: has natural selection shaped human reason? Studies with the Wason selection task // Cognition, V.31, p. 187276, 1989.

140. Henrich J., Boyd R., Bowles S., et al. In search of Homo economicus: Behavioral experiments in 15 small-scale societies // Am. Econ. Rev. V.91, p.73— 78,2001.

141. Batson C.D. The Altruism Question: Toward a Social Psychological Answer. Hillsdale, NJ: Erlbaum, 1991.

142. Fehr E., Gachter S. Altruistic punishment in humans // Nature V.415, p.137-140, 2002.

143. Boyd R., Richerson P.J. The evolution of ethnic markers // Cultural Anthropology V.2, p.65-79, 1987.

144. Boyd R., Richerson P.J. The evolution of reciprocity in sizable groups // Journal of Theoretical Biology V.132, p.337-56, 1988.

145. Boyd R., Richerson P.J. The evolution of indirect reciprocity // Social Networks V.ll,p.213-36, 1989.

146. Boyd R., Richerson P.J. Punishment allows the evolution of cooperation (or anything else) in sizable groups // Ethology and Sociobiology V.13, p. 171-95, 1992.

147. Soltis J., Boyd R., Richerson P.J. Can group-functional behaviors evolve by cultural group selection? An empirical test // Current Anthropology V.36, p.437-94, 1995.

148. Ostrom E. A behavioral approach to the rational choice theory of collective action // Am. Pol. Sci. Rev. V.92, p. 1-22, 1998.

149. Oppenheimer S. The Real Eve: Modern Man's Journey Out of Africa. NY.: Carroll & Graf, 2003. (<Оппенгеймер С. Изгнание из эдема. - М.: Эксмо, 2004.)

150. Бутовская M.JI. Эволюция человека и его социальной структуры // Природа №9, 1998.

151. Кабо В. Первобытная доземледельческая община. М.: Наука, 1986

152. Otterbein K.F. Killing of Captured Enemies: A Cross-cultural Study I I Current Anthropology V.44, N3, p.439-443, 2000.

153. Шнирелъман В.А. У истоков войны и мира. Война и мир в ранней истории человечества, т.1. М.: ИЭА, 1994.

154. Pasternak В., Ember C.R. and Ember Е. Sex, Gender, and Kinship: A Cross-Cultural Perspective. Upper Saddle River, NJ: Prentice Hall, 1997.

155. Dyson-Hudson R., Smith E.A. Human territoriality: An Ecological Reassessment // American Anthropologist V.10, p.21-41, 1978.

156. Казанков A.A. Агрессия в архаических обществах. М.: Иаф РАН, 2002.

157. Cashdan Е. Territoriality among Human Foragers: Ecological Models and an Application to Four Bushman Groups // Current Anthropology V.24, N1, p.47-55, 1983.

158. Ember C.R., Ember M. War, Socialization and Interpersonal Violence: A Cross-Cultural Study // The Journal of Conflict Resolution V.38, N4, p.620-646, 1994.

159. Standard Cross-Cultural Sample Variables (Edited by William T. Divale, Daria Khaltourina and Andrey Korotayev) // World Cultures V.13,2002.

160. World Cultures. Journal of Comparative and Cross-Cultural Research // URL: http://eclectic.ss.uci.edu/~drwhite/worldcul/world.htm

161. Murdoch G.P., White D.R. Standard Cross-Cultural Sample // Ethnology V.8, p.329-69, 1969.

162. Nolan P.D. Toward an Ecological-Evolutionary Theory of the Incidence of Warfare in Preindustrial Societies // Sociological Theory V.21, N1, p. 18-30, 2003.

163. Turchin P., Korotayev A. Population Dynamics and Internal Warfare: a Reconsideration // American Anthropologist (в печати).

164. Ember M. Statistical evidence for an ecological explanation of warfare // American Anthropologist V.84, p.645-649, 1982.

165. Ember C.R., Ember M. Resource Unpredictability, Mistrust, and War: A Cross-Cultural Study //Journal of Conflict Resolution V.36, p.242-262, 1992.

166. Shankman P. Culture contact, cultural ecology, and Dani warfare // Man V.26 p.299-321,1991.

167. KangB.W A Reconsideration of Population Pressure and Warfare: A Prehistoric Korean Case // Current Anthropology, V.41, p.873-881, 2000.

168. Lekson S.H. War in the Southwest, War in the World // American Antiquity V.67, p.607-624,2002.

169. Burtsev M.S., Korotaev A.V. An Evolutionary Agent-Based Model of PreState Warfare Patterns: Cross-Cultural Tests // submitted to World Cultures.

170. Bettinger R.L. Why Corn Never Came to California / SFI Workshop on Co-Evolution of Behaviors and Institutions, 2002. (http://discuss.santafe.edu/coevolution/papers)