Le projet Optimisation, Identification, Commande regroupe des activités du Laboratoire I3S qui n'ont pas de domaine d'application privilégié et pour lesquelles l'optimisation joue un rôle essentiel. Les principaux résultats concernent les points suivants.

1. Etude de techniques d'optimisation : analyse de convergence d'algorithmes par une approche «Systèmes Dynamiques», approches évolutionnistes (Algorithmes Génétiques).
2. Identification : statistique non linéaire, estimation à erreurs bornées, planification d'expériences optimales.
3. Commande robuste : commande robuste non-linéaire, algèbres "tropicales" (ou max +) , concept de "frayeur mathématique", jeux différentiels, commande prédictive robuste.

 

 
 
 

Ces travaux ont fait l'objet d’une cinquantaine de publications internationales, de collaborations avec une douzaine d’universités ou instituts étrangers, et de quatre programmes de recherche industriels, dont un européen (BRITE-EURAM).

Equipe du projet OIC :

Responsable Scientifique : Philippe COLLARD, MC, Tel. 33 (0)4 92 94 27 75, e-mail : pc@i3s.unice.fr

Membres permanents
Bernhard, Pierre, Professeur
Collard, Philippe, Maître de Conférences
Escazut, Catherine, Maître de Conférences
Favier, Gérard, Directeur de Recherche
Folcher, Jean Pierre, Maître de Conférences
Pronzato, Luc, Directeur de Recherche
Theys-Ferrari, Céline, Maître de Conférences
Thierry, Eric, Maître de Conférences

Membres non-permanents
Gaspar, Alessio, Allocataire MENRT
Gautier, Roland, ATER

Présentation générale et objectifs scientifiques :
 

1. Etude de techniques d'optimisation

A.  Analyse de convergence d'algorithmes d'optimisation
Permanent : L. Pronzato
Dans le cadre d'une collaboration avec les Professeurs  H.P. Wynn de l'Université de Warwick (programme d'action intégrée Alliance 94-95) et A.A Zhigljavsky de l'Université de Cardiff (invitation triennale 94-96, dans le cadre d'une procédure PAST), nous nous intéressons à l'analyse de la convergence d'algorithmes d'optimisation à partir de l'étude des propriétés des systèmes dynamiques que nous leur associons. Une renormalisation de la région de recherche à chaque itération de l'algorithme permet de considérer celle-ci comme fixe, tandis que l'objet recherché (par exemple le point où la fonction atteint son minimum) se déplace dans cette région renormalisée, obéissant ainsi aux équations d'évolution d'un système dynamique. Il apparaît alors que le comportement de ce système est fréquemment chaotique, et que les pires cas de l'analyse minimax (qui empêchent une convergence rapide) correspondent à des conditions initiales appartenant à un ensemble de mesure nulle (pour la mesure invariante du système dynamique). Nous venons de publier un ouvrage sur le sujet (L. Pronzato, H.P. Wynn, A.A. Zhigljavsky: "Dynamical Search. Applications of Dynamical Systems in Search and Optimisation", Chapman & Hall/CRC Press, 2000).



Itérations typiques de deux algorithmes (point milieu et algorithme symétrique) de minimisation unidimensionelle






Le projet OIC a participé au projet Européen CE2 (Computer Experiments in Concurrent Engineering) du programme BRITE-EURAM qui concerne :
(i) la construction d'émulateurs rapides pour des simulateurs numériques à partir de méthodes statistiques et de techniques de planification d'expériences,
(ii) l'optimisation de la réponse des émulateurs par rapport aux variables d'entrées (géométrie d'une pièce mécanique par exemple).
La contribution d'I3S concerne le point (ii). Trois industriels (Centro di Ricerche Fiat, Turin ; Intrasoft, Athènes ; SNECMA, Moissy Cramayel) et trois laboratoires de recherche universitaires (Université de Warwick ; Politecnico di Torino et I3S) ont participé à ce projet, dont l'objectif était le développement d'un logiciel commercialisable (en cours de finalisation), surpassant ses concurrents (peu nombreux !) par la qualité des modèles utilisés (les émulateurs) et l'efficacité des méthodes d'optimisation employées.


Computer experiments for concurrent engineering
Brite/EuRam project BE963046
Partenaires : FIAT, SNECMA, IntraSoft, Warwick University, Politecnico di Torino, CNRS







B.   Approches évolutionnistes pour l'optimisation
Permanents : P. Collard, C. Escazut
 Les algorithmes génétiques (AG) sont des algorithmes généraux utilisés soit pour résoudre des problèmes d’optimisation soit dans des systèmes dotés de capacités d’apprentissage. Les données manipulées par un AG sont codées sous la forme de chaînes de symboles pour former des chromosomes (génotypes). A chaque itération, plusieurs valeurs, qui constituent une population de chromosomes, sont évaluées en parallèle. Les AG s’inspirent des mécanismes naturels de l’évolution et plus précisément de la biologie moléculaire ; ils impliquent la survie des structures les mieux adaptées. La génération de nouvelles structures met en œuvre des mécanismes tels que la sélection, la mutation et le croisement.
 Les AG ont été proposés dès l'origine comme des systèmes adaptatifs ; or on constate une dérive qui consiste à les utiliser et à les concevoir uniquement comme des outils pour l'optimisation. Dans cette optique les AG standards montrent rapidement leurs limites et ont du mal à concurrencer des méthodes plus spécialisées. Bien que notre objectif soit de proposer des outils d'optimisation reposant sur une approche évolutionniste, il est important d'une part de recentrer l'étude des AG sur les aspects adaptatifs et, d'autre part, de viser des problèmes pour lesquels ces algorithmes pourront exploiter leurs capacités à manipuler une population comme les problèmes multimodaux, multicritères ou dynamiques. Nous avons développé deux axes de recherche. D'une part, nous avons réalisé des études théoriques portant sur des problèmes spécifiques aux approches évolutionnistes : étude de fonctions "trompeuses", étude et visualisation des dynamiques, détermination et étude de critères de difficulté a priori … D'autre part, nous avons étudié l'utilisation des AG pour résoudre des problèmes d'optimisation complexes : multicritères ou dynamiques.
 

2. Identification et planification d'expériences optimales

Permanents : L. Pronzato, E. Thierry
Planifier une expérience de manière optimale correspond à déterminer les conditions expérimentales permettant d'effectuer au mieux l'identification d'un système (choix de la structure de modèle, estimation de ses paramètres). Nous travaillons sur ce sujet depuis de nombreuses années, et avons acquis une certaine reconnaissance au niveau international : invitation régulière aux principales conférences, organisation du 5ème colloque "Model-Oriented Data Analysis" (Marseille, juin 1998) qui constitue la principale conférence sur le sujet.
Nous travaillons essentiellement suivant deux axes :
• Statistique non-linéaire (Collaboration avec A. Pazman, Université Comenius de Bratislava). Lorsque la réponse du modèle est non-linéaire en les paramètres à estimer, les critères traditionnellement  utilisés en planification d'expériences reposent sur des propriétés asymptotiques de l'estimateur (matrice d'information de Fisher), qui sont loin d'être vérifiées pour un faible nombre d'observations. Il convient alors d'étudier plus finement les propriétés de l'estimateur, et de proposer des critères non-asymptotiques de précision de l'estimation.
• Planification séquentielle et commande adaptative (Collaboration avec E. Walter, Laboratoire des Signaux et Systèmes, CNRS-SUPELEC). La planification d'expériences possède des liens étroits avec la commande adaptative lorsque les conditions expérimentales sont choisies de manière séquentielle (chaque phase de planification est suivie d'une phase de recueil de données et d'estimation de paramètres). Une vision du type "commande adaptative" permet alors de proposer de nouvelles politiques de planification séquentielle, et, inversement, la planification d'expériences, qui poursuit par nature un objectif d'identification, permet de proposer des lois de commande adaptative prenant en compte leur effet dual (commande duale).
3. Commande Robuste

Permanents : P. Bernhard, G. Favier
La commande robuste consiste à prendre en compte explicitement des incertitudes de modèle au niveau de la synthèse d'un correcteur. Deux types de méthodes de commande robuste sont étudiés dans le projet : d'une part, des méthodes qui s'apparentent au problème d'optimisation "H-infini'' ou à des variantes non-linéaires et d'autre part, des méthodes de type prédictif. Dans le monde "H-infini non lineaire", on s'est notamment intéressé aux apports du parallèle avec le contrôle stochastique permis par l'algèbre  (max, +) et les mesures de coût. Nous avons développé le concept de "frayeur mathématique" comme parallèle à l'espérance mathématique, et nous poursuivons l'utilisation de ces outils. Des méthodes d'identification de domaines d'incertitude paramétrique de types ellipsoïdal et hypercubique ont également été étudiées, en vue de leur application à la commande robuste.
Collaborations :

1 - Académiques
· Université de Warwick (Pr. H.P. Wynn, dept. of Statistics), programme d'action intégrée "Alliance", 1994-95 (L. Pronzato)
· Université de Cardiff (Pr. A.A Zhigljavsky dept. of Math., Professeur associé, procédure PAST, 1994-1996) (L. Pronzato)
· Napier University, Edinburgh (C. Escazut, Post-doc, 1996)
· Ecole Polytechnique Fédérale de Lausanne (O. Michel, Post-doc, 1997)
· Université de Campinas, Brésil (Pr. W. do Amaral; Département d'Automatique et d'Informatique) (G. Favier)
· University of British Columbia, Vancouver, Canada (Pr. G. Dumont; dept. of Electrical Engineering) (G. Favier)
· University of Illinois at Urbana Champaign (Prof T. Basar) (opération co-financée INRIA-NSF)  (P. Bernhard)
· Université Dauphine (J-P. Aubin) (P. Bernhard)
· Politecnico de Turin (projet européen CE2) (L. Pronzato)
· Académie des sciences Russe: IUP Moscou (A. Melikyan) (P. Bernhard)
· ORSTOM (P. Bernhard)
· Université Comenius de Bratislava (Pr. A. Pàzman) (L. Pronzato)
· INRA Montpellier (Biométrie et économie)  (P. Bernhard)
· Imperial College (projet Alliance), (Pr. Alfonsi)
· INRIA Sophia Antipolis (projets COMORE et MIAOU) (P. Bernhard)

2 - Industrielles
· Dans le cadre du projet Computer Experiments in Concurrent Engineering (CE2) du programme européen Brite-Euram : Centro di Ricerche Fiat (It), INTRASOFT (Gr), SNECMA (Fr), 200 kEcus de financement pour le laboratoire I3S (L. Pronzato)
· Dans le cadre du projet Elite : TEXAS INSTRUMENT (E. Thierry)
· Dans le cadre du Programme Recherche Industrie du Ministère des Affaires Etrangères : PETROBRAS (Brésil), SIMULOG (Fr) (G. Favier)

Perspectives :
 

1. Analyse de convergence d'algorithmes d'optimisation

· Analyse de convergence d'algorithmes de point-intérieur en programmation linéaire et programmation convexe.
· Poursuite des travaux concernant les liens entre performances asymptotiques d'un algorithme d'optimisation et caractéristiques du comportement du système dynamique associé (exposants de Lyapunov, entropie de Kolmogorov, de Renyi, etc.).
· Construction d'algorithmes d'optimisation performants en moyenne pour un nombre fini d'itérations.
· Construction d'algorithmes permettant la détermination de l'ellipsoïde de volume maximum contenu dans un polytope à partir d'algorithmes ellipsoïdaux extérieurs classiques (algorithme de Kachiyan par exemple). Applications en estimation à erreurs bornées, planification d'expériences et programmation convexe.


Comportement chaotique d'un algorithme ellipsoïdal




2. Approches évolutionnistes pour l'optimisation

Nous souhaitons poursuivre nos travaux en développant en parallèle les deux axes complémentaires que représentent l'étude théorique des AG en tant que système adaptatif et leur mise en œuvre sur des problèmes complexes.

· Il sera nécessaire d'étendre les résultats théoriques obtenus sur un modèle minimal. En particulier, il serait souhaitable d'obtenir une caractérisation plus fine des comportements limites (analyse des différents scénarios de routes vers le chaos).
· Nous avons entrepris l'étude des facteurs qui ont une influence sur l'AG-difficulté d’une fonction en utilisant une mesure de corrélation sur le paysage d'adaptation. Cette corrélation peut être mesurée (visualisée) sur le graphe de dispersion statique de la distance génotypique par rapport à la fitness. Nous envisageons d'étendre cette étude à l'analyse de la dynamique des populations dans l'espace des phases distance/fitness.
· De façon plus prospective, nous projetons de poursuivre nos travaux sur l'introduction de concepts issus de la chronobiologie dans les algorithmes évolutionnistes.
· Concernant l'optimisation dynamique, nous avons proposé une dynamique évolutionniste qui, sans contrarier la convergence, garantisse la viabilité du système dans un environnement changeant. Ces travaux ont été validés sur des problèmes académiques ; il sera nécessaire de confirmer ces résultats sur des problèmes industriels.
· Bien qu'il existe encore peu de travaux théoriques dans le domaine concernant l'optimisation multicritère, nous pensons que cet axe de recherche va se développer. Ceci tient essentiellement au fait que l'on puisse traiter directement la pareto optimalité sans être obligé d'utiliser des méthodes de vectorisation.
 

3. Identification, planification d'expériences optimales

 L'axe que nous souhaitons privilégier concerne l'utilisation de techniques de planification d'expériences en commande adaptative. La loi de commande optimale en boucle fermée (il s'agit de commander un modèle de paramètres inconnus et estimés en ligne) est solution d'un problème de programmation dynamique stochastique, qui ne peut être résolu (même numériquement) que dans des cas extrêmement simples. Dès le début des années 70 de nombreux chercheurs ont proposé des approches sous-optimales actives, c'est-à-dire prenant en compte le caractère dual de la commande (commande et estimation sont réalisées simultanément). Nos premiers travaux dans cette direction conduisent à des résultats tout-à-fait satisfaisants. Cependant, l'approche demeure lourde sur le plan des calculs et est limitée au cas d'un horizon fini. Une approche plus simple, et plus classique, consiste à perturber la commande par équivalence forcée à la certitude, soit par l'introduction de perturbations aléatoires, soit par une modification du critère de commande faisant apparaître explicitement l'objectif d'estimation de paramètres. C'est ce dernier type d'approche que nous souhaitons étudier plus en détail. Nous avons déjà pu établir des conditions sur une modification du critère de commande permettant de garantir la convergence presque sure i) des paramètres estimés vers leur vrai valeur, ii) du critère de commande vers sa valeur optimale. Cependant, seul le cas d'un système statique a été considéré (chaque régresseur peut être choisi indépendamment des régresseurs précédents). L'extension au cas d'un système dynamique reste à effectuer. Par ailleurs, au delà de la garantie de convergence, il s'agira d'assurer un compromis satisfaisant entre l'exploitation (la commande pour un modèle de paramètres connus) et l'exploration (la perturbation du système pour estimer au mieux ses paramètres), l'idée étant de ne perturber le système que lorsque cela est absolument nécessaire, et de la manière la plus efficace possible.
La suite de l’activité en matière de filtrage non linéaire, actuellement dans le projet ASTRE, va être accueillie dans le projet OIC, dans la partie traitant de planification d’expériences et de commande adaptative. Nous souhaitons en effet, nous intéresser au même type de modèles semi-paramétriques (Krigeage), le choix d’une séquence d’apprentissage en filtrage non-linéaire est un problème de planification d’expériences, et la détermination d’un bon compromis exploration/exploitation est là aussi fondamental.
 
4. Commande robuste

· La collaboration avec l'INRA (travail de thèse de Abdelamlek Maloum) a mené à une première loi de commande du modèle de station d'épuration, fondée sur un "observateur d'ensemble" des états possibles. Les résultats en simulation sont très encourageants. Mais dans sa forme actuelle, cette théorie ne prend pas en compte des incertitudes de mesure, toujours présentes. Nous travaillons donc à l'étendre dans cette direction.
· La notion d'observateur d'ensemble en elle même est intéressante. Nous avons dégagé une méthodologie générale pour construire un tel observateur. Il reste à comprendre ses liens avec la théorie des observateurs non-linéaires, qui est une théorie riche et bien développée, et à en étudier l'efficacité pratique.
· Nous poursuivons aussi des recherches théoriques et appliquées sur les jeux différentiels, en collaboration avec l'INRIA (Collaboration Thomson Airsys et Aero, contacts avec le CEA)
· Une collaboration avec l'INRIA et Coordinated Sciences Laboratory of University of Illinois at Urbana Champaign sur le contrôle de flux dans les réseaux de télécommunication, a été retenue par la NSF et l'INRIA et va démarrer.
· Enfin, nous nous intéressons à certaines questions de mathématiques financières justiciables de méthodes de type commande robuste.