Hallo,
ich weiß nicht, ob sich hier jemand mit Optimierungsverfahren für mehrdimensionale Funktionen auskennt oder einen guten Literaturtip für mich hat.
Ich beschäftige mich mit der Ausrichtung zweier Bilder aneinander (registrierung), d.h. ich suche z.b. nach den Rotations- und Translationsparametern eines Bildes, damit es optimal auf das andere passt. Nun ist mir aber aufgefallen, dass das Powell-Verfahren (auch Direction Set), welches ich bisher immer genutzt habe, nur das nächste lokale Minimum anstrebt (und nicht das, wo die ausrichtung wirklich optimal wird).
Hat jemand eine Ahnung, ob es ein Verfahren gibt, welches in der Hinsicht besser funktioniert?
Weiß sonst keine Lösung…
Hi,
zunächst einmal ist das Auffinden des globalen Maximums einer mehrdimensionalen Funktion ein schwieriges, eigentlich nicht gelöstes Problem und aktueller Forschungsgegenstand.
Einen ersten ganz brauchbaren Einblick geben die bewährten „Numerical Recipes“. Da finden sich Erklärungen über „Standard“-Verfahren wie Downhill Simplex und Simulated Annealing, etc.
Weiter kommst Du evtl, wenn Du im Netz nach „Operations Research“, „Algorithm“ und z.B. „Optimization“ suchst.
Auch Methoden wie evolutionäre/genetische Algorithmen, Sinflood, Ant, etc. könnten helfen.
Das Thema ist komplex, und man muß erst einmal herausfinden, welcher Ansatz genau für Dein Problem der beste ist. Unterschätze dies aber nicht.
Gruß
Moriarty
Hallo,
ich muß da meinem Vorredner mehr als Recht geben. Ein globales
Optimum zu finden ist kein Zuckerschlecken und manchmal schirr
unmöglich.
Ich kenne mich nun leider garnicht mit deinem Problem aus, aber in
der Numerik hilft manchmal der folgende „Trick“:
Wenn dein Algorithmus schon verlässlich lokale Optima findet und die
Berechnung dieser nicht alzu lange dauert, dann kann man die
Anfangsdaten ja so ändern, dass man die Hoffnung hat möglichst viele
lokale Optima zu erwischen. Nach einem Vergleich der „Funktionswerte“
nimmt man sich das beste raus und ist einem globalem Optimum schon
sehr nahe…
Ob das dir hilft weiß ich aber nicht!
Ciao Qasi
Hi Moriarty,
ja, ich weiß, dass die mehrdimensionale Optimierung eine heikle Sache ist. Mein Problem bei dem ganzen ist, dass ich mich nicht in die Mathematik gängiger Verfahren erst einarbeiten möchte, um dann bewerten zu können wie gut dieses oder jenes Verfahren sich für mein Problem eignet (sprengt einfach den Rahmen meiner Diplomarbeit). Daher bin ich auf der Suche nach einem Vergleich möglicher Verfahren (halt Vorteile und Nachteile etc.)
Die Numerical Recipes erscheinen mir sehr wenig bewertend (wenn auch gut um grundlegend etwas zu verstehen, wie’s funktioniert).
Genetische Algorithmen etc. werden wohl für mich nicht in Frage kommen, da hier der Zeitfaktor (nehm ich an) höher ist, als mir lieb ist.
Eigentlich ist die Auswahl für mein Problem eh nicht sonderlich groß, da ich eigentlich nur das Powell-Verfahren (a la Numerical Recipes) und die Downhill Simplex Methode zur Verfügung habe.
Nur würde ich eben gern erklären, ob es Alternativen gibt, die womöglich bessere Ergebnisse erziehlen (ohne es zu testen). Deswegen würd ich mich gern auf einen bereits existierenden Vergleich beziehen.
Grüße, July
Hi Qasi,
im Prinzip keine schlechte Idee, aber mit Sicherheit zu zeitaufwendig.
Trotzdem danke.
Grüße, July
Hallo July,
Nur würde ich eben gern erklären, ob es Alternativen gibt, die
womöglich bessere Ergebnisse erziehlen (ohne es zu testen).
Deswegen würd ich mich gern auf einen bereits existierenden
Vergleich beziehen.
ich hatte mal ein ähnliches Problem. Dabei habe ich in meiner beschränkten Übersicht folgendes gefunden:
Alle Algorithmen finden nur ein lokales Optimum, von dem man nie weiß, ob’s auch das globale ist. Die Algorithmen unterscheiden sich insofern, als daß ausgehend von den Startwerten für die Optimierung manche das (im vieldimensionalen Optimierungsraum) nächste Optimum, andere je nach eingestellter Schrittweite der Suche auch ein über- oder über-über-nächstes Optimum finden können. Ein weiterer Unterschied ist die Geschwindigkeit, mit welcher das Optimum gefunden wird. Die hängt zum einen stark ab von der Topologie der Optimumsfunktion und von der Wahl der Schrittweiten. Manche Algorithmen gibt es daher in einigen Varianten mit und ohne, statischer und dynamischer, fuzzy und sonstwelcher Schrittweitenanpassung. Also fällt auch da ein Vergleich nicht leicht.
Conclusion: Ein Vergleich, welcher Algorithmus das globale Optimum am besten findet, ist für höherdimensionale Probleme nicht wirklich möglich. Der Vergleich hinsichtlich der Schnelligkeit, mit der ein Optimum gefunden wird, ist zwar möglich, aber von der Problemstellung bzw. der Optimumsfunktion und deren Charakteristika abhängig - die du für deine Aufgabe erstmal bestimmen müßtest.
Gruß
Jochen
PS: Ich schliße mich dem Tipp meines Vorredners an, einige unterschiedliche Startpunkte zu wählen. Es brauchen nur 3-5 zu sein, das reicht (erstmal) vollkommen. Alternativ oder in Kombination damit kann man auch verschiedene Schrittweiten probieren.
Hallo Jochen,
vielen Dank für Deine Anwort. Das hilft mir dann doch etwas weiter.
Mehrere Startwerte auszutesten ist trotzdem für mein Problem nicht möglich, da ein einzelner Durchlauf schon bis zu 5 min braucht. Wenn ich dann drei zu optimierende Parameter habe und die jeweils mit drei unterschiedlichen Werten belegn möchte in jeglichen Kombinationen, wird das einfach zu zeitaufwändig (und da hab ich noch lange keine Garantie, das DAS Optimum gefunden wird). Zumal eben beschriebenes nur ein Teil der Optimierungsaufgabe wäre.
Ich werd davon ausgehen müssen (und dürfen hoffentlich auch), dass das Optimum in der Nähe des Startwertes (0,0,0,…) liegt. Dann sollte auch das Optimierungsverfahren vernünfige Ergebnisse liefern.
Ich frag mich, wie manche das mit minimalen Zeitaufwand schaffen…
Ist eben schade, dass man bei Arbeiten, die ähnlich meiner sind, nie direkten Einblick hat. Das würde mir eine Menge helfen…
Grüße, July