二次赋值(method=‘FAQ’)¶

scipy.optimize.quadratic_assignment(A, B, method='faq', options={'maximize': False, 'partial_match': None, 'rng': None, 'P0': 'barycenter', 'shuffle_input': False, 'maxiter': 30, 'tol': 0.03})

(近似)解二次指派问题。

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

二次赋值解决以下形式的问题：

\[\begin{split}\min_P&\{\\text{trace}(A^T P B P^T)}\\ \mbox{s.t.}&{P\\ε\\Mathcal{P}}\\\end{split}\]

哪里 \(\mathcal{{P}}\) 是所有置换矩阵的集合，并且 \(A\) 和 \(B\) 是方阵。

图形匹配尝试 最大化 同样的目标函数。该算法可以被认为是寻找两个图的节点的排列，以最小化诱导边不一致的数量，或者在加权图的情况下，最小化边权重差的平方和。

请注意，二次指派问题是NP难的。这里给出的结果是近似值，不能保证是最优的。

参数

A二维阵列，正方形: 方阵 \(A\) 在上面的目标函数中。
B二维阵列，正方形: 方阵 \(B\) 在上面的目标函数中。
method字符串输入{‘FAQ’，‘2opt’}(默认值：‘FAQ’): 用于解决问题的算法。这是“常见问题”的方法特定文档。 '2opt' 也是可用的。

退货

resOptimizeResult

OptimizeResult 包含以下字段。

col_ind一维阵列: 的节点中找到的最佳排列对应的列索引 B 。
有趣的浮动: 解决方案的客观价值。
NIT集成: 执行的Frank-Wolfe迭代次数。

参见

有关参数睡觉的文档，请参阅 scipy.optimize.quadratic_assignment

选项

maximize布尔值(默认值：FALSE)

如果满足以下条件，则最大化目标函数 True 。

partial_match整数的二维数组，可选(默认值：无)

修复了部分匹配。也被称为“种子” [2].

每行 partial_match 指定一对匹配的节点：节点 partial_match[i, 0] 的 A 与节点匹配 partial_match[i, 1] 的 B 。阵列具有形状 (m, 2) ，在哪里 m 不大于节点数， \(n\) 。

rng ：{无，整型， numpy.random.Generator ，{无，整型，

numpy.random.RandomState }，可选

如果 seed 为无(或 np.random )、 numpy.random.RandomState 使用的是Singleton。如果 seed 是一个整型、一个新的 RandomState 实例，其种子设定为 seed 。如果 seed 已经是一个 Generator 或 RandomState 实例，则使用该实例。

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

初始位置。必须是双随机矩阵 [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)

对终止的容忍度。Frank-Wolfe迭代在以下情况下终止 \(\frac{{||P_{{i}}-P_{{i+1}}||_F}}{{\sqrt{{m')}}}} \leq tol\) ，在哪里 \(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，Vol.第10期，第4期，E0121002页，2015年 DOI:10.1371/journal.pone.0121002
2: D.菲什金德，S.Adali，H.Patsolic，L.Meng，D.Singh，V.Lyzinski，C.Priebe，“种子图匹配”，模式识别.87(2019年)：203-215， DOI: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

scipy.optimize.quadratic_assignment

二次赋值(method=‘2opt’)