Неравновесное программирование

УДК 004.42

Е. А. Кольчугина НЕРАВНОВЕСНОЕ ПРОГРАММИРОВАНИЕ

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

Ключевые слова: парадигма программирования, искусственная химия, эволюционный катализ, неравновесие, самоорганизация.

Abstract. We propose a new programming paradigm based on nonequilibrium and anti-entropic directedness of internal system processes. The models of artificial chemistry, evolutionary catalysis and hypercyclic self-organization are the fundamentals for basic model of the paradigm proposed.

Keywords: programming paradigm, artificial chemistry, evolutionary catalysis, nonequilibrium, self-organization.

Введение

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

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

1 Условия и виды самоорганизации

В настоящее время выделяют два основных принципа структурной организации вещества [1]:

- принцип организации, для которого характерно стремление к равновесию со средой, минимуму внутренней энергии и максимуму энтропии;

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

Необходимыми условиями для проявления внутрисистемной самоорганизации и образования эволюционирующих структур являются [1-3]:

- избыточность и конкуренция структур;

- ограниченность времени существования структур;

- неравновесность и антиэнтропийная направленность процессов;

- мультистабильность, неустойчивость стационарных состояний и удаление от равновесия в случае малых возмущений;

- открытость и диссипативность систем;

- наличие свободной энергии;

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

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

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

Континуальный тип самоорганизации рассматривается в теории эволюционного катализа и предполагает взаимодействие разнородных элементов на уровне микросистем. Решающее значение для данного типа самоорганизации имеет образование в ходе базисной реакции промежуточного неравновесного функционально неделимого объекта, а именно кинетического континуума веществ и реакций [1]. Этот тип самоорганизации приводит к функциональной упорядоченности и прогрессивной эволюции. Более того, континуальная самоорганизация определяет возможность когерентной самоорганизации.

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

2 Модели искусственной химии

Модель искусственной химии определяется в [5] как тройка вида («5,R,А), где ^ - множество возможных типов молекул; R - набор правил

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

К данной группе относятся модели Иегга и Ау!ёа [5, 6], реализуемые одноименными компьютерными программами. В них исследуется эволюция ассемблерных программ, исполняемых виртуальной ЭВМ. Язык ассемблера, на котором пишутся программы, распознается только виртуальной ЭВМ, а не реальным процессором, что является гарантией безопасности моделей данного класса. Виртуальная ЭВМ - это программа, моделирующая виртуальный процессор, несколько внутренних регистров и стеков, а также буферы ввода-вывода.

Каждая ассемблерная программа рассматривается как молекулярный цифровой организм. В Ау1ёа молекулярный цифровой организм снабжается счетчиком внутренней энергии, значения которого переводятся в единицы

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

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

Важно отметить, что случаев самозарождения программ среди хаотической последовательности байт памяти виртуальной ЭВМ не отмечено. Для начала эволюционного процесса необходим «Первопредок», т.е. некоторая исходная программа, обладающая способностью к самокопированию.

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

- ограниченные возможности ассемблера, на котором кодируются программы-организмы;

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

- второстепенная роль данных в памяти.

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

3 Модель программной системы как кинетического континуума каталитических реакций

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

Операционное устройство выполняет следующие функции:

- замещает молекулы, находящиеся в пространстве камеры реактора, молекулами, поступающими из входного резервуара; замещаемые молекулы поступают в выходной резервуар;

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

Пространство камеры реактора будем рассматривать как линейное клеточное. Оно является аналогом памяти виртуальной ЭВМ. Как и в модели Ау!ёа, в качестве энергии будем рассматривать время работы операционного устройства. Энергия, или процессорное время, является необходимым ресурсом, от наличия которого зависит возможность выполнения реакции.

Будем считать, что вещества в модели могут быть как простыми, так и сложными. Молекулы простых веществ одноатомны, молекулы сложных веществ состоят из нескольких атомов (одинаковых или различных) и представляют собой линейные структуры произвольно большой длины, в том числе макромолекулы. Поскольку пространство памяти клеточное, будем полагать, что каждая клетка соответствует одному байту памяти и может содержать один атом. Следовательно, в модели присутствует 28 различных видов атомов, которые и образуют «таблицу Менделеева».

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

Наиболее вероятным состоянием вещества в пространстве объема реактора является неупорядоченное, характеризующееся максимальным значением энтропии 5тах . Под термином «энтропия» будем понимать энтропию Шеннона. Общую неупорядоченность пространства нарушают структуры -устойчивые пространственно-временные образования в виде макромолекул, представляющих структуры данных и программы.

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

В модели будем различать два основных вида молекул, которым присущи разные степени химической активности:

- пассивные молекулы-реагенты;

- катализаторы.

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

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

А Х, е > В ,

где А - субстрат; В - продукт реакции; X - катализатор; е - энергия.

Разновидностью каталитической реакции является автокатализ. Автокатализаторы обладают способностью к увеличению своей численности после вступления в реакции:

А X + В .

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

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

Bi —Х,£l > Bi + е2, Bi е B, ei < е2 .

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

Следующим шагом является введение в модель матричных процессов синтеза. Молекулярный цифровой организм в этом случае может быть представлен как совокупность фенотипа и генотипа. Фенотип представляет собой комплекс из макромолекулы-катализатора в сочетании с высокоэнергетич-ными соединениями. Генотип задается линейной структурой, или цифровой ДНК, которая служит матрицей для построения цифрового организма. Матричный процесс синтеза и основная реакция катализа обобщенно описываются уравнениями:

Comp + D + M———> X ;

A Х, е >M

где X - цифровой организм; Comp - множество программных компонентов; D - элементы данных; M - цифровая ДНК, являющаяся матрицей для построения нового цифрового организма (аналогов РНК в данной модели нет); M' - копия матрицы M , модифицированная в результате ошибки копирования или выполнения генетической операции; P - системный процесс-построитель, определяющий допустимость создания нового цифрового организма на основе заданной матрицы с точки зрения безопасности, и в случае положительного решения компонующий новый цифровой организм в соответствии с матрицей цифровой ДНК.

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

{Бот.}. + М ——^>X ,

где {Бот.}. - множество всех возможных доменов значений для всех локу-

сов цифровой суперхромосомы.

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

Предложенная модель позволяет описать программную систему как неравновесный объект в виде кинетического континуума каталитических, авто-каталитических и матричных реакций образования-распада связей между данными и программными единицами. Следовательно, в данной модели возможны процессы самоорганизации континуального (синкретического) типа, а значит, и прогрессивная эволюция. Кроме того, каталитические реакции, задаваемые уравнениями (3), (5) и (6), образуют гиперцикл [8], что также может служить критерием возможности самоорганизации в модели.

Заключение

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

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

- иерархичность - любая структура может рассматриваться как компонент более высокого уровня;

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

- ограниченность времени существования структур;

- неравновесность - каждый акт обработки данных рассматривается как работа против равновесия; также отсутствует равновесие между реакциями образования и распада связей;

- антиэнтропийная направленность внутрисистемных процессов, приводящая к образованию структур и уменьшению энтропии;

- мультистабильность, неустойчивость стационарных состояний и удаление от равновесия в случае малых возмущений;

- открытость и диссипативность;

- присутствие матричных процессов;

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

Аналогия с каталитическими реакциями позволяет использовать уже

существующие математические модели [2, 3] для предсказания и исследования свойств программных систем, построенных в соответствии с предложенной парадигмой.

Список литературы

1. Руденко, А. П. Самоорганизация и синергетика / А. П. Руденко. - Режим доступа: http://utc.uni-dubna.ru/~mazny/students/site2/ideal_2.htm.

2. Эбелинг, В. Образование структур при необратимых процессах: Введение в теорию диссипативных структур / В. Эбелинг. - М. ; Ижевск : Институт компьютерных исследований, НИЦ «Регулярная и хаотическая динамика», 2004. - 256 с.

3. Эбелинг, В. Физика процессов эволюции / В. Эбелинг, А. Энгель, Р. Файстель ; пер. с нем. Ю. А. Данилова. - М. : Эдиториал УРСС, 2001. - 328 с.

4. Галимов, Э. М. Феномен жизни: Между равновесием и нелинейностью. Происхождение и принципы эволюции / Э. М. Галимов. - Изд. 3-е. - М. : Книжный дом «ЛИБРОКОМ», 2009. - 256 с.

5. Dittrich, P. Artificial Chemistries - A Review / P. Dittrich, J. Ziegler, W. Banzhaf // Artificial Life. - 2001. -№ 7 (3). - P. 225-275.

6. Эвери, Д. Теория информации и эволюция / Д. Эвери. - М. ; Ижевск : НИЦ «Регулярная и хаотическая динамика», Институт компьютерных исследований, 2006. -252 с.

7. Кольчугина, Е. А. Модель эволюционирующего программного обеспечения / Е. А. Кольчугина // Известия высших учебных заведений. Поволжский регион. -2006. - № 6 (27). - 2006. - С. 78-86. - (Технические науки).

8. Эйген, М. Гиперцикл: принципы самоорганизации молекул / М. Эйген, П. Шустер. - М. : Мир, 1982. - 272 с.

Кольчугина Елена Анатольевна

кандидат технических наук, доцент, кафедра математического обеспечения и применения ЭВМ, Пензенский государственный университет

E-mail: kea@pnzgu.ru

Kolchugina Elena Anatolyevna Candidate of engineering sciences, associate professor, sub-department of computer application and software, Penza State University

УДК 004.42 Кольчугина, Е. А.

Неравновесное программирование / Е. А. Кольчугина // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2009. -№ 3 (11). - С. 25-31.