Software & Systems

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

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

Искусственный мир можно описать как совокупность вида: W=áS, T, R, A, Dñ, где S – пространство; T – время; R – множество правил и ограничений целостности; A – множество обитателей мира, или активных сущностей (живая природа); D – множество пассивных объектов, присутствующих в мире (неживая природа) [1].

Пространство в классических моделях искусственных миров

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

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

В первом случае суть моделирования состоит в том, что каждая клетка пространства в каждый момент времени динамически изменяет свое состояние по заданному набору правил. При этом образуются динамически устойчивые конфигурации, которые можно рассматривать как живые организмы. К таким моделям относятся самовоспроизводящиеся автоматы фон Неймана [2], игра «Жизнь» Конвея [3], модель Q-loops Лангтона [4], модель червеобразных организмов Саяма [5]. Ключевое значение для моделей данного типа имеет понятие соседства, то есть определения множества клеток, находящихся в окрестностях рассматриваемой клетки, чье состояние учитывается при формировании нового состояния рассматриваемой клетки.

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

Наиболее наглядным примером моделей подобного типа является ERL-модель [6], в которой агенты перемещаются в пределах двухмерного клеточного пространства. В каждой клетке могут находиться пища, укрытие (дерево), препятствие (камень) или вредитель (хищник либо конкурирующий агент своего вида). Пища способствует улучшению состояния агента. Укрытие представляет собой дерево, на которое может взобраться агент, чтобы спастись от хищников. Но дерево, вырастая, падает и убивает агента. Камень и агент-конкурент ударяют агента, ухудшая его состояние. Хищник может убить агента.

В модели MANTA [7] клетки пространства делятся на две группы: свободные клетки (посещаемые места) и препятствия. Препятствия отличаются тем, что не могут содержать агентов и не распространяют стимулы.

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

В некоторых моделях, таких как Tierra и Avida [8], сочетаются свойства моделей двух основных групп. Клеточное пространство в этих моделях рассматривается как ресурс, за обладание которым борются искусственные организмы в виде псевдоассемблерных программ. Цель организмов в том, чтобы или удлинить запись своей программы, заняв большее количество соседних клеток пространства, или размножиться, заполнив соседние клетки пространства копиями программы.

В рассматриваемой далее модели агенты по своей структуре близки к цифровым организмам моделей Tierra и Avida, однако в целом модель родственна ERL и MANTA, в том числе и в отношении пространственных свойств.

Предлагаемый способ организации пространства искусственного мира

Будем рассматривать пространство как множество неделимых участков, которые интерпретируем как точки или клетки: S=áX, Weightñ, где X – множество точек пространства, X={xi}i; Weight – функция, которая каждой паре элементов из X ставит в соответствие значение из множества N0+ÈNull (вес дуги): Weight: X´X®N0+ÈNull.

Здесь и далее N0+ – множество всех целых неотрицательных чисел. Значение Null соответствует особому пустому значению, вес дуги, равный Null, означает отсутствие смежности между точками. Нулевой вес дуги между xi и xj – это тождество точек.

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

Каждая точка пространства, или клетка, идентифицируется номером indX: X®N0+. В декартовом решетчатом пространстве точка может быть идентифицирована и набором координат, или номеров, с учетом мерности пространства S:

xi=((…((coordn–shiftn)´sizen+(coordn-1–shiftn-1))´ ´size n-1+…+(coord2–shift2))´ size2)+(coord1–shift1),

где coordi – координата точки в i-м измерении; sizei – количество единиц (i–1) измерения в измерении i; shifti – смещение начала отсчета в i-м измерении относительно нуля.

В дальнейшем будем полагать, что, если не оговорено иное, связи между клетками имеют регулярный характер и задаются так же, как соседства в клеточных автоматах [2, 3]. Для декартова пространства S важны и такие свойства, как замкнутость или незамкнутость по каждому из измерений. Будем считать, что по умолчанию все измерения пространства замкнуты, если другое не определено.

По аналогии с клеточными автоматами для множества точек пространства можно ввести отношение соседства. Это позволит сделать регулярным правило вычисления смежности вершин: если координаты точек xi и xj удовлетворяют правилу соседства, то Weight(xi, xj)£r, где r – радиус соседства.

Особенностью предлагаемой здесь модели является то, что в ней присутствует еще и дополнительное измерение пространства. Дополнительное измерение, или глубина, представлено совокупностью бесконечного числа логических слоев, на которые разбита каждая клетка. Множество слоев Layers проиндексировано целыми неотрицательными числами: indLayers: Layers ®N0+.

Каждую клетку можно рассматривать как совокупность бесконечного числа слоев " xiÎX: xi={xi, lj}¥j=0. С другой стороны, весь пространственный слой с индексом i представляет собой совокупность слоев с номером i отдельных клеток:

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

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

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

Кроме того, в предлагаемой модели поддерживается возможность сохранения в клетке следов пребывания агентов. Эти следы являются аналогами феромонных меток насекомых и похожи на стимулы, используемые в модели MANTA [7]. След реализуется в виде записи в системном журнале, в котором фиксируются уникальный идентификатор агента, время пребывания агента в клетке и его важнейшие параметры. В настоящее время в модели предполагается, что только сам агент использует свои феромонные метки. Однако следы пребывания агентов могут использоваться и в моделях коллективного поведения искусственных организмов одного вида, и для интеллектуализации поиска агента-жертвы агентом-хищни­ком.

Алгоритмы перемещения цифровых организмов в клеточном пространстве

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

Примерами регулярных алгоритмов перемещения в клеточном пространстве являются алгоритм virtual ant (или vant, или Langton’s ant) [4] и алгоритм перемещения по спирали [9].

В случае алгоритма vant в клеточном пространстве перемещается активный агент виртуальный муравей. Как правило, пространство задано как одномерное или двухмерное, каждая клетка может быть раскрашена. В исходной модели [4] используются два цвета – синий или желтый, но есть и многоцветные модификации. В пустом пространстве муравей движется прямо. Если он наблюдает синюю клетку, то поворачивает направо и оставляет клетку желтой, а если наблюдает желтую клетку, то поворачивает налево и оставляет клетку синей.

Спиралевидная схема перемещения [9] может использоваться агентами, имеющими свою территорию и охраняющими ее. Агент рассматривается как ориентированный в пространстве, он различает четыре направления: вперед, назад, влево, вправо. Ориентация по сторонам света несущественна. В данном алгоритме элементарными действиями являются поступательное движение вперед-назад и изменение направления движения (поворот на 90 градусов). Обход территории начинается из некоторой исходной точки, или гнезда. Основной алгоритм обхода состоит из следующих шагов.

1.     Переместиться вперед на L клеток, повернуть на 90 градусов влево.

2.     Повторить предыдущий шаг.

3.     Увеличить значение L на единицу.

4.     Если значение L больше установленного значения Lmax, то перейти к шагу 5; если нет – перейти к шагу 1.

5.     Переместиться назад на L клеток, повернуть на 90 градусов вправо.

6.     Повторить предыдущий шаг.

7.     Уменьшить значение L на единицу.

8.     Если значение L больше 1, перейти к шагу 5, если нет – перейти к шагу 1.

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

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

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

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

Литература

1.     Кольчугина Е.А. Моделирование биоценозов // Новые информационные технологии и системы: тр. VI междунар. науч.-технич. конф. Пенза, ПГУ, 2004. С. 240–246.

2.     Нейман Дж. фон. Теория самовоспроизводящихся автоматов; [пер. с англ.]. М.: Мир, 1971. 382 c.

3.     Тоффоли Т., Марголус Н. Машины клеточных автоматов; [пер. с англ.]. М.: Мир, 1991. 280 с.

4.     Langton C.G., Physica D: Nonlinear Phenomena, 1986, Vol. 22, Iss. 1–3, pp. 120–149.

5.     Sayama H., Artificial Life, 1999, Vol. 5, no. 4, pp. 343–365.

6.     Ackley D.H., Littman M.L., Artificial Life II, SFI Studies in the Sciences of Complexity, Redwood City, CA: Addison-Wesley, 1991, Vol. X, pp. 487–509.

7.     Drogoul A., Corbara B., Lalande S., Artificial Societies: the Computer Simulation of Social Life, London: UCL Press, 1995, pp. 190–211.

8.     Dittrich P., Ziegler J., Banzhaf W., Artificial Life, 2001, Vol. 7, no. 3, pp. 225–275.

9.     Кольчугина Е.А. Моделирование перемещений особи // Новые информационные технологии и системы: тр. VI междунар. науч.-технич. конф. Пенза, ПГУ, 2004. С. 246–249.

10.  Кольчугина Е.А. Результаты эксперимента по созданию эволюционирующего программного обеспечения // Изв. вузов. Поволжский регион. Технические науки. № 1, 2007. Пенза, ИИЦ ПГУ, 2007. С. 54–60.