scipy.optimize.

quadratic_assignment#

scipy.optimize.quadratic_assignment(A, B, method='faq', options=None)[source]#

逼近求解二次分配问题和图匹配问题。

二次分配问题求解下列形式的问题：

\[\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-hard 问题。此处给出的结果是逼近结果，无法保证是最优解。

参数:
A2-D 数组，方阵

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

B2-D 数组，方阵

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

methodstr in {‘faq’, ‘2opt’}（默认值："faq"）

用于解决问题的算法。可以使用‘faq’（默认值）和‘2opt’。

options字典，可选

求解器选项词典。所有求解器都支持以下操作：

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,

如果seed 为 None（或np.random），则会使用numpy.random.RandomState 单例。如果seed 为一个整数，则会使用一个新的RandomState 实例，并使用seed 进行填充。如果seed 已经是一个Generator 或RandomState 实例，那么就会使用该实例。

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

返回:
res优化结果

优化结果，其中包含以下字段。

col_ind一维数组

B 节点的最佳顺序对应的列指标。

funfloat

解决方案的目标值。

nitint

优化过程中执行的迭代次数。

注意

默认方法 ‘faq’ 使用快速近似 QP 算法 [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，卷 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]

“2-opt”，维基百科。https://en.wikipedia.org/wiki/2-opt

示例

>>> import numpy as np
>>> from scipy.optimize import quadratic_assignment
>>> 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)
>>> 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)
>>> 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 = {'partial_guess': guess})
>>> print(res)
     fun: 176
 col_ind: [1 2 3 0]
     nit: 17
在此页面上