quadratic_assignment(method='faq')#

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

求解二次分配问题（近似解）。

此函数使用快速近似 QAP 算法 (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 难问题。此处给出的结果是近似值，不能保证是最优的。

参数:

A二维数组，方阵: 目标函数中的方阵 \(A\) 。
B二维数组，方阵: 目标函数中的方阵 \(B\) 。
method字符串，取值范围为 {'faq', '2opt'} (默认值: 'faq'): 用于解决问题的算法。这是 'faq' 方法的特定文档。‘2opt’ 也可用。

返回:

resOptimizeResult

OptimizeResult 包含以下字段。

col_ind一维数组: 与找到的 B 节点最佳置换对应的列索引。
fun浮点数: 解的目标值。
nit整数: 执行的 Frank-Wolfe 迭代次数。

另请参阅

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

选项:

——-

maximize布尔值 (默认值: False)

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

partial_match二维整数数组，可选 (默认值: 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。

P0二维数组、“重心”或“随机化”（默认值：“重心”）

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

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

如果为 "barycenter"（默认值），则初始位置是 Birkhoff 多胞形（双随机矩阵空间）的重心。这是一个所有条目都等于 \(1 / m'\) 的 \(m' \times 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 和 C.E. Priebe，“用于图匹配的快速近似二次规划”，PLOS one，第 10 卷，第 4 期，第 e0121002 页，2015 年，DOI:10.1371/journal.pone.0121002

[2]

D. Fishkind、S. Adali、H. Patsolic、L. Meng、D. Singh、V. Lyzinski、C. Priebe，“种子图匹配”，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