quadratic_assignment(method='faq')

scipy.optimize.quadratic_assignment(A, B, метод='faq', опции=None)

Решить квадратичную задачу назначения (приближенно).

Эта функция решает задачу квадратичного назначения (QAP) и задачу сопоставления графов (GMP) с использованием быстрого приближённого алгоритма QAP (FAQ) [1].

Квадратичное назначение решает задачи следующего вида:

\[\begin{split}\min_P & \ {\ \text{trace}(A^T P B P^T)}\\ \mbox{s.t. } & {P \ \epsilon \ \mathcal{P}}\\\end{split}\]

где \(\mathcal{P}\) является множеством всех матриц перестановок, \(A\) и \(B\) являются квадратными матрицами.

Сопоставление графов пытается максимизировать той же целевой функции. Этот алгоритм можно рассматривать как поиск выравнивания узлов двух графов, которое минимизирует количество индуцированных расхождений рёбер или, в случае взвешенных графов, сумму квадратов разностей весов рёбер.

Обратите внимание, что задача квадратичного назначения является NP-трудной. Результаты, приведённые здесь, являются приближениями и не гарантируют оптимальности.

Параметры:

A2-D массив, квадратный

Квадратная матрица \(A\) в целевой функции выше.

B2-D массив, квадратный

Квадратная матрица \(B\) в целевой функции выше.

методstr в {'faq', '2opt'} (по умолчанию: 'faq')

Алгоритм, используемый для решения задачи. Это специфичная для метода документация для 'faq'. ‘2opt’ также доступен.

Возвращает:

resOptimizeResult

OptimizeResult содержащий следующие поля.

col_indОдномерный массив

Индексы столбцов, соответствующие наилучшей найденной перестановке узлов B.

funfloat

Целевое значение решения.

nitint

Количество выполненных итераций Франка-Вольфа.

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

Для документации по остальным параметрам см. scipy.optimize.quadratic_assignment

Опции:

——-

максимизироватьbool (по умолчанию: False)

Максимизирует целевую функцию, если True.

partial_match2-D массив целых чисел, опционально (по умолчанию: None)

Исправляет часть сопоставления. Также известен как "начальное значение" [2].

Каждая строка partial_match задаёт пару сопоставленных узлов: узел partial_match[i, 0] of A соответствует узлу partial_match[i, 1] of B. Массив имеет форму (m, 2), где m не больше, чем количество узлов, \(n\).

rng{None, int, numpy.random.Generator, опционально

Состояние генератора псевдослучайных чисел. См. quadratic_assignment подробности.

P02-D массив, "барицентр" или "рандомизированный" (по умолчанию: "барицентр")

Начальная позиция. Должна быть дважды стохастической матрицей [3].

Если начальная позиция является массивом, она должна быть дважды стохастической матрицей размера \(m' \times m'\) где \(m' = n - m\).

Если "barycenter" (по умолчанию), начальная позиция — это барицентр многогранника Биркгофа (пространства дважды стохастических матриц). Это \(m' \times m'\) матрица со всеми элементами, равными \(1 / m'\).

Если "randomized" начальная позиция поиска — \(P_0 = (J + K) / 2\), где \(J\) является барицентром и \(K\) является случайной дважды стохастической матрицей.

shuffle_inputbool (по умолчанию: False)

Установить в True для разрешения вырожденных градиентов случайным образом. Для невырожденных градиентов эта опция не имеет эффекта.

maxiterint, положительное (по умолчанию: 30)

Целое число, задающее максимальное количество итераций Франка-Вольфа.

tolfloat (по умолчанию: 0.03)

Допуск для завершения. Итерация Франка-Вольфа завершается, когда \(\frac{||P_{i}-P_{i+1}||_F}{\sqrt{m'}} \leq tol\), где \(i\) — это номер итерации.

Примечания

Алгоритм может быть чувствителен к начальной матрице перестановок (или "позиции" поиска) из-за возможности нескольких локальных минимумов в допустимой области. Инициализация барицентром с большей вероятностью приведет к лучшему решению, чем единичная случайная инициализация. Однако, вызов quadratic_assignment несколько раз с разными случайными инициализациями может привести к лучшему оптимуму за счёт большего общего времени выполнения.

Ссылки

[1]

J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik, S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein, и C.E. Priebe, «Fast approximate quadratic programming for graph matching», PLOS one, vol. 10, no. 4, p. e0121002, 2015, DOI:10.1371/journal.pone.0121002

[2]

D. Fishkind, S. Adali, H. Patsolic, L. Meng, D. Singh, V. Lyzinski, C. Priebe, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203-215, DOI:10.1016/j.patcog.2018.09.014

[3]

“Дважды стохастическая матрица,” Википедия. https://en.wikipedia.org/wiki/Doubly_stochastic_matrix

Примеры

Как упомянуто выше, инициализация барицентром часто даёт лучшее решение, чем единичная случайная инициализация.

>>> from scipy.optimize import quadratic_assignment
>>> import numpy as np
>>> rng = np.random.default_rng()
>>> n = 15
>>> A = rng.random((n, n))
>>> B = rng.random((n, n))
>>> options = {"rng": rng}
>>> res = quadratic_assignment(A, B, options=options)  # FAQ is default method
>>> print(res.fun)
47.797048706380636  # may vary

>>> options = {"rng": rng, "P0": "randomized"}  # use randomized initialization
>>> res = quadratic_assignment(A, B, options=options)
>>> print(res.fun)
47.37287069769966 # may vary

Однако, рассмотрите запуск из нескольких рандомизированных инициализаций и сохранение лучшего результата.

>>> res = min([quadratic_assignment(A, B, options=options)
...            for i in range(30)], key=lambda x: x.fun)
>>> print(res.fun)
46.55974835248574 # may vary

Метод '2-opt' может быть использован для попытки улучшения результатов.

>>> options = {"partial_guess": np.array([np.arange(n), res.col_ind]).T, "rng": rng}
>>> res = quadratic_assignment(A, B, method="2opt", options=options)
>>> print(res.fun)
46.55974835248574 # may vary