⚡ electrical engineering

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

Ce papier présente un algorithme exact d'énumération par blocs et une heuristique évolutionnaire NSGA-III adaptée pour résoudre le problème de planification séquentielle de la topologie de transmission multi-objectif, démontrant que la méthode exacte calcule efficacement l'ensemble complet du front de Pareto pour des données réelles du réseau néerlandais tout en servant de référence de vérité terrain pour les approches futures.

Auteurs originaux : Job Groeneveld, Miguel Muñoz, Jan Viebahn, Alessandro Zocca

Publié 2026-05-06

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Job Groeneveld, Miguel Muñoz, Jan Viebahn, Alessandro Zocca

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un jeu de Tetris électrique massif et à enjeux élevés.

Dans ce jeu, les « blocs » sont l'électricité circulant dans les lignes à haute tension, et le « plateau » est le réseau électrique national. L'objectif est d'empêcher les blocs de s'empiler trop haut (ce qui provoque des surcharges dangereuses) tout en respectant des règles strictes concernant la manière dont les blocs peuvent se déplacer.

Ce document aborde une version spécifique de ce jeu : Comment un gestionnaire de réseau électrique devrait-il réorganiser les connexions de son réseau au cours des 24 prochaines heures pour prévenir les pannes et les surcharges, tout en maintenant les coûts et les efforts à un niveau bas ?

Voici la décomposition de l'histoire du document, en utilisant des analogies simples :

Le Problème : Le Réseau est Sous Tension

Imaginez le réseau électrique comme un système autoroutier très fréquenté. Récemment, de plus en plus de « voitures » (électricité provenant de parcs éoliens et solaires) ont été ajoutées sur les routes. Mais les routes n'ont pas été élargies assez rapidement. Cela provoque des embouteillages (congestion).

Si une route devient trop encombrée, elle peut surchauffer et se briser. Pour résoudre ce problème, les opérateurs ont généralement deux choix :

Éteindre certaines voitures : Demander aux parcs éoliens de cesser de produire de l'électricité (cela coûte de l'argent et gaspille de l'énergie verte).
Rediriger le trafic : Ouvrir et fermer des interrupteurs dans les sous-stations pour modifier la forme du réseau routier, permettant au trafic de circuler plus fluidement.

Le document se concentre sur l'Option 2. Le défi est que vous ne pouvez pas simplement changer les routes une fois ; vous devez planifier une nouvelle carte routière pour chaque heure individuelle du lendemain. Et vous devez équilibrer quatre objectifs concurrents :

Sécurité : Maintenir la charge de trafic la plus lourde aussi basse que possible (pour qu'aucune ligne ne se brise).
Simplicité : Ne pas rendre le réseau routier trop compliqué (moins d'interrupteurs ouverts).
Effort : Ne pas changer la carte routière trop souvent (changer de vitesse use la mécanique).
Stabilité : Essayer de conserver la « carte routière » par défaut autant que possible, en ne la modifiant que lorsque cela est absolument nécessaire.

La Solution : Deux Approches Différentes

Les auteurs ont construit deux « joueurs » différents pour résoudre ce puzzle de planification sur 24 heures.

Joueur 1 : L'Algorithme « Bloc » (Le Planificateur Parfait)

Imaginez que vous essayez de résoudre un puzzle, mais que vous réalisez que les pièces du puzzle n'ont pas besoin de changer chaque seconde. Si le trafic est léger de 2 h 00 à 4 h 00, vous n'avez pas besoin d'un nouveau plan pour 2 h 01, 2 h 02, etc. Vous pouvez simplement garder le même plan pour tout ce bloc de temps.

L'Algorithme Bloc utilise cette astuce. Au lieu de vérifier chaque heure individuellement, il regroupe les heures en « blocs » où le plan reste le même.

Fonctionnement : Il teste systématiquement chaque combinaison possible de ces blocs de temps et de ces agencements routiers.
Résultat : Il trouve la liste parfaite de tous les « meilleurs » plans possibles. En termes mathématiques, il trouve le « front de Pareto ». Cela signifie qu'il montre à l'opérateur tous les compromis possibles : « Si vous voulez une sécurité maximale, voici le plan. Si vous voulez moins de commutations, voici le plan. Si vous voulez un équilibre, voici le plan. »
Vitesse : Étonnamment, même s'il existe des millions de possibilités, cet algorithme est si intelligent dans le regroupement du temps qu'il résout un plan complet d'une journée en moins de 3 minutes.

Joueur 2 : L'Algorithme Évolutif (L'Explorateur par Essais et Erreurs)

Ce joueur est comme un simulateur d'évolution biologique.

Fonctionnement : Il commence avec une foule aléatoire de 1 000 plans différents. Il les laisse « s'accoupler » (combiner des parties de deux plans) et « muter » (modifier aléatoirement une partie d'un plan). Il conserve les meilleurs plans et jette les mauvais, répétant ce processus encore et encore.
Objectif : Finir par « évoluer » un ensemble de bons plans qui ressemblent à la liste parfaite.
Résultat : Il s'approche de près de la liste parfaite, mais il manque certaines des meilleures options. C'est comme un randonneur essayant de trouver le sommet le plus élevé dans une chaîne de montagnes brumeuse ; il pourrait trouver un sommet élevé, mais il pourrait manquer le sommet absolu le plus haut parce qu'il ne peut pas voir toute la carte.

L'Affrontement : Qui a Gagné ?

Les auteurs ont testé les deux joueurs en utilisant de vraies données du réseau électrique néerlandais (TenneT) lors d'une journée où le réseau était sous une tension extrême.

Le Planificateur Parfait (Algorithme Bloc) a gagné. Il a trouvé la liste complète de 83 stratégies de compromis « parfaites » en moins de 3 minutes.
L'Explorateur (Algorithme Évolutif) est arrivé deuxième. Il a trouvé quelques bonnes stratégies, mais il a manqué les toutes meilleures. Plus précisément, il n'a réussi à trouver aucun plan capable de maintenir le réseau à 100 % sûr sans surcharger les lignes, alors que le Planificateur Parfait en a trouvé plusieurs.

La Grande Conclusion

L'article affirme que pour ce type spécifique de problème de réseau électrique, vous n'avez pas besoin de deviner ou d'utiliser des approximations « intelligentes » de l'IA. Parce que le problème possède une structure « bloc » spéciale (les plans restent les mêmes pendant des tranches de temps), vous pouvez en fait calculer la réponse exacte et parfaite très rapidement.

Pourquoi cela importe-t-il ?

Pour les Gestionnaires de Réseau : Ils disposent désormais d'un outil qui leur offre un menu complet d'options parfaites à choisir, plutôt qu'une simple supposition.
Pour la Recherche Future : Ce « Planificateur Parfait » sert désormais de « Référence Or » (ou vérité terrain). Toute nouvelle méthode d'IA ou d'apprentissage automatique développée à l'avenir pourra être testée contre cette liste pour voir si elle est réellement bonne ou simplement chanceuse.

En résumé : Les auteurs ont trouvé un moyen de résoudre parfaitement et instantanément un puzzle complexe de réseau électrique sur 24 heures, prouvant que parfois, la méthode de « force brute », lorsqu'elle est exécutée intelligemment, est supérieure à la méthode de devinette « intelligente ».

Résumé technique : Algorithmes exacts et évolutionnaires pour la planification séquentielle de la topologie de transmission multi-objectif

Formulation du problème
L'article aborde la planification de la topologie de transmission à J-1 comme un problème d'optimisation séquentielle multi-objectif. L'objectif est de déterminer une séquence de topologies de réseau sur un horizon de 24 heures (24 pas de temps) pour gérer les congestions du réseau. Le problème est défini par quatre objectifs opérationnels reflétant les critères de décision réels des gestionnaires de réseau de transport (GRT), tous devant être minimisés :

Charge maximale des lignes ( $LF_1$ ) : La capacité maximale d'utilisation de n'importe quelle ligne de transmission dans le cadre des contingences de sécurité $N-1$ sur l'ensemble de l'horizon.
Profondeur topologique ( $d$ ) : Le nombre maximal de barres de bus supplémentaires créées par l'ouverture de couplages de barres (découplage de nœuds) par rapport à la topologie de référence (tous les couplages fermés) à tout moment.
Nombre d'actions de commutation ( $w$ ) : Le nombre total de changements de topologie (commutations) effectués sur la période de 24 heures.
Utilisation de topologies non de référence ( $z$ ) : Le nombre de pas de temps où le réseau fonctionne dans une configuration différente de la topologie de référence par défaut.

L'étude utilise des données opérationnelles réelles du réseau haute tension néerlandais géré par TenneT GRT, en se concentrant sur une journée fortement congestionnée où la topologie de référence dépasse fréquemment 100 % de charge dans des conditions $N-1$ .

Méthodologie
Les auteurs proposent et comparent deux algorithmes complémentaires : une méthode d'énumération exacte et une heuristique évolutionnaire adaptée.

L'algorithme par blocs (Méthode exacte) :
- Concept de base : Cet algorithme exploite la structure temporelle en blocs des stratégies réalisables. Au lieu d'évaluer chaque pas de temps indépendamment, il divise l'horizon de 24 heures en intervalles contigus et non chevauchants (blocs) où la topologie reste constante.
- Mécanisme : Il énumère systématiquement toutes les configurations de blocs possibles, les affectations de topologie de référence et les niveaux de profondeur. En pré-calculant les valeurs d'écoulement de charge pour toutes les topologies disponibles par pas de temps, l'algorithme évalue les combinaisons de blocs pour identifier l'ensemble complet du front de Pareto.
- Complexité : Pour des bornes opérationnelles fixes sur la profondeur maximale ( $d_{max}$ ) et le nombre maximal de commutations ( $s_{max}$ ), le nombre d'évaluations croît de manière polynomiale avec l'horizon de planification. L'algorithme filtre les stratégies en se basant sur un tri non dominé, exploitant le fait que trois des quatre objectifs sont des entiers discrets pour identifier efficacement les solutions optimales au sens de Pareto.
Algorithme évolutionnaire multi-objectif (MOEA) :
- Cadre : Basé sur NSGA-III, sélectionné pour son efficacité dans les problèmes à nombreux objectifs (quatre objectifs).
- Représentation : Utilise un codage direct de longueur variable où chaque gène représente la topologie pour un pas de temps spécifique.
- Initialisation : Emploie une stratégie d'échantillonnage « guidée par la structure » plutôt qu'une initialisation aléatoire uniforme. Il génère des populations initiales en équilibrant des nombres de commutations spécifiques et des profondeurs topologiques pour assurer la diversité dans les dimensions pertinentes de l'espace des objectifs.
- Variation : Utilise un croisement à $k$ points (avec $k=2$ ) pour préserver la cohérence temporelle et une mutation de réinitialisation aléatoire pour assurer la faisabilité au sein de l'ensemble des topologies disponibles pour chaque pas de temps.

Contributions clés

Formalisation : Le problème est défini formellement comme une optimisation séquentielle multi-objectif avec quatre objectifs spécifiques pertinents pour les GRT, dépassant les formulations mono-objectif ou isolées par pas de temps.
Énumération exacte : Le développement de l'« algorithme par blocs », qui calcule l'ensemble complet du front de Pareto pour une journée congestionnée réelle en moins de trois minutes. Il fournit une référence de vérité terrain pour cette classe de problèmes.
Heuristique adaptée : La conception d'un MOEA spécialisé avec une initialisation guidée par la structure et des opérateurs de variation spécifiques au problème, évalué par rapport au front exact en utilisant la distance génératrice inversée plus (IGD+) et une nouvelle métrique de couverture multi-fronts.
Validation empirique : Une étude comparative utilisant des données TenneT démontrant que l'énumération exacte est computationnellement réalisable et surpasse la recherche évolutionnaire pour retrouver l'ensemble complet des stratégies optimales.

Résultats

Performance de l'algorithme par blocs : La méthode exacte a énuméré avec succès l'ensemble complet du front de Pareto, identifiant 83 points uniques dans l'espace des objectifs (représentant 163 807 652 stratégies distinctes). Elle a constaté que l'atteinte d'une charge $LF_1 < 100\%$ (sécurité $N-1$ complète) nécessite d'abandonner entièrement la topologie de référence pendant les heures de congestion et de fonctionner à des profondeurs topologiques plus élevées.
Performance du MOEA : L'algorithme évolutionnaire a convergé vers le front de Pareto mais n'a pas réussi à retrouver l'ensemble exact des solutions.
- La configuration la plus performante (taille de population 1 621, taux de mutation 0,10) n'a récupéré qu'environ 6 % des points uniques optimaux au sens de Pareto trouvés par l'algorithme par blocs.
- Le MOEA a eu du mal à trouver des solutions avec $LF_1 < 100\%$ , qui ont été identifiées par la méthode exacte.
- La couverture était particulièrement faible pour les stratégies impliquant de nombreuses topologies non de référence (régions extrêmes de l'espace de recherche).
Comparaison : Bien que le MOEA ait montré une convergence initiale rapide (en moins de 5 minutes), il a atteint un plateau et n'a pas pu égaler l'exhaustivité de l'algorithme par blocs. La capacité de l'algorithme par blocs à énumérer toutes les stratégies réalisables lui a permis d'identifier des compromis que l'heuristique a manqués.

Importance et affirmations
L'article affirme que la complexité combinatoire de l'optimisation des stratégies topologiques sur un horizon de 24 heures, souvent perçue comme insoluble, peut être résolue de manière exacte et efficace en exploitant la structure temporelle en blocs du problème.

Aide à la décision : L'algorithme par blocs fournit aux GRT un menu complet de stratégies optimales au sens de Pareto, permettant aux opérateurs de sélectionner des actions en fonction de priorités quotidiennes spécifiques (par exemple, minimiser les commutations par rapport à maximiser la sécurité).
Étalonnage : Le front exact sert de référence de vérité terrain rigoureuse pour évaluer les futures méthodes heuristiques et basées sur l'apprentissage.
Faisabilité : L'étude démontre que l'énumération exacte n'est pas seulement théoriquement possible mais pratiquement viable pour des scénarios de réseau réels fortement congestionnés, remettant en question l'hypothèse selon laquelle les heuristiques sont strictement nécessaires pour de tels problèmes.

Les auteurs reconnaissent des limites, notamment l'utilisation d'approximations de flux de puissance DC, de prévisions déterministes et la dépendance à des jeux de données précalculés. Ils suggèrent que des travaux futurs pourraient impliquer des formulations stochastiques, une optimisation robuste et l'application de l'apprentissage par imitation pour contourner le goulot d'étranglement du précalcul. Cependant, dans le cadre de l'étude, l'algorithme par blocs est présenté comme la méthode préférée pour son exactitude, sa rapidité et son exhaustivité.