Сергей Бобровский
Продолжение. Начало см. PC Week/RE, № 30-31/98, с. 37; № /98, с. 28.
Программы могут зарождаться самопроизвольно
А чем сегодня на Западе занимаются специалисты по теории искусственной жизни (ИЖ)?
Формальный основоположник этого направления Крис Г. Лэнгтон разработал систему Swarm - инструментальное средство моделирования, позволяющее создавать миры, в которых правила развития автономных агентов задаются с помощью алгоритмов генетического программирования. Агенты, которыми являются любые объекты физического мира (насекомые, молекулы или продавцы), могут обмениваться друг с другом и с окружающей средой различными сообщениями, а также быстрее или медленнее реагировать на происходящие события. Swarm позволяет задавать произвольные наборы свойств проектируемого виртуального пространства - число измерений, форму, способы передвижения агентов и их методы влияния на характеристики мира.
С помощью Swarm проектировались сети связи, описываемые двухмерными графами, а по их узлам перемещались агенты, имитирующие пакеты данных. Система использовалась для имитации процессов загрязнения окружающей среды, для моделирования торговых систем, когда агенты не могли двигаться, а только обменивались информацией о покупке-продаже товаров. Биолог Дэйв Хайбилер на базе Swarm построил систему, моделирующую развитие колонии муравьев.
Этим проектом заинтересовалось американское военное научное агентство DARPA. Оно добавило в Swarm иерархию уровней функциональности объектов, а также реализовало возможность временно/й и событийной синхронизации действий одновременно функционирующих агентов, что более точно соответствует физике реального мира. Кроме того, в Swarm был реализован большой набор различных алгоритмов обучения и эволюции. Формализация модели объекта позволила легко включать в Swarm новые типы агентов. Графический индекс пользователя ГИП-системы был переписан с X Windows на Tk/Tcl, и она стала платформно-независимой.
Для достижения общей цели агентам позволено объединяться в группы, организовывать действия этих групп и управлять ими. Исследовалось поведение больших коллективов виртуальных существ в пространствах со сложной или динамически изменяемой геометрией.
Интерес военных к ИЖ понятен. Например, в современном масштабном воздушном бою даже самый мощный суперкомпьютер, установленный в наземном центре, сегодня не способен оперативно организовать слаженную работу групп истребителей и “на лету” вырабатывать оптимальную стратегию и тактику сражения. Когда не удается осуществлять надежный обмен информацией с быстро движущимися объектами в условиях очень высокого уровня помех, непомерно высокая нагрузка ложится на каналы связи. В таком случае единственным выходом может стать наращивание мощности бортовых компьютеров, способных самостоятельно принимать решения и согласовывать их с компьютерами других самолетов.
Классическую систему ИЖ - MANTA (Modeling an ANTnest Activity) - разработал Алексис Дрогаул из Парижского университета. Первоначально она предназначалась для исследования коллективной деятельности муравьев - их миграции, размножения, развития колоний, войн с другими видами и т. д. Муравьи вообще считаются самым любимым объектом моделирования у специалистов по ИЖ.
MANTA представляет собой колонию реактивных агентов. Этот тип автономного агента характеризуется следующими особенностями:
- он может обмениваться сообщениями с другим реактивным агентом;
- реактивный агент не способен обучаться и “думать”, а только стереотипно реагирует на принимаемые сообщения.
В MANTA имеется три класса реактивных агентов:
- базовые - королева, рабочие, самцы;
- вспомогательные - личинки на разных стадиях развития, коконы;
- физические - свет, влажность, пища, мусор, мертвые особи.
Каждый агент определяется заданной формой поведения, имеет графическое представление на экране, свое место в пространстве, может расти в зависимости от времени и (в некоторых случаях) от количества пищи. Все характеристики агентов представлены в виде дерева и могут произвольно настраиваться.
В недрах операционных систем зарождаются Web-пауки
Дрогаул с помощью MANTA имитировал развитие колоний самых разных насекомых, в частности ос. Начиная с одной осы-матки, он практически всегда получал результаты моделирования, совпадающие с реальными данными: популяция колонии колебалась очень похоже на то, как это происходит в жизни. Процент гибели ос-маток также был примерно одинаковым.
Филипп Шенцер и Рик Белью из Калифорнийского университета (Сан-Диего) создали программу Latent Energy Environments (LEE), занимающую 7 тыс. строк кода на Си и объединяющую алгоритмы генетической эволюции и нейронных сетей.
Виртуальный мир представляет собой двухмерное замкнутое пространство (тор), где случайным образом распределены элементарные физические объекты (атомы) трех типов - A, B и C. В каждой ячейке пространства может одновременно располагаться несколько существ и разных атомов. Если атомы объединяются в определенных комбинациях, то происходит химическая реакция, в результате которой выделяется или поглощается энергия.
Виртуальные существа имеют “кишку”, в которую они могут заглатывать по одному атому в единицу времени, а также “органы чувств” (сенсоры), определяющие, есть ли по соседству атомы и какова плотность их скопления в разных направлениях. Кроме того, виртуальное существо понимает, имеется ли у него в кишке атом и какого он типа. Орган передвижения позволяет LEE-существу сделать шаг вперед или повернуться на месте.
Каждое LEE-существо снабжено нейронной сетью, связывающей сенсоры и моторную систему. Сеть анализирует и запоминает результаты взаимодействия заглатываемых атомов с атомами, уже находящимися в кишке.
Один временной цикл виртуального существа в LEE происходит так:
- собирается информация об окружающей среде;
- нейронная сеть выдает рекомендацию о действии, которое затем выполняется;
- результат передвижения возвращается в нейронную сеть, и ее настроечные коэффициенты уточняются;
- вычисляется расход энергии, затраченной на движение, и результат химической реакции между атомами в кишке;
- если энергия понизилась до нуля, существо считается умершим;
- если энергия превысила некоторый порог, искусственный организм воспроизводит себе подобного с такой же, как у родителя - уже обученной, нейронной сетью (наследственными “генами”), но с некоторыми случайными отклонениями в весовых коэффициентах (мутация);
- если энергия лежит в “спокойном” диапазоне, то ничего не происходит.
Этот цикл выполняется одновременно для всех существ.
Эксперименты с разными параметрами настройки нейронных сетей показали, что более жизнеспособны организмы, действующие более примитивно, на основе данных о ближайшем окружении, нежели те, которые пытаются действовать с долгосрочной перспективой. Причина такого несколько странного результата, по-видимому, в том, что создание эффективных механизмов выработки даже не оптимальной, а просто рациональной стратегии поведения в LEE-мире - сложная задача сама по себе, и решить ее с помощью небольшой нейронной сети невозможно. Хотя, конечно, известный жизненный принцип “будь попроще” не теряет актуальности на протяжении всей истории человечества.
Особняком стоит система Tierra, моделирующая эволюцию компьютерных программ. Ее написал Том Рэй из Делаверского университета. В Tierra каждый организм представляет собой программу, написанную на своеобразном ассемблере - наборе 32 модифицированных инструкций процессора 80x86 с нечисловыми аргументами. На каждом такте “жизни” программы в рамках виртуального окружения выполняется ее очередной оператор, и указатель текущей инструкции перемещается к следующему оператору. Двоичный код программы может подвергаться случайным мутациям, становясь в некоторых случаях невыполнимым. Тогда считается, что программа генерирует ошибку, т. е. больна.
Главной проблемой для Рэя при создании Tierra был подбор хорошего набора инструкций, который можно модифицировать, сохраняя работоспособность программы. Для этого он придумал две новые команды: “Нет_действия_0” и “Нет_действия_1”(аналоги двоичных нуля и единицы), - благодаря чему стало возможно трактовать двоичные числа как команды. Для организации ветвления Рэй ввел инструкции jump_ forward и jump_backward с использованием последующего числа как адреса перехода. Если этот адрес выходит за допустимый диапазон, то команда перехода игнорируется.
Программы мутируют по разным правилам: случайно смещается указатель текущей команды, инвертируются некоторые биты кода, происходит перестановка команд, инструкция может быть заменена на “Нет_действия_0/1”, и т. д. Живут наборы команд в виртуальной ОС, имитирующей работу ЦПУ и ОЗУ.
В типичном эксперименте с Tierra виртуальная память “заражается” единственной программой, способной самовоспроизводиться - копировать себя в другие области памяти. В результате мутаций некоторые программы теряют способность к размножению, а другие повышают скорость воспроизведения.
Когда память переполняется, Tierra проверяет, сколько ошибок генерирует каждая программа, и удаляет самые больные. Выживают в основном программы, генерирующие небольшое число ошибок и способные быстро размножаться. Более живучими оказываются также “организмы”, менее требовательные к ресурсам. Это компактные программы, для выполнения которых нужно немного компьютерных тактов (аналог жизненной энергии) и небольшое количество памяти (аналог занимаемого пространства).
Похожие исследования ведутся НАСА в рамках проекта Dyna, представляющего собой популяцию экспертных систем, которые могут обмениваться информацией и правилами вывода друг с другом. Цель этих работ - повышение вычислительной мощности интеллектуальных решателей путем их реализации в распределенных мультикомпьютерных средах, в частности, в Интернете.
Продолжение см. PC Week №49 стр.1
