Комбинированный метод формирования мультиверсионного программного обеспечения

В настоящее время по государственному заказу в рамках Федеральной космической программы на 2006–2015 гг. ОАО «Информационные спутниковые системы имени академика М. Ф. Решетнева» создает многофункциональную систему персональной спутниковой связи «Гонец-Д1М».

Планируется, что в составе орбитальной группировки будут функционировать 12 космических аппаратов (КА) «Гонец-М» (по 3 КА в четырех плоскостях). Такое количество спутников на орбите будет обеспечено к концу 2015 г.

Круг потребителей услуг системы очень широк. К ним относятся Министерство РФ по делам ГО и ЧС, Министерство транспорта РФ, Мининформсвязи РФ, Росатом, РАО ЕС и другие ведомства и организации.

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

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

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

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

• 1.    Использование многоцелевых методов принятия решений (MODM-процедур) в комбинации с модифицированными алгоритмами случайного поиска для решения исходных оптимизационных задач с целью получения множества недоминируемых решений.

• 2.    Применение многоатрибутивных методов принятия решений (MADM-методов) для окончательного выбора альтернативы, принимаемой в качестве решения на полученном множестве.

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

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

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

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

• 1.    Базовый вариант (БВ), предусматривающий минимально возможную избыточность мультиверсий ( N = 2) и обеспечивающий гарантоспособность компонента NVS_{( N = 2)}-системы.

• 2.    Радикальный вариант (РВ), предусматривающий избыточность мультиверсий при N > 2 (радикально увеличивающий глубину мультиверсионности компонента NVS_{( N > 2)}-системы) и, естественно, требующий дополнительных затрат по сравнению с БВ.

• 3.    Основной вариант (ОВ), который соответствует одноверсионному (безызбыточному) программированию компонента NVS-системы и обеспечивает минимальную стоимость его реализации.

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

Задача предварительного этапа, фактически, сводится к выбору между РВ и БВ для конкретного мультивер-сионного компонента, причем на этом этапе ничего не известно о шансах на успех РВ, что соответствует выбору при полной неопределенности. В статье [4] анализируются правила выбора из нескольких альтернатив для случаев, когда результат или выигрыш зависит от конкретного выбора: для конкретного выбора известен выигрыш по всем альтернативам; вероятность конкретного выбора неизвестна. Там же рассмотрены и реализованы основные методы выбора при полной неопределенности – правила максимина и максимакса, правило Лапласа, или равной вероятности, применяемые на данном этапе процедуры. Критически проанализированы оптимистичность и пессимистичность, а также сильные и слабые стороны каждого из подходов. Несмотря на применение экспертных оценок вероятностей (как метода преодоления влияния полной неопределенности) и соответствующего метода интервального анализа, а также функции полезности, поиск хорошей альтернативы является исключительно трудной задачей, причем для указанных методов существуют классы ситуаций, в которых назначается противоестественный выбор при полном отсутствии информации о возможных исходах. Несомненно, что такая информация способна дать значительный эффект при решении поставленной задачи.

Метод решения. Предлагается следующий метод повышения знаний о конечном состоянии мультиверсион-ного компонента NVS-системы ПО, который становится возможным благодаря организации в составе средств сопровождения модельного блока прототипов мультиверсий, реализующего основные функции компонента при погружении в среду моделирования технологии управления КА и логики функционирования бортового комплекса управления. Естественно, в этой ситуации значительно повышается риск для РВ, хотя в общем случае не представляется возможным получить полную информа- цию, так как существуют два источника неопределенности, которые выражаются вероятностью P(Б[РВ] / неблагоприятный случай (НС)), что соответствует вероятности того, что исследование с помощью модельного блока приводит к выбору РВ при условии, что в действительности этот вариант окажется неудачным, и P(Б[РВ] / благоприятный случай (БС)) – вероятность того, что использование модельного блока приводит к выбору РВ при условии, что он действительно оказывается удачным.

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

Итак, имеется m альтернатив NVS₁ ^{( N > 2)} , NVS₂ ^{( N > 2)} , …, NVS _m ^{( N > 2)} в ситуации, имеющей n возможных состояний S ₁, S ₂, …, S_n , вероятности которых равны P ( S ₁), P ( S ₂), …, P ( S_n ), а значения выигрышей от выбора альтернативы в состоянии S_J задается матрицей выигрышей с элементами v_ij ( j = 1, …, n ; i = 1, …, m ). Необходимо выбрать альтернативу (вариант реализации мультиверсионного компонента ПО) с максимальным математическим ожиданием М выигрыша. При полной информации, рассчитав М дохода при выборе каждой альтернативы и выбрав максимально значимую, вычислим М дохода от полной информации:

nn

M S P ⁽ S j )( max V ij ) - max S P(S j ) V ij . j = 1 i = 1,---, m i = 1,---, mj = 1

Таким образом, если применение модельного блока Б прототипов обеспечивает полную информацию для определения глубины мультиверсионности NVS-системы ПО, то всегда можно рекомендовать альтернативу, максимизирующую выигрыш. Рекомендуемые в результате этого применения альтернативы Б[NVS _i ] связаны с состояниями S_j , причем в практике инженерного программирования рекомендация Б[NVS _i ] основана на неполной информации о состояниях S_j (где для нашего случая Б[NVS _i ] соответствуют БВ, РВ или ОВ, а S_j – суть НС и БС). Тогда общая формула для М дохода при решении задачи выбора варианта мультиверсионности из Б[NVS _i ] ( i = 1, …, m ) имеет следующий вид:

M(Б[NVS₁], Б[NVS₂],,,,, Б[NVS m ]) = mn

= S P (Б[NVS i D[ S P ( S j /Б[NVS i D V ij ]- i = 1 j = 1

В соответствии с вышесказанным, разработана процедура определения дохода от информации, в результате реализации которой определяется структура мультивер-сионности NVS-системы ПО и обеспечивается наилучшее соотношение между затратами на применение модельного блока прототипов и доходами от результатов этого применения и полученной при этом информации. Здесь же отметим, не касаясь случая, когда значением М можно пренебречь, что, вычислив М, получаем «грубую» верхнюю оценку допустимых затрат и в этих пределах определяем оценочную стоимость Ck наиболее обещающей компоновки модельного блока. Вычислив чистую стоимость по каждому Б[NVSi], выбираем наиболее предпочтительный вариант мультиверсионного исполнения компонента ПО.

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

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

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

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

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

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

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

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

U = { f ( x *u ), u = 1,2, ..., r }.

Из этого множества необходимо отобрать наилучшее компромиссное решение. Следующие ( к + 1) критериев отбора C ( i ), i = 1, ..., к и C ( к + 1) могут оказать существенную помощь при отыскании такого решения:

C ( i ): 0 < pc . - E i < pa. <  100 V i = 1,2, ..., к , где pa . и pc i - процент достижимости и предпочтительность i -го критерия для каждой целевой функции соответственно; E i - неотрицательное значение нижней оценки (недооценка цели) i -й функции, устанавливаемая экспертом;

k

C(к + 1): 0 < V (pag - pai) < Eg, i=1

где pa g - глобальный процент желаемости для i -й целевой функции, который может быть рассчитан в результате решения оптимизационной задачи:

k max V pa i , F i = 1

где F - подмножество достижимых целей, определяемое допустимым подмножеством X; Eg - максимум установленного ЛПР неотрицательного значения разности меж- ду суммой глобальных и действительных процентов достижимости по всем к целям.

Итак, будем рассматривать ( к + 1) подмножеств U j множества U испытательных недоминируемых решений. Тогда подмножество определится следующим образом (для j = 1, ..., к ):

U j =^{ fx *u ^): paf^x *u )) удовлетворяет C j' ^)},

U ₊ 1 = { fx * _u ): p j fx * _u )), i = 1, ^, к , удовлетворяют C ( к +1)}.

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

Взяв за основу базис для правил выбора, используемых в максимине и fuzzy-программировании [5] и положив h j ( U j ) >  Z , V j = 1, 2, ..., к + 1, запишем задачу в следующем виде:

max Z

F таким образом, чтобы для j = 1,2, _, к + 1 hj (Uj) > Z, где hj(Uj), j = 1, ..., к + 1 - функции принадлежности, задаваемые для каждого подмножества U, j = 1, ..., к + 1 недоминируемых решений, удовлетворяющих j-му критерию выбора; F - допустимое пространство целей, заданное ограничениями исходной задачи.

Эта последняя постановка может быть переписана в виде задачи нечеткого программирования ( FP ), причем все ограничения задаются четко:

(FP): max Z таким образом, чтобы для i = 1,2, _, к

(pa i - pc i + E i ) / (100 - pc i + E i ) >  Z ,

0 < pc i - E i < pa . <  100, k

• ¹ - V ⁽ pa ig - pa i )/ E g >  ^Z ,

i = 1 k

• ⁰ <  V ⁽ pa g - pa i ) <  ^E g , i = 1

pa = [1 - f(x) - fi(xi*)) / f+-fi(x,*))]-100„ f+ * f(xi*), fx) = (f, ...,f e F, где fi(xi*) = minf при выполненных ограничениях задачи, в том числе заданных алгоритмически; pci (i = 1,2, _, к) -входная информация о предпочтительности критериев; Ei (i = 1, 2, ..., к) и Eg - входная информация о степени недооценки, принятая проектировщиком;

fi ⁺ = max ^{ fj ⁽ x i * ^)}.

1 < j <  к

Фактически, приведенная выше формулировка задачи полностью описывает все необходимые вычислительные процедуры, причем решение задачи ( FP ) однозначно указывает на недоминируемое решение исходной задачи.

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

Шаг 0. Сформулировать нечеткую модель ( FP ), соответствующую исходной MODM-задаче.

Шаг 1. Ввод исходных параметров pc i , i = 1, ..., k ; E i , i = 1, ..., k ; E g .

Шаг 2. Решение FP -модели. Если это невозможно, то переход на шаг 1, иначе - шаг 3 .

Шаг 3. Предоставление ЛПР результирующего значения Z и соответствующего недоминируемого решения исходной задачи. Если предпочтительное решение выбрано, то остановка, в противном случае - переход на шаг 1.

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

Итак, имеется m альтернатив, представляющих собой различные составы ПО ТЦУ для мультиверсионного программного продукта, из которых необходимо сделать выбор. Каждому выбору соответствует n значений атрибутов. Для к -й альтернативы существует х ^{( k )} ₁, х ^{( k )} ₂, _, х ^{( k} ) n , где х ^{( k} ) . - значение i -го атрибута, если k -я альтернатива выбрана. Будем обозначать через NVS ^{( k} ) некоторую k -ю альтернативу, однозначно определяющую х ^{( k} )_р х ^{( k} ) ₂, ..., х ^{( k} ) и соответствующую одному из вариантов состава мультиверсионного ПО.

Обозначим субъективную оценку относительной важности каждого i -го атрибута с помощью нечеткого множества H, т е. X . = { х ^{( k}i 1 < k < m } и x * }, где x * соответствует идеальной альтернативе NVS * . Нечеткое множество H_i описывается своей характеристической функцией вида f Hi : X. ^ [0,1]. Таким образом, f_H(x i ^{( k} ) ) характеризует предпочтительность NVS ^{( k} ) по i -му атрибуту

С использованием метода энтропии и с учетом соотношения между размытым множеством и распределением вероятностей [6] определим генерируемую размытость по i -му атрибуту е. и общую неопределенность E , полученную путем суммирования. Определим коэффициент сатисфакции как n

S i = (1 — ^ед/ j (1 — ^е 1 ) = (1 — ^е 1 )/ ( n — E ), 0 <  i <  n .

i = 1

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

n

S i ^комб = S i w i / j S i w i , 0 <  i <  n .

i = 1

Итак, если необходимо определить, насколько удалены друг от друга NVS * и NVS(k) по i-му атрибуту, то это можно определить по степени неудовлетворенности ЛПР значением i-го атрибута для NVS(k), т е. введя дополнение нечеткого множества, которое будем обозначать Ц и для которого выполняетсяfUi(x(k)) = 1 - fHi(xi(k)). Определим

Dis ^{( i )} [ NVS* , NVS- ^k ) ] = S ^_Ц1(x^{( k} ) ) и тогда

Dis [NVS * , NVS ^{( k} ) ] =

• = j ( Dis ⁽ t ) [NVS*,NVS ^{( k} ) ]) ² ,

• V i = 1                                            ’

где обозначение Dis соответствует нотации, введенной в работе [7], и характеризует функцию различимости по каждому отдельному i -му атрибуту

Собственно процедура выбора может быть представлена последовательностью следующих этапов:

Этап 1. В момент t все доступные альтернативы, специфицированные по каждому атрибуту относительно «идеальной» альтернативы, предоставляются ЛПР, который затем определяет f_H . ( x i ^{( k )} ) ⁽ t ) V i , k . Дополнительно могут быть рассмотрены и выбраны некоторые лучшие альтернативы предыдущего этапа t -1 и обозначены f_{H i}(x *-^k ) ) ^{( t +}1) ^{на f} Hi ⁽ x ( k ^{) ) (} t ) .

Этап 2. Расчет частных энтропий (по каждому атрибуту), суммарной энтропии и S_i (используется количественная шкала и периодически предоставляется возможность сверить коэффициенты соответствия - интерактивный режим).

Этап 3. Определение w^t ) (используется количественная шкала и периодически предоставляется возможность сверить коэффициенты относительной важности отдельных атрибутов - интерактивный режим).

Этап 4. Расчет весовых коэффициентов S i ⁽ t ^)комб , комбинирующих нечеткость и субъективную оценку.

Этап 5. Расчет Dis ⁽ t ) [NVS * , NVS ^{( k} ) ].

Этап 6. Определение наилучшей альтернативы путем минимизации Dis ^{( t )} .

Последовательность указанных шагов может повторяться до тех пор, пока не будет принято решение о том, что полученная альтернатива максимально близка к NVS * . В интерактивном режиме с учетом сверки коэффициентов и обновления информации (этапы 2, 3) пользователю могут быть предоставлены и альтернативы, полученные на предыдущих этапах t - 1 применения алгоритма.

Таким образом, процедуры комбинированного метода, соответствующие выбору структуры мультиверси-онности состава комплекса управления КА «Гонец-М» (нулевой этап), реализованы в рамках стоимостно-ориентированного подхода, что возможно только с учетом методов анализа риска, теории статистических решений при оценке их значения для экономики инженерного проектирования при выработке решений в условиях неопределенности. Комбинированный MODM-метод (первый этап), реализующий теоретико-групповой подход к бинарной оптимизации, позволяет ввести направление в пространстве булевых переменных, что обеспечивает использование на этом этапе для решения поставленных задач рандомизированных методов направленного поиска. Завершающим шагом первого этапа процедуры является формирование конечного множества недоминируемых решений многокритериальной задачи, который осуществим в результате применения предпочтений критериев в нечетком программировании и организации интреактивной (и итеративной) пошаговой схемы. Решение интерпретированной задачи нечеткого программирования однозначно определяет недоминируемое решение исходной MODM-задачи, и более того, модификация предложенного алгоритма позволяет получить наилучшее компромиссное решение задачи по составу мульти-версионного комплекса управления КА «Гонец-М».

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