Wie können die Details des Bergsteigens mit Schrotflinten implementiert werden, um es effektiv zu machen?

7

Ich arbeite derzeit an einer Lösung für ein Problem , für die (nach einem wenig Forschung) die Verwendung eines Hügel Klettern und mehr specificly eine Schrotflinte (oder Zufallswiederanlauf ) Hügel klettern algorithmische Idee scheint die beste Lösung , wie ich zu sein Ich habe keine Ahnung, wie der beste Startwert gefunden werden kann.

Es gibt jedoch nicht viele Informationen über diese Art von Algorithmus, außer der rudimentären Idee dahinter:

[Shotgun] Hill Climbing ist ein Meta-Algorithmus, der auf dem Hill Climbing-Algorithmus aufbaut. Es macht iterativ Bergsteigen, jedes Mal mit einer zufälligen Anfangsbedingungx0. Das bestexm wird gehalten: wenn ein neuer Lauf des Bergsteigens ein besseres ergibt xm als der gespeicherte Zustand ersetzt es den gespeicherten Zustand.

Wenn ich das richtig verstehe, bedeutet das ungefähr so ​​(unter der Annahme einer Maximierung):

x = -infinity;
for ( i = 1 .. N ) {
  x = max(x, hill_climbing(random_solution()));
}
return x;

Aber wie kann man das wirklich effektiv machen, das ist besser als normales Bergsteigen? Es ist kaum zu glauben, dass die Verwendung von zufälligen Startwerten sehr hilfreich ist, insbesondere bei großen Suchbereichen. Genauer gesagt frage ich mich:

  • Gibt es eine gute Strategie für die Auswahl der x0(das heißt implementieren random_solution), insbesondere (Zwischen-) Ergebnisse früherer Iterationen kennen?
  • Wie man wählt N.Wie viele Iterationen sind erforderlich, um sicherzugehen, dass die perfekte Lösung nicht (um ein Vielfaches) übersehen wird?
Sim
quelle

Antworten:

8

Die allgemeine Idee hinter mehreren Anstiegen ist, lokale Optima zu vermeiden. Dies ist der Grund, warum das Klettern mit der Schrotflinte möglicherweise besser funktioniert als nur eine einfache Bergsteigermethode.

Normalerweise beginnt man mit einem zufälligen Wert. Wenn man dagegen etwas Besseres erraten kann, kann dies auch als Anfangswert verwendet werden. Wenn nicht bekannt ist, was ein guter Startwert sein sollte, ist es sinnvoll, einen zufälligen zu verwenden.

Der passende Wert für N.variiert. Normalerweise muss man ein Stoppkriterium definieren. Ein geeignetes Kriterium kann von Ihrer spezifischen Domain abhängen. Wenn Sie beispielsweise für eine kleine Anzahl von Zügen Ihre Lösung überhaupt nicht verbessern, hören Sie auf. Im Allgemeinen wissen Sie es nicht - Sie verwenden Heuristiken und sie geben Ihnen keine Garantie. Vielleicht möchten Sie sogar eine geeignete bestimmenN. experimentell.

Juho
quelle