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
[math]X_i=[-3…+3][/math]
[math]Y_i=[-3…+3][/math]
zu berechnen. Wählt man eine Schrittweite von
[math]\Delta X= \Delta Y=0{,}001[/math]
so ergibt sich bereits ein zu berechnender Parameterraum von
[math]n=\left(\cfrac{3-(-3)}{0{,}001}\right)^2=36.000.000[/math]
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:
httpvh://www.youtube.com/watch?v=2uQ2BSzDvXs
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.
