Software & Systems

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

Применительно к программным системам способность к самоорганизации может означать:

–      способность к самовосстановлению после сбоев и повреждений;

–      способность к самообучению и адаптации;

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

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

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

Главными вопросами создания самоорганизующихся программных систем являются:

–      определение принципов построения сред, в которых могут происходить процессы самоорганизации;

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

Самоорганизация и модели искусственной химии

В [1] выделены два вида самоорганизации: когерентная (или синергетическая) и континуальная (или синкретическая).

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

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

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

Целью разработки модели алгоритмической химии AlChemy У. Фонтана [2] было исследование возникновения новшеств, в первую очередь, появление в модели новых структур и правил. Правила преобразования структур соответство- вали реакциям, а сами структуры – молекулам. Фонтана обратил внимание на взаимную двойственность как молекул и реакций, так и данных и программного кода. Молекулы – это пространственные структуры, которые определяют функциональность как множество возможных реакций. Аналогично программы задают последовательности действий по обработке данных, но символьная запись программы может рассматриваться как данные.

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

Двойственность данных и программ была использована в моделях искусственной химии Tierra и Avida [3]. В этих моделях вводится понятие цифрового организма как строки псевдоассемблерных команд, которая может рассматриваться либо как данные и переписываться другими организмами, либо как набор инструкций процессора виртуальной ЭВМ.

Структурная модель цифрового организма

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

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

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

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

Коды значений переменных и программных реализаций поведенческих блоков можно рассматривать как номерные множества нумераций [5]. Если для представления нумераций использовать БД, то номерные множества будут соответствовать ключам, на основе которых можно получить программные реализации поведенческих блоков и значения переменных состояния, то есть синтезировать фенотип цифрового организма.

Нумерацией здесь и далее будем называть взаимнооднозначное отображение множества номеров на множество нумеруемых объектов:

vObj: N1→Obj, N1ÍN0+.

Обратную к vObj  функцию назовем функцией индексирования: indObj: Obj→N1,  .

Рассматривая структуру суперхромосомы, будем различать:

–      локусы, или элементарные участки суперхромосомы;

–      номера, или индексы локусов;

–      значения, находящиеся в локусах суперхромосомы.

Структура суперхромосомы может быть определена  как множество локусов, упорядоченных по индексу [4]:

Здесь Loc – не более чем счетное множество всех локусов, которые могут входить в состав структуры суперхромосомы. Индексы локусов будем определять с помощью функции IndLoc: Loc→NLoc, NLocÍN0+.

Каждому локусу поставим в соответствие взаимнооднозначным образом элемент программы из множества Item=ParamsÈBH, то есть или глобальную переменную состояния из множества всех глобальных параменных состояния Params, или поведенческий блок bhÎBH, где  – множество всех блоков поведения: Locus: Item→ →Loc.

С учетом того, что локусам соответствуют элементы программы, представляющие либо код, либо данные, множество локусов можно представить как Loc=LocBHÈLocParams,, LocBHÇLocPar=Æ. Элементы множества Items можно обобщенно рассматривать как функции или аналоги молекул в модели AlChemy, а сам цифровой организм – как совокупность молекул и реакций [6].

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

На рисунке 1 приведена коммутативная диаграмма для функций Pos, Locus, indLoc.

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

,

где Val – множество всех возможных значений для всех параметров из Params; Code – множество всех возможных программных реализаций для всех элементов BH; P(X) – булеан X; Å – знак, обозначающий операцию «исключающее ИЛИ». Каждое множество Yi является элементом одного из булеанов, то есть подмножеством либо Val, либо Code.

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

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

Структура суперхромосомы описывает общий принцип организации цифровой ДНК для всех программных агентов (цифровых организмов) данной модели, то есть задает шаблон. Конкретный экземпляр цифровой ДНК, то есть сама суперхромосома, отражает состояние генома конкретного агента в определенный момент времени. Функция  позволяет вычислить значение локуса в заданное время tjÎT для цифрового организма aiÎA:

,

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

В общем случае

,

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

На основе функции iv можно дать описание суперхромсомы, или цифровой ДНК, как последовательности значений, описывающей состояние особи aiÎA в момент tjÎT:

Операции над цифровой ДНК

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

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

Реализация предложенной модели цифрового организма может быть выполнена с использованием различных средств: языков скриптового типа, XML или языков типа С\С++.

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

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

Литература

1. Руденко А.П. Самоорганизация и синергетика. URL: http://utc.uni-dubna.ru/~mazny/students/site2/ideal_2.htm (дата об­ращения: 10.05.2011).

2. Fontana W. Algorithmic Chemistry // Artificial Life II, SFI Studies in the Sciences of Complexity. Vol. X, edit. by C.G. Lang­ton, C. Taylor, J.D. Farmer, S. Rasmussen. Redwood City, CA: Addison-Wesley, 1991, pp. 159–209.

3. Dittrich P., Ziegler J., Banzhaf W. Artificial Chemistries – A Review // Artificial Life. 2001. Vol. 7. (No. 3), pp. 225–275.

4. Кольчугина Е.А. Модель эволюционирующего программного обеспечения // Изв. вузов. Поволж. рег. Технич. науки. Пенза: ИИЦ ПГУ. 2006. № 6 (27).  С. 78–86.

5. Ершов Ю.Л. Теория нумераций. М.: Наука, 1977. 416 с.

6. Кольчугина Е.А. Неравновесное программирование // Изв. вузов. Поволж. рег. Технич. науки. Пенза: ИИЦ ПГУ. 2009. № 3 (11). С. 25–31.