GERT-анализ формирования технологических циклов управления космическими аппаратами

Решение задачи формирования технологических циклов управления (ТЦУ) связано в первую очередь с необходимостью обеспечить взаимодействие с объектом (космическим аппаратом) в соответствии с временными циклограммами в режиме реального времени. Более простая форма режима реального времени предполагает лимитирование времени ответа центра управления полетами (ЦУП) на запрос от объекта. Ограничения на время реакции связываются в этом случае с выполнением периодических действий в рамках технологического цикла управления.

Естественной математической интерпретацией распределенных, асинхронных, мультипроцессорных и муль- типрограммных систем являются сетевые модели, которые позволяют отражать распределенность структуры, сетевой характер взаимосвязей между процессами и ресурсами, аппаратными и программными компонентами средств управления. В связи с этим для решения задач оптимизации формирования ТЦУ целесообразно привлекать аппарат сетевого анализа, включая GERT-анализ (GERT - аббревиатура от graphical evaluation and review technique). В последнее время GERT-сети получают все большее распространение для моделирования и оптимизации технических систем, к числу которых можно отнести ТЦУ космических аппаратов.

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

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

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

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

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

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

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

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

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

Пусть N - ациклическая сетевая модель ТЦУ с источниками и стоками (действия, соответствующие задачам ТЦУ, представляются дугами), где множество узлов обозначается V , а множество дуг - E . Предположим, что N имеет только один исток, который обозначается через r и соответствует началу рассматриваемого ТЦУ Также предположим, что один из стоков N представляет собой успешное завершение ТЦУ Обозначение этого стока - 5 . Оставшиеся стоки, если они есть, могут представлять собой различные виды неудачного завершения или прерывания процесса управления.

Определение 1 . Ациклическую сетевую модель ТЦУ N ( V , E ) только с одним истоком и со стоками назовем сетью для проектирования (решения) ТЦУ, если каждый узел i из N определен через входную характеристику CH ^- . е {0, 1, ...,| P ( i )|} и выходную характеристику CH + . е {0,1, ...,| S ( i )|}, где множество узлов обозначается V , а множество дуг - E ; | P ( i )|, | S ( i )| - мощность множества предшественников и последователей узлов I соответствен-но. Эти характеристики, формирующие узловую логику, имеют следующие значения:

• а)    узел активируется сразу же, как только входные действия CH i завершаются;

• б)    как только узел i активирован, то не более CH +i выходных действий начинает выполняться. Если узел i не активируется, то ни одно выходное действие не выполняется. Иногда уместно заменить сочетание «не более» на «точно».

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

Для источника r полагаем CH r = 0, т е. он всегда активирован. Кроме того, CH +i = 0 для i е S , где S - множество стоков N .

Заметим, что если CH +i = 1, то узел i имеет OR-вход, а если CH r = | P ( i )|, то тогда i имеет AND-вход. И если в определении 1б «не более» заменяется на «точно», то CH+. = 1 соответствует вероятностному выходу, а CH + = | S ( i )| - детерминированному выходу Если же заданная сеть N для формирования ТЦУ имеет множество источников R (| R |>1) и множество R ‘ Н R , R' ^ 0 активизируется в начале выполнения ТЦУ, то можно формально перевести N в соответствующую одноистоковую сеть.

Дуговые переменные обозначаются через w j , при этом полагается, что w j = 1, если ( i , j ) выполняется (( i , j ) е E ), и w j = 0 в противном случае. Узловые переменные u j = 1 ( i е V) , если i активируется, иначе u j = 0, где u r = 1, т. е. источник всегда активируется. Тогда условия узловой логики, введенные в определении 1, могут быть представлены в следующем виде:

У w^ CH-U; (i е V\{r}),(1)

k е P ( i )

У wh < CH + MiU; (i е V\{r}),(2)

k е P ( i )

где M i >  | P ( i ) - CH i |,

У w, < CH+i Ui; (i е V\ S).(3)

j е S ( i )

Так как решающая модель ациклична, то каждая задача соответствующего ТЦУ либо выполняется только один раз, либо не выполняется вообще. Таким образом, каждая реализация ТЦУ может быть соотнесена с множеством выполняемых задач ТЦУ или с функцией w : E ^ {0, 1}; (( i , j ) E ), значения которой задаются как w (( i , j )) =: w j = 1, если ( i , j ) выполняется, и 0, если иначе.

С другой стороны, если некоторая w -я реализация ТЦУ задана, то как узловые, так и дуговые переменные для этого случая специфицированы и можно говорить о допустимой реализации ТЦУ, если w удовлетворяет условиям узловой логики. Тогда e = { w : E ^ {0,1}| w j удовлетворяет условиям (1)-(3); ( i , j ) е E } и e - множество всех допустимых реализаций ТЦУ.

Если в решающей сети для формирования ТЦУ обозначить вес дуги ( i , j ) е E как длительность d_y е R + соответствующей задачи ТЦУ, то d W - длительность w -й реализации ТЦУ, т. е. время, требуемое для исполнения всех задач ( i , j ) при w_ij = 1. Необходимо минимизировать d_W при условиях: w активирует 5 ; ( w е е ) . Через е * : = { w е £ | w активирует $ } обозначим множество успешных реализаций ТЦУ. Для е * ^ 0 d * = min d W соответствует минимальному значению целевой функции задачи.

Приняв, что каждая реализация ТЦУ начинается с задействования истока r в момент 0, считаем для w е е , что t w есть время активации узла j е V для w -й реализации, причем t w = 0 и t w = да , если j не активируется в течение w -йреализации ТЦУ Для j е V \{ r } имеем J = min{ t >  01 существуют CH_j^- , отличные от i е P ( j ) и такие, что w_ij = 1 и t Jw + d j <  t }.

Кроме того, справедливо d W >  t w V, w е е * . Тогда d W >  t w , если сток 5 активируется, пока некоторые действия ( i , j ) при w j = 1 все еще выполняются. Так как t e = mn t j -самое раннее из возможных времен задействования узла j в течение какой-либо возможной реализации ТЦУ, то t^e = min max {( t w + d. ) w .},

• ⁵ w_e $ * ( i , j )е E ^И        i ^j V '

E w ={( i , j ) е E | w j =1}, где E w - множество задач, выполняемых в течение w -й реализации ТЦУ

Учитывая вышесказанное, можно утверждать, что минимальная длительность успешной реализации ТЦУ равна самому раннему моменту задействования стока $ : d * = t^e $ для е * ^ 0. Таким образом, можно найти величину d^* , вычисляя минимально возможные моменты задействования t^e $ (j ' е V ).

Рассматривая моменты t i как компоненты вектора временной развертки (ВВР) ТЦУ, которые удовлетворяют условию ( t , - t i - d j ) w j >  0, ( i , j ) е E ; t i >  0, i е V\ { r }; t r = 0, можно утверждать, что для некоторой w -й реализации ТЦУ ( w е е * ) моменты t iw отвечают этим ограничениям, а самые ранние моменты t_i^e удовлетворяют им для соответствующей минимальной w е е ^* . Соответствующая оптимизационная задача имеет вид: минимизировать max {( t iw + d j ) w j } при выполнении условий (1)-(3) и ограничений ВВР ( и $ = 0).

По сравнению с минимизацией затрат на выполнение ТЦУ здесь имеются не только добавочные ограничения, но и более сложная целевая функция. Кроме того, дополнительно к узловым и дуговым переменным существуют моменты t_i ; ( i е V ), которые также являются переменными данной оптимизационной задачи.

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

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

Процедура, используемая для анализа вероятностных характеристик ТЦУ, базируется на стохастических сетях типа GERT и совмещает теорию потоков в графах, функции генерации момента и PERT-анализ для получения результата. Стохастическое представление ТЦУ в виде GERT-сети позволяет получить достаточное количество полезной информации о временных характеристиках реализации ТЦУ. Используя неравенство Чебышева, можно показать пределы, в которых будет изменяться фактическое время реализации ТЦУ, а также получить более сильные утверждения. Кроме того, если реальный показатель не соответствует этим оценкам, то строится ряд критериев для проверки гипотез, позволяющих определить перспективные характеристики времени реализации ТЦУ.

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

Анализ моделей формирования ТЦУ показывает, что они имеют, как правило, алгоритмически заданный критерий, а часто – и ограничения. Очевидно, что при такой постановке задачи имеет смысл говорить только об эвристических процедурах случайного поиска.

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

F( X ) ^ extr, (4)

X e S

S J X e B n : У х, = m , m <  n I , (5) 2 j

L j =1

на решение которой ориентированы алгоритмы метода изменяющихся вероятностей (МИВЕР) [2].

Алгоритмы МИВЕР не укладываются в традиционную схему алгоритмов случайного поиска для непрерывной оптимизации, которая в общем случае включает два этапа:

– первый этап – в соответствии с некоторым правилом и вероятностным распределением на множестве всех возможных направлений поиска случайным образом выбирается одно из направлений;

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

Для реализации этой схемы в пространстве булевых переменных необходимо определить понятия направления в B ₂ ⁿ .

Определим инверсию p . (1 <  i <  n ) как подстановку на множестве B 2 . И пусть X , Y e B 2 . Тогда направлением K ( X , Y) с B 2 назовем множество таких точек Z e B 2 , которые можно представить в виде

Z = п1 -пt -...-пb X,

где n j e W ( X, Y ), W ( X, Y) = п i , п , ₂ ,..., n k , такое, что

Y = п i ₁■ П i_г ... . пи^Х ( k <  n ).

В соответствии с этим определением для любой точки X e B 2 существует (2 ⁿ - 1) направлений, каждое из которых однозначно определяется любой точкой Y e B 2 либо множеством W ( X , Y ) . Длину шага по направлению K ( X , Y ) определяем, используя метрику Хэмминга.

Для введенных таким образом понятий направления и длины шага общая схема построения алгоритмов направленного поиска выглядит следующим образом.

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

• 2.    По заданному правилу определяется длина шага l <  card( W ( X 0 , Y) ). Формируется множество инверсий W ( X 0 , Z) с W ( X 0 , Y), card( W ( X 0 , Z) ) = l . Осуществляется переход в точку

Z = п i -п , ₂ •... -п^ , п , e W ( X °, Z ).

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

Приведенные выше процедуры направленного случайного поиска были реализованы программно и прошли апробацию при решении задач формирования ТЦУ. Численные результаты показали, что в ряде случаев алгоритмы направленного поиска позволяют получить лучшие результаты по сравнению с алгоритмами МИВЕР.

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

Сепарабельные псевдобулевые функции определяются следующим образом:

x X ) =f(.^х i , ^, ^{X ) )} = S g i^{( x} i⁾ ,

1< j < 2

где f : B ₂ ⁿ → R ¹ .

Оценкой сверху числа необходимых вычислений значений целевой функции, когда поиск начинается в точке (1, …, 1) (самой дальней от минимума), будет n ² – n + 2 вычислений, а оценкой в среднем (по выбору начальной точки поиска) будет величина ( n ² + 4)/2 – 1/2 ⁿ . Данные оценки позволяют сравнить эффективность локального поиска на классе сепарабельных псевдобулевых функций с эффективностью других подходов, например эволюционных алгоритмов.

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