Присвоение S-D с помощью лагранжевой релаксации
[ возвращает таблицу присвоений, assignments,cost,solutionGap] = assignsd(costmatrix)assignments, из обнаружений к дорожкам путем нахождения субоптимального решения проблемы присвоения S-D с помощью лагранжевой релаксации. Стоимость каждого потенциального присвоения содержится в матрице стоимости, costmatrix. Алгоритм останавливается, когда разрыв достигает ниже 0.01 (1 процент) или если количество итераций достигает 100.
costmatrix n-мерная матрица стоимости где costmatrix(i,j,k ...) задает стоимость n-кортежа (i,j,k, ...) в присвоении. Индекс '1' на всех размерностях в costmatrix представляет фиктивное измерение или ложную дорожку и используется, чтобы завершить проблему присвоения. Индекс 1, будучи макетом, может быть частью нескольких n-кортежей. Индекс может быть присвоен несколько раз. Типичная величина затрат для costmatrix(1,1,1,1, ...) 0.
Все входные параметры могут быть одинарные или двойная точность, но они все должны иметь ту же точность.
Функция также возвращает разрыв решения, solutionGap, и общая стоимость присвоений, cost.
[также задает желаемый максимальный разрыв, assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap)desiredGap, между двойным и выполнимыми решениями как скаляр. Разрыв управляет качеством решения. Значения обычно лежат в диапазоне от 0 до 1. Значение 0 средних значений двойные и выполнимые решения является тем же самым.
[также задает максимальное количество итераций, assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations)maxIterations.
[также задает алгоритм присвоения, assignments,cost,solutionGap] = assignsd(costmatrix,desiredGap,maxIterations,algorithm)algorithm.
Лагранжевый релаксационный метод вычисляет субоптимальное решение проблемы присвоения S-D. Метод ослабляет проблему присвоения S-D к 2D проблеме присвоения с помощью набора лагранжевых множителей. Расслабленная 2D проблема присвоения обычно известна как двойную задачу, которая может быть решена оптимально с помощью алгоритмов как алгоритм Munkres. Ограничения затем осуществляются на двойном решении путем решения нескольких 2D задач присвоения, чтобы получить выполнимое решение исходной проблемы. Стоимость двойного решения и выполнимого решения служит нижними и верхними границами на оптимальной стоимости, соответственно. Алгоритм итеративно пытается минимизировать разрыв между двойными и выполнимыми решениями, обычно известными как двойной разрыв. Итерация останавливается, когда двойной разрыв ниже желаемого разрыва, или максимальное количество итераций достигли.
При использовании аукционного алгоритма, assignsd функционируйте использует Эвристический Ценовой алгоритм Обновления, чтобы обновить лагранжевые множители. При использовании Манкров и алгоритмов JV, функция использует Ускоренный алгоритм Обновления Подградиента.
Для матриц стоимости с четко определенными решениями, такими как пассивная связь с датчиками высокой точности, разрыв решения сходится к в 0,05 (5 процентов) приблизительно в 100 итерациях.
Когда оптимальное решение неизвестно, разрыв решения может быть ненулевым, даже когда возвращенное решение оптимально.
[1] Деб, S., Yeddanapudi, M., Pattipati, K. и Панель Шалом, Y. (1997). Обобщенный алгоритм присвоения SD для мультицелевой мультидатчиком оценки состояния. Транзакции IEEE на Космических и Электронных системах, 33 (2), 523-538.
[2] Блэкмен, Сэмюэль и Роберт Пополи. Проект и анализ современных систем слежения. Норвуд, MA: Дом Artech, 1999. (1999)