Wie führt man eine diskrete Optimierung von Funktionen über Matrizen durch?
Ich möchte über alle 30 mal 30 Matrizen mit Einträgen, die 0 oder 1 sind, optimieren. Meine Zielfunktion ist die Determinante. Eine Möglichkeit wäre eine stochastische Gradientenabsenkung oder simuliertes Annealing.
Ich habe mir scipy.optimize angesehen, aber das scheint diese Art von Unterstützung nicht zu unterstützen Optimierung, soweit ich das beurteilen kann. scipy.optimize.basinhopping sah sehr verlockend aus, aber es scheint kontinuierliche Variablen zu benötigen.
Gibt es in Python irgendwelche Werkzeuge für diese Art der allgemeinen diskreten Optimierung?
3 Antworten
Ich denke, ein genetischer Algorithmus könnte in diesem Fall gut funktionieren. Hier ist ein kurzes Beispiel, das zusammen mit deap zusammengestellt wurde, basierend auf dem Beispiel hier :
Es dauert ungefähr 40 Sekunden, um 1000 Generationen auf meinem Laptop zu laufen, was mich von einem minimalen Determinantenwert von ungefähr -5,7845x10 8 bis -6,41504x10 11 bringt. Ich habe nicht wirklich viel mit den Meta-Parametern (Bevölkerungsgröße, Mutationsrate, Crossover-Rate usw.) herumgespielt, also bin ich mir sicher, dass es viel besser geht.
Hier ist eine stark verbesserte Version, die eine viel intelligentere Crossover-Funktion implementiert, die Blöcke von Zeilen oder Spalten über Individuen hinweg tauscht und eine % Funktion verwendet. co_de% , um zu garantieren, dass jeder Mutationsschritt eine neue Konfiguration erzeugt, und um die Bewertung der Determinante für Konfigurationen zu überspringen, die bereits ausprobiert wurden:
%Vor% Mein bisher bestes Ergebnis liegt bei -3.23718x10 13 -3.92366x10 13 nach 10000 1000 Generationen Das dauert etwa 45 Sekunden an meinem Gerät.
Basierend auf der in den Kommentaren verlinkten Lösung cthonicdaemon muss die maximale Determinante für eine 31x31-Hadamard-Matrix mindestens 75960984159088 × 2 30 ~ = 8.1562x10 22 (es ist noch nicht bewiesen, ob diese Lösung optimal ist). Die maximale Determinante für eine (n-1 x n-1) binäre Matrix ist 2 1-n-mal der Wert für eine (n × n) Hadamard-Matrix, dh 8.1562 × 10 22 x 2 -30 ~ = 7.5961x10 13 , so dass der genetische Algorithmus in einer Größenordnung der derzeit bekanntesten Lösung liegt.
Allerdings scheint die Fitness-Funktion hier zu plateau, und ich habe es schwer, -4x10 13 zu brechen. Da es sich um eine heuristische Suche handelt, gibt es keine Garantie dafür, dass das globale Optimum irgendwann gefunden wird.
Ich kenne keine direkte Methode zur diskreten Optimierung in scipy . Eine Alternative ist das simanneal -Paket von pip oder github, mit dem Sie Ihre eigene Move-Funktion einführen können Beschränke es auf Bewegungen innerhalb deiner Domain:
Ich habe das ein bisschen untersucht.
Ein paar Dinge zuerst: 1) 56 Millionen ist der Maximalwert, wenn die Größe der Matrix 21x21 ist, nicht 30x30: Ссылка .
Aber das ist auch eine obere Schranke für -1, 1 Matrizen, nicht für 1.0.
BEARBEITEN: Lesen Sie diesen Link genauer:
Die maximalen Determinanten von {1, -1} -Matrizen bis zur Größe n = 21 sind in der folgenden Tabelle angegeben. Größe 22 ist der kleinste offene Fall. In der Tabelle repräsentiert D (n) die maximale Determinante dividiert durch 2n-1. Gleichermaßen repräsentiert D (n) die maximale Determinante einer {0, 1} -Matrix der Größe n-1.
Diese Tabelle kann also für obere Grenzen verwendet werden, aber denken Sie daran, dass sie durch 2n-1 geteilt sind. Beachten Sie auch, dass 22 der kleinste offene Fall ist. Daher wurde das Maximum einer 30x30-Matrix nicht gefunden und ist noch nicht einmal annähernd fertig.
2) Der Grund, warum David Zwickers Code eine Antwort von 30 Millionen gibt, liegt wahrscheinlich an der Tatsache, dass er minimiert. Nicht maximierend.
%Vor%Siehst du, wie er dort das Minuszeichen hat?
3) Auch der Lösungsraum für dieses Problem ist sehr groß. Ich berechne die Anzahl der verschiedenen Matrizen zu 2 ^ (30 * 30), d.h. in der Größenordnung von 10 ^ 270. Es ist einfach unmöglich, jede Matrix zu betrachten, und selbst die meisten von ihnen betrachten wir auch.
Ich habe hier ein bisschen Code (angepasst von David Zwickers Code), der läuft, aber ich habe keine Ahnung, wie nahe es dem tatsächlichen Maximum ist. Es dauert ungefähr 45 Minuten, um 10 Millionen Iterationen auf meinem PC durchzuführen, oder nur ungefähr 2 Minuten für 1 Milliteriterationen. Ich bekomme einen Maximalwert von rund 3,4 Milliarden. Aber ich habe keine Ahnung, wie nah das dem theoretischen Maximum ist.
%Vor%Hilft das?
Tags und Links python numpy mathematical-optimization scipy discrete-mathematics