scipy.optimize.

quadratic_assignment

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

Аппроксимирует решение квадратичной задачи назначения и задачи сопоставления графов.

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

\[\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’ доступны.

опцииdict, optional

Словарь опций решателя. Все решатели поддерживают следующее:

максимизировать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\).

rngnumpy.random.Generator, опционально

Состояние генератора псевдослучайных чисел. Когда rng равно None, новый numpy.random.Generator создаётся с использованием энтропии из операционной системы. Типы, отличные от numpy.random.Generator передаются в numpy.random.default_rng для создания экземпляра Generator.

Изменено в версии 1.15.0: В рамках SPEC-007 переход от использования numpy.random.RandomState to numpy.random.Generator происходит. Предоставление np.random.RandomState к этой функции теперь будет выдавать DeprecationWarning. В SciPy 1.17 его использование вызовет исключение. Кроме того, использование глобального состояния с помощью np.random.seed будет выдавать FutureWarning. В SciPy 1.17 глобальный генератор случайных чисел больше не будет использоваться. Использование целочисленного seed вызовет FutureWarning, в SciPy 1.17 она будет нормализована через np.random.default_rng вместо np.random.RandomState.

Для специфичных для метода опций см. show_options('quadratic_assignment').

Возвращает:

resOptimizeResult

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

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

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

funfloat

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

nitint

Количество итераций, выполненных во время оптимизации.

Примечания

Метод по умолчанию ‘faq’ использует быстрый приближенный алгоритм QAP [1]; обычно он предлагает наилучшее сочетание скорости и точности. Метод ‘2opt’ может быть вычислительно затратным, но может быть полезной альтернативой или использоваться для уточнения решения, возвращённого другим методом.

Ссылки

[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]

“2-opt,” Википедия. https://en.wikipedia.org/wiki/2-opt

Примеры

Попробуйте в вашем браузере!

>>> import numpy as np
>>> from scipy.optimize import quadratic_assignment
>>> rng = np.random.default_rng()
>>> A = np.array([[0, 80, 150, 170], [80, 0, 130, 100],
...               [150, 130, 0, 120], [170, 100, 120, 0]])
>>> B = np.array([[0, 5, 2, 7], [0, 0, 3, 8],
...               [0, 0, 0, 3], [0, 0, 0, 0]])
>>> res = quadratic_assignment(A, B, options={'rng': rng})
>>> print(res)
     fun: 3260
 col_ind: [0 3 2 1]
     nit: 9

Чтобы увидеть взаимосвязь между возвращаемыми col_ind и funиспользуйте col_ind чтобы сформировать найденную наилучшую матрицу перестановок, затем вычислить целевую функцию \(f(P) = trace(A^T P B P^T )\).

>>> perm = res['col_ind']
>>> P = np.eye(len(A), dtype=int)[perm]
>>> fun = np.trace(A.T @ P @ B @ P.T)
>>> print(fun)
3260

В качестве альтернативы, чтобы избежать явного построения матрицы перестановок, непосредственно переставьте строки и столбцы матрицы расстояний.

>>> fun = np.trace(A.T @ B[perm][:, perm])
>>> print(fun)
3260

Хотя в общем случае не гарантируется, quadratic_assignment случайно нашел глобально оптимальное решение.

>>> from itertools import permutations
>>> perm_opt, fun_opt = None, np.inf
>>> for perm in permutations([0, 1, 2, 3]):
...     perm = np.array(perm)
...     fun = np.trace(A.T @ B[perm][:, perm])
...     if fun < fun_opt:
...         fun_opt, perm_opt = fun, perm
>>> print(np.array_equal(perm_opt, res['col_ind']))
True

Вот пример, для которого метод по умолчанию, ‘faq’, не находит глобальный оптимум.

>>> A = np.array([[0, 5, 8, 6], [5, 0, 5, 1],
...               [8, 5, 0, 2], [6, 1, 2, 0]])
>>> B = np.array([[0, 1, 8, 4], [1, 0, 5, 2],
...               [8, 5, 0, 5], [4, 2, 5, 0]])
>>> res = quadratic_assignment(A, B, options={'rng': rng})
>>> print(res)
     fun: 178
 col_ind: [1 0 3 2]
     nit: 13

Если важна точность, рассмотрите использование ‘2opt’ для уточнения решения.

>>> guess = np.array([np.arange(len(A)), res.col_ind]).T
>>> res = quadratic_assignment(A, B, method="2opt",
...     options = {'rng': rng, 'partial_guess': guess})
>>> print(res)
     fun: 176
 col_ind: [1 2 3 0]
     nit: 17

НазадОткрыть во вкладке