quadratic_assignment(method=’faq’)

scipy.optimize.quadratic_assignment(A, B, method='faq', options=None)

（近似地）解决二次指派问题。

此函数使用快速近似二次指派算法 (FAQ) [1] 解决二次指派问题 (QAP) 和图匹配问题 (GMP)。

二次指派解决以下形式的问题：

\[\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\)。

method字符串，取值范围 {'faq', '2opt'} (默认值: 'faq')

用于解决问题的算法。这是针对 'faq' 的方法特定文档。'2opt' 也可用。

返回:

resOptimizeResult

包含以下字段的 OptimizeResult 对象。

col_ind1-D 数组

对应于找到的 B 节点最佳置换的列索引。

fun浮点数

解的目标值。

nit整数

执行的 Frank-Wolfe 迭代次数。

另请参阅

有关其余参数的文档，请参见 scipy.optimize.quadratic_assignment

选项:

——-

maximize布尔值 (默认值: False)

如果为 True，则最大化目标函数。

partial_match2-D 整数数组，可选 (默认值: None)

固定部分匹配。也称为“种子” [2]。

partial_match 的每一行指定一对匹配的节点：A 的节点 partial_match[i, 0] 与 B 的节点 partial_match[i, 1] 匹配。该数组的形状为 (m, 2)，其中 m 不大于节点数 \(n\)。

rng{None, int, numpy.random.Generator}，可选

伪随机数生成器状态。有关详细信息，请参见 quadratic_assignment。

P02-D 数组，“重心”，或“随机化” (默认值: “重心”)

初始位置。必须是双随机矩阵 [3]。

如果初始位置是一个数组，它必须是一个大小为 \(m' \times m'\) 的双随机矩阵，其中 \(m' = n - m\)。

如果为 "barycenter"（默认值），初始位置是 Birkhoff 多胞形（双随机矩阵空间）的重心。这是一个 \(m' \times m'\) 矩阵，所有元素都等于 \(1 / m'\)。

如果为 "randomized"，初始搜索位置是 \(P_0 = (J + K) / 2\)，其中 \(J\) 是重心，\(K\) 是一个随机双随机矩阵。

shuffle_input布尔值 (默认值: False)

设置为 True 可随机解决退化梯度。对于非退化梯度，此选项无效。

maxiter整数，正数 (默认值: 30)

指定执行的最大 Frank-Wolfe 迭代次数的整数。

tol浮点数 (默认值: 0.03)

终止容差。当 \(\frac{||P_{i}-P_{i+1}||_F}{\sqrt{m'}} \leq tol\) 时，Frank-Wolfe 迭代终止，其中 \(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, and 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]

“Doubly stochastic Matrix,” Wikipedia. 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