Ctrl+K
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-hard 問題。此處給出的結果是近似值，並不保證是最佳解。

參數:
A二維陣列，方陣

目標函數中的方陣 \(A\)。

B二維陣列，方陣

目標函數中的方陣 \(B\)。

methodstr，可選值為 {‘faq’, ‘2opt’} (預設值：‘faq’)

用於解決問題的演算法。‘faq’ (預設值) 和 ‘2opt’ 可用。

optionsdict，選填

求解器選項的字典。所有求解器都支援以下選項

maximizebool (預設值：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 中，將不再使用全域隨機數產生器。使用類似整數的種子將引發 FutureWarning，在 SciPy 1.17 中它將通過 np.random.default_rng 而不是 np.random.RandomState 進行標準化。

有關方法特定的選項，請參閱 show_options('quadratic_assignment')。

回傳:
resOptimizeResult

OptimizeResult 包含以下欄位。

col_ind一維陣列

對應於 B 節點的最佳排列的列索引。

funfloat

解的目標值。

nitint

最佳化期間執行的迭代次數。

註解

預設方法 ‘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, and C.E. Priebe, “Fast approximate quadratic programming for graph matching,” 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, “Seeded graph matching”, Pattern Recognit. 87 (2019): 203-215, DOI:10.1016/j.patcog.2018.09.014

[3]

“2-opt,” Wikipedia. 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
本頁面