Discovering Interpretable Multi-Parameter Control Policies for Evolutionary Algorithms Using Deep Reinforcement Learning

Problemstellung
Obwohl Deep Reinforcement Learning (Deep-RL) zu einem State-of-the-Art-Werkzeug für die dynamische Algorithmenkonfiguration (Dynamic Algorithm Configuration, DAC) geworden ist, insbesondere für die Parametersteuerung von Evolutionären Algorithmen (EAs), bleibt eine erhebliche Barriere bestehen: der Mangel an rigoroser theoretischer Analyse für Multi-Parameter-Szenarien. Bestehende theoretische Beweise für die Parametersteuerung beschränken sich weitgehend auf Single-Parameter-Szenarien, da die Ableitung effektiver, interpretierbarer Multi-Parameter-Policies, die einer formalen Untersuchung zugänglich sind, schwierig ist. Darüber hinaus schafft die Abhängigkeit von neuronalen Netzen einen „Black-Box“-Engpass; Praktiker und Theoretiker benötigen explizite, symbolische mathematische Regeln statt opaker neuronaler Gewichte, um algorithmische Verhaltensweisen zu verifizieren, zu analysieren und zu generalisieren. Die spezifische Herausforderung besteht darin, vier Parameter gleichzeitig in dem $(1+(\lambda, \lambda))$-Genetischen Algorithmus (GA) zur Optimierung der OneMax-Funktion zu steuern – ein Problem, bei dem super-konstante Beschleunigungen durch dynamische Steuerung formal nachgewiesen wurden, die Multi-Parameter-Steuerung jedoch untererforscht bleibt.

Methodik
Die Autoren schlagen ein zweistufiges Framework vor, um die Lücke zwischen der empirischen Deep-RL-Leistung und der theoretischen Interpretierbarkeit zu schließen, wie in Abbildung 1 der Arbeit illustriert:

1. Deep-RL Oracle Generierung (Stufe I):

   • Umgebung: Der $(1+(\lambda, \lambda))$-GA wird als kontextueller Markov-Entscheidungsprozess (MDP) modelliert, wobei der Zustand die aktuelle Fitness ist und die Aktionen die vier Parameter sind: Mutationspopulationsgröße ($\lambda_m$), Crossover-Populationsgröße ($\lambda_c$), Mutationsraten-Koeffizient ($\alpha$) und Crossover-Bias-Koeffizient ($\beta$).
   • Algorithmenvergleich: Die Studie vergleicht Double Deep Q-Networks (DDQN) und Proximal Policy Optimization (PPO).
   • Repräsentation des Aktionsraums: Zwei Architekturen werden getestet: kombinatorisch (Behandlung von Parameterkombinationen als atomare Aktionen) und faktoriert (Zerlegung des Aktionsraums in unabhängige Teil-Aktionen für jeden Parameter).
   • Verbesserungen: Die Autoren führen algorithmus-agnostische Verbesserungen ein, einschließlich Aktionsraum-Zerlegung, Reward-Shifting (adaptiver Bias) und Long-Horizon-Discounting (unter Verwendung von $\gamma \approx 1.0$).
   • Ergebnisse zu RL: DDQN mit faktorierten Aktionsrepräsentationen, adaptivem Reward-Shifting und hohen Discount-Faktoren erweist sich als robust. Im Gegensatz dazu leidet PPO unter „Policy Collapse“, wobei es häufig zu suboptimalen, statischen Policies konvergiert (z. B. Fixierung von $\lambda_m=1$), unabhängig vom Aktionsraum oder den Versuchen des Reward-Shaping.

2. Symbolische Destillation (Stufe II):

   • Handgefertigtes Design: Basierend auf den von dem besten DDQN-Agenten generierten Trajektorien leiten die Autoren manuell eine transparente, symbolische Steuerungs-Policy ab. Sie analysieren die Beziehung zwischen Fitness-Fortschritt und Parameterwerten, um explizite Gleichungen zu formulieren.
   • Feinabstimmung: Diese handgefertigten symbolischen Gleichungen werden weiter durch SMAC3 (ein automatisiertes Algorithmen-Konfigurationstool) verfeinert. Der Suchraum umfasst Schaltpunkte für Populationsgrößen und Amplifikationsfaktoren, was eine präzise Optimierung der symbolischen Konstanten ermöglicht.

Zentrale Beiträge

• Vergleichende Wirksamkeit von Deep-RL-Methoden: Die Arbeit zeigt, dass PPO zwar in allgemeinen RL-Domänen stabil ist, in dieser spezifischen DAC-Umgebung jedoch aufgrund von Policy Collapse versagt. Im Gegensatz dazu navigiert DDQN, wenn es mit faktorierten Aktionsrepräsentationen und spezifischen Reward-/Discounting-Strategien ausgestattet ist, erfolgreich durch die Multi-Parameter-Landschaft, um qualitativ hochwertige Trajektorien zu generieren.
• Entdeckung symbolischer Policies: Die Autoren gehen über Black-Box-neuronale Netze hinaus, indem sie gelernte Verhaltensweisen in eine symbolische Policy destillieren. Diese Policy ist nicht nur interpretierbar, sondern übertrifft auch bestehende Baselines.
• Zweistufiges Destillations-Framework: Die Arbeit führt eine Methodik ein, die zuerst Deep-RL zur Exploration des Lösungsraums nutzt und anschließend Algorithmen-Konfiguration (SMAC3) zur Verfeinerung handgefertigter symbolischer Repräsentationen verwendet, was eine Policy ergibt, die sowohl empirisch überlegen als auch theoretisch handhabbar ist.
• Analyse der Parameterwichtigkeit: Durch Ablationsstudien stellt die Arbeit eine Hierarchie der Parameterwichtigkeit fest: $\lambda_m \gg \alpha \gg \lambda_c \gg \beta$. Es wird aufgezeigt, dass die Entkopplung von $\lambda_m$ und $\lambda_c$ (Ermöglichung eines $\lambda_c$, das signifikant größer als $\lambda_m$ ist) ein entscheidender Faktor für die Leistung ist.

Ergebnisse

• RL-Leistung: Die beste DDQN-Konfiguration (faktoriert Repräsentation, adaptives Reward-Shifting, $\gamma=0.9998$) übertrifft PPO und Single-Parameter-Steuerungs-Policies konsistent über verschiedene Problemgrößen hinweg ($n=100$ bis $n=2.000$).
• Leistung der symbolischen Policy: Die finale, durch SMAC3 verfeinerte symbolische Policy erreicht eine normalisierte erwartete Laufzeit (Expected Runtime, ERT) von etwa 4,7, verglichen mit 6,9 für die theoretische Baseline ($\pi_{THEORY}$) und 5,8 für die IRACE-basierte Baseline.
• Skalierbarkeit: Die abgeleitete symbolische Policy behält ihren Leistungsvorteil über einen weiten Bereich von Problemgrößen bei, einschließlich sehr großer Instanzen bis zu $n=40.000$.
• Größenordnung der Verbesserung: Die finale SMAC3-getunte Policy liefert eine konsistente Beschleunigung und übertrifft die theoretisch abgeleitete Baseline um etwa 27,5 % und den IRACE-basierten Ansatz um 19,4 % bis 32,2 %, abhängig von der Problemgröße.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass diese Arbeit erfolgreich die Lücke zwischen empirischer Deep-RL-Entdeckung und theoretischer Verifizierung in der Evolutionären Berechnung schließt. Durch die Umwandlung der „Black-Box“-Ausgabe eines neuronalen Netzes in eine „White-Box“-symbolische Policy bieten die Autoren:

1. Interpretierbarkeit: Explizite mathematische Regeln, die es Forschern ermöglichen, formale Laufzeitanalysen durchzuführen – eine Aufgabe, die zuvor durch die Komplexität neuronaler Netze erschwert wurde.
2. Generalisierung: Die symbolische Natur der Policy ermöglicht eine Zero-Shot-Generalisierung auf ungesehene Probleminstanzen und -dimensionen und vermeidet so das bei neuronalen Netzen übliche Overfitting.
3. Effizienz: Die Evaluierung der symbolischen Policy verursacht lediglich einen $O(1)$-Overhead und umgeht so die Rechenkosten der tiefen Netzwerk-Inferenz.
4. Theoretische Handhabbarkeit: Die abgeleitete Policy bietet ein konkretes Ziel für zukünftige theoretische Beweise bezüglich der konstanten Faktoren linearer erwarteter Laufzeiten für den $(1+(\lambda, \lambda))$-GA und adressiert damit eine Lücke, in der aktuelle theoretische Grenzen oft zu pessimistisch gegenüber empirischen Ergebnissen sind.

Die Autoren kommen zu dem Schluss, dass der wahre Wert von Deep-RL für die Algorithmenkonfiguration erst realisiert wird, wenn seine Ergebnisse in interpretierbare, symbolische Formen destilliert werden, die rigoros analysiert und generalisiert werden können.