Описание алгоритма.
Методы локальной оптимизации базируют-
ся на метризации дискретного пространства [5], на понятиях окрестно-
сти точки в дискретном пространстве и локального экстремума функ-
ции по аналогии с непрерывным пространством.
Обозначим через
O
Δ
доп
(
X, r
)
— окрестность точки
X
∈
Δ
доп
ради-
усом
r >
0
, тогда
O
Δ
доп
(
X, r
) =
Y
∈
Δ
доп
|
ρ X, Y r ,
(4)
где
ρ X, Y
— расстояние между точками
X
и
Y
в дискретном метри-
ческом пространстве. В случае булевых переменных наиболее часто
используется метрика Хэмминга [6].
Для характеристики точек окрестности определим вектор, называ-
емый вектором спада, характеризующий изменение целевой функции
при переходе в различные точки окрестности:
−→
σ
r
(
−→
X
) =
σ X, Y
(1)
, σ X, Y
(2)
, . . . , σ X, Y
(
k
)
т
,
(5)
где
σ
−→
X,
−→
Y
(
i
)
=
F
−→
Y
(
i
)
−
F
−→
X , i
= 1
,
2
, . . . , k
;
k
— число точек
окрестности.
Идея метода вектора спада заключается в том, что на каждом ша-
ге рассматривается окрестность некоторой точки, соответствующей
допустимому решению задачи и осуществляется переход с помощью
вычисления компонент вектора спада к той точке окрестности, которая
имеет наибольшее (наименьшее) значение целевой функции. Процесс
продолжается до получения локального максимума (минимума) зада-
чи.
Приведем алгоритм одной измодификаций метода вектора спада
для решения задачи оптимального выбора вариантов защиты от угроз
безопасности вычислительной сети.
Шаг 0 (предварительный).
Выбираем начальное допустимое при-
ближение
X
(0)
∈
Δ
доп
. Например, будем использовать все допустимые
средства для защиты, в этом случае
x
j
= 1
,
∀
j
∈
M
(это решение будет
всегда допустимым при корректной постановке задачи, т.е. если огра-
ничения позволяют задать хотя бы одно допустимое решение). Задаем
значение радиуса
r
= 1.
Шаг
k
(
k
1)
.
1. Определяем для каждой точки, которая является допустимой со-
гласно введенным ограничениям, окрестности
O
Δ
доп
X
(
k
−
1)
, r
ком-
поненты вектора спада
σ X
(
k
−
1)
, Y
, где
Y
∈
O
Δ
доп
X
(
k
−
1)
, r
.
2. Определяем точку окрестности, для которой компонента векто-
ра спада отрицательная и является минимальной (так как решается
76 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 2
