Лекция 12

В конце 80-х - начале 90-х годов возникли два интересных, тесно связанных между собой направления кибернетических исследований: "Искусственная жизнь" (английское название Artificial Life или ALife) [1,2] и "Адаптивное поведение" (Adaptive Behavior) [3]. В этой лекции мы рассмотрим направление "Искусственная жизнь", следующая лекция будет посвящена направлению "Адаптивное поведение".

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

Сторонники направления "Искусственная жизнь" часто считают, что они исследуют более общие формы жизни, чем те, которые существуют на Земле. Т.е. изучается жизнь, какой она могла бы в принципе быть ("life-as-it-could-be"), а не обязательно та жизнь, какой мы ее знаем ("life-as-we-know-it").

Искусственная жизнь – это синтетическая биология, которая по аналогии с синтетической химией пытается воспроизвести биологическое поведение в различных средах. Это жизнь, созданная человеком, а не природой ("life made by Man rather than by Nature''). Исследования искусственной жизни направлены не только на теоретические исследования свойств жизни, но и (аналогично синтетической химии) на практические приложения, такие как подвижные роботы, медицина, нанотехнология, "жизнь" социальных систем и т.п.

В 60-х годах блестящий кибернетик и математик М.Л.Цетлин предложил и исследовал модели автоматов, способных адаптивно приспосабливаться к окружающей среде. Работы М.Л.Цетлина инициировали целое научное направление, получившее название "коллективное поведение автоматов" [4,5] .

В 60-70-х годах под руководством талантливого кибернетика М.М.Бонгарда была построена весьма нетривиальная модель "Животное", характеризующая адаптивное поведение искусственных организмов, живущих на разбитой на клетки плоскости и обладающих рядом конкурирующих между собой потребностей [6,7].

Исследование динамики жизнеподобных структур в клеточных автоматах (К.Лангтон) [8].

ПолиМир (PolyWorld) Л. Ягера: компьютерная модель искусственных организмов, которые имеют структурированную нейронную сеть, обладают цветовым зрением, могут двигаться, питаться (и увеличивать тем самым свою энергию), могут скрещиваться и бороться друг с другом [9]. При моделировании эволюции в ПолиМире возникал ряд нетривиальных стратегий поведения организмов. Подробнее эта модель описана ниже.

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

Анализ взаимодействия между обучением и эволюцией, выполненный Д.Экли и М. Литтманом [12]. Эта работа продемонстрировала, что "обучение и эволюция вместе более успешны в формировании адаптивной популяции, чем обучение либо эволюция по отдельности". Подробнее эта модель описана ниже.

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

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

Классифицирующие системы Дж.Холланда с сотрудниками [17]. Это модель эволюции когнитивного процесса. Классифицирующая система есть система индуктивного вывода, которая основана на наборе логических правил. Каждое правило имеет следующую форму: "если <условие>, тогда <действие>". Система правил оптимизируется как посредством обучения, так и эволюционным методом. В процессе обучения меняются приоритеты использования правил (т.е. меняются коэффициенты, характеризующие силу правил). При обучении используется так называемый алгоритм "пожарной бригады": при успехе поощеряются не только те правила, которые непосредственно привели к успешному действию, но и те, которые были предшественниками успеха. Поиск новых правил осуществляется эволюционным методом.

Модели искусственной жизни – активно развивающаяся область исследований. Большинство моделей – остроумные компьютерные эксперименты. Серьезное математическое описание здесь только начинается. Хороший пример серьезного математического исследования – работы К. Адами по анализу распределения особей в эволюционирующих популяциях [18]. Этот анализ основан на теории саморганизованной критичности [19] и разумно интерпретирует как компьютерные эксперименты на моделях Тьерра и Авида, так и реальные биологические данные. Эти работы "примыкают" к теории популяционной генетики, которую мы рассматривали в лекции 8 .

Исследования искусственной жизни тесно связаны с другими интересными направлениями: моделями происхождения жизни, автоматами С.А. Кауффмана, работами по прикладному эволюционному моделированию, по теории нейронных сетей (см. предыдущие лекции). Эволюция популяций искусственных организмов – одно из ведущих направлений исследований искусственной жизни. Модели эволюции здесь часто основаны на генетическом алгоритме (см. лекцию 10 ). Правда в моделях искусственной жизни часто не вводится явно понятие приспособленности, как это делается в генетическом алгоритме. Приспособленность проявляется естественным путем: особи рождаются, когда их родители готовы дать потомков, и погибают, когда не хватает пищи или когда их убивает и съедает хищник. В этом случае говорят, что приспособленность эндогенна. Примеры такой эндогенной приспособленности приведены ниже, в описании модели ПолиМир [9] и модели Д.Экли и М. Литтмана. Управление поведением искусственных организмов часто моделируется с помощью нейронных сетей (см. лекцию 11 ).

Модели искусственной жизни проливают новый свет на эволюционные явления. Отличный пример, иллюстрирующий этот тезис – исследования эффекта Балдвина. В 1986 году Дж.Балдвин [20] предложил мехпнизм, согласно которому первоначально приобретенные навыки организмов могут в дальнейшем стать наследуемыми. Эффект Балдвина работает в два этапа. На первом этапе эволюционирующие организмы (благодаря соответствующим мутациям) приобретают свойство обучиться некоторому полезному навыку. Приспособленность таких организмов увеличивается, следовательно, они распространяются по популяции. Но обучение имеет свои недостатки, так как оно требует энергии и времени. Поэтому возможен второй этап (который называют генетической ассимиляцией): приобретенный полезный навык может быть "повторно изобретен" генетической эволюцией, в результате чего он записывается непосредственно в геном и становится наследуемым. Второй этап длится множество поколений; устойчивая окружающая среда и высокая корреляция между генотипом и фенотипом облегчают этот этап. Таким образом, полезный навык, который первоначально был приобретенным, может стать наследуемым, хотя эволюция имеет Дарвиновский характер.

Ряд исследователей (Г. Хинтон и С. Новлан, Д.Экли и М. Литтман, Г, Мейлей и многие другие) анализировали эффект Балдвина. Они показали, что этот эффект может играть существенную роль в процессе эволюции искусственных особей. Подробнее см. сборники статей [21,22]. Конкретный пример модели, в которой проявляется эффект Балдвина – модель Д.Экли и М. Литтмана – описан ниже.

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

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

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

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

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

Отметим достоинства и недостатки модели ПолиМир. К несомненным достоинствам этой модели относится продуманная схема поведения: естественная реакция на события в окружающей среде, естественные действия организма, естественные взаимодействия между организмами. Но модель "перегружена" деталями, связанными с цветовым зрением. Это обусловило и другой недостаток модели: слишком сложная нервная система. В итоге результаты моделирования оказались довольно туманными. В частности, хотя в модель была заложена возможность обучения, на самом деле обучение себя никак не проявило. Фактически модель показала, 1) что сложное цветовое зрение вполне могло сформироваться в процессе эволюции и 2) что возможно эволюционное формирование указанных выше стратегий, – этим основные результаты модели и исчерпываются.

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

В модели предполагается, что агенты живут в двумерном мире, разбитом на клетки. В клетках может располагаться сами агенты, трава, хищники, деревья, камни. Трава служит пищей агентов. Хищники и другие агенты могут драться с данным агентом, уменьшая его здоровье. Хищники бьют агентов сисльнее, чем агенты хищников. Залезая на деревья, агенты становятся недоступными для хищников. Деревья вырастают и погибают. Если дерево погибает, и при этом на дереве сидел агент, то дерево убивает данного агента. Камни являются препятствиями для агентов: если агент сталкивается с камнем, то он теряет при этом часть своего здоровья. Агенты могут скрещиваться, давая потомков. Агенты погибают от голода или теряя здоровье. Погибшие агенты служат пищей для других агентов и хищников.

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

Поведение агентов управляется их нейронной сетью. Входами нейронной сети являются: видимая картина мира и внутреннее состояние агентов (количество энергии и здоровья). Агенты видят мир вокруг себя на расстоянии до 4 клеток в 4-х направлениях (север, юг, восток, запад). Поведение агентов определяется выходами их нейронной сети (структура нейронной сети описана ниже). Мир развивается в дискретном времени t . Каждый такт времени нейронная сеть определяет выбор действий агента. Выбор действий очень простой: выбрать одно из 4-х направлений движения. После выбора действия "локальная судьба" агента в следующий такт времени будет однозначно определена – она зависит только от того, что есть в целевой клетке (клетке по направлению движения).

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

Блок оценки действий состоит из одного нейрона, выход этого нейрона определяет обучающий сигнал r. Cигнал r имеет простой смысл: он показывает, улучшилось ( r > 0) или ухудшилось ( r < 0) ("с точки зрения" блока оценки) состояние агента в данный такт времени по сравнению с предыдущим тактом в результате выполненного действия.

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

Обучение блока поведения осуществлялось специальным способом: "Комплементарным методом обратного распространения ошибки" ("Complementary reinforcement back- propagation" (CMRB) ) [12,23] – этот метод можно рассматривать как вариант метода обратного распространения ошибки (см. лекцию 11 ). Основная идея метода состоит в том, что ошибка на выходе каждого нейрона блока поведения определяется по выходу данного нейрона и по сигналу обучения r , поступающего от блока оценки действий. Сигнал обучения r может быть положительным, если блок оценки "считает", что команда блока поведения улучшает жизнь агента, либо отрицательным – в противном случае. В соответствии с ошибками на выходах нейронов корректируются веса синапсов нейронов, аналогично тому, как это делается в обычном методе обратного распространения ошибок.

При моделировании Д. Экли и М. Литтман анализировали как полную модель агентов (ERL), включающую как обучение, так и эволюцию (так, как это описано выше), так и частные модели, включающие только эволюцию (E), либо только обучение (L).

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

В одном из компьютерных экспериментов над полной версией программы (ERL) Д. Экли и М. Литтман запустили программу на несколько дней, а затем с удивлением обнаружили, что популяция не вымерла, хотя число тактов жизни агентов t достигло 9•106 .

С этим экспериментом они решили разобраться детально и проанализировали скорость мутационных замен в генах, ответственных за начальные веса синапсов нейронов блока поведения, и в генах, ответственных за веса синапсов нейронов блока оценки действий. Оказалось, что для агентов, живущих на начальных и конечных этапах эволюции (до и после момента времени t = 6•105), распределение скоростей мутационных существенно различно (Рис.3).

Рис.3. Скорость мутационных замен (частота замен на один сайт за поколение) для синапсов ответственных за обнаружение травы (две верхних полосы) до (слева) и после (справа) момента времени t = 6•105. Нижняя полоса на обеих диаграммах соответствует несущественным для адаптации генам агентов. Схематично, по результатам моделирования [12].

Низкая скорость мутационных замен соответствует важным для агентов генам, высокая скорость – несущественным генам. Этот факт справедлив и биологических организмов. Д. Экли и М. Литтман приводят данные по скорости аминокислотных замен для гена белка aA-кристаллина (aA-crystallin), важного для хрусталика глаза, для зрячих грызунов и слепышей (для которых зрение не так существенно) и псевдогенов, которые не кодируют белков (Рис.4).

Данные, приведенные на Рис.3, показывают, что до момента времени t = 6•105 для агентов более важны гены, кодирующие синапсы блока оценки. Т. е. важна процедура обучения поиску пищи: блок оценки говорит: "пища – это хорошо, учись двигаться к пище". Однако после момента времени t = 6•105 для агентов становятся более важными гены врожденного поведения, направленного на движение к пище. Т.е. агентам не требуется обучаться идти в направлении пищи, так как они и так это делают с самого рождения.

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

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

В настоящее время мы с Р.В.Гусаревым начали работу над более естественной моделью эволюционного возникновения целенаправленного адаптивного поведения. Модель может рассматриваться как развитие работ Л. Ягера и Д. Экли и М. Литтмана. В нашей модели мы делаем цели более естественными по сравнению с тем, как это делается Д. Экли и М. Литтманом и связываем их с основными потребностями организмов. Ниже приводится краткая характеристика нашей модели. Более детальное обсуждение модели (с демонстрацией работы имеющейся программы) мы проведем в дальнейшем.

1. Имеется популяция агентов (искусственных организмов), имеющих естественные потребности (Безопасность, Энергия, Размножение).
2. Популяция агентов эволюционирует в простой среде, где растут лужайки травы (пища агентов). Агенты взаимодействуют между собой: агенты могут скрещиваться и бороться друг с другом. Борьба может привести к гибели агента (погибший агент превращается в пищу и может быть съеден победителем). Скрещивание приводит к рождению новых агентов.
3. Каждая потребность характеризуется количественно мотивацией. Например, если энергетический ресурс агента мал, то есть мотивация найти пищу и пополнить энергетический ресурс.
4. Поведение агента управляется его нейронной сетью, которая имеет специальные входы от мотиваций. Если имеется определенная мотивация, то поведение агента меняется с тем, чтобы удовлетворить соответствующую потребность. Такое поведение будем называть целенаправленным (есть цель достигнуть определенную потребность).

1. Langton, C. G. (Ed.) Artificial Life: The Proceedings of an Interdisciplinary Workshop on the Synthesis and Simulation of Living Systems, Redwood City CA: Addison-Wesley, 1989. 655 p.
2. Langton, C. G., Taylor, C., Farmer, J. D., and Rasmussen, S. (Eds.) Artificial Life II: Proceedings of the Second Artificial Life Workshop, Redwood City CA: Addison-Wesley. 1992. 854 p.
3. Meyer, J.-A., Wilson, S. W. (Eds) (1990), "From animals to animats". Proceedings of the First International Conference on Simulation of Adaptive Behavior. The MIT Press: Cambridge, Massachusetts, London, England.
4. Цетлин М.Л. Исследования по теории автоматов и моделирование биологических систем. М.: Наука, 1969. 316 с.
5. Варшавский В.И., Поспелов Д.А. Оркестр играет без дирижера. М.: Наука, 1984. 208 с.
6. Моделирование обучения и поведения. М.: Наука, 1975.
7. Гаазе-Рапопорт М.Г., Поспелов Д.А. От амебы до робота: модели поведения. М.: Наука, 1987. 288 с.
8. Langton, C. G. (1992). Life at the edge of chaos. In [2] . P.41-91.
9. Yaeger, L. (1994). Computational genetics, physiology, metabolism, neural systems, learning, vision, and behavior or Polyworld: Life in a new context. In Langton C.G. (ed). Artificial Life III. Addison-Wesley, pp. 263-298. See also: http://www.beanblossom.in.us/larryy/PolyWorld.html
10. Ray, T. S. (1992), An approach to the synthesis of life. In [2] . P.371-408. See also: http://www.hip.atr.co.jp/~ray/tierra/tierra.html
11. Adami, C., Brown, C.T. Evolutionary learning in the 2D Artificial Life system 'Avida' // In Artificial Life IV, edited by R.A.Brooks and P.Maes. Cambridge, MA: MIT Press. P.377. See also: http://www.krl.caltech.edu/avida/
12. Ackley, D. Littman, M. (1992). Interactions between learning and evolution. // Langton, C. G., Taylor, C., Farmer, J. D., and Rasmussen, S. (Eds.) Artificial Life II. Reading, MA: Addison-Wesley. pp.487-509.
13. Holland, J.H. (1994). Echoing emergence: Objectives, rough definitions, and speculations for Echo-class models. In G.A.Cowan, D.Pines, and D.Meltzer (eds.), Complexity: Metaphors, models and reality, volume XIX of Santa Fe Institute Studies in the Sciences of Complexity (pp.309-342). Reading, MA: Addison-Wesley. See also: http://www.santafe.edu/projects/echo/
14. Hillis, W.D. Co-evolving parasites improve simulated evolution as an optimization procedure. In [2] pp. 313-322.
15. Mitchell, M., Crutchfield, J.P., Das, R. Evolving cellular automata with genetic algorithms: A review of recent work // In Proc. of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996. See also: http://www.santafe.edu/projects/evca/evabstracts.html#evca-review
16. Collings, R.J., Jefferson, D.R. AntFarm: Towards simulated evolution. In [2], pp. 579-601.
17. Holland, J.H., Holyoak, K.J., Nisbett, R.E., Thagard, P. (1986). Induction: Processes of Inference, Learning, and Discovery. Cambridge, MA: MIT Press.
18. Adami, C., Seki, R., Yirdaw, R. Critical exponent of species-size distribution in evolution // In Adami, C., Belew, R., Kitano, H., Taylor, C., (Eds.) (1998). Artificial Life VI. MIT Press, pp. 221-227.
19. Bak, P. (1996). How Nature Works: The Science of Self-Organized Criticality, Springer, Berlin.
20. Baldwin, J.M. A new factor in evolution // American Naturalist, 1896. V.30, pp. 441-451. See also: http://www.santafe.edu/sfi/publications/Bookinforev/baldwin.html
21. Belew, R.K. and Mitchell, M. (Eds.) (1996). Adaptive Individuals in Evolving Populations: Models and Algorithms, Massachusetts: Addison-Wesley. See also: http://www.santafe.edu/sfi/publications/Bookinforev/ipep.html
22. Turney, P., Whitley, D., Anderson, R. (Eds.). Evolution, Learning, and Instinct: 100 Years of the Baldwin Effect // Special Issue of Evolutionary Computation on the Baldwin Effect, V.4, N.3, 1996. See also: http://ai.iit.nrc.ca/baldwin/toc.html
23. Ackley, D. Littman, M. (1990). Generalization and scaling in reinforcement learning. // In Advances in Neural Information Processing Systems – 2, edited by S. Touretzky. San Mateo, CA: Morgan Kauffmann.
24. Кимура М. Молекулярная эволюция: теория нейтральности. М.: Мир, 1985, 400 с.