Labor für Kraftfahrzeugmechatronik
youtube

  • Startseite
  • Labor
    • Kernkompetenzen
    • Kooperationspartner
    • Laborausstattung
    • Prüffeld für automatisierte und vernetzte Fahrfunktionen
    • Laborleitung
    • Mitarbeiter
      • Christopher Dunkel
      • Dirk Engert
      • Marcus Degenkolbe
      • Patrick Richter
      • Stanley Pfeiffer
      • Sven Eckelmann
  • Projekte
    • GEwAF
      • Kurzbeschreibung
      • Systemarchitektur
      • Implementierungen
        • GEwAF’s Docker Integration
        • Connecting ROS & ADTF
        • GEwAF’s MATLAB/Simulink Integration
        • Update – GEwAF’s MATLAB/Simulink Integration
      • Konzepte
        • Lane Clustering using Filtered LiDAR Point Clouds
    • Methodik zur Bewertung der Übertragungs- und Datensicherheit in Fahrzeug-Ad-Hoc Netzwerken
    • Neue Methoden der Informationsfusion
      • Kurzbeschreibung
      • Car2X
      • Lokalisierung
      • LiDAR
      • Digitale Karten
    • Platooning
      • Projektziele
      • Projektbeteiligte
      • Projektfortschritt (Timeline)
      • Projektergebnisse
        • HMI
        • Querführung (Stufe 1)
        • Längsführung (Stufe 1)
        • Quer- und Längsführung (Stufe 2)
        • Car2X
      • join the project
    • Untersuchung von Fahrzeug Ad-hoc Netzwerken
    • Abgeschlossene Projekte
      • Kreuzungsassistent
      • Bewertungsverfahren für FAS
      • iSuPia
  • Lehre
    • Video-Tutorials und Messdaten
    • Matlab-Sprechstunde
    • Unterlagen VDI-Seminar
  • Abschlussarbeiten
    • 2019
    • 2018
    • 2017
    • 2016
    • 2015 und älter
      • 2015
      • 2014
      • 2013
      • 2012
      • 2011
      • 2010
    • Themen für Abschlussarbeiten
  • Blog
  • Impressum
  • Datenschutzerklärung



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

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.

Beiträge, die sie auch interessieren könnten:

  1. Optimierung eines Matlab Algorithmus mit dem Profiler
  2. Kantenerkennung in Matlab: Vergleich zwischen Canny Algorithmus und Betragsoperator
  3. Kamerabasierte Spurerkennung
Social Share

    Leave a Reply Antworten abbrechen

    Du musst angemeldet sein, um einen Kommentar abzugeben.

    • Startseite
    • Labor
      • Kernkompetenzen
      • Kooperationspartner
      • Laborausstattung
      • Prüffeld für automatisierte und vernetzte Fahrfunktionen
      • Laborleitung
      • Mitarbeiter
        • Christopher Dunkel
        • Dirk Engert
        • Marcus Degenkolbe
        • Patrick Richter
        • Stanley Pfeiffer
        • Sven Eckelmann
    • Projekte
      • GEwAF
        • Kurzbeschreibung
        • Systemarchitektur
        • Implementierungen
          • GEwAF’s Docker Integration
          • Connecting ROS & ADTF
          • GEwAF’s MATLAB/Simulink Integration
          • Update – GEwAF’s MATLAB/Simulink Integration
        • Konzepte
          • Lane Clustering using Filtered LiDAR Point Clouds
      • Methodik zur Bewertung der Übertragungs- und Datensicherheit in Fahrzeug-Ad-Hoc Netzwerken
      • Neue Methoden der Informationsfusion
        • Kurzbeschreibung
        • Car2X
        • Lokalisierung
        • LiDAR
        • Digitale Karten
      • Platooning
        • Projektziele
        • Projektbeteiligte
        • Projektfortschritt (Timeline)
        • Projektergebnisse
          • HMI
          • Querführung (Stufe 1)
          • Längsführung (Stufe 1)
          • Quer- und Längsführung (Stufe 2)
          • Car2X
        • join the project
      • Untersuchung von Fahrzeug Ad-hoc Netzwerken
      • Abgeschlossene Projekte
        • Kreuzungsassistent
        • Bewertungsverfahren für FAS
        • iSuPia
    • Lehre
      • Video-Tutorials und Messdaten
      • Matlab-Sprechstunde
      • Unterlagen VDI-Seminar
    • Abschlussarbeiten
      • 2019
      • 2018
      • 2017
      • 2016
      • 2015 und älter
        • 2015
        • 2014
        • 2013
        • 2012
        • 2011
        • 2010
      • Themen für Abschlussarbeiten
    • Blog
    • Impressum
    • Datenschutzerklärung

    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