Labor für Kraftfahrzeugmechatronik
youtube

  • Start
  • Mechlab@Spain
  • Laboratory
  • Projects
  • Downloads
  • Blog



Numerische Optimierung in Matlab mit Twiddle-Algorithmus

Juli 10, 2012
by Toralf Trautmann
Algorithmus, Brute Force, code, M-File, Matlab, optimierung, optimization, Twiddle
0 Comment

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

[matlab]
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‘)])
[/matlab]

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:

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

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.

Social Share

    Leave a Reply Antworten abbrechen

    Du musst angemeldet sein, um einen Kommentar abzugeben.

    • Start
    • Mechlab@Spain
    • Laboratory
    • Projects
    • Downloads
    • Blog

    Archiv

    Intern

    Autoren-Login
    Wiki

    Impressum und Kontakt

    Hochschule für Technik & Wirtschaft
    Labor für KFZ Mechatronik
    Prof. Dr. rer. nat. Toralf Trautmann
    Friedrich-List-Platz 1
    01069 Dresden


    Die Fakten sprechen für uns.
    © Copyright 2019 | mechlab.de