Файл: лекции по ксзи.pdf

телей  (требований),  а  также  указания  по  поиску  ее  экстремума 

(min,  max,  min  max,  max  min  и  др.).

В  настоящее  время  используются  следующие  основные  виды 

целевых  функций:  простая 

L  =  ( Y -

  Ҳр);  модульная 

L  =  \ Y -   Y

w|; 

квадратичная 

L

  = 

[ Y -   Yw]2.

Наличие  множества  различных  и  зачастую  противоречивых 

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

мальности  (ВКО),  нормализации  и  последующей  скаляризации 
(свертки)  его  компонент.

Уменьшение размерности системы показателей (критериев оп­

тимальности)  значительно  упрощает  решение  задачи  ВКО.  Од­

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

Вычисление  матрицы  коэффициентов  корреляции  ВКО  про­

водится  на  основе  следующего  выражения:

Mp{Pwi'}

,

где 

К(Іп,  І

п)  = 

M(I

n, 

In )  —

  матричная  взаимная  корреляционная 

функция 

п

-го  и 

гі

-го  критериев,  диагональные  члены  которой 

являются  дисперсиями 

п-х

 критериев,  а  остальные  члены  харак­

теризуют степень линейной  независимости любой  пары  критери­
ев; 

рп,  п' —

  номера критериев оптимальности;  / =  1,..., 

М

 —  номе­

ра дискретных значений критериев; 

1п

= 

ІпРп(

  — среднее значе-

/=1

ние  критерия; 

РпЬ  Рп’Г  —

  вероятности  принятия 

п(п')-

м  критери­

ем значения  /; 

Рц

—  совместная вероятность принятия 

п-

м крите­

рием  /-го  значения  и 

п'-м

  критерием  /'-го  значения.

Редукция  системы  критериев  осуществляется  путем  удаления 

из  исходной  системы тех критериев  /„,  которым  в матрице  коэф­
фициентов  корреляции  {р„л}  соответствуют  такие  недиагональ­
ные  элементы,  которые  превышают величину 0,95.  Следует отме­

тить,  что  критерии  оптимальности  в  исходной  системе  должны 
быть  предварительно  ранжированы  по  степени  их  важности  для 
информационной  безопасности АС. Для  случая  непрерывнознач­
ных критериев вероятности в выражении  (9.7) должны быть заме­

нены  на  плотности  распределения,  а  суммы  на  интегралы.

Процесс нормализации включает этапы перехода к единой раз­

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

iw( x; k)  = cnl n(x;k) + dn,

(9.8)

где  с„  = -— ----- —^---- ----- -г  —  масштабный  коэффициент;

І Ч Щ

dn  =

 -—  

”  ---- —— -  —  коэффициент  сдвига,  корректиру-

(/; ( * ;£ ) - /„°(х; Л:))

ющий  начало  отсчета;  /М,/*,/®  —  нормированное,  наибольшее
и  наименьшее  значения  критериев  соответственно.

Задача  оптимизации  по  векторному критерию состоит  в  отыс­

кании решений, удовлетворяющих экстремуму одновременно всех 
компонент ВКО.  Существует два основных пути решения данной 

задачи:  поиск компромиссных решений, оптимальных по Парето, 

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

строгих математических методов оптимизации для широкого кру­

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

Суть  второго  пути  заключается  в  сведении  векторной  задачи 

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

•  методы,  основанные  на  последовательной  оптимизации  по 

частным  критериям  (метод  ведущей  компоненты,  оптимизация 

по  ранжированной  последовательности  критериев,  метод  после­

довательных  уступок);

•  методы,  основанные  на  получении  обобщенных  скалярных 

критериев  (метод  аддитивной  свертки  компонент  ВКО  с  весовы­
ми  коэффициентами,  метод  идеальной  (утопической)  точки,  ме­

тод  вероятностной  свертки).

Особенностями  первой  группы  методов  является  последова­

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

Основным недостатком метода взвешенной суммы является субъек­

тивный характер выбора весовых коэффициентов,  определяющих 

важность  различных  компонент  ВКО,  и,  как  следствие,  субъек­

тивность  получаемых  решений.

Свободным  от  большинства  указанных  недостатков  является 

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

где  <

7

=

1

,

2

, 

—  степень целевой  функции; 

х  —

  вектор  оптими­

зируемых  по  ВКО  параметров.

Следует  отметить,  что  в  качестве  идеальных  значений  крите­

риев  /„ид  могут  выступать либо  экстремальные  значения  ;/-х  кри­
териев,  либо  требования  к  их  значениям  со  стороны  заказчика

После решения задач сокращения размерности векторного кри­

терия  оптимальности  (ВКО),  нормализации  и  последующей  ска- 

ляризации  (свертки)  его  компонент  можно  приступать  к  реше­

нию  задачи  многокритериальной  оптимизации.  Рассмотрим  наи­
более  распространенные  подходы  к ее  решению.

Вначале  необходимо  выделить  область  компромиссов.  Каждо­

му из вариантов проекта системы  соответствует набор значений 

q

или  точка  в  ^-мерном  пространстве.  Все  множество  возможных 
вариантов проектов системы 

Q

 можно разделить на два непересе- 

кающихся  подмножества:

где 

Qk  —

  область  компромиссов; 

Qs

 —  область согласия.

Область  согласия  —  подмножество  множества  вариантов  воз­

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

Область компромиссов — подмножество решений,  каждый  ва­

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

Г 

N

(9.9)

АС.

Q =  Qk  uQs, 

Qk^Qs =

0

,

(9.10)

(9.11)

ны:  «область  Парето»,  «переговорное  множество»,  «область  эф­

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

Выделение  области  компромиссов  —  важный  шаг  при  выборе 

варианта проекта системы. Область Парето инвариантна к масшта­
бу и  шкале измерений локальных параметров и к их приоритету — 
это  характеризует корректность разработанного  проекта.  Область 
компромиссов существенно  сужает область поиска оптимального 
варианта.

Часто  выделение  данной  области  недостаточно  для  полного 

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

рая  аксиоматика).  В  ряде  случаев  целесообразно  предоставить 

выбор  варианта  проекта  системы  внутри  области  компромиссов 

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

тором или в некоторых параметрах,  в этом случае заказчик может 
сформулировать,  какие  из  параметров  наиболее  важны  для  него 

(произвести  коррекцию  критериев)  и  исходя  из  этого  принимать 

решение  о  выборе.

Приведем  наиболее  распространенные  методы  поиска  реше­

ний  внутри  области  компромиссов.

1.  Принцип равномерности.  Пусть критерии нормализованы  и 

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

такого  варианта  решения,  при  котором  достигается  некоторая 
равномерность показателей по всем критериям. Выделим три прин­

ципа  реализации  принципа  равномерности:  принцип  равенства, 

принцип  квазиравенства  и  принцип  максимина.

Формально  принцип  равенства  описывается  следующим  обра­

зом:

^opt  = 

\Я\

  = 

Яі  ~ Ъ  = Ят\^  Qk

• 

(9.12)

Не всегда существует такой вариант решения,  при котором  все 

критерии равны (или он не принадлежит области компромиссов). 
Тогда  применяется  метод  квазиравенства.

2.  Метод  квазиравенства.  При  этом  методе  требуется  достичь 

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

3.  Принцип  максимина.  Из области  Парето  выбираются  вари­

анты  проекта  с  минимальными  значениями  локальных  парамет­

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

4. 

Принцип  справедливой  уступки.  Проектировщик  должен 

проверить,  не  дает  ли  небольшое  отклонение  от  равномерных 
критериев  значительное  улучшение  по  одному  или  нескольким 
критериям.  В этом случае целесообразно применять данный прин­
цип.  На  рис.  9.3  приведен  пример  области  Парето.  Кружочками 
изображены возможные варианты решения задачи оптимизации в 
плоскости  «стоимость—уровень  защищенности».  Цифрами  обо­
значены  варианты,  принадлежащие  области  компромиссов.  Пря­
мые линии показывают ограничения на возможность достижения 
определенных  значений  рассматриваемых  параметров  многокри­
териальной  задачи  оптимизации.

При  совместном  анализе  трех  параметров,  например  врем я- 

стоимость—защищенность,  на графике  появляется дополнитель­

ная  ось.  В  общем  случае  мы  имеем  дело  с  я-мерным  графиком, 
где 

п  —

 число параметров многокритериальной  задачи оптимиза­

ции.

Если небольшой проигрыш по одному из факторов ведет к зна­

чительному  выигрышу  другого  параметра,  то  это  и  называется 
точкой справедливой уступки.  Приведенный рисунок демонстри­

рует,  что  при  очень высоком диапазоне  весов третья точка  всегда 

попадает в лучшую точку уступки.  Если  множество  Парето  не со­

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

Переход от одного варианта из области компромиссов к друго­

му из этой же  области  всегда сопровождается  улучшением  по од­
ному из  критериев  и  ухудшением  по другому  (другим)  критерию. 

Принцип справедливой уступки основан на оценке  и сопоставле­

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

С

Рис.  9.3.  Пример  области  Парето  (пояснения  см.  в  тексте)