Optimisation et parallélisme

Choix des modèles

De nombreux problèmes de trafic aérien font appel à une méthode d'optimisation dans leur traitement. Certains sont même directement modélisables comme des problèmes d'optimisation sous contraintes (voir l'onglet Optimisation du menu "La recherche/Mathématiques" pour la formalisation de ces problèmes). Typiquement, pour un ensemble d'avions en conflit, on cherchera l'ensemble des manoeuvres permettant de séparer les trajectoires prévues en minimisant les déviations par rapport aux trajectoires initiales.

Certains de ces problèmes sont de grande taille, parfois combinatoires ou NP-difficiles, et les informations traitées sont généralement incertaines ou incomplètes (facteurs météorologiques, interventions humaines).

Pour pouvoir traiter ces problèmes difficiles, nous cherchons à améliorer des méthodes existantes d'optimisation, par exemple en les combinant par un mécanisme de parallélisme coopératif. Cette recherche est menée en étroite collaboration avec l'équipe "Algorithmes Parallèles et Optimisation" (APO) de l'Institut de recherche en informatique de Toulouse (IRIT).


Algorithme génétique (à gauche) et branch & bound par intervalles (à droite) minimisant la fonction de Griewank

La démarche pour aborder les problèmes de gestion du trafic aérien passe en premier lieu par une étape de modélisation. La réalité physique des phénomènes observés étant beaucoup trop riche pour pouvoir être traitée dans son ensemble, il s'agit d'en extraire un modèle, mathématique ou informatique, plus ou moins détaillé selon le degré de réalisme souhaité.

Les choix de modélisation conditionnent généralement le choix de la méthode d'optimisation. Par exemple, le choix entre variables discretes ou continues est essentiel, tout comme celui de la modélisation des incertitudes sur les variables (densité de probabilité, intervalles de confiance, intervalles de tolérance).

Certains problèmes de trafic aérien peuvent être abordés par une modélisation et des méthodes mathématiques (voir l'onglet Mathématiques dans le menu "La recherche"). Pour les problèmes d'optimisation, cela nécéssite généralement que la fonction-objectif et les contraintes soient représentées sous une forme analytique.

D'autres problèmes sont parfois plus directement accessibles en utilisant des modèles informatiques classiques (graphes, arbres, CSP, etc). Par exemple :

Pour des applications concrètes, le modèle doit être suffisamment proche de la réalité. Lorsque l'approche analytique n'est pas praticable, il faut faire appel à des modèles calculatoires, parfois complexes. C'est par exemple le cas lorsque les expressions analytiques des contraintes et/ou de la fonction à minimiser ne sont pas directement accessibles. Elles doivent alors être évaluées par une simulation informatique. En voici quelques exemples :

Les méthodes

Parmi les méthodes d'optimisation employées au MAIAA pour résoudre les problèmes de gestion de trafic aérien, citons :

Quand c'est possible, nous appliquons directement une méthode existante. Par exemple, les séquences de décollage sont optimisées avec un algorithme de branch and bound, le cheminement optimal sur le réseau de taxiways est calculé par un algorithme de recherche arborescente (A*, par exemple). Pour des instances suffisamment modestes, le problème de partitionnement optimal de l'espace peut également être traité par une méthode de recherche arborescente.

Les méthodes citées dans les applications ci-dessus parcourent exhaustivement l'espace des solutions candidates. Dans d'autres cas, on utilise des approches introduisant une marche aléatoire dans l'espace de recherche, avec une heuristique pour orienter ce cheminement aléatoire vers les meilleures solutions. Ce type de méthode s'est révélé particulièrement efficace pour l'optimisation du réseau de routes aériennes, la résolution des conflits aériens ou des conflits au roulage des avions, par exemple.

Ces méthodes ("méta-heuristiques") sont essentiellement des algorithmes stochastiques itératifs, opérant sur des variables continues ou discrètes, et qui font progresser un individu ou une population d'individus vers un optimum global de la fonction-objectif que l'on cherche à minimiser ou maximiser, sans toutefois prouver l'optimalité des solutions trouvées.

La recherche sur les méthodes d'optimisation

Dans leur forme canonique, les méthodes d'optimisation évoquées ci-dessus fonctionnent souvent assez mal sur des instances réalistes des problèmes traités. Une grande part de notre expertise consiste à trouver une modélisation adaptée et des opérateurs spécifiques au problème traité, voire à hybrider différentes méthodes pour atteindre un résultat satisfaisant.

A titre d'exemple, la définition d'un opérateur de croisement adapté aux fonctions partiellement séparables, pour les algorithme évolutionnaires, a permis d'améliorer grandement les solutions trouvées pour la résolution de conflits aérienset des conflits au roulage. Cependant, comme pour toute méta-heuristique, l'optimalité des solutions trouvées n'est pas garantie pour un nombre fini d'itérations.

Un axe plus récent de nos recherches consiste à combiner des méthodes exhaustives comme le branch and bound par intervalles et des méta-heuristiques, par un parallélisme coopératif. La méta-heuristique (algorithme évolutionnaire, ou évolution différentielle, par exemple) permet de trouver rapidement de bonnes solutions, en cherchant dans le domaine admissible mis à jour par la méthode d'intervalles. Ces solutions sont éventuellement utilisées par la méthode d'intervalles comme borne de coupure, pour éliminer les parties du domaine dont l'image par une fonction d'inclusion est moins bonne que la meilleure solution trouvée.

Dans ce cadre, nous cherchons également à améliorer la méthode d'intervalles en propageant des contraintes du problème (ou les conditions nécessaires d'optimalité), lors de la recherche arborescente effectuée par le branch and bound par intervalles. Cette hybridation fait appel à des techniques de programmation par contraintes.

L'objectif est de trouver le ou les optima globaux de fonctions multi-modales difficiles à optimiser, et surtout d'en prouver l'optimalité globale. D'un point de vue pratique, ces méthodes innovantes pourraient garantir l'optimalité des solutions pour des problèmes tels que la régulation en vitesse des avions.

Voir aussi la page optimisation de la recherche en Mathématiques, pour les autres recherches en cours au MAIAA sur les méthodes d'optimisation.