optimierungsproblem

peter Gast 12.10.2011 09:54 #2378631

Lesenswert?

•

hi,

Ich beschäftige mich derzeit mit der Optimierung eines 
Klassifikationssystems mit 12 Parameter ... wobei ich jeweileis 4 
unabhängig voneinander behandeln kann. Derzeit verwende ich das 
Gradientenverfahren da irgendwie alle anderen Verfahren Signalkenntniss 
oder sogar Modelkenntnis voraussetzen.

D.h ich gehe folgendermaßen vor :

1.) ... probieren eines Schritt µ1 für jeden Parameter (mit einer 
Anfangsschrittweite und Ermittlungs der Kostenfunktion (Zusatzinfo: 
einmaliger Durchlauf benötigt ca. 1/2 h)
2.) Ermittlung des neg. Gradienten -> -(neue Kosten - alte Kosten / 
Parameterschritt) -> d.h implizite Annahme eines linearen Models !
3.) Berechnung des neuen Parametersatzes mit: p_neu=p - µ2 * grad(f(p));

Setzte ich die Schrittweite zu gross an ... konvergiert die Optimierung 
nur schlecht, umgekehrt gehts richtig schleppend und ich bleibe 
womöglich in einems lokalen minima stecken. -> Gibt es hier Methoden zur 
Schrittweitenbestimmung die "nicht von Signalstatistik bzw. 
Modellkenntniss ausgehen" ?!

Bin für jeden Tipp dankbar !

lg Peter

Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden

Matthias Gast 12.10.2011 12:59 #2378890

Lesenswert?

•

▲
▼

Mit fester Schrittweite bist du auch sehr unflexibel.

Hast du mal das Downhill-Simplex-Verfahren mit seiner adaptiven 
Schrittweite probiert?
http://de.wikipedia.org/wiki/Downhill-Simplex-Verfahren
http://comjnl.oxfordjournals.org/content/7/4/308.abstract

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Klaus W. (mfgkw) 12.10.2011 13:23 #2378913

Lesenswert?

•

▲
▼

peter schrieb:
> Bin für jeden Tipp dankbar !

Dann hoffentlich auch für den: genetische Algorithmen
http://www.wachtler.de/informatik_2/node26.html

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Georg A. Gast 15.10.2011 11:31 #2382453

Lesenswert?

•

▲
▼

Im ersten Ansatz kannst Du Deine Gradienten ermitteln, wichten und die 
steilsten für die erste Näherung heranziehen. Dies ist insbesondere dann 
von Vorteil, wenn man keine Annahmen über das Gefüge der Gleichungen 
machen kann.

Antwort Zitieren Bearbeiten Löschen Beitrag melden

peter Gast 15.10.2011 21:10 #2383009

Lesenswert?

•

▲
▼

Danke für die die Tipps !

Werd mich mal vorerst über das Simplexverfahren stürzen ... und dann 
weiter zu genetischen Algorithmen, danke

@georg ... das ist ja genau der ansatz den ich gewählt hatte !

Antwort Zitieren Bearbeiten Löschen Beitrag melden

A. S. (rava) 21.10.2011 11:10 #2389871

Lesenswert?

•

▲
▼

Das Simplex-Verfahren ist ein Verfahren 0. Ordnung. Das heißt, du 
benötigst die Ableitung nicht. Dafür wird es mehr Iterationen benötigen. 
Ein Problem könnte vielleicht sein, die Simplexe im 12-dimensionalen 
Raum auszurechnen. Immerhin geht's da heiß her, was sin und cos angeht, 
oder?

Es gibt in dem Zusammenhang auch noch das Hooke-Jeeves-Tastverfahren, 
das nur die die kartesischen Koordinatenrichtungen tastet.

Beide Verfahren bleiben, richtig implementiert, an einem lokalen Minimum 
hängen
--> ab Seite 321:
http://books.google.de/books?id=2_jkkX4DNWAC&printsec=frontcover&source=gbs_atb


die Jungs von wiki schreiben auch noch über ein paar andere Methoden, 
von denen ich aber nichts weiß:
http://en.wikipedia.org/wiki/Pattern_search_(optimization)



1. Ordnung
wenn du den gradienten berechnen kannst, dann macht es Sinn, in diese 
Richtung eine Liniensuche zu machen, um die Schrittweiten sinnvoll zu 
wählen. Dabei wird immer in Richtung des Gradienten ein Minimum gesucht.
Dazu steht auch viel im Schröder bei den Verfahren 1. Ordnung. Zum 
Beispiel die ALIS-Liniensuche.


Da das alles deterministische Verfahren sind, findest du IMMER nur 
lokale Minima, außer du hast einen glücklich gewählten Startpunkt!



Für die Hoffnung auf ein globales Minimum brauchst du einen 
stochastischen Ansatz über viele Messpunkte, was im 12-D wohl happig 
werden kann...
Aber nur so erhältst du nichtdeterministische Ergebnisse.
Die generischen Algorithmen wurden schon vorgeschlagen.
Wenn die Minima nahe beieinander liegen, kann man auch einen 
Ant-colony-Ansatz wählen.
Oder einer von den vielen anderen: 
http://en.wikipedia.org/wiki/Stochastic_optimization


Viel Erfolg =]

Antwort Zitieren Bearbeiten Löschen Beitrag melden

optimierungsproblem

Antwort schreiben