assignsd

Присвоение 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.

Примеры

свернуть все

Используйте assignsd выполнять строгое присвоение без индекса 1.

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

costMatrix = rand(6,6,6);

Инициализируйте fullmatrix ко всему Inf. fullmatix один размер, больше, чем матрица стоимости во всех размерностях.

fullMatrix = inf(7,7,7);

Установите внутреннюю матрицу на costMatrix обеспечивать присвоения включающий индекс 1, чтобы иметь бесконечную стоимость.

fullMatrix(2:end,2:end,2:end) = costMatrix;
fullMatrix(1,1,1) = 0;
[assignments,cost,gapAchieved] = assignsd(fullMatrix,0.01,100);

Восстановите фактические индексы.

assignments = assignments - 1
assignments = 6x3 uint32 matrix

   1   6   6
   2   4   3
   3   3   4
   4   1   2
   5   2   1
   6   5   5

Входные параметры

свернуть все

Стойте матрицы в виде n-мерного массива где costmatrix(i,j,k ...) задает стоимость n-кортежа (i,j,k, ...) в присвоении. Индекс '1' на всех размерностях в costmatrix представляет фиктивное измерение или ложную дорожку и используется, чтобы завершить проблему присвоения. Индекс 1, будучи макетом, может быть частью нескольких n-кортежей. Индекс может быть присвоен несколько раз. Типичная величина затрат для costmatrix(1,1,1,1, ...) 0.

Типы данных: single | double

Желаемый максимальный разрыв между двойным и возможными решениями в виде неотрицательного скаляра.

Пример: 0.05

Типы данных: single | double

Максимальное количество итераций в виде положительного целого числа.

Пример: 50

Типы данных: single | double

Алгоритм присвоения для того, чтобы решить 2D задачу присвоения в виде 'munkres' для алгоритма Munkres, 'jv' для алгоритма Jonker-Volgenant или 'auction' для Аукционного алгоритма.

Пример: 'jv'

Выходные аргументы

свернуть все

Присвоения дорожек к обнаружениям, возвращенным как P-by-N список присвоений. Присвоения типа [1 1 Q 1] от четырехмерной стоимости матрица может рассматриваться как Q-1 сущность от размерности 3, который оставили неприсвоенным. Величина затрат в (1,1,Q,1) задает стоимость не присвоения (Q-1) th сущность от размерности 3.

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

Типы данных: single | double

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

Типы данных: single | double

Алгоритмы

  • Лагранжевый релаксационный метод вычисляет субоптимальное решение проблемы присвоения 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)

Расширенные возможности

Смотрите также

Функции

Введенный в R2018b
Для просмотра документации необходимо авторизоваться на сайте