Exponenta Banner
exponenta event banner

assignsd

Назначение S-D с использованием лагранжевой релаксации

свернуть все на странице

Синтаксис

[присвоения, затраты, solityGap] = assignsd (costmatrix)
[присвоения, затраты, solityGap] = assignsd (costmatrix, desiredGap)
[присвоения, затраты, solityGap] = присваиваемые (costmatrix, desiredGap, maxIterations)
[assignments, cost, solityGap] = assignsd (costmatrix, desiredGap, maxIterations, алгоритм)

Описание

[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

Алгоритм назначения для решения задачи назначения 2-D, указанный как 'munkres' для алгоритма Манкра, 'jv' для алгоритма Йонкера-Волгенанта, или 'auction' для алгоритма аукциона.

Пример: 'jv'

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

свернуть все

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

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

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

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

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

Алгоритмы

  • Метод лагранжевой релаксации вычисляет неоптимальное решение задачи назначения S-D. Способ уменьшает проблему назначения S-D до проблемы назначения 2-D, используя набор множителей Лагранжа. Проблема расслабленного назначения 2-D обычно известна как двойственная задача, которая может быть решена оптимально с использованием алгоритмов, таких как алгоритм Манкра. Затем на двойное решение накладываются ограничения путем решения множества задач назначения 2-D для получения возможного решения первоначальной задачи. Стоимость двойного решения и выполнимого решения служит нижней и верхней границами для оптимальной стоимости, соответственно. Алгоритм итеративно пытается минимизировать зазор между двойственным и возможным решениями, обычно известным как двойной зазор. Итерация останавливается, когда двойной промежуток находится ниже требуемого промежутка или достигнуто максимальное число итераций.

  • При использовании алгоритма аукциона assignsd функция использует алгоритм эвристического обновления цены для обновления множителей Лагранжа. При использовании алгоритмов Munkres и JV функция использует алгоритм Accelerated Subgradient Update.

  • Для матриц затрат с четко определенными решениями, такими как пассивная связь с высокоточными датчиками, зазор решения сходится в пределах 0,05 (5 процентов) приблизительно за 100 итераций.

  • Поскольку оптимальное решение неизвестно, зазор в решении может быть ненулевым, даже когда возвращаемое решение является оптимальным.

Ссылки

[1] Деб, С., Йедданапуди, М., Паттипати, К. и Бар-Шалом, Ю. (1997). Обобщенный алгоритм назначения SD для оценки многосенсорного-многоцелевого состояния. Сделки IEEE по аэрокосмическим и электронным системам, 33 (2), 523-538.

[2] Блэкман, Сэмюэл и Роберт Пополи. Проектирование и анализ современных систем слежения. Норвуд, Массачусетс: Artech House, 1999. (1999)

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

.

См. также

Функции

Представлен в R2018b

Документация по комплекту инструментов для слияния и отслеживания датчиков

Поддержка