The solution of the target assignment problem using a constructive algorithm and a combinatorial optimization algorithm is considered. The input data and the results of the
problem solution are presented in the form of tensors. The tensor trace characterizes the residual threat from the whole set of targets and is considered as a global target function. The task of finding the optimal solution is performed in two stages. At the first stage, the problem is solved using a constructive algorithm.
The second stage is combinatorial optimization. 1 Введение Управление противовоздушной обороной (ПВО) подразумевает решение задачи назначения целей средствам поражения. Одним из известных алгоритмов является конструктивный алгоритм [1]. Алгоритм анализирует все подходящие решения и находит оптимальное решение за довольно длительное время. Известно решение задач о назначениях методом целочисленного программирования [2]. Алгоритмы целочисленного программирования является NP-сложным, что делает невозможным применение этих алгоритма в режиме реального времени при достаточно большом количестве целей. Количество итераций при решении задачи велико и составляет O (m !) , где m – количество целей.
Ближайшей к задаче назначения целей по постановке является задача назначений. Для решения этих задач рекомендуется использовать три группы методов. Представителями первой группы являются метод линейного программирования, метод ветвей и границ, венгерский метод [14, 15]. Эти методы относятся к методам математического программирования и обеспечивают решение задачи о назначениях за полиноминальное время. Сложность алгоритмов реализующих эти методы составляет O(m3 ) .
Вторую группу представляют методы дискретной оптимизации: метод ветвей и границ, метод динамического программирования [16. 19. 20]. Сложность алгоритмов реализации методов второй группы составляет O(n3 ) . Третью группу составляют методы комбинаторной оптимизации [3, 13, 17, 19]. Методы комбинаторной оптимизации основаны на понятии «пространство состояний» [3]. Особенность этих алгоритмов состоит в том, что для снижения вычислительной сложности используются идеи сокращения размерности пространства, разбиения задачи назначения целей на подзадачи [4, 21].
В связи с разработанностью эффективных методов решения задачи о назначениях, представляется возможным задачу о назначении целей разделить на подзадачи. Первая подзадача – назначение целей с использованием конструктивного алгоритма, сложность которого O(m) . Вторая подзадача – преобразование полученных результатов и постановка задачи о назначениях, которая может быть решена с использованием менее сложных алгоритмов. Третья подзадача - поиск оптимального назначения целей с использованием комбинаторного алгоритма, сложность которого O(m2 ) . 2 Постановка задачи о назначениях целей Рассмотрим постановку задачи комбинаторной оптимизации, которая обеспечивает как сокращение размерности предметного пространства, так и разбиение задачи на подзадачи. Предположим, что имеется множество средств поражения W w1,..., w j ,..., wn , множество целей C c1,..., ci ,..., cm . Каждое средство поражения wj имеет g j целевых каналов и может быть назначено на любую цель. Каждая цель ci характеризуется уровнем угрозы Ui , i 1, 2,..., m и множеством вероятностей (степеней) поражения:
pi pi,1,..., pi, j ,..., pi,n , i 1, 2,..., m
На основе вероятностей поражения pi pi,1,..., pi, j ,..., pi,n для каждой цели формируется множество оценок
выживания цели ci :
qi qi,1,..., qi, j ,..., qi,n (1 pi,1),...,(1 pi, j ),...,(1 pi, j ),
(1)
(
Таким образом, при появлении новой цели для всех средств поражения на основе выражений (
F (X) im1 nj1Uiqi, j X j,i min , где X - неизвестный тензор назначения целей размерности n m . Задача решается при следующе системе ограничений:
X × H L, LT X Q HT , X j,i 0 ,
H hi , hi 1, i 1, 2,..., m; L l j , l j O, j 1, 2,..., n где Q - количество целевых каналов средств поражения . Для Q 3 и m 9 тензор остаточных угроз A может быть задан в следующем виде:
c1 c2 c3 c4 c5 c6 c7 c8 c9 AT Uiqi, j T 12,,35 22,,15 24,,13 12,,42 33,,73 54,,61 52,,29 53,,53 25,,14 ww12
3, 7 1, 2 3,1 2, 7 4, 3 4, 7 5,8 2, 5 3, 4 w3 Решением задачи о назначении целей является тензор:
c1 c2 c3 c4 c5 c6 c7 c8 c9 X 10 00 10 10 10 00 10 00 10 ww12 .
0 1 0 0 0 1 0 1 0 w3 При этом решение является оптимальным, а величина остаточной суммарной угрозы составляет:
U im nj Ai, j X j,i 23, 2 . На основе выражений (4, 5) решение задачи о назначении целей может быть представлено в виде тензора: (3) (4) (5) 3 Конструктивный алгоритм решения задачи о назначениях целей Рассмотрим решение задачи о назначениях целей с использованием тензорной методологии на конкретном примере [1, 2, 12]. Пусть m 9, n 3 и xi, j 0,1,i 1, 2,..., m, j 1, 2,..., n . Тензор остаточных угроз A в матричной форме определяется выражением (4). В тензоре AT строки соответствую средствам поражения целей, столбцы – воздушным целям: Значения элементов тензора остаточных угроз A определяются при поступлении данных о воздушных целях.
Задача назначения целей может быть решена с использованием конструктивного алгоритма. Схема алгоритма приведена на рисунке 1.
PrA(A) "Determining the dimension of the matrix À(n,m)" "Setting initial values X, K" "Reset the counter of channels Sj, j=1..m" "Definition of the q element with the maximum value in A " for k 1 n "The selection of the row G of the matrix A" for j 1 m
Gj q if Sj m K k if (Sj m) (K
0) "Search in G for a g element with a minimum value" "Determination of the index i of the element G by the value g" "Correction of the channel counter value Si = Si+1" "To assign Xj,k a value of 1"
N n "Output X, V, N, K"
Рисунок 1 – Схема конструктивного алгоритма В схеме конструктивного алгоритма, приведенного на рисунке 1, использованы следующие обозначения: A тензор остаточных угроз, X - тензор назначения целей, K - номер итерации, при которой назначение цели производится с нарушением минимума остаточной угрозы, S j - количество занятых каналов средства поражения, G тензор первого ранга, сформированный из строки тензора A , q - максимальное значение элемента тензора остаточных угроз, V - тензор двойной индексации средств поражения.
Результатом выполнения конструктивного алгоритма является тензор второго порядка X и тензор первого порядка V . Тензор X содержит результаты назначения целей и имеет вид: c1 c2 c3 c4 c5 c6 c7 c8 c9 В тензоре G строки соответствуют целям, столбцы – средствам поражения и номерам целевых каналов. На главной диагонали тензора G выделены значения остаточных угроз сформированных назначений с использованием конструктивного алгоритма. Решение задачи с использованием конструктивного алгоритма не является оптимальным tr(G) 27,0 . Сложность конструктивного алгоритма Q(n) . Тензоры G, V можно использовать для решения задачи назначения целей как задачи назначений с использование известных алгоритмов линейного и динамического программирования, алгоритмов метода ветвей и границ, венгерского метод. Сложность перечисленных алгоритмов Q(n3 ) . Кроме того, на основе тензоров G, V можно решить подзадачу поиска оптимального решения с использованием алгоритма комбинаторной оптимизации, имеющим сложность Q(n2 ) . 4 Решение задачи о назначениях методом линейного программирования Результаты решения задачи о назначениях с использованием перечисленных выше алгоритмов линейного программирования, венгерского алгоритма, метода ветвей и границ, динамического программирования могут быть представлены в виде тензора G . В этом можно убедиться на примере решения задачи с использованием алгоритма линейного программирования. Выполним постановку задачи в следующем виде:
n m F (G, X) j1i gi, j xi, j min ; nj1 xi, j 1, i 1, 2,..., m;
n
i1 xi, j 1, j 1, 2,..., n.
В результате решения задачи определяется тензор (матрица) назначения целей, который имеет вид:
(
Решение задачи можно также представить в виде, при котором остаточные угрозы назначенных целей
располагаются на главной диагонали:
(
W 3 1 W , W A j, X , j ; j 1, 2,..., 9. (
При формировании W вектор столбец выбирается из множества столбцов тензора A , а вектор строка из тензора назначения целей X , являющегося результатом выполнения конструктивного алгоритма. Например, для третьего средства поражения сумма диад имеет вид:
.
Значение функции Fi, j определяется в результате сравнения суммы следов диад (ai bi ) (a j bj ) и диад (a j bi ) (ai bj ) , которые могут быть сформированы за счет преобразования диад тензора W .
Для тензора (
2,1 1, 2 2,5 2,3 3,1 2, 3 4,1 4,1 3,1 2,3 3,1 4,1 2, 2 2, 7 2, 2 1, 4 1.4 2, 7 2, 2 2, 7 1, 4 W G × C 3, 7 4,3 3.7 3,3 3, 3 4,3 3, 7 4,3 3,3 5, 6 4, 7 5, 6 4,1 4,1 4.7 5, 6 4.7 4.1 5, 2 5,8 5, 2 2,9 2,9 3, 2 5, 2 5,8 2,9 3,5 2,5 3,5 5,3 5,3 2.5 3,5 2, 5 5,3 5,1 3.4 5,1 2, 4 2, 4 3, 4 5,1 3, 4 2, 4 Несложно убедиться, что счет преобразования диад след составил tr(W) 25, 5 . Следовательно, с использованием введенной локальной целевой функции Fi, j можно вести поиск несоответствий в последовательности диад и осуществлять поиск минимума целевой функции tr(W ) . С использованием тензора C изменения в тензор V вводятся следующим образом:
V V C (2.3 3.1 2.1 1.2 1.3 3.2 3.2 2.2 1.1) . (16) Из (16) видно, что первая цель в результате преобразований назначена 2-му средству поражения (третий целевой канал), а девятая цель – 1-му средству поражения (первый целевой канал).
Одной из проблем реализации комбинаторной оптимизации является определение необходимого и достаточного условий, выполнение которых позволяет локально осуществить снижение значения целевой функции за счет преобразования двух диад. Преобразование диад существенно отличается от перестановки столбцов в матрице, так w w ... wk w ... w k w
w ... w k w ... ... ... ...
wk ... wkk wk w ... w k
w ... wjk . wk ... ... ...
... wkk
Рисунок 2 - Преобразование диад тензора
В тензорах фиксированные индексы обозначены греческими символами , , переменный индекс латинским
символом k 1, 2,..., n (k i, j) . Обозначим диады в тензоре следующим образом: D , D , Dk . Индексы диад
указывают на расположение элементов w , w , wkk , значения которых определяют значения глобальной и локальной
целевых функций. Кроме того, индексы диад соответствуют двойным индексам средств поражения. Для
выбранных диад (см. рисунок 1), независимо от этапа оптимизации, можно составить систему следующих уравнений:
(a a ) (a a ) R1 .
(akk a ) (a k ak ) R2
(akk a ) (a k ak ) R3
В уравнениях (
2akk (a a ) (a k ak a k ak ) R2 R3 2akk (a a ) (a k ak a k ak ) R1 R2 R3 Из выражения (21) следует, что независимо от значений R2 , R3 можно выполнить операцию переназначения целей и преобразовать диады D , D . Преобразование диад приведет к снижению значения следа тензора только за счет преобразования выделенных диад. В этом несложно убедиться, сравнив выражения (20) и (21). Значение третьего слагаемое в выражениях (20, 21) определяется одними и теми же элементами тензора . Таким образом, достаточным и необходимым условием переназначения целей (преобразования диад) является выполнение неравенства: Если имеет место (a a ) (a a ) 0 .
(a a ) (a a ) 0 , то переназначение целей и преобразование диад не выполняется.
Выражение (23) можно использовать для оценки качества полученного решения. Если это неравенство
выполняется для всех возможных пар диад тензора, то след тензора имеет минимальное значение и найденное решение
является оптимальным.
5.3 Алгоритм комбинаторной оптимизации назначений.
Схема разработанного алгоритма комбинаторной оптимизации приведена на рисунке 3. Входные данные алгоритма
– результаты выполнения конструктивного алгоритма: тензор второго ранга W и тензор первого ранга V . В
соответствие с рисунком 3 локальный поиск начинается с первой цели и заканчивается на цели m . Количество
итераций по поиску несоответствий в назначениях целей N m (m 1) . Если m 9 , то N 72 . При m 32
количество итераций по поиску несоответствий значительно возрастает и составляет N 1024 .
(
1 2 3 ⁞ 9 1 2 3 ⁞ 9 Рисунок 4 – Поиск несоответствий в назначениях целей В соответствии со схемой поиска несоответствий в назначении целей количество итераций составляет величину, определяемую формулой.
N Q m(m 1) , где Q – коэффициент, учитывающий повторные вычисления. При проведении вычислительных экспериментов оптимальное назначение целей достигалось при значениях коэффициента Q равным 1. 6 Результаты вычислительного эксперимента Результаты вычислительного эксперимента приведены в таблице 1. Количество распределяемых целей m 16 . Остаточные угрозы формировались как случайная выборка с равномерным распределением. Количество целей равно количеству целевых каналов всех средств поражения. Первый столбец таблицы содержит номера вычислительного эксперимента, второй столбец – количество несоответствий в назначениях целей по результатам комбинаторной оптимизации R , в третьем столбце приведены значения остаточной угрозы по результатам решения задачи назначения целей с использование конструктивного алгоритма. В четвертом столбце приведены значения следа тензор tr (W ) , сформированного с использованием алгоритма комбинаторной оптимизации. В пятом столбце приведены значения коэффициента эффективности решения задачи о назначении целей методом комбинаторной оптимизации.
Из таблицы 1 следует, что за счет комбинаторной оптимизации величин остаточной угрозы U снижена на величину равную сумме остаточных угроз, от двух целей. Количество итераций при решении задачи комбинаторной оптимизации
N m(m 1) m m 2 240 .
Таблица 1– Результаты вычислительного эксперимента
Номер эксперимента 1 2 3 4 5 6 7 8 9 10
R 0 0 0 0 0 0 0 0 0 0 tr (W ) 71,45 112,36 78,36 51,31 80,64 102,34 86,17 102,52 84,73 92,40 tr (Q) 57,97 93,52 73,32 51,31 68,40 72,37 81,19 79,1 75,07 72,70 (tr (W ) tr (Q)) / tr (W ) 0,19 0,17 0,06 0,00 0,15 0,29 0,06 0,29 0,14 0,21 Если исключить сравнения между целями, назначенными каналам одного и того же устройства поражения, то количество итераций в можно значительно уменьшить. При этом количество итераций можно рассчитать по формуле:
N m(m g) . При m 16 и g 4 количество итераций N 192 . Таким образом, сложность вычислений снижена на 48 итераций. С увеличением количества целевых каналов эффект от исключения процедуры вычисления локальной целевой функции будет более значимым. 7 Разбиение задачи комбинаторной оптимизации на две подзадачи Сложность рассмотренного выше алгоритма состоит в необходимости проверки условия начального распределения целей одному и тому же средству поражения, что требует также затрат вычислительных ресурсов. Эту операцию можно исключить, если использовать подход к решению задачи, основанный на сведении задачи к двум подзадачам [4]. Для рассматриваемого примера поиск и устранение несоответствий в назначениях целей выполняется с использованием двух подзадач (рисунок 5).
ЗРКi ЗРКj Каналы ЗРКi Каналы ЗРКj 1 2 3 1 2 3 1 2 3 1 2 3 а)
б) Рисунок 5 – Поиск и устранение несоответствий: а) на уровне средств поражения, б) на уровне целевых каналов кальная целевая функция. Третий этап связан с поиском минимума глобальной целевой функции при ограничениях на количество средств поражения. При поиске минимума глобальной целевой функции вычисляются значения локальной целевой функции. В случае отрицательного значения локальной целевой функции выполняется операция преобразования диад тензора назначений. Последовательное выполнение всех этапов обеспечивает поиск оптимального решения. Сложность объединения двух алгоритмом Список использованной литературы