quadratic_assignment(方法=“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\)。

methodstr，取 {‘faq’, ‘2opt’} (默认值：“faq”)

用于解决该问题的算法。这是“faq”的方法特定文档。还可以使用‘2opt’。

返回:

resOptimizeResult

OptimizeResult包含下列字段。

col_ind1-D 数组

B 节点的最佳排列的相应列索引。

funfloat

解的目标值。

nitint

执行的 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，

numpy.random.RandomState}, 可选

如果seed 为 None（或np.random），则使用numpy.random.RandomState单例。如果seed为 int，则使用新的RandomState实例，并用seed设置种子。如果seed已经是Generator或RandomState实例，则使用该实例。

P02 维数组、“质心”或“随机”（默认值：“质心”）

初始位置。必须是双随机矩阵 [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 以随机解决退化梯度。对于非退化梯度，此选项无效。

maxiterint，正数（默认值：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，数字对象标识符：10.1016/j.patcog.2018.09.014

[3]

“双随机矩阵”，维基百科。https://en.wikipedia.org/wiki/Doubly_stochastic_matrix

示例

如上所述，质心初始化常常比单次随机初始化产生更好的解决方案。

>>> from numpy.random import default_rng
>>> rng = default_rng()
>>> n = 15
>>> A = rng.random((n, n))
>>> B = rng.random((n, n))
>>> res = quadratic_assignment(A, B)  # FAQ is default method
>>> print(res.fun)
46.871483385480545  # may vary

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

但是，考虑从多个随机初始化开始并保留最佳结果。

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

可以使用“2-opt”方法进一步优化结果。

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