Reinforcement Learning optimiert Nachbarschaftsauswahl in lokalen Suchalgorithmen

In einer neuen Studie aus dem arXiv-Repository wird gezeigt, wie Reinforcement Learning (RL) die Auswahl von Nachbarschaften in lokalen Suchalgorithmen verbessern kann. Dabei wurden verschiedene RL-Strategien – von klassischen Multi-Armed-Bandit-Methoden wie Upper Confidence Bound und ε‑Greedy bis hin zu modernen Deep‑RL-Ansätzen wie Proximal Policy Optimization und Double Deep Q‑Network – systematisch mit traditionellen Baselines verglichen.

Die Experimente erstreckten sich über drei unterschiedliche Optimierungsprobleme: das Travelling‑Salesman‑Problem, das Pickup‑and‑Delivery‑Problem mit Zeitfenstern und das Car‑Sequencing‑Problem. Ein zentrales Ergebnis ist, dass die Effektivität der RL‑Methoden stark von der Problemstellung abhängt. Insbesondere die Gestaltung der Belohnungsfunktion spielt eine entscheidende Rolle, da große Kostenvariationen durch Straftermine für Regelverletzungen stabile Lernsignale erschweren.

Unter den getesteten Algorithmen zeigte sich die ε‑Greedy‑Strategie konstant als einer der besten Performer, während die Deep‑RL‑Ansätze trotz ihrer theoretischen Vorteile durch einen erheblichen Rechenaufwand nur bei deutlich längeren Laufzeiten konkurrenzfähig wurden. Diese Erkenntnisse unterstreichen sowohl das Potenzial als auch die praktischen Grenzen von Deep‑RL in lokalen Suchverfahren.