Optimierung mit diskreten Parametern in Matlab

Grundsätzlich ist dies ein Lock-Pick-Problem, bei dem die Lock-Pins 20 verschiedene Positionen haben und es 12 Pins gibt. Auch:

• einige der Pin-Positionen werden blockiert, abhängig von den Positionen aller anderen Pins.
• Abhängig von den Besonderheiten der Sperre können mehrere Schlüssel vorhanden sein, die zu
passen

... interessant!

Basierend auf Rasmans Ansatz und Phpdnas Kommentar, und ist die Annahme, dass Sie int8 als Datentyp verwenden, unter den gegebenen Einschränkungen

mögliche Vektoren s (gib oder nimm ein paar, habe nicht an +1 gedacht usw.). ~ 740 Millionen Auswertungen Ihrer relativ einfachen f(s) sollten nicht länger als 2 Sekunden dauern, und nachdem Sie alle s gefunden haben, die f(s) maximieren, bleibt Ihnen das Problem, lineare Kombinationen zu finden in Ihrem Vektorsatz, der zu einer dieser Lösungen s addiert.

Natürlich ist dieses Finden von Kombinationen keine leichte Aufgabe, und die ganze Methode bricht trotzdem zusammen, wenn Sie es mit

Also werde ich hier einen direkteren und allgemeineren Ansatz diskutieren.

Da wir Integer und einen ziemlich großen Suchraum sprechen, würde ich vorschlagen, einen Branch-and-Bound-Algorithmus zu verwenden. Im Gegensatz zum bintprog -Algorithmus müssten Sie jedoch verschiedene Verzweigungsstrategien verwenden, und diese sollten natürlich auf einer nichtlinearen Zielfunktion basieren.

Leider gibt es nichts dergleichen in der Optimierungs-Toolbox (oder den Dateiaustausch, soweit ich finden konnte). fmincon ist ein No-Go, da es Gradienten- und hessische Informationen verwendet (die für Ganzzahlen normalerweise nur Null sind), und fminsearch ist ein No-Go, da Sie wirklich ein brauchen gute anfängliche Schätzung, und die Rate der Konvergenz ist (etwa) O(N) , was bedeutet, dass Sie für dieses 20-dimensionale Problem ziemlich lange vor der Konvergenz warten müssen, ohne die Garantie zu haben fand die globale Lösung.

Eine Intervallmethode könnte eine Möglichkeit sein, aber ich persönlich habe sehr wenig Erfahrung damit. Es gibt keine nativen intervallbezogenen Sachen in MATLAB oder einer seiner Toolboxen, aber es gibt das frei verfügbare INTLAB .

Wenn Sie also nicht Ihren eigenen nichtlinearen binären Integer-Programmieralgorithmus implementieren möchten oder keine Lust auf ein Abenteuer mit INTLAB haben, gibt es nur noch eines: heuristische Methoden . In diesem Link gibt es diesen Link ist eine ähnliche Situation, mit einem Überblick über die Lösung: Verwenden Sie den genetischen Algorithmus ( ga ) aus der Toolbox Globale Optimierung.

Ich würde das Problem ungefähr so ​​implementieren:

Beachten Sie, dass, obwohl Ihre Integritätsregeln im Wesentlichen linear sind, die Art und Weise, wie Sie den Wert für s berechnen müssen, die Verwendung einer benutzerdefinierten Einschränkungsfunktion ( nonlcon ) erfordert.

Beachten Sie, dass dies derzeit (wahrscheinlich) eine suboptimale Methode ist, um ga zu verwenden - ich kenne die Einzelheiten Ihrer Zielfunktion nicht, es könnte also viel mehr möglich sein. Zum Beispiel benutze ich derzeit eine einfache round() , um die Eingabe X in Ganzzahlen zu konvertieren, aber 'PopulationType', 'custom' (mit einer benutzerdefinierten 'CreationFcn' , 'MutationFcn' usw.) zu verwenden, könnte bessere Ergebnisse liefern. Außerdem wird 'Vectorized' die Dinge wahrscheinlich sehr beschleunigen, aber ich weiß nicht, ob Ihre Funktion leicht vektorisiert werden kann.

Und ja, ich benutze geschachtelte Funktionen (ich liebe diese Dinge einfach!); Es verhindert diese riesigen, normalerweise identischen Listen von Eingabeargumenten, wenn Sie Unterfunktionen oder Standalone-Funktionen verwenden, und sie können wirklich eine Leistungssteigerung sein, da nur wenig Daten kopiert werden. Aber ich weiß, dass ihre Scoping-Regeln sie etwas mit goto constructs ähnlich machen, und so sind sie -ahum- "nicht jedermanns Sache" ... du könntest sie in Unterfunktionen umwandeln wollen, um lange und nutzlos zu verhindern Diskussionen mit Ihren Mitarbeitern :)

Wie auch immer, das sollte ein guter Anfang sein. Lassen Sie mich wissen, ob dies überhaupt nützlich ist.

Wenn Sie nicht irgendeine Intelligenz darüber definieren, wie die Vektormengen organisiert sind, wird es keine intelligente Möglichkeit geben, Ihr Problem anders als reine rohe Gewalt zu lösen.

Sagen Sie, Sie finden s s.t. f (s) ist max gegebenen Einschränkungen von s, müssen Sie noch herausfinden, wie man s mit zwölf 4-Element-Vektoren (ein überbestimmtes System, wenn es jemals war), wo jeder Vektor 20 mögliche Werte hat. Sparsity mag helfen, obwohl ich mir nicht sicher bin, wie es möglich ist, einen Vektor mit vier Elementen zu haben 70-90% zero, und Sparsity wäre nur dann nützlich, wenn es noch einige Methoden zur Strukturierung des Vektors gäbe. p>

Ich sage also nicht, dass Sie das Problem nicht lösen können, ich sage, dass Sie überdenken müssen, wie das Problem aufgebaut ist.

Ich weiß, diese Antwort erreicht Sie wirklich late .

Leider zeigt das Problem, so wie es ist, nicht viele Muster, die außer der rohen Gewalt - Branch & amp; Bound, Master & amp; Slave, usw.- Versuchen eines Master-Slave-Ansatzes -i.e. zuerst die Funktion kontinuierliches nichtlineares Problem als Master zu lösen, und das Lösen der diskreten Auswahl als Slave könnte helfen, aber mit so vielen Kombinationen und ohne weitere Informationen über die Vektoren gibt es nicht zu viel Platz für die Arbeit.

Aber basierend auf den gegebenen kontinuierlichen fast überall Funktionen, basierend auf Kombinationen von Summen und Multiplikationsoperatoren und deren Inversen, ist die Sparsity ein klarer Punkt, der hier ausgenutzt werden soll. Wenn 70-90% der Vektoren Null sind, ist fast ein guter Teil des Lösungsraums nahe bei Null oder nahe bei infinite . Daher würde eine 80-20-Pseudolösung die "Null" -Kombinationen leicht verwerfen und nur die "unendlichen" Kombinationen verwenden.

Auf diese Weise könnte die Brute-Force geführt werden.