scipy.optimize.

quadratic_assignment

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

Approximiert die Lösung für das quadratische Zuordnungsproblem und das Graph-Matching-Problem.

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 zur Lösung des Problems. ‘faq’ (Standard) und ‘2opt’ sind verfügbar.

optionsdict, optional

Ein Dictionary von Solver-Optionen. Alle Solver unterstützen das Folgende

maximizebool (Standard: False)

Maximiert die Zielfunktion, wenn True.

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

Fixiert einen Teil der Zuordnung. 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\).

rngnumpy.random.Generator, optional

Zustand des Pseudozufallszahlengenerators. Wenn rng None ist, wird ein neuer numpy.random.Generator mit Entropie aus dem Betriebssystem erstellt. Typen außer numpy.random.Generator werden an numpy.random.default_rng übergeben, um einen Generator zu instanziieren.

Geändert in Version 1.15.0: Als Teil des SPEC-007 Übergangs von der Verwendung von numpy.random.RandomState zu numpy.random.Generator. Die Übergabe von np.random.RandomState an diese Funktion gibt nun eine DeprecationWarning aus. In SciPy 1.17 löst die Verwendung eine Ausnahme aus. Darüber hinaus wird die Abhängigkeit vom globalen Zustand durch np.random.seed eine FutureWarning auslösen. In SciPy 1.17 wird der globale Zufallszahlengenerator nicht mehr verwendet. Die Verwendung eines int-ähnlichen Seeds löst eine FutureWarning aus, in SciPy 1.17 wird er über np.random.default_rng anstelle von np.random.RandomState normalisiert.

Für methodenspezifische Optionen siehe show_options('quadratic_assignment').

Rückgabe:

resOptimizeResult

OptimizeResult mit den folgenden Feldern.

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 während der Optimierung durchgeführten Iterationen.

Hinweise

Die Standardmethode ‘faq’ verwendet den Fast Approximate QAP-Algorithmus [1]; er bietet typischerweise die beste Kombination aus Geschwindigkeit und Genauigkeit. Die Methode ‘2opt’ kann rechenintensiv sein, ist aber eine nützliche Alternative oder kann zur Verfeinerung der von einer anderen Methode zurückgegebenen Lösung verwendet werden.

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]

„2-opt“, Wikipedia. https://en.wikipedia.org/wiki/2-opt

Beispiele

Probieren Sie es in Ihrem Browser aus!

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

Um die Beziehung zwischen dem zurückgegebenen col_ind und fun zu sehen, verwenden Sie col_ind, um die beste gefundene Permutationsmatrix zu bilden, und werten Sie dann die Zielfunktion \(f(P) = trace(A^T P B P^T )\) aus.

>>> perm = res['col_ind']
>>> P = np.eye(len(A), dtype=int)[perm]
>>> fun = np.trace(A.T @ P @ B @ P.T)
>>> print(fun)
3260

Alternativ können Sie, um die explizite Konstruktion der Permutationsmatrix zu vermeiden, die Zeilen und Spalten der Distanzmatrix direkt permutieren.

>>> fun = np.trace(A.T @ B[perm][:, perm])
>>> print(fun)
3260

Obwohl im Allgemeinen nicht garantiert, hat quadratic_assignment die global optimale Lösung gefunden.

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

Hier ist ein Beispiel, für das die Standardmethode ‘faq’ nicht die globale Optimallösung findet.

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

Wenn Genauigkeit wichtig ist, sollten Sie die Methode ‘2opt’ verwenden, um die Lösung zu verfeinern.

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

ZurückIn Tab öffnen