Optimierung mit diskreten Parametern in Matlab

Im Grunde ist dies ein lock-picking-problem, wobei die lock pins haben 20 unterschiedliche Positionen, und es sind 12 pins. Auch:

• einige der pin-Positionen blockiert werden, abhängig von den Positionen aller anderen pins.
• Je nach den Besonderheiten des Schlosses, kann es mehrere Schlüssel, die passen

...interessant!

Basierend auf Rasman-Ansatz und Phpdna Kommentar, und der Annahme, dass Sie mit int8 als Daten-Typ, unter den gegebenen Einschränkungen gibt es

>> d = double(intmax('int8'));
>> (d-40) * (d+100) * (d+20) * 2*d
ans =
    737388162

möglichen Vektoren s (geben oder nehmen ein paar, nicht etwa gedacht haben, +1 etc.). ~740 Millionen Bewertungen Ihrer relativ einfachen f(s) sollte nicht mehr als 2 Sekunden, und gefunden zu haben alle s dass maximieren f(s), Sie sind mit dem problem des Findens von linearen Kombinationen in der Vektor-set, die bis zu hinzufügen eine dieser Lösungen s.

Natürlich das finden der Kombinationen ist kein Kinderspiel, und die ganze Methode bricht sowieso, wenn Sie den Umgang mit

int16:   ans = 2.311325368800510e+018
int32:   ans = 4.253529737045237e+037
int64:   ans = 1.447401115466452e+076

So, ich werde diskutieren einer direkteren und allgemeineren Ansatz.

Da sprechen wir ganze zahlen und eine ziemlich große Suchraum, ich würde vorschlagen, mit einem branch-and-bound-Algorithmus. Aber im Gegensatz zu den bintprog Algorithmus, müssten Sie verwenden verschiedene branching-Strategien, und natürlich, diese sollte auf der Grundlage einer nicht-linearen Zielfunktion.

Leider, es gibt nichts wie dies in der optimization toolbox (oder die Datei Exchange soweit ich finden konnte). fmincon ist ein no-go, da es verwendet die Gradienten und Hesse-Informationen (die werden in der Regel alle-zero für ganze zahlen), und fminsearch ist ein no-go, da Sie brauchen werden, eine wirklich gute erste Schätzung, und die rate der Konvergenz ist (in etwa) O(N), das heißt, für diese 20-dimensionalen problem, müssen Sie warten ganz lange, bevor die Konvergenz ohne die Garantie für das finden des globalen Lösung.

Einer Intervall-Methode könnte eine Möglichkeit sein, aber ich persönlich habe sehr wenig Erfahrung mit dieser. Es gibt keine native Intervall-bezogene Dinge in MATLAB oder einer Ihrer Schubladen, aber es gibt den frei verfügbaren INTLAB.

Also, wenn Sie nicht das Gefühl, wie die Umsetzung Ihrer eigenen, nicht-linear, Binär-integer-programming-Algorithmus, oder sind nicht in der Stimmung für ein Abenteuer mit INTLAB, es gibt wirklich nur eine Sache Links: heuristische Methoden. In dieser link es ist eine ähnliche situation, mit einer Gliederung der Lösung: Nutzung des genetischen Algorithmus (ga) von der Global Optimization toolbox.

Ich würde implementieren das problem in etwa so:

function [sol, fval, exitflag] = bintprog_nonlinear()

    %//insert your data here
    %//Any sparsity you may have here will only make this more 
    %//*memory* efficient, not *computationally*
    data = [... 
        ...  %//this will be an array with size 4-by-20-by-12
        ...  %//(or some permutation of that you find more intuitive)
        ];

    %//offsets into the 3D array to facilitate indexing a bit
    offsets = bsxfun(@plus, ...
        repmat(1:size(data,1), size(data,3),1), ...
        (0:size(data,3)-1)' * size(data,1)*size(data,2));   %//'

    %//your objective function
    function val = obj(X)

        %//limit "X" to integers in [1 20]
        X = min(max(round(X),1),size(data,3));

        %//"X" will be a collection of 12 integers between 0 and 20, which are 
        %//indices into the data matrix

        %//form "s" from "X"        
        s = sum(bsxfun(@plus, offsets, X*size(data,1) - size(data,1)));


        %//XxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxX        
        %//Compute the NEGATIVE VALUE of your function here
        %//XxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxXxX


    end

    %//your "non-linear" constraint function 
    function [C, Ceq] = nonlcon(X)

        %//limit "X" to integers in [1 20]
        X = min(max(round(X),1),size(data,3));

        %//form "s" from "X"        
        s = sum(bsxfun(@plus, offsets, X(:)*size(data,1) - size(data,1)));

        %//we have no equality constraints
        Ceq = [];

        %//Compute inequality constraints
        %//NOTE: solver is trying to solve C <= 0, so: 
        C = [...
            40 - s(1)
            s(2) - 100
            -20 - s(4)
        ];

    end

    %//useful GA options
    options = gaoptimset(...
        'UseParallel', 'always'...
        ...
    );

    %//The rest really depends on the specifics of the problem.
    %//Useful to look at will be at least 'TolCon', 'Vectorized', and of course, 
    %//'PopulationType', 'Generations', etc.

    %//THE OPTIMZIATION 
    [sol, fval, exitflag] = ga(...
        @obj, size(data,3), ...  %//objective function, taking a vector of 20 values
        [],[], [],[], ...        %//no linear (in)equality constraints
        1,size(data,2), ...      %//lower and upper limits
        @nonlcon, options);      %//your "nonlinear" constraints


end

Beachten Sie, dass, obwohl Ihre Einschränkungen sind im wesentlichen lineare, die Art und Weise, durch die Sie müssen berechnen Sie den Wert für Ihr s erfordert die Verwendung von ein benutzerdefiniertes constraint-Funktion (nonlcon).

Besonders beachten Sie, dass dies derzeit (wahrscheinlich) eine sub-optimale Möglichkeit zur Nutzung ga - ich weiß nicht, die Besonderheiten Ihres Ziel-Funktion, so dass viel mehr möglich sein kann. Zum Beispiel, ich verwende derzeit eine einfach round() zum konvertieren der Eingangs - X Ganzzahlen, aber mit 'PopulationType', 'custom' (mit einer benutzerdefinierten 'CreationFcn', 'MutationFcn' etc.) könnte zu besseren Ergebnissen führen. Auch 'Vectorized' wird wahrscheinlich die Dinge beschleunigen, eine Menge, aber ich weiß nicht, ob Ihre Funktion ist leicht vektorisiert.

Und ja, ich benutze verschachtelte Funktionen (ich Liebe diese Dinge!); es verhindert, dass diese riesig, in der Regel identische Listen von input-Argumente wenn Sie die Nutzung von sub-Funktionen oder stand-alone-Funktionen, und Sie können wirklich ein performance-Schub, weil es wenig kopieren von Daten. Aber, ich merke, dass Ihre scoping-Regeln machen Sie etwas ähnlich goto Konstrukte, und so sind Sie -ahum- "not everyone' s cup of tea"...möchten Sie vielleicht, um Sie zu konvertieren sub-Funktionen zur Vermeidung von langen und nutzlosen Diskussionen mit Ihren Arbeitskollegen 🙂

Sowieso, sollte dies ein guter Ort, um zu starten. Lassen Sie mich wissen, ob dies überhaupt nützlich sind.

Ich weiß, diese Antwort erreicht Sie wirklich late.

Leider, das problem ist, zeigen nicht viele Muster genutzt werden, neben der brute-force -Branch&Gebunden, Master& Slave, etc.- Sie versuchen eine Master-Slave-Ansatz-d.h. die Lösung erst die Funktion kontinuierliche nichtlineare problem als master, und die Lösung der diskreten Auswahl als slave könnte helfen, aber mit so vielen Kombinationen, und ohne weitere Informationen über die Vektoren, es ist nicht allzu viel Platz zum arbeiten.

Aber auf der Grundlage der gegebenen kontinuierlichen fast überall-Funktionen, basierend auf der Kombination von Summenbildung und Multiplikation von Operatoren und deren inversen, die sparsity ist ein klarer Punkt, ausgebeutet zu werden hier. Wenn 70-90% der Vektoren null sind, fast ein guter Teil der solution space in der Nähe von null oder nahe infinite. Daher ist eine 80-20 pseudo-Lösung verworfen werden würde einfach die "null" - Kombinationen und verwenden Sie nur das "unendliche" ersetzt.

Diese Weise, die brute-force-geleitet werden können.