Numerische Optimierung in Matlab mit Twiddle-Algorithmus

Funktionswerte Z in Abhängigkeit der Parameter X und Y

Man stelle sich vor, es gilt einen Parameterraum (X und Y) abzusuchen, in welchem irgendwo optimale Parametervariationen versteckt sind, welche ein System (Z) maximieren oder minimieren. Ist das System nicht mehr analytisch (also mit Gleichungen) zu beschreiben, wird die in der Schule erlernte Variante, einfach die 1. und 2. Ableitung zu bilden und durch Nullstellensuche die Maxima und Minima zu finden, unmöglich. Es hilft nur noch die numerische Optimierung, auch simulationsbasierte Optimierung genannt.

Standardvariante Brute Force

Die einfachste, langsamste und mitunter unmögliche Variante ist, einfach alle Parameter mit bestimmter Schrittweite durch zu probieren und den Funktionswert Z auszurechnen. Bei dem Beispiel im Bild oben, sind

zu berechnen. Wählt man eine Schrittweite von

so ergibt sich bereits ein zu berechnender Parameterraum von

Varianten. Man kann sich vorstellen, dass bei größeren Parameterintervallen oder höherdimensionalen Problemen die Berechnung teilweise nicht mehr zu stemmen ist. Es ist also ein Verfahren nötig, welches die Suche irgendwie intelligenter gestaltet.

“Twiddle”-Algorithmus von Sebastian Thrun

Eine relativ einfach zu implementierende Suche ist der so genannte Twiddle-Algorithmus, welchen Prof. Sebastian Thrun am besten persönlich erklärt:

Dieser Algorithmus sucht nun den Parameterraum intelligent ab und variiert die Schrittweite der Suche, je nachdem ob man in der Nähe eines Maxima bzw. Minima ist.

Twiddle Algorithmus in Matlab zur Maximierung einer Funktion

clear all, clc, close all
%% Twiddle Algorithmus nach Sebastian Thrun
tic

params = [0 0];   %Startparameter X & Y
dparams = [3 3];  %Startschrittweite DeltaX & DeltaY

it=1;

%Kostenfunktion ausrechnen
cfzz(it) = calcCost(params(1),params(2));
bestcost = cfzz(it);

% Maximierung der Kostenfunktion!
while sum(dparams) > 0.01
    for i=1:length(params) % alle Parameter durch gehen
        params(i)=params(i)+dparams(i);

        %Kostenfunktion ausrechnen
        cfzz(it) = calcCost(params(1),params(2));

        if cfzz(it) > bestcost
            bestcost = cfzz(it);
            dparams(i)= dparams(i)*1.05;
        else
            % in andere Richtung suchen
            params(i)=params(i)- 2*dparams(i);
            cfzz(it) = calcCost(params(1),params(2));

            if cfzz(it) > bestcost %wenn aktuelle Kosten höher (=gut)
                bestcost = cfzz(it);
                dparams(i) = dparams(i)*1.05; %mit größerem Schritt probieren
            else
                params(i)=params(i)+dparams(i);
                dparams(i)=dparams(i)*0.95; % an sonsten kleineren Schritt
            end
        end

    it = it+1;
    disp(['Twiddle #' num2str(it-1) ' mit Parametern ' num2str(params,'%2.5f \t') ', Funktionswert: ' num2str(cfzz(it-1),'%2.5f \t')])
    paramsstore(it,:) = params; % für späteres Plotten in Variable ablegen

    end %paramseter durch gehen

end

disp(['Twiddle-Berechnungsdauer ' num2str(toc) 's'])
disp(['                X           Y '])
disp(['Maximum bei ' num2str(params,'%2.5f \t')])

Beispielhafte Matlab-Funktion “Peaks” mit Optimum (rot), welches vom Twiddle Algorithmus gefunden wurde. Als blaue Kreise sind die Stellen dargestellt, an welchen der Algorithmus gerechnet hat. Zu beachten ist die Häufung im Bereich des Maximums (Reduzierung der Schrittweite)

Die Funktion calcCost, welche den Funktionswert Z zurück gibt, ist die in Matlab enthaltene Standardfunktion “peaks”, welche in diesem Beispiel gewählt wurde:

function [out] = calcCost(X,Y)
% Kostenfunktion, welche von Eingangsparametern
% abhängt
out = peaks(X,Y);

Natürlich ist das Ergebnis Abhängig von den gewählten Eingangsparametern. Der Algorithmus kann auch in lokalen Maxima/Minima hängen bleiben und kein globales (absolut bestes) Ergebnis bringen. Dies kann man zum Beispiel schon erreichen, wenn man den oben genannten Twiddle-Algorithmus mit dparams=[1 1] los laufen lässt. Er schafft es dann nicht mehr, vom ersten lokalen Maximum weg zu kommen. Es ist also immer Vorsicht geboten mit den Ergebnissen!

Funktionswert von Z in Abhängigkeit der Twiddle-Durchläufe

Anwendung auf mehr Dimensionen

Diese Vorgehensweise scheint beim Finden von 2 Parametern etwas umständlich, kann man sich doch einfach das 3D-Diagramm anschauen und das Optimum sehen. Bei höherdimensionalen Parameterräumen ist das Darstellen allerdings nicht mehr möglich und man kann sich keine Vorstellung von einem optimalen Parameterset machen. Dann muss ein solcher Optimierungsalgorithmus zum Einsatz kommen.