Titre : Identification Génétique d’Automates Structurés
       Application à l’étude de sensibilité des systèmes        complexes.

Lieu : LESIA, Groupe Sûreté de Fonctionnement des Systèmes.

Cadres : C. Baron, J-C. Geffroy

Les algorithmes génétiques constituent une technique de résolution performante pour de nombreux problèmes d’optimisation. Leur avantage réside essentiellement dans leur pouvoir de parcours d’un espace de recherche qui peut être très grand, tout en limitant l’explosion combinatoire de cette recherche. Leur efficacité se manifeste donc par des temps de calcul très faibles par rapports à d’autres techniques plus classiques (parcours d’arbre de décision, résolution d’un ensemble de contraintes,...). Ils visent en fait plutôt à la mise en place d’une stratégie pour guider et favoriser l’orientation du système (par l’introduction d’un facteur hasard) vers la ou les meilleures solutions. On distingue 3 étapes essentielles dans leur application : une initialisation de la population, puis sa reproduction (privilégiant les "meilleurs candidats"), ainsi que des opérations de croisement et mutation permettant l’évolution dispersive de la population sur une faible partie de ses membres.

Les algorithmes génétiques sont utilisés dans des domaines très variés : au CNES pour l’optimisation de la configuration d’une constellation de satellite (une première étude a été effectuée au LESIA en collaboration avec cet organisme), ainsi que pour le contrôle du trafic aérien, la reconnaissance de formes par apprentissage, ou encore comme outil de prévision des tendances boursières !

Le groupe Sûreté de Fonctionnement des Systèmes du LESIA s’intéresse à l’identification d’automates dans un contexte d’analyse des systèmes matériels et logiciels. Une étude a déjà été réalisée dans le cadre d’une thèse de doctorat démontrant l’efficacité de l’approche génétique pour la résolution du problème de l’identification d’automates. Pour identifier un système, il s’agit en effet, a partir d’une description comportementale d’un système (sous forme d’une série de réactions observées à partir de séquence d’entrées que l’on applique au système), d’en déduire un modèle fonctionnel sous forme d’automate. On peut vouloir rechercher tous les modèles possibles qui correspondent a la description fournie, ou n’en chercher qu’un seul. Une approche classique explose rapidement du point de vue temps de calcul. Les techniques génétiques se sont révélées très performantes de ce point de vue là. Elles permettent de plus d’obtenir uns solution approchée dans le cas ou aucune solution ne concorde véritablement avec la description du système.

Cette étude donne lieu à des applications dans différents domaines, comme le travail de reconception rapide, la prévision et la maîtrise du comportement des systèmes, etc.

Au sein du LESIA, deux thèses de doctorat ont été soutenues dans le domaine de l’identification d’automates (K. El Maadani en 1993 et C. Baron en 1995) ainsi qu’une thèse sur le thème de l’identification génétique (L. Ngom).

Le travail de recherche proposé s’inscrit dans la continuité des études précédentes. Il s’agira de participer au travail théorique du groupe sur l’identification des systèmes structurés par algorithme génétique et de mettre au point un outil informatique d’évaluation.

Etude théorique. Le groupe étudie depuis plusieurs années l’identification fonctionnelle des automates sous plusieurs formes (simple ou différentielle, mono-module ou multi-modules). Le travail proposé concernera essentiellement l’analyse de systèmes constitués d’automates interconnectés. Il s’agira de définir quelques contextes d’identification dynamique (par exemple l’apprentissage) et de proposer une méthode de simulation génétique.

Outil d’évaluation. Un premier outil informatique écrit en langage C a été développé pour le réglage et la validation de l’identification génétique mono-module. Un outil similaire devra être mis au point pour la méthode d’analyse des systèmes structurés.

César ZAMILPA