scipy.optimize.

quadratic_assignment#

scipy.optimize.quadratic_assignment(A, B, method='faq', options=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 难的。这里给出的结果是近似值，不能保证是最优的。

参数:

A二维数组，方阵

目标函数中的方阵 \(A\)。

B二维数组，方阵

目标函数中的方阵 \(B\)。

method字符串，取值于 {‘faq’, ‘2opt’} (默认值: ‘faq’)

用于解决问题的算法。 ‘faq’ (默认) 和 ‘2opt’ 可用。

options字典，可选

求解器选项的字典。所有求解器都支持以下选项

maximize布尔值 (默认值: False)

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

partial_match二维整数数组，可选 (默认值: None)

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

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

rngnumpy.random.Generator，可选

伪随机数生成器状态。当 rng 为 None 时，将使用来自操作系统的熵创建一个新的 numpy.random.Generator。除 numpy.random.Generator 之外的类型将传递给 numpy.random.default_rng 以实例化一个 Generator。

在 1.15.0 版本中更改: 作为从使用 numpy.random.RandomState 过渡到 numpy.random.Generator 的 SPEC-007 过渡的一部分正在发生。向此函数提供 np.random.RandomState 现在会发出 DeprecationWarning。在 SciPy 1.17 中，它的使用将引发异常。此外，依赖使用 np.random.seed 的全局状态将发出 FutureWarning。在 SciPy 1.17 中，将不再使用全局随机数生成器。使用 int-like 种子将引发 FutureWarning，在 SciPy 1.17 中，它将通过 np.random.default_rng 而不是 np.random.RandomState 进行规范化。

有关特定于方法的选项，请参阅 show_options('quadratic_assignment')。

返回:

resOptimizeResult

OptimizeResult，其中包含以下字段。

col_ind一维数组: 与找到的 B 节点最佳排列对应的列索引。
fun浮点数: 解的目标值。
nit整数: 优化期间执行的迭代次数。

注释

默认方法 ‘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, “用于图匹配的快速近似二次规划,” 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, “种子图匹配”, 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