GotAI.NET - Форум - Искусственный интеллект

Кто то интересовался статьей Бурцева опубликованной в НАТУРЕ.
Это он мне прислал русский вариант, выставляю.

Эволюция кооперативных стратегий из первых принципов
М.С. Бурцев, П.В. Турчин

Объяснение эволюции кооперативного поведения является одним из величайших вызовов для современной биологи и социологии. Сегодня развитие теорий родственного отбора1-7, взаимности8-10, многоуровневого11-15 и отбора культурных групп16,17 приводит к появлению общих подходов к решению этой проблемы. Обычно, в данной области исследований основным инструментом, используемым для проверки теоретических предсказаний, является теория игр, представленная аналитическими или мультиагентными компьютерными моделями6,7,9,18-24. Теория игр дает четкие результаты, но, как правило, за это приходится платить простой структурой выигрышей и небольшим числом возможных стратегий. В данной работе мы предлагаем компьютерную модель, обладающую гораздо более широким спектром возможных стратегий, что позволяет подвергнуть теорию эволюции кооперации более жесткому тесту. В нашей модели агенты имеют ограниченный набор рецепторов, связанных искусственной нейронной сетью с набором элементарных действий. Поведенческие стратегии агентов не заданны заранее, а возникают в процессе эволюции из элементарных действий. Численные эксперименты с моделью продемонстрировали эволюцию хорошо известных в теории игр стратегий – голубя, ястреба и буржуа, а также позволили обнаружить две новые ранее не исследовавшиеся стратегии – кооперативной атаки и обороны. Наши результаты показывают, что эволюция стратегий кооперации возможна даже при таком минимальном предположении, как возможность восприятия агентом наследуемого внешнего маркера другого агента.
Модель представляет собой двухмерный мир, разбитый на клетки, которые могут быть пустыми или содержать ресурс. Порция ресурса появляется в пустой клетке с заданной вероятностью и исчезает после потребления агентом. Агент характеризуется наборами рецепторов и эффекторов, связанными между собой искусственной нейронной сетью. Каждый эффектор отвечает за определенное действие. Агенты могут совершать следующие действия: ничего не изменять в среде (отдых); извлечь ресурс из клетки среды (питание); произвести потомка (деление); переместиться на одну клетку вперед (движение); повернуться направо или на лево (поворот); атаковать другого агента в клетке (нападение). Все действия приводят к уменьшению уровня внутренней энергии агента. Если внутренняя энергия агента падает ниже нуля, то он погибает. Отдых требует наименьших затрат энергии, а нападение наибольших. Потребление ресурсов из клеток среды увеличивает уровень внутренней энергии агента. Максимально возможное значение внутренней энергии ограничено и одинаково для всех агентов. При размножении родитель передает потомку, помещаемому в ту же клетку, половину своей энергии. При нападении жертва теряет энергию, часть которой передается атакующему агенту (энергетические затраты на действия приведены в разделе Методы).
Сенсорные входы агента позволяют ему воспринимать текущий уровень собственной внутренней энергии, наличие ресурсов и количества агентов в клетках поля зрения (поле зрения состоит из клетки, в которой агент находится в данный момент, и соседних клетках прямо, справа и слева). Каждый агент имеет внешний фенотип, кодируемый вектором, компоненты которого принимают целочисленные значения (маркеры). Маркеры не влияют на поведение агента и служат только как индикаторы фенотипической схожести. Евклидово расстояние между собственными маркерами агента и маркерами другого агента в клетке (потенциального объекта атаки) воспринимается через отдельный сенсорный вход. Поведение агента управляется однослойной нейронной сетью. Наследование потомком весов нейронной сети и маркеров родителя, сопровождается мутациями заданной интенсивности. Детали реализации модели изложены в разделе Методы.
Все вычислительные эксперименты с моделью начинались с начальной популяции агентов, поведение которых не зависело от маркеров (веса, соединяющие сенсорный вход от детектора схожести маркеров, с действиями были приравнены нулю). Таким образом, стратегии использования маркеров в популяции должны были эволюционировать с «чистого листа». Маркеры и стратегии не связаны (за исключением того, что наследуются от предков), и агенты могут терять кооперативное поведение в результате мутации, оставаясь при этом носителем маркеров «группы». Это значит, что структура модели позволяет возникнуть стратегии «халявщика», эксплуатирующего кооперативное поведение других и ничего не дающего взамен.
Число потенциальных поведенческих стратегий в нашей модели астрономически велико (более 101000, см. раздел Методы). Большое число стратегий затрудняет анализ возникающих стратегий, ведь каждая матрица весов связей нейронной сети аналогична «черному ящику». Чтобы сделать результаты понятными, мы тестировали поведение агентов в некотором небольшом множестве ситуаций, выбранных в соответствии с целями исследования. Этот подход позволил классифицировать стратегии по агрессивности и способности дискриминировать агентов по маркерам (см. раздел Методы).
Нами было проведено исследование спектров стратегий, возникающих в процессе эволюции, в полной и упрощенной модели (в последней агенты не имели маркеров). Мы также получили зависимость эволюции стратегий поведения от количества ресурсов в среде (количество изменялось за счет размера порции ресурса при неизменной вероятности ее появления в клетке).
Анализ результатов для модели без маркеров показал, что эволюция приводит к появлению стратегий, соответствующих стратегиям в хорошо известной игре голубей-ястребов-буржуа25. Голуби никогда не атакуют других агентов и пытаются уйти из под атаки, а ястребы охотятся на других агентов. Стратегия буржуа проявляется в модели, как нахождение в одной и той же клетке и атака любого агента, входящего в клетку. В модели без маркеров при количестве ресурсов в среде C1, достаточном для существования осёдлого агента (количество ресурса в порции позволяет выжить до появления следующей порции без перемещения из клетки), доминантной стратегией является буржуа. При меньшем количестве ресурса в среде существование стратегии буржуа невозможно, потому что агенты вынуждены постоянно передвигаться для того, чтобы собрать ресурсы, необходимые для выживания. В этих условиях популяция состоит из голубей и ястребов. Установившаяся плотность популяции растет линейно с увеличением количества ресурсов в среде до значения C1, а затем остается постоянной (рис. 1). Подобная зависимость вызвана тем, что после того, как стратегия буржуа становится доминантной, каждая клетка обычно занята только одним агентом. Даже если ресурсов достаточно для выживания в клетке нескольких агентов, то они нападают друг на друга, пока в живых не останется лишь один.
В полной модели, с агентами, имеющими возможность определять фенотипическую схожесть, возникает три типа кооперативных стратегий. Первая – кооперативная версия голубя. Кооперирующиеся голуби игнорируют не членов своей группы (фенотипическая схожесть низкая), и покидают клетки с членами своей группы (фенотипическая схожесть высокая) во избежание конкуренции за ресурс. Агенты, придерживающиеся второй стратегии, также покидают клетку с членами группы, но при обнаружении в клетке агента, не принадлежащего к группе, атакуют его. Мы назвали эту стратегию «ворон», потому что она напоминает пословицу: «Ворон ворону глаз не выклюет». Третья кооперативная стратегия – оставаться в клетке с членами своей группы и нападать на любого чужака, попадающего в клетку. Агенты, следующие третьей стратегии, имеют маленький размер, так как они вынуждены делить ресурсы одной клетки, однако, их шансы уничтожить чужака велики, благодаря численному перевесу. Эта стратегия похожа на стайную защиту от хищника, демонстрируемую многими видами малых стайных птиц, поэтому мы назвали ее стратегией скворца.

Рис. 1. Зависимость плотности популяции от количества ресурсов в среде. Пунктирная линия – версия модели без маркеров, сплошная – с маркерами. Плотность популяции – среднее число агентов на одну клетку (усредненное по времени), количество ресурса варьировалось путем изменения размера порции ресурса при фиксированной вероятности его появления в клетке.
Появление стратегии скворца значительно изменяет зависимость установившейся плотности популяции от количества ресурсов в среде. При низких значениях ресурса зависимости для обоих вариантов модели (с маркерами и без маркеров) совпадают до С2 = 2С1, а затем плотность популяции для полного варианта модели начинает расти (рис. 1). Если ресурсов в среде недостаточно для выживания двух агентов в одной клетке (С < C2), то стратегия скворца не может распространиться в популяции, и единственное отличие от модели без маркеров заключается в появлении стратегии ворона, замещающей часть ястребов и буржуа. При количестве ресурса большем С2 стратегия скворца получает возможность существования (рис. 2). Однако, появление скворцов не приводит к полному вымиранию воронов, и в популяции наблюдаются устойчивые колебания численности скворцов, воронов и голубей (рис. 3). В результате стратегии сосуществуют в течение длительного времени (рис. 2).
При низком уровне ресурсного обеспечения (С < C1) наблюдается появление другой новой стратегии, которая заключается в уходе из клетки при появлении там другого агента вне зависимости от его маркеров. Эта стратегия отличается от стратегии голубей, так как последние покидают клетку, только попав под атаку. Подобное поведение является полной противоположностью стратегии буржуа и напоминает стратегии, которые должны существовать в равновесии «анти-частной-собственности» (Г. Гинтис персональное сообщение). Необходимо отметить интересную особенность поведения скворцов, демонстрирующую предсказанный ранее эффект «бедного родственника»26. Если внутренняя энергия одного из скворцов в клетке опускается ниже определенного уровня, то этот агент покидает клетку, чтобы почти наверняка погибнуть в борьбе за ресурс с чужаками, а не продолжать истощать, возможно, перенаселенную клетку.

Рис. 2. Зависимость усредненных частот стратегий ворона, кооперирующегося голубя и скворца от количества ресурсов в среде. Вороны – сплошная, кооперирующиеся голуби –пунктир, скворцы – точки. Сумма частот приведенных на рисунке не равна единице, так как не все стратегии приведены (в частности не кооперативные).
Наши результаты имеют важные последствия для теорий эволюции территориальности у животных (и частной собственности у людей). За редким исключением27, теоретики обращают мало внимания на роль, которую кооперация может играть в эволюции территориального поведения. Наше исследование наводит на мысль, что кооперативная оборона территории может радикально изменять эволюцию территориальности в условиях высокой обеспеченности ресурсами (С > C2). Когда ресурсов становится достаточно для выживания двух и более агентов, и слишком много для эффективного использования одним агентом, то при условии дифференциации по фенотипическим признакам отдельные буржуа и вороны частично заменяются скворцами, образуя сложную систему динамических взаимодействий (рис. 3).
В исследованной модели агентам не была предоставлена возможность перемещения в группе, поэтому стратегия кооперативной атаки (стратегия «волка») не появится в эволюции. В будущей работе мы планируем изучить влияние введения действия «следуй за другим агентом» на эволюцию кооперативной охоты в модели. То, что агенты могли наследовать фенотипические признаки только вертикально от родителя к потомку является еще одним ограничением нашей модели. Это означает, что члены одной «группы» в модели являлись родственниками, но одной из крупнейших загадок человеческой ультрасоциальности является возникновение кооперации между неродственными индивидами в процессе эволюции. Возможно, что для решения этой проблемы достаточно введения культурной передачи внешних фенотипических признаков между агентами.

Рис. 3. Динамика численности стратегий ворона, кооперирующегося голубя и скворца для одной из реализаций численного эксперимента. Вороны – пунктир, кооперирующиеся голуби – точки, скворцы – сплошная.
Наша работа показывает, что в рамках искусственной эволюции возможно моделирование не только процесса смены одной поведенческой стратегии другой, но и само их возникновение из очень большого пространства потенциальных стратегий. В нашей модели выбор стратегий для агентов не был ограничен некоторым небольшим множеством заданных стратегий, вместо этого каждый агент имел набор возможных сенсорных входов и набор возможных действий. Отбор связей между воспринимаемой ситуацией и действиями происходил в процессе эволюции. Необходимо отметить, что эволюция в модели привела к возникновению многих стратегий, постулированных предыдущими исследователями. Так в отсутствие фенотипических маркеров в эволюции возникли три стратегии, соответствующие стратегиям голубя, ястреба и буржуа. Это показывает, что наши результаты не противоречат теории игр, а представляют ее дальнейшее развитие. При введении в модель маркеров эволюция привела к предсказуемым изменениям трёх базовых стратегий, а также к возникновению одной новой. Кооперирующиеся голуби избегали конкуренции за ресурс с членами своей группы, тогда как кооперативные ястребы – «вороны» не нападали на фенотипически похожих на них агентов. Новой стратегией оказалась стратегия «скворцов», которые жили группами и кооперативно защищали территорию от вторжений.

Методы

Поведение агентов и эволюция
Поведение каждого агента определяется простой системой управления, в которой каждый выход, связанный с заданным действием, соединен с сенсорным входом от внешней среды или внутреннего состояния агента. Система управления линейна и может рассматриваться, как однослойная искусственная нейронная сеть прямого распространения. Для вычисления значений выходного вектора O входной вектор I умножается на матрицу весов W, значения которой ограничены интервалом [-Wmax;Wmax]:

(1)

В каждый такт времени агент совершает действие, соответствующее выходу с максимальным значением (последовательность выбора агентов из популяции для совершения действий случайна и меняется на каждом такте). Значения входного вектора I определяются присутствием ресурса и других агентов в поле зрения (клетке в которой находится агент и соседних клетках прямо, слева и справа), уровнем внутренней энергии и евклидовым расстоянием между вектором маркеров агента и потенциального партнера для взаимодействия. Полный список входных переменных и их определения приведены в таблице 1. Для каждого запуска модели, начальная популяция состояла из агентов с одинаковыми весами матрицы W. Все веса матрицы имели значение ноль за исключением трех весов, задававших следующую примитивную стратегию: двигаться, если ресурс находится в клетке по направлению прямо; потреблять ресурс, если он находится в клетке рядом; если ресурса нет в обеих клетках, то делиться. Соответствие между выходами системы управления и действиями, а также зависимость изменения внутренней энергии r от совершаемых действий приведены в таблице 2.
Таблица 1. Список входных переменных и их определение
Входная переменная* Значение
I1 константа, k
I2, I3, I4, I5 k – если порция ресурса присутствует в соответствующей клетке поля зрения агента, 0 – в противном случае
I6, I7, I8, I9 cNc, где c константа, Nc – число агентов в соответствующей клетке поля зрения агента
I10 уровень внутренней энергии, r
I11 rmaxr
I12 , где – центроид маркеров всех агентов в клетке

I13 , где mp – вектор маркеров партнера для взаимодействия
*Примечание. I1 – константа, а переменные с I2 по I5 бинарные (k – функциональный аналог единицы значение которого приравнивалось rmax, где rmax – максимально возможное значение внутренней энергии).
Для ускорения численных экспериментов все переменные в программе принимали целочисленные значения. Для всех запусков модели размер мира составлял 900 клеток, Wmax было равно 1000, размерность вектора маркеров – 10, а значения его компонент лежали в интервале [-Wmax;Wmax].
Если агент совершает действие «делиться», то в ту же клетку помещается его потомок. Геном потомка создавался следующим образом – к каждому весу матрицы весов унаследованной от родителя добавлялось случайное значение, равномерно распределенное на интервале [-0.03Wmax;0.03Wmax], а к каждому компоненту наследуемого вектора маркеров случайное значение, равномерно распределенное на интервале [-0.15Wmax;0.15Wmax]. Предварительная версия модели была исследована в работе 29.
Таблица 2. Энергетические затраты агента на совершение действий*
------------------------------------------------------------------
| Выходной вектор | Действие | Изменение внутренней энергии r**
------------------------------------------------------------------
| O0 | Отдых | 0.001rmax
| O1 | Поворот налево | 0.002rmax
| O2 | Поворот направо | 0.002rmax
| O3 | Потребление порции ресурса | +[0.06rmax,0.4rmax]***
| O4 | Движение | 0.004rmax
| O5 | Деление | 0.004rmax****
| O6 | Нападение (на случайно выбранного агента из присутствующих в клетке) | Затраты на нападение равны 0.1 rmax;
------------------------------------------------------------------
прирост энергии хищника +0.2rmax если энергия жертвы rn 0.2rmax и +rn в противном случае;
жертва теряет 0.2 rmax.
* rmax – максимально возможное значение внутренней энергии агента.
** Значения параметров отражают наше предположение, что затраты на движение (перемещение в другую клетку, повороты) выше затрат на отдых, а затраты на нападение значительно выше затрат на передвижение. В таблице уменьшение внутренней энергии агента отмечено знаком минус, а увеличение знаком плюс.
*** Количество потребляемого ресурса зависело от размера порции. Во всех экспериментах вероятность появления ресурса в клетке составляла 0.01, а энергетическая ценность порции изменялась от 0.06rmax до 0.4rmax.
**** На деление агента затрачивается 0.004rmax, затем половина оставшейся энергии передается потомку.

Определение стратегий
Каждый моделируемый агент имел 11 независимых входов из 13 возможных (I1 – константа, и I11 = rmax - I10) и 7 действий. Если мы будем учитывать только по два возможных значения для каждого входа (это дает нижнюю границу оценки), то общее число возможных стратегий может быть оценено как , что приблизительно равно 101730. Для того чтобы уменьшить слишком большое пространство стратегий, мы рассматриваем только 6 ситуаций, в которых агент, имеющий одно из трех возможных значений внутренней энергии (0.02rmax, 0.5rmax и 0.98rmax), находится в одной клетке с членом группы или чужаком. Действия «отдыхать», «потреблять ресурс» и «поворачиваться» объединяются в одну группу, так как они соответствуют отсутствию непосредственного взаимодействия между агентами. В результате пространство стратегий уменьшается до 46=4096. Частоты стратегий в популяции подсчитывались последовательным тестированием действий каждого агента в каждой из ситуаций.
Наша классификация стратегий, возникавших в процессе моделируемой эволюции, основывалась на подмножестве пространства стратегий описанного в предыдущем параграфе. Агент считался «вороном», если для любого из трёх значений внутренней энергии он нападал на агента, не принадлежащего группе, и покидал клетку с членом группы. «Скворец» не покидал клетку в присутствии члена группы и нападал на не принадлежащего к группе агента при значении внутренней энергии r -> 0.5rmax.

Благодарности
Мы благодарим П.Тэйлора, Х.Гинтиса и К.Чоффи-Ревилла за замечания при подготовке рукописи. Работа поддержана РФФИ и NSF.

1. Hamilton, W. D. The genetical evolution of social behaviour. I and II. J. Theor. Biol. 7, 1–52 (1964).
2. Maynard Smith, J. Kin selection and group selection. Nature 201, 1145–1147 (1964).
3. Michod, R. E. & Abugov, R. Adaptive topography in family-structured models of kin selection. Science 210, 667–669 (1980).
4. Lacy, R. C. & Sherman, P. W. Kin recognition by phenotype matching. Am. Nat. 121, 489–512 (1983).
5. Queller D. C. A general model for kin selection. Evolution 46, 376–380 (1992).
6. Riolo, R. L., Cohen, M. D. & Axelrod, R. Evolution of cooperation without reciprocity. Nature 414, 441–443 (2001).
7. Axelrod, R., Hammond, R. A. & Grafen, A. Altruism via kin-selection strategies that rely on arbitrary tags with which they coevolve. Evolution 58, 1833–1838 (2004).
8. Trivers, R. The evolution of reciprocal altruism. Q. Rev. Biol. 46, 35–57 (1971).
9. Nowak, M. A. & Sigmund, K. Evolution of indirect reciprocity by image scoring. Nature 393, 573–577 (1998).
10. Bowles, S. & Gintis, H. The evolution of strong reciprocity: cooperation in heterogeneous populations. Theor. Popul. Biol. 65, 17–28 (2004).
11. Sober, E. & Wilson, D. S. Unto Others: the Evolution and Psychology of Unselfish Behavior (Harvard Univ. Press, Cambridge, MA, 1998).
12. Wilson, D. S. Altruism and organism: disentangling the themes of multilevel selection theory. Am. Nat. 150 (suppl.), 122–134 (1997).
13. Gintis, H. Strong reciprocity and human sociality. J. Theor. Biol. 206, 169–179 (2000).
14. Bowles, S. in Social Dynamics (eds Durlauf, S. N. & Young, H. P.) 155–190 (MIT Press, Cambridge, MA, 2001).
15. Turchin, P. Historical Dynamics: Why States Rise and Fall (Princeton Univ. Press, Princeton, NJ, 2003).
16. Boyd, R. & Richerson, P. J. Culture and the Evolutionary Process (Univ. Chicago Press, Chicago, IL, 1985).
17. Richerson, P. J. & Boyd, R. in Indoctrinability, Ideology, and Warfare (eds Eibl-Eibesfeldt, I. & Salter, F. K.) 71–95 (Berghahn, New York, 1998).
18. Axelrod, R. & Hamilton, W. D. The evolution of cooperation. Science 211, 1390–1396 (1981).
19. Axelrod, R. The Complexity of Cooperation: Agent-based Models of Competition and Collaboration (Princeton Univ. Press, Princeton, NJ, 1997).
20. Epstein, J. M. & Axtell, R. Growing Artificial Societies: Social Science from the Bottom Up (Brookings Institution Press, Washington DC, 1996).
21. Nowak, M. A. & May, R. M. Evolutionary games and spatial chaos. Nature 359, 826–829 (1992).
22. McNamara, J. M., Barta, Z. & Houston, A. I. Variation in behavior promotes cooperation in the Prisoner’s Dilemma game. Nature 428, 745–748 (2004).
23. Nowak, M., Sasaki, A., Taylor, C. & Fudenberg, D. Emergence of cooperation and evolutionary stability in finite populations. Nature 428, 646–650 (2004).
24. Hauert, C. & Doebeli, M. Spatial structure often inhibits the evolution of cooperation in the snowdrift game. Nature 428, 643–646 (2004).
25. Maynard Smith, J. The theory of games and the evolution of animal conflicts. J. Theor. Biol. 47, 209–222 (1974).
26. Grafen, A. The logic of divisively asymmetric contests: respect for ownership and the desperado effect. Anim. Behav. 35, 462–467 (1987).
27. Matthiopoulos, J., Moss, R. & Lambin, X. The kin facilitation hypothesis for red grouse population cycles: territorial dynamics of the family cluster. Ecol. Model. 147, 291–307 (2002).
28. Maher, C. R. & Lott, D. F. A review of ecological determinants of territoriality within vertebrate species. Am. Midl. Nat. 143, 1–29 (2000).
29. Burtsev, M. S. Tracking the trajectories of evolution. Artif. Life 10, 397–411 (2004).

Форум: Проблемы искусственного интеллекта