quadratic_assignment(method=’faq’)#

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

Löst das quadratische Zuordnungsproblem (näherungsweise).

Diese Funktion löst das Quadratische Zuordnungsproblem (QAP) und das Graph Matching Problem (GMP) unter Verwendung des Fast Approximate QAP Algorithm (FAQ) [1].

Das quadratische Zuordnungsproblem löst Probleme der folgenden Form

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

wobei \(\mathcal{P}\) die Menge aller Permutationsmatrizen ist und \(A\) und \(B\) quadratische Matrizen sind.

Graph-Matching versucht, die gleiche Zielfunktion zu *maximieren*. Dieser Algorithmus kann als das Finden der Ausrichtung der Knoten zweier Graphen betrachtet werden, die die Anzahl der induzierten Kanten-Diskrepanzen minimiert, oder im Fall von gewichteten Graphen die Summe der quadrierten Kanten-Gewichts-Differenzen.

Beachten Sie, dass das quadratische Zuordnungsproblem NP-schwer ist. Die hier angegebenen Ergebnisse sind Annäherungen und keine Garantie für Optimalität.

Parameter:

A2-D-Array, quadratisch: Die quadratische Matrix \(A\) in der obigen Zielfunktion.
B2-D-Array, quadratisch: Die quadratische Matrix \(B\) in der obigen Zielfunktion.
methodstr in {‘faq’, ‘2opt’} (Standard: ‘faq’): Der Algorithmus, der zur Lösung des Problems verwendet wird. Dies ist die methodenspezifische Dokumentation für 'faq'. ‘2opt’ ist ebenfalls verfügbar.

Rückgabe:

resOptimizeResult

OptimizeResult, der die folgenden Felder enthält.

col_ind1-D-Array: Spaltenindizes, die der besten gefundenen Permutation der Knoten von B entsprechen.
funfloat: Der Zielfunktionswert der Lösung.
nitint: Die Anzahl der durchgeführten Frank-Wolfe-Iterationen.

Siehe auch

Für die Dokumentation des Rests der Parameter siehe scipy.optimize.quadratic_assignment

Optionen:

——-

maximizebool (Standard: False)

Maximiert die Zielfunktion, wenn True.

partial_match2-D-Array von ganzen Zahlen, optional (Standard: None)

Legt einen Teil der Zuordnung fest. Auch bekannt als "Seed" [2].

Jede Zeile von partial_match gibt ein Paar zugeordneter Knoten an: Knoten partial_match[i, 0] von A wird dem Knoten partial_match[i, 1] von B zugeordnet. Das Array hat die Form (m, 2), wobei m nicht größer ist als die Anzahl der Knoten, \(n\).

rng{None, int, numpy.random.Generator}, optional

Zustand des Pseudozufallszahlengenerators. Details finden Sie unter quadratic_assignment.

P02-D-Array, „barycenter“ oder „randomized“ (Standard: „barycenter“)

Anfangsposition. Muss eine doppelt-stochastische Matrix sein [3].

Wenn die Anfangsposition ein Array ist, muss es sich um eine doppelt-stochastische Matrix der Größe \(m' \times m'\) handeln, wobei \(m' = n - m\).

Wenn "barycenter" (Standard), ist die Anfangsposition das Baryzentrum des Birkhoff-Polytops (des Raumes der doppelt-stochastischen Matrizen). Dies ist eine \(m' \times m'\) Matrix mit allen Einträgen gleich \(1 / m'\).

Wenn "randomized", ist die anfängliche Suchposition \(P_0 = (J + K) / 2\), wobei \(J\) das Baryzentrum und \(K\) eine zufällige doppelt-stochastische Matrix ist.

shuffle_inputbool (Standard: False)

Auf True setzen, um entartete Gradienten zufällig zu lösen. Für nicht-entartete Gradienten hat diese Option keine Auswirkung.

maxiterint, positiv (Standard: 30)

Ganze Zahl, die die maximale Anzahl der durchgeführten Frank-Wolfe-Iterationen angibt.

tolfloat (Standard: 0.03)

Toleranz für den Abbruch. Die Frank-Wolfe-Iteration wird beendet, wenn \(\frac{||P_{i}-P_{i+1}||_F}{\sqrt{m'}} \leq tol\), wobei \(i\) die Iterationsnummer ist.

Hinweise

Der Algorithmus kann empfindlich auf die anfängliche Permutationsmatrix (oder Such-"Position") reagieren, da es mehrere lokale Minima innerhalb des zulässigen Bereichs geben kann. Eine Baryzentrumsinitialisierung führt wahrscheinlich eher zu einer besseren Lösung als eine einzelne zufällige Initialisierung. Das mehrfache Aufrufen von quadratic_assignment mit unterschiedlichen zufälligen Initialisierungen kann jedoch zu einem besseren Optimum führen, allerdings auf Kosten einer längeren Gesamt-Ausführungszeit.

Referenzen

[1]

J.T. Vogelstein, J.M. Conroy, V. Lyzinski, L.J. Podrazik, S.G. Kratzer, E.T. Harley, D.E. Fishkind, R.J. Vogelstein und C.E. Priebe, „Fast approximate quadratic programming for graph matching“, PLOS one, Bd. 10, Nr. 4, S. 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

Beispiele

Wie oben erwähnt, führt eine Baryzentrumsinitialisierung oft zu einer besseren Lösung als eine einzelne zufällige Initialisierung.

>>> 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

Erwägen Sie jedoch, von mehreren randomisierten Initialisierungen auszuführen und das beste Ergebnis zu behalten.

>>> 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

Die Methode '2-opt' kann verwendet werden, um zu versuchen, die Ergebnisse zu verfeinern.

>>> 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