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\\ε\\Mathcal{P}}\\\end{split}\]哪里 \(\mathcal{{P}}\) 是所有置换矩阵的集合，并且 \(A\) 和 \(B\) 是方阵。
图形匹配尝试 最大化 同样的目标函数。该算法可以被认为是寻找两个图的节点的排列，以最小化诱导边不一致的数量，或者在加权图的情况下，最小化边权重差的平方和。
请注意，二次指派问题是NP难的。这里给出的结果是近似值，不能保证是最优的。
- 参数
- A二维阵列，正方形
方阵 \(A\) 在上面的目标函数中。
- B二维阵列，正方形
方阵 \(B\) 在上面的目标函数中。
- method字符串输入{‘FAQ’，‘2opt’}(默认值：‘FAQ’)
- optionsDICT，可选
求解器选项词典。所有解算器都支持以下功能：
- 最大化布尔值(默认值：FALSE)
如果满足以下条件，则最大化目标函数
True。- partial_match整数的二维数组，可选(默认值：无)
修复了部分匹配。也被称为“种子” [2].
每行 partial_match 指定一对匹配的节点：节点
partial_match[i, 0]的 A 与节点匹配partial_match[i, 1]的 B 。阵列具有形状(m, 2)，在哪里m不大于节点数， \(n\) 。- RNG：{None，int，
numpy.random.Generator，{无，整型， 如果 seed 为无(或 np.random )、
numpy.random.RandomState使用的是Singleton。如果 seed 是一个整型、一个新的RandomState实例，其种子设定为 seed 。如果 seed 已经是一个Generator或RandomState实例，则使用该实例。
有关特定于方法的选项，请参见
show_options('quadratic_assignment')。
- 退货
- resOptimizeResult
OptimizeResult包含以下字段。- col_ind一维阵列
的节点中找到的最佳排列对应的列索引 B 。
- 有趣的浮动
解决方案的客观价值。
- 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期，第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
“2-OPT，”维基百科。https://en.wikipedia.org/wiki/2-opt
示例
>>> 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) col_ind: array([0, 3, 2, 1]) fun: 3260 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) col_ind: array([1, 0, 3, 2]) fun: 178 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) col_ind: array([1, 2, 3, 0]) fun: 176 nit: 17