quadratic_assignment(method=’faq’)#

scipy.optimize.quadratic_assignment(A, B, method='faq', options=None)

求解二次指派問題（近似解）。

此函數使用快速近似 QAP 演算法 (FAQ) [1] 求解二次指派問題 (QAP) 和圖形匹配問題 (GMP)。

二次指派求解以下形式的問題

\[\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 in {‘faq’, ‘2opt’} (預設值：‘faq’): 用於解決問題的演算法。這是 ‘faq’ 的方法特定文件。‘2opt’ 也可用。

返回:

resOptimizeResult

OptimizeResult 包含以下欄位。

col_ind一維陣列: 對應於 B 節點的最佳置換的行索引。
fun浮點數: 解的目標值。
nit整數: 執行的 Frank-Wolfe 迭代次數。

另請參閱

有關其餘參數的文件，請參閱 scipy.optimize.quadratic_assignment

選項:

——-

maximizebool (預設值：False)

如果 True，則最大化目標函數。

partial_match二維整數陣列，可選 (預設值：None)

固定部分匹配。也稱為 “種子” [2]。

partial_match 的每一列指定一對匹配的節點：A 的節點 partial_match[i, 0] 與 B 的節點 partial_match[i, 1] 匹配。陣列的形狀為 (m, 2)，其中 m 不大於節點數，\(n\)。

rng{None, int, numpy.random.Generator}, 可選

虛擬隨機數產生器狀態。有關詳細資訊，請參閱 quadratic_assignment。

P0二維陣列，“重心”，或 “隨機化” (預設值：“重心”)

初始位置。必須是雙隨機矩陣 [3]。

如果初始位置是陣列，則它必須是大小為 \(m' \times m'\) 的雙隨機矩陣，其中 \(m' = n - m\)。

如果 "barycenter" (預設值)，則初始位置是 Birkhoff 多胞形（雙隨機矩陣空間）的重心。這是一個 \(m' \times m'\) 矩陣，其中所有條目都等於 \(1 / m'\)。

如果 "randomized"，則初始搜尋位置為 \(P_0 = (J + K) / 2\)，其中 \(J\) 是重心，而 \(K\) 是隨機雙隨機矩陣。

shuffle_inputbool (預設值：False)

設定為 True 以隨機解決退化梯度。對於非退化梯度，此選項無效。

maxiter整數，正數 (預設值：30)

指定執行的 Frank-Wolfe 迭代最大次數的整數。

tol浮點數 (預設值：0.03)

終止容差。當 \(\frac{||P_{i}-P_{i+1}||_F}{\sqrt{m'}} \leq tol\) 時，Frank-Wolfe 迭代終止，其中 \(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, 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]

“Doubly stochastic Matrix,” Wikipedia. https://en.wikipedia.org/wiki/Doubly_stochastic_matrix

範例

如上所述，與單一隨機初始化相比，重心初始化通常會產生更好的解。

>>> from scipy.optimize import quadratic_assignment
>>> import numpy as np
>>> rng = np.random.default_rng()
>>> n = 15
>>> A = rng.random((n, n))
>>> B = rng.random((n, n))
>>> options = {"rng": rng}
>>> res = quadratic_assignment(A, B, options=options)  # FAQ is default method
>>> print(res.fun)
47.797048706380636  # may vary

>>> options = {"rng": rng, "P0": "randomized"}  # use randomized initialization
>>> res = quadratic_assignment(A, B, options=options)
>>> print(res.fun)
47.37287069769966 # may vary

但是，考慮從多個隨機初始化執行並保留最佳結果。

>>> res = min([quadratic_assignment(A, B, options=options)
...            for i in range(30)], key=lambda x: x.fun)
>>> print(res.fun)
46.55974835248574 # may vary

‘2-opt’ 方法可用於嘗試改進結果。

>>> options = {"partial_guess": np.array([np.arange(n), res.col_ind]).T, "rng": rng}
>>> res = quadratic_assignment(A, B, method="2opt", options=options)
>>> print(res.fun)
46.55974835248574 # may vary