Schnelle hill climbing Algorithmus, stabilisieren kann, wenn in der Nähe von optimalen

Question

I eine Gleitkommazahl x von [1, 500] haben, die an einem gewissen Wahrscheinlichkeit p ein binäres y von 1 erzeugt. Und ich versuche, die x zu finden, die am meisten 1 erzeugen kann oder am höchsten hat. Ich gehe davon aus, dass es nur ein Maximum gibt.

Gibt es einen Algorithmus, der schnell mit der x mit der höchsten konvergieren kann, während sichergestellt wird, dass es nicht zu viel springt, nachdem es für e.x erreicht wurde. innerhalb von 0,1% des optimalen x? Insbesondere wäre es großartig, wenn es sich stabilisiert, wenn nahe < 0,1% von optimalem x.

Ich weiß, dass wir dies mit simuliertem Glühen tun können, aber ich glaube nicht, dass ich hart Code Temperatur sollte, weil ich den gleichen Algorithmus verwenden muß, wenn x von [1, 3000] sein könnte oder die p Verteilung ist anders.

Answer 1

This paper bietet eine für intelligente Hill-Climbing-Algorithmus. Die Idee ist im Grunde genommen n Proben als Ausgangspunkt zu nehmen. Der Algorithmus ist wie folgt (es in eindimensional für Ihr Problem vereinfacht):

1. Nehmen n Abtastpunkte im Suchraum. In der Arbeit verwendet er Linear Hypercube Sampling, da die Abmessungen der Daten im Papier als groß angenommen werden. In Ihrem Fall, da es eindimensional ist, können Sie einfach wie immer Zufalls-Bäumchen verwenden.
2. Für jeden Stichprobenpunkt Punkte aus seiner "lokalen Nachbarschaft" sammeln und eine quadratische Kurve mit der besten Anpassung finden. Finde den neuen maximalen Kandidaten aus der quadratischen Kurve. Wenn die Zielfunktion des neuen Maximalkandidaten tatsächlich höher als die vorherige ist, aktualisieren Sie den Abtastpunkt auf den neuen Maximalkandidaten. Wiederholen Sie diesen Schritt für jede Iteration mit einer kleineren Größe für die lokale Umgebung.
3. Den besten Punkt aus den Beispielpunkten verwenden
4. Neustart: Wiederholen Sie die Schritte 2 und 3, und vergleichen Sie dann die Maximalwerte. Wenn es keine Verbesserung gibt, hör auf. Wenn es Verbesserungen gibt, wiederholen Sie es erneut.