Frage von offeltoffel, 74

Wie nennt man diese Art von Algorithmus?

Hi zusammen,

ich habe für die Arbeit in Python einen Algorithmus geschrieben. Im Wesentlichen verändert er einen Parameter solange, dass das Argument "x - y" minimiert wird. Ich habe einmal stolz jemandem davon erzählt, dass ich mir das hab einfallen lassen und er meinte so "ach, das ist ein XY-Algorithmus". Ich Depp hab mir nicht gemerkt, wie er heißt, kann aber schlecht im Abschlussbericht so tun, als hätte ich ihn neu erfunden. Vielleicht kann mir jemand von euch sagen, wie man ihn nennt? Der Algorithmus geht folgendermaßen:

Ich setze einen Startwert X und eine Schrittweite Xs. Die Formel wird gerechnet und die Differenz d berechnet. Anschließend wird X um Xs erhöht und d erneut berechnet. d sollte dabei immer kleiner werden (minarg). Irgendwann wechselt d das Vorzeichen, nämlich wenn ich den gesuchten Wert überschritten habe. In dem Fall wird die Schrittweite halbiert (Xs / 2) und nun von X abgezogen. Wird der Wert wieder überschritten, wird Xs wieder halbiert und so weiter und so weiter. Man nähert sich also von beiden Seiten an den gesuchten Wert ran und hört auf, wenn ein bestimmter Schwellenwert zur Verbesserung nicht mehr überschritten werden kann.

Das ist so grob, wie das Teil arbeitet. Wie nennt man diese Art von Algorithmus? Ist eine sehr spezielle Frage, aber ich bin um jeden Hinweis dankbar...

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von ArchEnema, 47

https://de.wikipedia.org/wiki/Bisektion

Naja, jedenfalls eine Variante davon, das wird aus deiner Erklärung nicht ganz klar. Vielleicht hast du's ja nur umständlich implementiert? :D

Wenn es vom Problem her nicht anders geht, dann trifft vermutlich Grid-Search eher zu...

Kommentar von ArchEnema ,

Naja, eigentlich sogar eher Grid Walking, weil du von einem Ausgangspunkt ausgehst und nicht den ganzen Suchraum abklopfst.

Kommentar von offeltoffel ,

Bisektion trifft es eigentlich ganz gut! Ist dieser Begriff auch erlaubt, wenn nach dem Überschreiten des gesuchten Werts die Schrittweite nicht halbiert wird, sondern z.B. gedrittelt wird o.ä.? Der Nutzer kann den Wert nämlich selbst festlegen

Kommentar von ArchEnema ,

Da würde ich dann eher allgemein von Intervallschachtelung sprechen. Problem ist nur, dass du kein Intervall hast! Sondern nur einen Ausgangspunkt. Daher Grid Walking.

Kommentar von ArchEnema ,

Und wenn du einen "krummen" Faktor für die Schrittweitenverkleinerung wählst  kannst du ggf. sogar deinen Ausgangspunkt beim zurücklaufen wieder überschreiten - wenn die zugrundeliegende Funktion das hergibt, also zu wild oszilliert (Periodenlänge nicht deutlich größer als deine Schrittweite).

http://www.cs.berkeley.edu/~jrs/4/lec/22

Kommentar von ArchEnema ,

Der letzte Satz hierin ist auch interessant. Man könnte deine Lösung auch als eine eindimensionale Anwendung hiervon betrachten: https://de.wikipedia.org/wiki/Downhill-Simplex-Verfahren

Kommentar von offeltoffel ,

Ich bin auch längst kein Mathemaiker - der Algorithmus entstand aus der Not heraus möglichst schnell eine praktikable Lösung zu finden. Ich musste einige Probleme abfangen, z.B. darf ein Iterationsschritt nur abgeschlossen werden, wenn das Vorzeichen der Annäherung sich umkehrt UND die Differenz verringert werden konnte. Außerdem musste ich mehrere Aussteigsbedingungen setzen, wenn z.B. die maximale Genauigkeit der Floating Point Variable erreicht wurde und somit keine Verbesserung mehr eintreten KANN.

Das Downhill-Simplex-Verfahren kenne ich in der Tat, sehe aber nicht direkt einen Zusammenhang zu meinem Problem.

Danke für deine Hilfe!

Antwort
von DARKHalf, 42

Das müsste ähnlich der Binärsuche sein. Schau mal nach Teile- und Herrsche. Englisch: divide and conquer.

Kommentar von offeltoffel ,

Danke für den Hinweis! Leider ist das noch nicht genau das, was ich suche. Ich unterteile mein Problem nicht wirklich in mehrere kleine Probleme bis ich auf das kleinste die Antwort gefunden habe. Ich unterteile auch nicht über den Median in kleinere Hälften, sondern nähere mich iterativ einem Wert an und wechsle die Marschrichtung, wenn ich den Wert überschritten habe. Ähnlich, wie wenn man mit einem GPS eine Koordinate ansteuert: "weiter, weiter, weiter - oh, zu weit. Rückwärts, rückwärts...oh zu weit! Langsam vorwärts...vorwärts" etc.

Kommentar von DARKHalf ,

https://de.wikipedia.org/wiki/Bin%C3%A4re_Suche

Das trifft es doch eigentlich ziemlich genau, oder?

Kommentar von offeltoffel ,

leider nein. Erstens sucht er nicht, bis er einen Treffer hat, sondern könnte sich theoretisch beliebig dem "wahren" Wert nur annähern. Zweitens springe ich nicht immer zum Median, sondern nähere mich in definierter Schrittweise. Klar, es gibt eine Ähnlichkeit, aber es ist schon ein anderer Algorithmus.

Aber hey, wenn ich keinen anderen Namen finde, schreibe ich einfach von einer binären Suche und kann mich zur Not schon irgendwie rausreden ;) danke auf jeden Fall für deine Hilfe

Kommentar von DARKHalf ,

Die Binäre Suche deutet ja schon hin auf 1 oder 0. Also Treffer oder nicht. Bei Fließkommawerten kann man nicht direkt von Binärer Suche reden, da Du wie in der Integralrechnung Dich nur nähern kannst, aber nicht 100% treffen.

Nenne das Ding "Abwandlung einer Binären Suche" und verwende als Erklärung die mit dem annähern aber nie treffen. Wichtig ist nur, eine Abbruch-Bedingung zu haben, damit er nicht endlos läuft. Dann ist das mit der plausibilität auch kein Problem.

Ich habe übrigens genau den selben Algorithmus mal verwendet um rießig große Logfiles zu durchsuchen. Also mehrere 10 GB groß. Die Suche nach einem Zeitraum war damit innerhalb von 8-12 Sprüngen möglich.

Antwort
von Roderic, 29

Das - was du da beschreibst - ist einfach ein numerisches Annäherungsverfahren. Da gibts keinen besonderen Namen für.

Die Art und Weise, wie das "Ziel" in immer kleiner werdende Intervall eingegrenzt wird, nennt sich in der Tat Bisektion - ein Form der Intervallschachtelung.

Expertenantwort
von hypergerd, Community-Experte für Mathematik, 21

https://de.wikipedia.org/wiki/Bisektion

Kommentar von hypergerd ,

Das ist übrigens Beispiel 2 vom Iterationsrechner

http://www.gerdlamprecht.de/Roemisch_JAVA.htm

Nur 3 Zeilen statt 1000 Worte.

Dieser Algorithmus hat schlechtes Konvergenzverhalten! Für  mehr als 16 Nachkommastellen ungeeignet (sehr langsam).

Sollte man nur nehmen, wenn man nichts von Ableitung versteht, da Newtons Iterationsverfahren zig mal schneller konvergiert.

Es gibt Optimierungen zur Beschleunigung, die fast an Newton-V. herankommen.

Kommentar von hypergerd ,

Ach und zu Deinem Kommentar "Der Nutzer kann den Wert nämlich selbst festlegen..."

https://de.wikipedia.org/wiki/Regula\_falsi

Punkt "Anderson/Björk-Verfahren" -> nur das dieses die Schrittweite mit einer Funktion zur Laufzeit selbst optimiert wird (besser als jede feste Schrittweite)!

(Beispiel 35 braucht damit statt 49 Schritte nur noch 9 )

Kommentar von offeltoffel ,

Danke für den unterschwelligen Hinweis über mein Unvermögen in Sachen Mathematik :P

Ich hab mit Mathe eigentlich nichts am Hut und auch das Programmieren habe ich mir mehr oder weniger selbst beigebracht. Besagter Freund hat mir auch gleich gesagt, dass er das newtonsche Verfahren nehmen würde und es klang auch komplett plausibel - nur da stand mein Programmcode schon. Und der ist erst einmal dafür ausgelegt zu funktionieren. Eine Bildszene benötigt bei mir gerade mal 5 Minuten und ich muss alle paar Wochen mal eine rechnen. Sollte ich mal Zeit für ein Upgrade haben, nehme ich natürlich das da (die Ableitung ist nämlich schnell gerechnet und ja, das krieg ich grad noch hin :P).

Danke dir!

Kommentar von hypergerd ,

Bitte nicht zu negativ verstehen. Jeder Algorithmus hat Vor- & Nachteile. Wie das Beispiel 35 zeigt, kann bei gewissen Funktionen die Anderson/Björk-optimierte Bisektion mit der Newton-I.Schrittanzahl mithalten.

Dann gibt es Fälle, wo die Newton-I. divergiert oder man extrem dicht am Zielpunkt beginnen muss, um das gesuchte Ergebnis zu finden:

https://www.gutefrage.net/frage/newton-verfahren-mathematik?foundIn=list-answers...

Im Beispiel 118 habe ich mal eine universelle numerische Ableitung eingebaut, da es auch Funktionen mit Fallunterscheidungsbereichen gibt, die nicht so einfach ableitbar sind. Bei Messwerten {Stützstellen von Experimenten} gibt es keine Funktion -> alles numerisch... 

Was bedeutet "Bildszene" mathematisch? Immer die selbe Ausgangs-Funktion? Wenn man die genau kennt, lohnt eine genaue Untersuchung, ob nicht doch eine symbolische Umstellung, also exakte explizite Lösungsformel statt Näherungsverfahren gibt. (man staunt, was alles mit LambertW, PQRST usw. umgestellt werden kann...)

Keine passende Antwort gefunden?

Fragen Sie die Community