⚡ electrical engineering

Exact and Evolutionary Algorithms for Sequential Multi-Objective Transmission Topology Planning

Dieser Beitrag stellt einen exakten Blockenumerationsalgorithmus und eine maßgeschneiderte NSGA-III-evolutionäre Heuristik zur Lösung des sequenziellen mehrzieligen Problems der Netztopologieplanung vor und zeigt, dass die exakte Methode die vollständige Pareto-Front für reale niederländische Netzdaten effizient berechnet und gleichzeitig als Ground-Truth-Referenz für zukünftige Ansätze dient.

Ursprüngliche Autoren: Job Groeneveld, Miguel Muñoz, Jan Viebahn, Alessandro Zocca

Veröffentlicht 2026-05-06

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Job Groeneveld, Miguel Muñoz, Jan Viebahn, Alessandro Zocca

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich ein massives, hochriskantes Spiel elektrischen Tetris vor.

In diesem Spiel sind die „Steine" elektrischer Strom, der durch Leitungen fließt, und das „Spielfeld" das nationale Stromnetz. Das Ziel ist es, zu verhindern, dass sich die Steine zu hoch aufstauen (was zu gefährlichen Überlastungen führt), während strikte Regeln eingehalten werden müssen, wie sich die Steine bewegen dürfen.

Dieser Artikel behandelt eine spezifische Version dieses Spiels: Wie sollte ein Netzbetreiber die Verbindungen in seinem Netzwerk über die nächsten 24 Stunden neu anordnen, um Blackouts und Überlastungen zu verhindern, während Kosten und Aufwand gering gehalten werden?

Hier ist die Aufschlüsselung der Geschichte des Artikels, unter Verwendung einfacher Analogien:

Das Problem: Das Netz ist belastet

Stellen Sie sich das Stromnetz wie ein belebtes Autobahnsystem vor. In jüngster Zeit wurden immer mehr „Autos" (Strom aus Wind- und Solarparks) auf die Straßen gesetzt. Doch die Straßen wurden nicht schnell genug verbreitert. Dies führt zu Staus (Überlastungen).

Wenn eine Straße zu überfüllt wird, kann sie überhitzen und brechen. Um dies zu beheben, haben Betreiber normalerweise zwei Möglichkeiten:

Einige Autos abschalten: Windparks anweisen, die Stromerzeugung einzustellen (dies kostet Geld und verschwendet grüne Energie).
Den Verkehr umleiten: Schalter in den Umspannwerken öffnen und schließen, um die Form des Straßennetzes zu ändern und einen flüssigeren Verkehrsfluss zu ermöglichen.

Der Artikel konzentriert sich auf Option 2. Die Herausforderung besteht darin, dass man die Straßen nicht nur einmal ändern kann; man muss für jede einzelne Stunde des nächsten Tages eine neue Straßenkarte planen. Und man muss vier konkurrierende Ziele ausbalancieren:

Sicherheit: Die schwerste Verkehrsbelastung so niedrig wie möglich halten (damit keine Leitungen brechen).
Einfachheit: Das Straßennetz nicht zu kompliziert machen (weniger geöffnete Schalter).
Aufwand: Die Straßenkarte nicht zu oft ändern (das Schalten verschleißt die Maschinen).
Stabilität: Versuchen, die „Standard"-Straßenkarte so weit wie möglich beizubehalten und sie nur bei absoluter Notwendigkeit zu ändern.

Die Lösung: Zwei verschiedene Ansätze

Die Autoren entwickelten zwei verschiedene „Spieler", um dieses 24-Stunden-Planungsrätsel zu lösen.

Spieler 1: Der „Block"-Algorithmus (Der perfekte Planer)

Stellen Sie sich vor, Sie versuchen, ein Puzzle zu lösen, aber Sie merken, dass die Puzzleteile nicht jede einzelne Sekunde geändert werden müssen. Wenn der Verkehr zwischen 2:00 und 4:00 Uhr morgens leicht ist, benötigen Sie keinen neuen Plan für 2:01, 2:02 usw. Sie können denselben Plan für diesen gesamten Zeitblock beibehalten.

Der Block-Algorithmus nutzt diesen Trick. Anstatt jede einzelne Stunde einzeln zu prüfen, gruppiert er Stunden in „Blöcke", in denen der Plan gleich bleibt.

Funktionsweise: Er versucht systematisch jede mögliche Kombination dieser Zeitblöcke und Straßenlayouts.
Das Ergebnis: Er findet die perfekte Liste aller möglichen „besten" Pläne. Mathematisch ausgedrückt findet er die „Pareto-Front". Das bedeutet, er zeigt dem Betreiber jeden möglichen Kompromiss auf: „Wenn Sie maximale Sicherheit wollen, ist dies der Plan. Wenn Sie weniger schalten wollen, ist dies der Plan. Wenn Sie einen Ausgleich wollen, ist dies der Plan."
Geschwindigkeit: Überraschenderweise löst dieser Algorithmus, obwohl es Millionen von Möglichkeiten gibt, dank seiner intelligenten Zeitgruppierung einen vollständigen Tagesplan in unter 3 Minuten.

Spieler 2: Der evolutionäre Algorithmus (Der Trial-and-Error-Erkunder)

Dieser Spieler ist wie ein biologischer Evolutionssimulator.

Funktionsweise: Er beginnt mit einer zufälligen Menge von 1.000 verschiedenen Plänen. Er lässt sie sich „paaren" (Teile zweier Pläne kombinieren) und „mutieren" (einen Teil eines Plans zufällig ändern). Er behält die besten Pläne und verwirft die schlechten und wiederholt diesen Prozess immer wieder.
Das Ziel: Schließlich eine Reihe guter Pläne zu „entwickeln", die der perfekten Liste ähneln.
Das Ergebnis: Er kommt der perfekten Liste nahe, verpasst aber einige der allerbesten Optionen. Es ist wie ein Wanderer, der versucht, in einer nebligen Bergkette den höchsten Gipfel zu finden; er mag einen hohen Gipfel finden, aber er könnte den absolut höchsten verpassen, weil er die gesamte Karte nicht sehen kann.

Das Duell: Wer hat gewonnen?

Die Autoren testeten beide Spieler mit echten Daten des niederländischen Stromnetzes (TenneT) an einem Tag, an dem das Netz extrem belastet war.

Der perfekte Planer (Block-Algorithmus) gewann. Er fand die vollständige Liste von 83 „perfekten" Kompromissstrategien in unter 3 Minuten.
Der Erkunder (evolutionärer Algorithmus) landete auf Platz zwei. Er fand einige gute Strategien, verpasste aber die allerbesten. Insbesondere gelang es ihm nicht, Pläne zu finden, die das Netz zu 100 % sicher halten könnten, ohne Leitungen zu überlasten, während der perfekte Planer mehrere solcher Pläne fand.

Die große Erkenntnis

Der Artikel behauptet, dass für diese spezifische Art von Stromnetzproblem nicht geraten oder auf „smarte" KI-Näherungen zurückgegriffen werden muss. Da das Problem eine spezielle „Block"-Struktur hat (Pläne bleiben für Zeitabschnitte gleich), kann man tatsächlich die exakte, perfekte Antwort sehr schnell berechnen.

Warum ist das wichtig?

Für Netzbetreiber: Sie haben nun ein Werkzeug, das ihnen eine vollständige Auswahl an perfekten Optionen zur Verfügung stellt, anstatt nur eine Vermutung.
Für zukünftige Forschung: Dieser „perfekte Planer" dient nun als „Goldstandard" (oder Grundwahrheit). Jede neue KI- oder Machine-Learning-Methode, die in der Zukunft entwickelt wird, kann gegen diese Liste getestet werden, um zu sehen, ob sie tatsächlich gut ist oder nur Glück hatte.

Kurz gesagt: Die Autoren fanden einen Weg, ein komplexes, 24-Stunden-Stromnetz-Rätsel perfekt und sofort zu lösen, und bewiesen, dass manchmal die „Brute-Force"-Methode, wenn sie intelligent durchgeführt wird, besser ist als die „smarte" Ratemethode.

Technische Zusammenfassung: Exakte und evolutionäre Algorithmen für die sequenzielle multi-kriterielle Planung von Übertragungsnetztopologien

Problemformulierung
Der Beitrag behandelt die Planung der Übertragungsnetztopologie im Voraus als sequenzielles, multi-kriterielles Optimierungsproblem. Das Ziel besteht darin, eine Folge von Netztopologien über einen 24-Stunden-Horizont (24 Zeitschritte) zu bestimmen, um Netzüberlastungen zu bewältigen. Das Problem wird durch vier operative Ziele definiert, die reale Entscheidungskriterien von Übertragungsnetzbetreibern (TSO) widerspiegeln und alle zu minimieren sind:

Maximale Leitungsbelastung im Worst-Case ( $LF_1$ ): Die maximale Kapazitätsauslastung einer beliebigen Übertragungsleitung unter $N-1$ -Sicherheitsbedingungen über den gesamten Horizont hinweg.
Topologische Tiefe ( $d$ ): Die maximale Anzahl zusätzlicher Sammelschienen, die durch das Öffnen von Sammelschienenkupplungen (Knotenaufspaltung) im Vergleich zur Referenztopologie (alle Kupplungen geschlossen) zu einem beliebigen Zeitpunkt erzeugt werden.
Anzahl der Schaltvorgänge ( $w$ ): Die Gesamtzahl der Topologieänderungen (Schaltungen), die über den 24-Stunden-Zeitraum durchgeführt werden.
Ausnutzung von Nicht-Referenztopologien ( $z$ ): Die Anzahl der Zeitschritte, in denen das Netz in einer Konfiguration betrieben wird, die von der Standard-Referenztopologie abweicht.

Die Studie nutzt reale Betriebsdaten des niederländischen Hochspannungsnetzes, das von TenneT TSO verwaltet wird, mit Fokus auf einen stark überlasteten Tag, an dem die Referenztopologie unter $N-1$ -Bedingungen häufig eine Belastung von über 100 % aufweist.

Methodik
Die Autoren schlagen zwei komplementäre Algorithmen vor und vergleichen diese: ein exaktes Aufzählungsverfahren und eine maßgeschneiderte evolutionäre Heuristik.

Der Block-Algorithmus (Exakte Methode):
- Kernkonzept: Dieser Algorithmus nutzt die zeitliche Blockstruktur zulässiger Strategien aus. Anstatt jeden Zeitschritt unabhängig zu bewerten, unterteilt er den 24-Stunden-Horizont in zusammenhängende, nicht überlappende Intervalle (Blöcke), in denen die Topologie konstant bleibt.
- Mechanismus: Er enumeriert systematisch alle möglichen Blockkonfigurationen, Zuordnungen von Referenztopologien und Tiefenstufen. Durch die Vorab-Berechnung von Lastflusswerten für alle verfügbaren Topologien pro Zeitschritt bewertet der Algorithmus Blockkombinationen, um die vollständige Pareto-Front zu identifizieren.
- Komplexität: Bei festen operativen Grenzen für die maximale Tiefe ( $d_{max}$ ) und die maximale Schaltanzahl ( $s_{max}$ ) wächst die Anzahl der Bewertungen polynomial mit dem Planungshorizont. Der Algorithmus filtert Strategien basierend auf einer nicht-dominierenden Sortierung und nutzt die Tatsache, dass drei der vier Ziele diskrete ganze Zahlen sind, um Pareto-optimale Lösungen effizient zu identifizieren.
Multi-kriterieller evolutionärer Algorithmus (MOEA):
- Rahmenwerk: Basierend auf NSGA-III, ausgewählt aufgrund seiner Effektivität bei Problemen mit vielen Zielen (vier Ziele).
- Repräsentation: Verwendet eine direkte kodierung variabler Länge, wobei jedes Gen die Topologie für einen spezifischen Zeitschritt darstellt.
- Initialisierung: Setzt eine „strukturgeführte" Stichprobenstrategie ein, anstatt einer gleichmäßigen zufälligen Initialisierung. Es werden Anfangspopulationen generiert, indem spezifische Schaltanzahlen und topologische Tiefen ausbalanciert werden, um eine Diversität in den relevanten Dimensionen des Zielraums sicherzustellen.
- Variation: Verwendet einen $k$ -Punkt-Crossover (mit $k=2$ ), um die zeitliche Kohärenz zu bewahren, und eine zufällige Reset-Mutation, um die Zulässigkeit innerhalb des Satzes verfügbarer Topologien für jeden Zeitschritt sicherzustellen.

Hauptbeiträge

Formalisierung: Das Problem wird formal als sequenzielle multi-kriterielle Optimierung mit vier spezifischen, für TSO relevante Ziele definiert und geht damit über einzelne Zielsetzungen oder isolierte Zeitschritt-Formulierungen hinaus.
Exakte Aufzählung: Die Entwicklung des „Block-Algorithmus", der die vollständige Pareto-Front für einen realen, überlasteten Tag in weniger als drei Minuten berechnet. Er liefert einen Ground-Truth-Benchmark für diese Problemklasse.
Maßgeschneiderte Heuristik: Das Design eines spezialisierten MOEA mit strukturgeführter Initialisierung und problemspezifischen Variationsoperatoren, bewertet gegen die exakte Front unter Verwendung des Inverted Generational Distance Plus (IGD+) und einer neuartigen Multi-Front-Abdeckungsmetrik.
Empirische Validierung: Eine vergleichende Studie mit TenneT-Daten, die zeigt, dass die exakte Aufzählung rechnerisch machbar ist und die evolutionäre Suche bei der Wiederherstellung des vollständigen Satzes optimaler Strategien übertrifft.

Ergebnisse

Leistung des Block-Algorithmus: Die exakte Methode enumerierte erfolgreich die vollständige Pareto-Front und identifizierte 83 eindeutige Punkte im Zielraum (repräsentativ für 163.807.652 verschiedene Strategien). Sie ergab, dass das Erreichen von $LF_1 < 100\%$ (volle $N-1$ -Sicherheit) erfordert, die Referenztopologie während überlasteter Stunden vollständig aufzugeben und mit höheren topologischen Tiefen zu operieren.
Leistung des MOEA: Der evolutionäre Algorithmus konvergierte in Richtung der Pareto-Front, scheiterte jedoch daran, den exakten Lösungssatz wiederherzustellen.
- Die am besten performende Konfiguration (Populationsgröße 1.621, Mutationsrate 0,10) erholte nur etwa 6 % der eindeutigen, vom Block-Algorithmus gefundenen Pareto-optimalen Punkte.
- Der MOEA hatte Schwierigkeiten, Lösungen mit $LF_1 < 100\%$ zu finden, die von der exakten Methode identifiziert wurden.
- Die Abdeckung war insbesondere für Strategien mit vielen Nicht-Referenztopologien (extreme Regionen des Suchraums) sehr gering.
Vergleich: Während der MOEA eine schnelle initiale Konvergenz zeigte (innerhalb von 5 Minuten), erreichte er ein Plateau und konnte die Vollständigkeit des Block-Algorithmus nicht erreichen. Die Fähigkeit des Block-Algorithmus, alle zulässigen Strategien aufzuzählen, ermöglichte es ihm, Kompromisse zu identifizieren, die die Heuristik übersehen hatte.

Bedeutung und Behauptungen
Der Beitrag behauptet, dass die kombinatorische Komplexität der Optimierung topologischer Strategien über einen 24-Stunden-Horizont, die oft als unlösbar wahrgenommen wird, durch Ausnutzung der zeitlichen Blockstruktur des Problems exakt und effizient gelöst werden kann.

Entscheidungsunterstützung: Der Block-Algorithmus bietet TSOs ein vollständiges Menü Pareto-optimaler Strategien, das es Betreibern ermöglicht, Aktionen basierend auf spezifischen täglichen Prioritäten auszuwählen (z. B. Minimierung von Schaltvorgängen vs. Maximierung der Sicherheit).
Benchmarking: Die exakte Front dient als strenger Ground-Truth-Benchmark zur Bewertung zukünftiger heuristischer und lernbasierter Methoden.
Machbarkeit: Die Studie zeigt, dass die exakte Aufzählung nicht nur theoretisch möglich, sondern für reale, stark überlastete Netz-Szenarien praktisch durchführbar ist, was die Annahme herausfordert, dass Heuristiken für solche Probleme zwingend erforderlich sind.

Die Autoren erkennen Einschränkungen an, darunter die Verwendung von DC-Lastfluss-Näherungen, deterministische Prognosen und die Abhängigkeit von vorausberechneten Datensätzen. Sie schlagen vor, dass zukünftige Arbeiten stochastische Formulierungen, robuste Optimierung und den Einsatz von Imitationslernen beinhalten könnten, um den Engpass der Vorab-Berechnung zu umgehen. Im Rahmen der Studie wird der Block-Algorithmus jedoch aufgrund seiner Exaktheit, Geschwindigkeit und Vollständigkeit als bevorzugte Methode vorgestellt.