Simuliertes Abkühlen erklärt: CartPole mit 4 Parametern meistern

Das CartPole-Problem gilt als eine der einfachsten Benchmarks in der Reinforcement-Learning-Forschung. Doch während viele Algorithmen auf komplexe neuronale Netze oder Gradient-descent-Ansätze setzen, zeigt ein alternativer Weg: simuliertes Abkühlen (Simulated Annealing) kann mit minimalem Aufwand zu einer perfekten Lösung führen. Statt Hunderten von Evaluierungen pro Iteration kommt das Verfahren mit einem einzigen Parametersatz und gezielten Störungen aus – und erreicht dennoch das Maximum von 500 Punkten in nur 41 Schritten.

Ein Algorithmus ohne Gradienten: Wie Simulated Annealing funktioniert

Simuliertes Abkühlen ist ein Metaheuristik-Verfahren, das sich der physikalischen Metapher des „Abkühlens“ bedient: Mit fortschreitender Zeit werden mögliche Lösungen immer präziser an die beste gefundene Lösung angepasst. Im Gegensatz zu populationsbasierten Methoden wie der Cross-Entropy-Methode (CEM) oder REINFORCE arbeitet der hier vorgestellte Ansatz mit einem einzigen Parametersatz, der schrittweise optimiert wird.

Der Kernprozess besteht aus drei Phasen:

• Perturbation (Störung): Der aktuelle Parametersatz theta wird mit zufälligem Rauschen überlagert. Die Stärke dieser Störung wird durch den Parameter alpha gesteuert.
• Evaluation (Bewertung): Der gestörte Parametersatz wird in mehreren Episoden getestet, um eine stabile Leistungsmessung zu erhalten.
• Acceptance (Annahme): Nur wenn der gestörte Parametersatz besser abschneidet, wird er übernommen. Gleichzeitig wird alpha reduziert, um die Suche zu verfeinern.

import numpy as np
import gymnasium as gym

def evaluate_policy(env_name, theta, n_episodes=10):
    """Bewertet eine lineare Politik über mehrere Episoden und gibt die durchschnittliche Belohnung zurück."""
    total_reward = 0
    for _ in range(n_episodes):
        env = gym.make(env_name)
        obs, _ = env.reset()
        episode_reward = 0
        done = False
        while not done:
            # Lineare Entscheidung: Aktion basierend auf dem Skalarprodukt der Beobachtung mit theta
            action = 1 if np.dot(theta, obs) > 0 else 0
            obs, reward, terminated, truncated, _ = env.step(action)
            episode_reward += reward
            done = terminated or truncated
        env.close()
        total_reward += episode_reward
    return total_reward / n_episodes

Schrittweise Optimierung: Vom Zufall zur Präzision

Das Herzstück des Algorithmus liegt in der adaptiven Anpassung der Schrittweite. Zu Beginn ist alpha groß genug, um weite Bereiche des Parameterraums zu erkunden. Jede erfolgreiche Verbesserung führt zu einer Reduktion von alpha um 10 %, sodass die Suche im Laufe der Zeit feingranularer wird.

def simulated_annealing(env_name, n_params, n_iter=80, n_eval_episodes=10, alpha=1.0, decay=0.9):
    """Hügelklettern mit abnehmender Schrittweite für die Parametersuche."""
    best_theta = np.zeros(n_params)  # Initialisiere mit Nullvektor
    best_score = evaluate_policy(env_name, best_theta, n_eval_episodes)

    for i in range(n_iter):
        # Zufällige Störung der aktuellen besten Lösung
        perturbation = (np.random.rand(n_params) - 0.5) * alpha
        candidate = best_theta + perturbation

        # Bewertung des Kandidaten
        score = evaluate_policy(env_name, candidate, n_eval_episodes)

        # Nur bei Verbesserung wird die neue Lösung übernommen
        if score > best_score:
            best_theta = candidate
            best_score = score
            alpha *= decay  # Schrittweite reduzieren

        print(f"Iteration {i+1:3d} | Bewertung: {score:.1f} | Best: {best_score:.1f} | Alpha: {alpha:.4f}")

    return best_theta

Die Ausgabe des Algorithmus zeigt den typischen Verlauf einer solchen Suche:

Iteration   1 | Bewertung:  9.6 | Best:  9.6 | Alpha: 1.0000
Iteration   9 | Bewertung: 128.7 | Best: 128.7 | Alpha: 0.6561
Iteration  14 | Bewertung: 314.2 | Best: 314.2 | Alpha: 0.5314
Iteration  24 | Bewertung: 465.7 | Best: 465.7 | Alpha: 0.4783
Iteration  41 | Bewertung: 500.0 | Best: 500.0 | Alpha: 0.3874

Nach nur 41 Iterationen wird die maximale Punktzahl von 500 erreicht – ein Beweis für die Effizienz des Verfahrens.

Warum Multi-Episode-Bewertung entscheidend ist

Ein häufiger Fehler in einfachen RL-Implementierungen ist die Bewertung einer Politik anhand einer einzigen Episode. Doch CartPole unterliegt stochastischen Startbedingungen, die zu stark variierenden Ergebnissen führen können. Eine Politik könnte beispielsweise bei einem glücklichen Start 500 Punkte erzielen, während sie beim nächsten Versuch nur 50 Punkte erreicht.

Die Lösung: Bewertung über 10 Episoden und Mittelwertbildung. Diese Herangehensweise stabilisiert die Leistungsmessung und verhindert, dass zufällige Ausreißer den Algorithmus in die Irre führen. Der Code zeigt dies in der Funktion evaluate_policy, die die Belohnungen mehrerer Durchläufe mittelt.

Lineare Politik: Einfache Logik mit großer Wirkung

Die Politik selbst ist denkbar simpel: Ein vierdimensionaler Vektor theta gewichtet die Beobachtungen des Systems (Wagenposition, Wagen Geschwindigkeit, Stangenwinkel, Stangenwinkelgeschwindigkeit). Die Entscheidung für eine Aktion (links oder rechts) fällt auf Basis des Vorzeichens des Skalarprodukts zwischen theta und der aktuellen Beobachtung:

action = 1 if np.dot(theta, obs) > 0 else 0

Diese lineare Klassifikation macht deutlich, dass selbst komplexe Aufgaben mit minimalem Modellaufwand lösbar sind – vorausgesetzt, der Algorithmus findet die richtigen Gewichte.

Vergleich mit anderen Methoden: Effizienz auf einen Blick

Der Simulated-Annealing-Ansatz sticht durch seine geringe Komplexität hervor:

• Simulated Annealing: 800 Episoden (41 Iterationen × 10 Bewertungen + 100 finale Tests)
• Cross-Entropy-Methode (CEM): 10.000 Episoden (50 Iterationen × 200 Bewertungen)
• REINFORCE: 5.000 Episoden

Trotz dieses Unterschieds erreicht der Algorithmus vergleichbare oder bessere Ergebnisse. Die Stärke liegt in der zielgerichteten Anpassung der Schrittweite – ein Prinzip, das auch in anderen Optimierungsproblemen Anwendung findet.

Ausblick: Simulated Annealing jenseits von CartPole

Die hier vorgestellte Methode ist nicht nur für CartPole geeignet. Simulated Annealing eignet sich besonders für Probleme mit:

• Diskreten oder kontinuierlichen Parameterräumen
• Unbekannten Gradienteninformationen
• Lokale Optima, die mit zufälliger Exploration überwunden werden müssen

Zukünftige Anwendungen könnten in Bereichen wie Robotik, Logistik oder Finanzmodellierung liegen, wo klassische Gradientenmethoden an ihre Grenzen stoßen. Mit seiner Einfachheit und Robustheit bleibt Simulated Annealing ein mächtiges Werkzeug – auch ohne neuronale Netze oder aufwendige Mathematik.

Der Code steht als interaktives Notebook zur Verfügung. Probieren Sie es aus und entdecken Sie, wie wenig Aufwand nötig ist, um komplexe Probleme zu meistern.