ЭВОЛЮЦИОННЫЙ СИНТЕЗ ДИНАМИЧЕСКИХ СИСТЕМ УПРАВЛЕНИЯ
Эволюционные вычисления (ЭВ) – класс алгоритмов, использующих принципы естественной эволюции для решения задачи поиска экстремумов многоэкстремальной функции многих аргументов. Данное направление зародилось в 60-х годах прошлого века. Были выделены необходимые и достаточные условия эволюционного развития: наследственная изменчивость, конкуренция и отбор [1]. Были предложены алгоритмы на биологической основе [2] и модели автоматов, способных приспосабливаться к окружающей среде [3], а также выдвинут принцип замены моделирования объекта моделированием его эволюции [4]. Большое распространение получили генетические алгоритмы (ГА) [5, 17]. Используя различные подходы, авторы стремились приспособить природные принципы эволюции для решения практических задач, упрощая генетическую основу и оперирующие с ней алгоритмы до уровня реализуемой на компьютере модели. При сохранении общего принципа кодирования решений, развитие ЭВ шло по пути усложнения генетических операторов, способов отбора и организации особей в популяции. При этом, именно в последние 40 лет получила революционное развитие молекулярная генетика [6], появились подходы к системной интерпретации молекулярно-генетических процессов [7, 8], а также на порядки выросли вычислительные возможности компьютерной техники. Возникли предпосылки для расширения возможностей ЭВ, для выхода с уровня оптимизации на уровень имитации видообразования, синтеза новых структур. Это потребовало повторного обращения в сферу естественнонаучных знаний, анализа генетических систем и построения более сложной эволюционной модели. В данной статье, на основе математической модели биохимических процессов, предлагается класс эволюционных алгоритмов, особенностью которых является новый подход к кодированию решений и процессу интерпретации генетической информации. Описывается структура модели, рассматриваются результаты её применения для решения задачи синтеза динамической системы управления.
Рассмотрение биохимической модели клеточного управления
Живая клетка является элементарной биосистемой, поддерживающей исполнение генетической программы. Интерпретация записанной в геноме информации состоит из процессов транскрипции, и трансляции. В результате транскрипции образуются молекулы РНК, участвующие затем в трансляции — синтезе полипептидов, из которых затем образуются белки. Белки участвуют почти во всех клеточных процессах. Их активность можно разделить на следующие типы:
— обеспечение интерпретации генетической информации
— обеспечение репликации генома
— обеспечение метаболизма
— обеспечение физиологических процессов
— иммунная функция
— рецепторная функция
— управление онтогенезом
Кроме того, белки выступают в роли строительного материала, а также секретируются во внешнюю среду.
Управляющая функция белков связана со следующими проявлениями белковой активности:
1. Ферментативный катализ. Ферменты катализируют и ингибируют протекание реакций. Количество вещества катализатора в результате реакции не изменяется. Для ферментов существует предельный уровень концентрации Cmax, после которого повышение его концентрации не влияет на скорость реакции. Эволюционно сложилось так, что концентрация фермента варьирует в диапазоне 0<Cф<Cmax. То есть, управляя концентрацией фермента, клетка управляет скоростью протекания реакции.
2. Участие в транскрипции, трансляции и репликации. Считывание генетической информации, как и процесс копирования её носителя, осуществляется при участии обязательных и вспомогательных белков. Данный тип реакций также можно назвать ферментативным синтезом, но более сложным, чем простой катализ из предыдущего пункта. Обязательные для процесса считывания белки связываются в комплекс, который обеспечивает проистекание процесса, а вспомогательные существенно влияют на его скорость, связываясь с сигнальными последовательностями молекулы ДНК.
3. Внешний интерфейс. Мембранные белки осуществляют рецепторные и транспортные функции меж клеткой и средой. Рецепторные белки являются глазами и ушами клетки. Специфичные к различным факторам, они переводят их на внутренний химический язык клетки, вызывая цепь реакций с участием сигнальных белков, позволяющих клетке адаптироваться к воспринимаемым внешним факторам. [7, 8, 13]
Рассмотрим математические модели некоторых клеточных реакций. Для графического отображения схем реакций введём следующие обозначения:
Количество i-го белка в среде.
Рост количества белка со скоростью a.
1. Катализируемый синтез с накоплением продукта.
Механизм каталитической активности фермента состоит в образовании временных комплексов «молекула фермента + молекула субстрата». После того, как молекула субстрата прореагирует, фермент освобождается и переходит в исходное состояние. Средняя частота участия молекулы фермента в подобной реакции характеризуется коэффициентом активности фермента k. Таким образом, скорость образования катализируемого белка пропорциональна количеству молекул фермента и его активности. Природная зависимость несколько отлична от линейной зависимости, однако, для описываемой модели различие не существенно.
Рис. 1 Схема реакции катализируемого синтеза.
— количество фермента.
— количество продукта катализируемой реакции
— коэффициент активности фермента
Скорость изменения количества продукта реакции описывается следующей формулой:
Аналогом такой реакции может служить простой ферментативный синтез некоторого вещества, например превращение бактерией галактозы в промежуточный продукт с целью дальнейшего извлечений энергетической пользы. может также способствовать проникновению галактозы в клетку, и реакция будет описываться аналогичной формулой. Это также может быть синтез белка с матрицы информационной РНК или синтез этой РНК с матрицы ДНК, и в этих случаях является ферментом соответствующей функции.
Поскольку,
,
являет собой интегральную величину от функции количества фермента 
. Эта зависимость будет учтена при построении модели эволюционного поиска, которой посвящена данная статья.
2. Катализируемый синтез с расходованием продукта.
Как правило, первый тип реакции в живых системах практически не встречается, поскольку всякий продукт либо используется затем для внутренних нужд клетки, либо секретируется во внешнюю среду, либо деградирует и разлагается. Скорость реакций понижения концентрации вещества пропорциональна количеству этого вещества, а также зависит от причины этого понижения, для учёта которого введём коэффициент 
.
Рис. 2 Схема реакции катализируемого синтеза расходуемого продукта.
— количество фермента.
— количество продукта катализируемой реакции
— коэффициент активности фермента
— коэффициент скорости удаления продукта из среды
В такой реакции скорость изменения продукта описывается следующей формулой:
Приняв, что =const, получим решение для :
,
где 
— исходное количества вещества . Допустив, что до начала реакции, концентрация = 0, можем принять в момент 
концентрацию 
. Откуда имеем:
При этом, поскольку связь 
является отрицательной, учтём, что 
. Таким образом,
,
откуда видно, что 
при 
со скоростью, пропорциональной 
.
Прототипом этого класса реакций является синтез промежуточного вещества, в многоступенчатой реакции, каждый этап которой катализируется своим ферментом. Это может быть этап утилизации органического вещества, синтез секретируемого белка или промежуточной формы РНК, подвергающейся затем процессингу и трансляции.
3. Параллельный катализ.
Экспрессия генов управляется множеством факторов, включающих или выключающих транскрипцию некоторой группы генов, либо ускоряющих или замедляющих, порой на несколько порядков, данный процесс. Сигнальные последовательности генов, с которыми связываются эти факторы, имеют с ними различную степень родства, что делает возможным ситуацию, когда один фактор влияет на транскрипцию различных групп генов с разными скоростями.
Рассмотри модель:
Рис. 3 Реакция одновременного катализа разных продуктов.
— количество фактора одновременного синтеза и 
.
— количество первого продукта реакции
— количество второго продукта реакции
— коэффициент влияния фактора на образование первого продукта
— коэффициент влияния фактора на образование второго продукта
— коэффициент скорости удаления первого продукта из среды
— коэффициент скорости удаления второго продукта из среды
Уравнения скоростей изменения концентрации продуктов:
,
откуда, с учётом 
, 
, , 
, получаем:
,
Рассмотрим область пространства параметров реакции, образуемого множеством значений параметров , , , , такую, что выполняются условия 
, и 
. Если коэффициенты системы принадлежат этой области, то при длительном неизменном значении устанавливается состояние равновесия, при котором значения и приблизительно равны 
, где 
.
Предположим, что в момент времени , которому предшествовало состояние равновесия, значение изменилось на величину 
. Примером подобного изменения является проникновение в клетку молекул гормона, происходящее за время много меньшее, чем реакция клетки на это изменение.
Рассмотрим динамику реакции модели на указанное изменение, приняв для простоты k=1. В момент времени 
значения P равны: = = . В момент времени 
=
, (1)
= 
=
(2)
Затем, в течение некоторого промежутка времени до момента 
, значения P практически уравниваются, при чём, скорость стремления функций 
и 
к новому значению зависит от коэффициентов и :
Рис. 4. Графики изменения концентраций , , для модели на рис. 3.
Проинтегрируем функцию разности между функциями и на промежутке от момента изменения до момента установления равновесия, когда 
. Поскольку,
,
,
в соответствии с (1) и (2) запишем
.
Таким образом, для модели:
Рис. 5 Модель параллельного катализа с вычислением величины изменения
в пространстве коэффициентов k существует подмножество, для которого справедливо, что значение 
пропорционально изменению значения :
Рис. 6. Графики изменения концентраций , , , для модели на рис. 5.
Таким образом, несложная модель, построенная по аналогии с основополагающими типами клеточных реакций, обладает способностью вычислять интегральные характеристики внешних сигналов и дифференциальные характеристики их изменения. Активность живой клетки состоит из процессов управления по принципу обратной связи на основе значений концентрации веществ — участников множества параллельно и последовательно протекающих химических реакций. Описанный принцип математической формализации биохимических процессов предлагается положить в основу модели эволюционного синтеза систем управления.
Генетическая изменчивость, вносят случайные исправления в геном, что корректирует параметры соответствующего биохимического вычислителя: меняются сигнальные последовательности генов, чуткость их к определённым белкам и сила влияния на скорость транскрипции гена, изменяются кодирующие последовательности, задающие свойства белков, активируется и дезактивируется транскрипция генов. Ничтожные изменения, связанные с заменой лишь одного нуклеотида ДНК, участвуют в виде изменённых белков во множестве реакций, усиливаются, значительно проявляясь в биохимической картине, а следовательно в свойствах клетки. Благодаря отбору, неудачные варианты организмов отсеиваются, а проявляющие адекватные реакции на условия среды, оставляют потомство.
Изменения на клеточном уровне неизбежно отражаются на организации многоклеточных организмов, поскольку именно клеточная активность определяет векторы формообразования в процессе онтогенеза, и все высокоуровневые свойства взрослой особи. С уровня макрообъектов, образующих условия среды существования многоклеточного организма, сигналы передаются на клеточный, биохимический уровень, и пройдя вычислительную обработку, в виде сигналов управления вновь поднимаются на макро-уровень.
В настоящей работе рассматривается эволюционная модель, в основу которой положена интерпретация генетической информации по аналогии с биохимическими процессами живой клетки. В следующих разделах статьи подробно излагается сущность генетической модели, приводятся описание и результаты эксперимента по эволюционному синтезу системы управления.
Принципы построения эволюционной модели.
Всякая задача управления состоит в восприятии входного множества анализируемых факторов, в обработке значений их значений, и синтезе на их основе сигналов управления.
Клетка, как элементарная живая система, в качестве входных сигналов воспринимает проникающие в цитоплазму молекулы как таковые, либо опосредованно, через изменённую воздействием внешних химических и физических факторов конформацию рецепторных и сигнальных белков. Управляющими сигналами, компенсирующими возмущающий фактор, являются определённые вещества, синтезируемые в клетке и распределяемые по внутренней среде, либо секретируемые во внешнюю. Например, присутствие галактозы в среде у некоторых видов бактерий детектируется мембранным белком, запускающим обширную сеть реакций, в результате которых в клетке синтезируется ряд белков, один из которых поступает на мембрану и транспортирует галактозу во внутреннюю среду, а остальные — обеспечивают превращение её в энергетические молекулы.
В случае с многоклеточными организмами, управление приобретает межклеточный характер. У растений — за счёт секреции гормонов в межклеточную жидкость, у животных — за счёт активности нервной, иммунной и эндокринных систем.
В данной части статьи описывается принципы организации моделей эволюционного поиска, задачей которых является синтез управляющих систем, действующих по аналогии с живой клеткой.
К эволюционной модели, имитирующей возникновение и изменчивость генов клетки и соответствующей биохимической среды, предъявляется критерий структурной и вычислительной простоты. Действительно, невозможно учесть все нюансы и тонкости химических процессов, не сделав модель громоздкой. Стоит задача предельно простыми средствами выразить сущность эволюционных возможностей природы, а именно поиск и сохранение эффективных путей управления на основе биохимической модели.
Модель разрабатывалась в соответствии с двумя принципами:
1. Всякая информация возникает как элементарный случайный выбор. Постепенное усложнение системы осуществляется за счёт закрепления полученных случайно и повышающих эффективность управления связей между параметрами.
2. Любой параметр системы может служить информацией для управления, и любой параметр, кроме входных, может быть управляем.
Синтезируемая в рамках модели управляющая система представима в виде графа, вершины которого описываются тремя множествами: 
, 
, 
— входных, управляющих и внутренних параметров соответственно. Рёбра описываются множеством K, максимальный объём которого равен 
, где l, m, n — объёмы указанных множеств. Состояние системы управления характеризуется значениями элементов множества X. Множество генов G особи полностью определяет множества X и K. Таким образом, множество G составляет геном клетки, множества , , — соответствующую биохимическую систему. Каждый вновь возникающий ген определяет пару параметров и коэффициент влияния между ними.
Элементы множества K описывают взаимное влияние параметров системы друг на друга. Характер влияния — линейное изменение количественной характеристики параметра, пропорциональное величине источника влияния, 
, где 
— величина i-го параметра, а 
— коэффициент влияния j-го параметра на i-й параметр. Сложность системы характеризуется количеством параметров и связей между ними. Данная модель, как было показано в первой части, имитирует взаимные каталитические отношения между полипептидами и полинуклеотидами клетки.
У системы есть два пути количественного роста, связанные с увеличением объёма множества внутренних параметров:
1. Каждый вновь возникающий коэффициент связи 
пополняет, в соответствии со вторым принципом, число внутренних параметров системы.
2. Число внутренних параметров системы растёт вне зависимости от возникновения новых коэффициентов , за счёт простого увеличения объёма n множества внутренних параметров. Элементы множества K являются в данном случае константами, не изменяемыми в процессе управления.
Верхняя граница сложности в обоих случаях отсутствует.
Введём параметр V, характеризующий объём элементарных различимых путей усложнения системы управления. Параметр V влияет на количество вычислительного времени, требуемого для процесса эволюционного поиска.
Объёмы множеств I и O задаются условиями задачи, для которой эволюционно создаётся система управления. Поэтому, усложнение системы управления происходит за счёт увеличения объёма множества X внутренних параметров, а также заселения множества K возможных связей. Множество Х неограниченно по объёму, однако, вновь созданные его элементы не участвуют в процессе управления до тех пор, пока элементы множества K не соединят их связями с целой системой управления. Поэтому объём способов усложнения системы определяется по формуле
,
где 
— максимальное количество связей, а K — количество существующих.
Чтобы учесть возможность увеличения объёма множества X, будем считать его объём на единицу большим.
Рис. 7 Матрица связей между параметрами управляющей системы, усложняющейся по второму пути.
.
Эта формула справедлива для второго пути усложнения, поскольку для первого следует учесть, что вновь появившиеся коэффициенты связи пополняют число вершин графа:
Рис. 8. Матрица связей между параметрами управляющей системы, усложняющейся по первому пути.
Поскольку, в соответствии с первым принципом, всякая информация возникает как случайный выбор, параметр V для второго пути усложнения растёт линейно, а для первого — экспоненциально. Во втором случае вероятность увеличения матрицы связей равна 
, тогда как в первом случае это не вероятность, а определённость.
Очевидно, что в первом случае, с увеличением объёма множества связей K по сравнению с суммарным объёмом множеств I, O, X, среди вновь возникающих связей растёт доля таких, которые связывают не значения вершин, а значения коэффициентов существующих связей. Это обстоятельство требует большей сложности от механизма эволюционного поиска, поскольку увеличение параметра V значительно снижает эффективность поиска, хотя увеличивает сложность найденных зависимостей. Эта проблема решается введением механизма предпочтения одних направлений усложнения эволюционирующей системы в сравнении с другими. Исследованию возможностей данного варианта модели проводится в других работах.
Сия же работа посвящена исследованию эволюционной модели, синтезируемые в которой системы усложняются по второму пути.
Описание эволюционной модели.
Рассмотрение модели будет происходить по принципу снизу-вверх. Будут определены понятия гена, генома, особи, популяции и внешней среды. Затем будут описаны операции, производимые в модели над сущностями каждого уровня.
Ген. На химическом уровне природный ген представляет собой участок ДНК, включающий кодирующие и сигнальные области. Сигнальные области отвечают за транскрипцию гена и скорость этого процесса. Для каждого гена существует группа веществ, родственных сигнальным последовательностям, либо функционально необходимых для процесса транскрипции. Кодирующие области гена определяют полипептидную последовательность белка, образующегося в результате процессов транскрипции и трансляции. С целью сохранения свойственных клеточной среде зависимостей между концентрациями веществ, описанных в первой части, а также с учётом рассуждений второй части, была выбрана следующая модель гена:
, 
=
,
, 
=
,
В процессе моделирования, ген описывает изменение количества b-го вещества в зависимости от концентрации a-го по формуле:
,
где 
— коэффициент устойчивости белка, обратный скорости его естественной деградации. Его значение может быть равно 1, однако, эмпирически было установлено, что эффективность методики повышается в случае, если это значение чуть меньше единицы. Это связано с тем, что член 
, характеризующий концентрацию катализатора, часто становится очень мал, поскольку возникают гены, постоянно увеличивающие количество незначащего белка, что сводит к нулю более тонкие управляющие воздействия автоингибируемых белков. Указанная мера противодействия паразитным каталитическим реакциям является биологически адекватной и наиболее простой из существующих в природе. Накоплению незначащих генов противостоит система генетических операторов, включающая в себя оператор делеции случайного гена.
Описанная модель позволяет отразить основные типы зависимостей в клеточной среде:
— отношения между сигнальными белками, реагирующими на факторы среды и уровнем экспрессии определённых генов,
— отношения между концентрацией веществ, влияющих на транскрипцию, и скоростью синтеза продукта транскрипции,
— отношения между концентрацией определённых ферментов и скоростью синтеза продукта катализируемой ими реакции.
Создание новых генов состоит в случайном выборе значений a и b из диапазонов [1 .. (l+m+n+1)] и [1 .. (m+n+1)] соответственно (см. рис. 7). Первый диапазон адресует элементы множеств I, O, X, второй — элементы множеств O, X. Выбор n+1 элемента множества X увеличивает объём этого множества на 1. Коэффициент влияния k выбирается из диапазона [-1 .. 1], хотя в результате мутаций 
может быть >1.
Передаваемые по наследству гены могут претерпевать мутации, в результате которых может измениться любой из трёх параметров гена.
Геном. Множество генов одной особи, хранящих информацию о её свойствах и совокупно влияющих на процесс её функционирования, образуют геном.
Геном передаётся по наследству от предков к потомкам, претерпевая при этом относительно небольшие изменения в слагающих его генах, заключающиеся в добавлении одного или нескольких случайно сформированных генов, либо исключении или мутационном изменении одного или нескольких случайно выбранных генов.
Особь. Особь представляет собой объект, функционирующий под управлением генома в некоторой среде, имитирующей естественные условия прототипа объекта. В процессе функционирования оценивается, в соответствии с предъявленными критериями, степень эффективности управления.
Особь взаимодействует с внешней средой посредством «интерфейса», то есть связи определённых параметров особи с соответствующими факторами внешней среды. Интерфейс определяет множества I и O, входной информации и управляющих сигналов, на основе и посредством которых геном осуществляет управляющую функцию. Например, для бактериальной клетки входная информация представлена множеством мембранных и сигнальных белков, отражающих свойства среды, такие как температура, солёность, кислотность, концентрация определённых молекул и т. п. Будучи выражены на языке внутренней биохимии клетки, факторы влияют на экспрессию определённых генов, продукты которых являются управляющим ответом на факторы среды. Это могут быть молекулы, стимулирующие метаболизм, дрожание локомотивных отростков, секрецию слизи, деление клетки и т. п.
Функционирование особи в описываемой модели состоит в синтезе, под управлением генома и в зависимости от внешних факторов, множества «веществ» — внутренних параметров, принадлежащих множеству Х — концентрации которых являются функцией от множества связей между ними и множества значений входных и управляющих параметров.
Вероятности размножения и гибели особи зависят от коэффициента успешности функционирования её в среде. Гибель состоит в удалении особи из популяции. Размножение в данной модели реализовано на основе бесполого деления клеток.
Популяция. Множество особей одного вида образуют популяцию. В описываемом варианте модели особи могут являться «родственниками», имея общего предка, однако, в отсутствие полового размножения, отсутствует и процесс обмена участками генома между особями, каковое условие входит в определение биологической популяции. Здесь особи объединены в популяцию с целью выявления относительного коэффициента эффективности особей. Это позволяет реализовать конкурентную борьбу между особями, и регулировать их численность.
Возникновение функциональных групп генов
Формирование начальной популяции состоит в создании множества особей, каждая из которых получает небольшой набор случайным образом созданных генов. Поскольку, количество генов и связей между ними не ограничено сверху, возникают трудности с подходом к описанию пространства вариантов в виде многомерного пространства по числу параметров особи. Фазовое пространство Эйнштейна прекрасно подходило для исследования частиц с фиксированным числом степеней свободы, определяющих размерность пространства. Особи же модели имеют разные наборы генов и существуют в различных и несравнимых пространствах отличающейся размерности. Поэтому, подход к анализу характеристик эволюционного развития приходится усложнить. Основу подхода составляет концепция квазивидов Эйгена [9, 10] и рассуждения из первой части статьи.
Эволюционный процесс в популяции приводит к образованию квазивидов. Квазивид — множество родственных особей, группирующихся близ одной стратегии функционирования. За поддержание этой стратегии отвечает подмножество генов особи, которое назовём функциональной группой (ФГ). Функциональная группа включает в себя ансамбли генов, обрабатывающие входные сигналы и формирующие выходные, по принципу обратной связи управляющие некоторым аспектом функционирования особи в среде. ФГ возникают на основе случайным образом установленной закономерности, контура обратной связи, обеспечивающего «осмысленную» реакцию на фактор, активизирующий данную связь. Функциональная группа состоит из фиксированного числа необходимых для её обеспечения генов и произвольного числа дополнительных, исключение которых из генома не разрушит функциональной группы. Например, на рис.5 представлена группа из четырёх генов, обеспечивающих воспроизведение данной группой дифференциальной величины функции изменения некоторого параметра. Подобная группа генов может служить частью функциональной группы, обеспечивающей обратную связь по анализируемому параметру.
Поскольку, число необходимых для существования ФГ число генов фиксировано, для анализа ФГ мы можем применить метод фазового пространства. В пространстве, образованном значениями коэффициентов влияния, необходимых для поддержания функциональной группы генов, существует притягивающий аттрактор, отвечающий оптимальному функционированию данной группы. Мутационный процесс этих генов способствует движению точки ФГ в пространстве параметров в направлении аттрактора.
Процесс эволюции в описываемой модели состоит из:
— отыскания комбинации генов, образующих функциональную группу
— оптимизации её, и распространения на всю популяцию благодаря преимуществам
— поиска новых ФГ и постепенного присоединения их к существующим, если таковое способствует повышению эффективности поведения
— возникновения мета-функциональных групп, отвечающих за «переключение» различных ФГ в различных условиях среды, выстраивающих иерархию ФГ.
Таким образом, реализующийся в описываемой эволюционной модели синтез управляющих систем включает в себя два генетических процесса, протекающих параллельно. Подмножество генов, не вовлеченных в ФГ, участвует в поиске таковых в неограниченном пространстве вариантов. Гены, образовавшие ФГ, подвергаются процессу оптимизации, укладывающемуся в процесс оптимизации классических генетических алгоритмов. Оба процесса, синтез ФГ и их оптимизация, реализуются на едином базисе эволюционной модели, включающем в себя организацию и интерпретацию генов, а также набор операторов, действующих на всех уровнях организации эволюционного процесса: популяции, особи, генома и генов.
Подробный теоретический анализ концепции функциональных групп выходит за рамки статьи и ему посвящена другая работа. В настоящей работе будут перечислены эволюционные операторы, описанием которых завершится третья часть статьи, а в четвёртой будут описаны эксперимент, поставленный на основе модели, и полученные результаты.
Внешняя среда и модель объекта управления. Для проведения эволюционного поиска системы управления требуется модель управляемого объекта, существующая в некоторой среде, имитирующей условия существования прототипа.
Рис. 9. Схема управляемого объекта и его взаимодействия со средой
Параметрами управляемого объекта определяется множество входных параметров системы управления. Функциональные возможности объекта управления задают множество параметров управления.
Эволюционные операторы. Эволюционный процесс состоит в последовательном применении к иерархии сущностей модели эволюционных операторов, осуществляющих процессы наследственности, изменчивости, анализа и отбора. Эволюционные операторы также составляют иерархию. Операторы нижнего уровня обеспечивают выполнение операторов верхнего уровня. Цикл применения эволюционных операторов продолжается до тех пор, пока не будет удовлетворён критеий эволюционного поиска.
Рис. 10. Схема эволюционных операторов для модели бесполого размножения
Операции над генами. Ген описывается тремя параметрами: Генетические операторы при бесполом размножении сводятся к изменению каждого из параметров.
— Изменение коэффициента катализа k
,
где 
вычисляется по закону нормального распределения, 
, максимум функции в точки =0.
— Изменение номера параметра-катализатора
— Изменение номера параметра-продукта
Значения a и b выбираются случайно из множеств и соответственно.
Операции над геномом.
— Мутации
Случайно выбранный ген подвергается действию одного или нескольких генетических операторов.
— Делеции
Случайно выбранный ген изымается из генома
— Инсерции
К геному добавляется случайно созданный новый ген.
Операции над особями.
— Выяснение пригодности
Особь, являя собой систему управления, участвует в имитации процесса управления моделью объекта в соответствующей среде. На основе результатов управления, особи присваивается коэффициент пригодности по абсолютной шкале.
— Размножение.
Особь оставляет потомство, над геном которого подвергается изменчивости путём воздействия на него геномных операторов.
— Удаление.
Особь уничтожается.
Операции над популяцией.
— Анализ популяции в условиях среды.
Все особи подвергаются проверке «способностей», и на основе полученных абсолютных коэффициентов пригодности, выясняется их относительная пригодность в диапазоне [0..1], где 0 соответствует худшему результату, а 1 — лучшему.
— Отсев старых и менее приспособленных.
Каждая особь имеет характеристику «возраст», равную нулю при появлении новой особи, и возрастающую с каждым новым циклом. У «старых» особей выше вероятность быть отсеянными. Если особь демонстрирует хорошее значение относительной пригодности, то может просуществовать в популяции 10-20 циклов, оставив большое количество потомства. Порог отсева повышается если численность популяции выше предустановленного среднего значения и понижается в обратном случае.
— Получение нового поколения.
Вероятность оставить потомство пропорционально коэффициенту относительной пригодности и обратно-пропорционально величине популяции.
Описание эксперимента и результатов
В качестве экспериментальной задачи был выбран простейший вариант управления, 
, 
: управляемый объект предоставляет системе управления один входной параметр и управляется через один управляющий параметр.
Условия задачи: Объект движется с постоянной горизонтальной скоростью в ограниченном сверху и снизу пространстве типа «коридор», имеющем спуски, подъёмы и крутые изломы. Вертикальная скорость объекта является функцией от ускорения свободного падения g=const, направленного вниз, и силы F, прилагаемой к объекту в противоположном направлении. Величина усилия F вычисляется системой управления объекта, на вход которой поступает текущее значение высоты h до нижней границы коридора. Прикосновение объекта к нижней, либо верхней границе, считается его уничтожением. Требуется создать систему управления, обеспечивающую сколь угодно долгое движение по коридору без падений и столкновений.
Рис. 11. Внешняя среда и объект управления.
В начальный момент эволюционного поиска система управления не содержит никаких генов, так что усилие F=0. Очевидно, что задача окажется решённой тогда, когда система генов реализует две компоненты усилия F, противостоящего снижению высоты полёта. Мгновенное значение первой должно быть равно 
, а значение второй должно быть пропорционально изменению значения высоты 
.
Начальная популяция создаётся из множества особей, чей геном формируется из случайным образом созданных генов в количестве [2..20]. После чего начинается циклическое применение к популяции эволюционных операторов, описанных в предыдущей части. Всякое новое испытание особей проводится на случайно созданном варианте коридора с фиксированным максимальным значением кривизны изгибов.
Абсолютным критерием пригодности является горизонтальное расстояние, на которое особь успела продвинуться до момента столкновения с верхней или нижней стенкой.
Рис. 12. Фрагменты коридора. Красная линия — траектория особи.
а. Без управляющих воздействий.
б. Под управлением генотипа с возникшей, но не оптимизированной функциональной группой, связывающей dh и усилие F.
Рис. 13. Системы управления для объектов, чьи траектории изображены на рис. 12
Синим выделены внутренние параметры, образующие функциональную группу.
После возникновения в популяции функциональной группы, обеспечивающей обратную связь по высоте полёта, множество особей, образующих квазивид относительно данной функциональной группы, эволюционирует, фокусируясь многомерным облаком вокруг области оптимального значения параметров, что приводит к появлению особей, способных практически неограниченно двигаться в коридоре, соответствующей кривизны.
Рис. 14. Траектория особи под управлением оптимизированной функциональной группы.
Колебательный характер движения ожидаем, поскольку в системе управления отсутствует параметр с неизменным значением, чьё влияние могло бы быть передано на управляющий параметр F, и модулироваться затем обратным значением высоты полёта. Напротив, система имеет на входе лишь переменное значение высоты полёта, и вынуждена приспосабливаться к тому, чтобы компенсировать изменение данного параметра. Это требует синтеза системы извлечения дифференциального значения, возможность чего в рамках модели обоснована в первой части, и с чем эволюционная модель легко справляется.
Для эксперимента с параметрами
— средняя величина популяции 50 особей
— количество поколений 600,
вероятность нахождения удовлетворяющей критерию поиска системы управления составляет >90%.
Рис. 15. График прогресса эволюционного поиска. L — длина пути, N — номер поколения. Зелёная кривая — лучший результат популяции. Красная — средний по популяции. В 200 поколении возникла эффективная функциональная группа, в 323 найдено удовлетворяющее критерию соотношение коэффициентов.
Уровень мутационной изменчивости выбран такой, чтобы популяция имела возможность выходить из локальных оптимумов, связанных с неэффективными ФГ.
Выводы
В работе был описан класс эволюционных моделей и экспериментально исследованы возможности одного из простых вариантов среди принадлежащих данному множеству моделей. Результаты эксперимента подтверждают принципиальную возможность модели к адекватному описанию управляющей системы для простых условий существования управляемого объекта. Планируются также эксперименты с более сложным поведением управляемого объекта, с большим числом входных и управляющих сигналов. Например, строится модель синтеза системы управления для самонаводящейся ракеты, учитывающей слежение за маневрирующей целью и избегание ложных целей.
Основной вывод — возможность перехода эволюционных моделей от задачи оптимизации к задаче синтеза систем. В одной из ранних работ [18] был описан эксперимент, использующий описанную модель для эволюции искусственной многоклеточной флоры. В условиях, имитирующих земную поверхность, освещённую солнцем, наблюдался процесс поиска формы у конкурирующих организмов. У многоклеточных особей наблюдалась дифференциация клеток, возникновение и закрепление на генетическом уровне конкурентоспособных принципов организации кроны и корневой системы. Это открывает два полюса возможностей: создания методик эволюции совместного поведения множества агентов, а так же эволюционного поиска пространственных параметров материальных объектов.
Поведение живых существ, в частности разумная деятельность человека, связано с планирования действий на основе модели текущей ситуации и модели себя. Описанная в статье модель эволюционного поиска могла бы послужить основой для разработки принципов адаптивного поведения и принятия решений в режиме реального времени у мобильных роботов, способных на основе воспринимаемых сигналов строить модель ситуации. Эволюционные поиск системы управления собственной модели в рамках модели ситуации при существовании критериев, определяемых целью поведения, приблизил бы внутренние вычисления роботов к происходящим в мозгу животных и человека.
Кроме того, модель позволяет планировать развитие экономических субъектов, получая в качестве входных параметров количественные характеристики экономической среды, и формируя затем управляющую систему, в виде управляющих воздействий на субъект, представляющую стратегию развития в данных условиях.
Литература
1. Шмальгаузен вопросы биологии. Новосибирск: Наука, 1968, -224 с.
2. Расстригин методы поиска. – М.: Наука, 1968
3. Цетлин по теории автоматов и моделированию биологических систем. М.: – Наука, 1969
4. Искусственный интеллект и эволюционное моделирование. - М.: Мир, 1969
5. Holland John H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial intelligence. – USA: University of Michigan, 1975.
6. Гены и геномы. В 2-х т. — М.: Мир, 1998.
7. Ратнер -генетические системы управления. Новосибирск: Наука, 1975
8. , Шамин : моделирование фундаментальных особенностей молекулярно-биологической организации // Математические модели эволюционной генетики. Новосибирск: ИЦИГ, 1980. С. 66.
9. Самоорганизация материи и эволюция биологических макромолекул. — М.: Мир, 1973.
10. Гиперцикл. Принципы самоорганизации макромолекул. — М.: Мир, 1982.
11. Порядок из хаоса. Новый диалог человека с природой. — М.: Прогресс, 1986.
12. Редько кибернетика. — М.: Наука, 2001.
13. Гены и геномы. В 2-х т. — М.: Мир, 1998.
14. Мир живого. Системность, эволюция и управление. — М.: Политиздат, 1986.
15. и др. Гомеостаз на различных уровнях организации биосистем. — Новосибирск: Наука, 1991.
16. Fiegna F., Yuen-Tsu N. Yu, Supriya V. Kadam, Gregory J. Velicer. Evolution of an obligate social cheater to a superior cooperator. — Nature. 2006. V. 441. P. 310-314.
17. , Курейчик и практика эволюционного моделирования. — М.: ФИЗМАТЛИТ 2003
18. Милов усложнение систем на основе эволюционного моделирования. – AIS’06 CAD-2006 Труды конференций, М.: Физматлит 2006, Том 2. стр. 487-493.
