Suchstrategie



  • Nehmen wir an, ich habe eine Art Spielautomaten, der verschiedene Schalter und Regler hat und bei gleicher Konfiguration immer das selbe Ergebnis erzielt.
    Bei diesem Automaten gibt es Regler mit reellen Zahlen, bei denen man annehmen darf, dass der Einfluss auf das Ergebnis in irgendeiner Weise "stetig" ist, aber die Auswirkungen des Reglers eventuell von einem Schalter abhängen. Zum Beispiel:

    Regler R [1,100] erziel maximale Gewinnsumme bei 50, wenn Schalter S nicht gesetzt ist und maximale Gewinnsumme bei R = 25, wenn S gesetzt ist.

    Und nun habe ich gleich mehrere Regler und Schalter, die sich beeinflussen können aber nicht müssen. Manche Regler sind reelle Zahlen, andere nur ganze Zahlen, bei manchen Schaltern gibt es nur zwei Zustände, bei anderen mehrere.
    Wie kann man die maximale oder eine gute Gewinnsumme des Automaten effizient suchen, wenn man weder die maximale Gewinnsumme kennt (also nicht abschätzen kann, ob man schon "gut" war) und man eine zu große Anzahl an möglichen Konfigurationen für eine vollständige Suche hat.


  • Global Moderator |  Mod

    Ohne jetzt Stunden von Informatikerdenke auf das Problem angewendet zu haben, ist eine gute Faustregel, dass bei hochdimensionalen Optimierungsproblemen oft eine Monte-Carlo Strategie sehr gut funktioniert. Das heißt, man fängt irgendwo an, macht eine zufällige Änderung, und guckt den neuen Wert an. Ist dieser besser, so nimmt man die neue Konfiguration und fängt wieder von vorne an. Ist der neue Wert schlechter, so nimmt man ihn mit einer gewissen Wahrscheinlichkeit an, die davon abhängt, wie groß der Unterschied zum vorherigen Wert ist. Je größer der Unterschied, desto unwahrscheinlicher. Meistens skaliert man das mit einer Exponentialfunktion (das hat seine Wurzeln in der Physik, weil dann der Faktor in der Exponentialfunktion einer Temperatur entspricht). So verhindert man, dass man sich in irgendwelchen "Tälern" festfährt und aus diesen nicht mehr rauskommt. Je größer die "Temperatur", desto besser kommt man aus falschen Optima, aber desto schlechter findet man den absolut besten Wert.

    Das funktioniert vor allem gut, bei irgendwie stetigen, differenzierbaren Funktionen. Die Schalter könnten hier Schwierigkeiten machen, weil die nur wenige, diskrete Zustände haben. Das ruiniert zwar nicht die Methodik, aber es macht die Suche schwieriger. Die Methodik ist vor allem für irgendwelche halbwegs gutartigen Probleme gut. Wenn dir jemand mit den Schaltern einen reinwürgen möchte, um es möglichst schwer zu machen, dann kann er das auch schaffen.

    Es gibt auch fortgeschrittene Suchstrategien dieser Art, z.B. Umbrella Sampling, die (mit deutlich mehr Aufwand) auch mit fiesen Schalterkonfigurationen umgehen können. Aber das ist ein ganzes Studienthema, über das du mindestens eine Diplomarbeit schreiben könntest. Die Wikipedia-Übersichtsseite über fortgeschrittene Samplingmethoden für Monte-Carlo-Verfahren ist ziemlich lang, und jede der Methoden hat ihre eigenen Vor- und Nachteile. Es wird kaum eine perfekt zu deinem Problem passen (Monte-Carlo kommt aus der Computerphysik und dein Problem ist sehr untypisch für physikalische Probleme), aber ich kenne auch nicht alle Methoden so gut, dass ich dir sagen könnte, ob und welche Methode am besten passt.



  • Ohne alles auszuprobieren? Selbst wenn du alle Regler mit reelen Zahlen schon mit ihrem Optimum kennen würderst, wie sollte man jetzt das beste Ergebnis finden ohne die Gewinnsummern bei allen 2^n Schalterstellungen der n binären Schalter zu berechnen.



  • Ein "gutes" Ergebnis reicht auch. Man kann sogar weiter gehen und sagen: "Mir reicht das beste mir bekannte Ergebnis und ich bin mir recht sicher genug Ausprobiert zu haben."

    Was SeppJ beschrieben hat, klingt ein wenig nach Simulated Annealing, oder?


  • Global Moderator |  Mod

    @ravenheart_ggg sagte in Suchstrategie:

    Was SeppJ beschrieben hat, klingt ein wenig nach Simulated Annealing, oder?

    Ja. Simulated Annealing ist eine der vielen erwähnten Spezialformen, auf die ich nicht genauer eingegangen bin.



  • Hier ist der Unterschied bzw die Ähnlichkeit zwischen Simulated Annealing und (dem allgemeinen) Monte Carlo ganz anschaulich dargestellt. https://www.quora.com/Is-simulated-annealing-a-Monte-Carlo-method


  • Global Moderator |  Mod

    @Schlangenmensch sagte in Suchstrategie:

    Hier ist der Unterschied bzw die Ähnlichkeit zwischen Simulated Annealing und (dem allgemeinen) Monte Carlo ganz anschaulich dargestellt. https://www.quora.com/Is-simulated-annealing-a-Monte-Carlo-method

    Das ist totaler Müll. Demnach wäre die Metropolis-Methode kein Monte Carlo. Dabei ist das die gängiste Monte Carlo Methode. Und Simulated Annealing ist bloß Metropolis mit nicht-konstanter Temperatur. Siehe die Kommentare darunter, die absolut recht haben.



  • Ich bleibe dabei, dass ich seine Visualisierung für anschaulich halte.

    Natürlich ist Monte Carlo Simulation ein Überbegriff für verschiedene Methoden und SA liegt der Metropolis Algorithmus zugrunde. Daher pass die Antwort mit "not exactly" nicht und "kind of" wäre passender gewesen.