Sujet de Doctorat

 

Title : Genetic Identification of Structured Automats
       Application to the study of sensitivity of the complex systems.

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

Cadres : C. Baron, J-C. Geffroy

Les genetic algorithms constitute a technique of powerful resolution for many problems of optimization. Their advantage lies primarily in their capacity of course of a space of search which can be very large, while limiting the combinative explosion of this search. Their effectiveness thus appears by very weak calculating times by reports/ratios with other more traditional techniques (course of decision tree, resolution of a whole of constraints…). They aim in fact rather to the installation of a strategy to guide and support the orientation of the system (by the introduction of a factor chance) towards the best solutions. One distinguishes 3 essential stages in their application: an initialization of the population, then its reproduction (privileging the "best candidates"), as well as operations of crossing and transfer allowing the dispersive evolution of the population on a weak part of its members.

Les genetic algorithms are used in very varied fields: in the CNES for the optimization of the configuration of a constellation of satellite (a first study was carried out with the LESIA in collaboration with this organization), like for the control of the air traffic, the pattern recognition per training, or as tool of forecast of the stock exchange tendencies!

Le group of SFS the Systems of the LESIA is interested in the identification of automats in a context of analysis of the hardware and software systems. A study was already carried out within the framework of a thesis of doctorate showing the effectiveness of the genetic approach for the resolution of the problem of the identification of automats. To identify system, it acts indeed, from description behavioral of system (in the form of a series of reactions observed starting from sequence of inputs that one applies to the system), to deduce a functional model in the form of automat from it. One can want to seek all the possible models which correspond has provided description, or to seek one of them. A traditional approach explodes quickly from the time point of view calculating. The genetic techniques appeared very powerful from this point of view there. They make it possible of more than obtain ones solution approached in the case or no solution agrees truly with the description of the system.

This study gives place to applications in various fields, like the work of fast reconception, the forecast and the control of the behavior of the systems, etc.

Within the LESIA, two theses of doctorate were constant in the field of the identification of automats (K El Maadani in 1993 and C Baron in 1995) as well as a thesis on the topic of the genetic identification (L Ngom).

The research task suggested falls under the continuity of the preceding studies. It will be a question of taking part in the theoretical work of the group on the identification of the systems structured by genetic algorithm and of developing a data-processing tool of evaluation. 

The group has studied for several years the functional identification of the automats in several forms (simple or differential, mono-module or multi-modules). Work suggested will relate to primarily the analysis of systems made up of inter-connected automats. It will be a question of defining some contexts of dynamic identification (for example the training) and of proposing a method of simulation génétique. 

A first data-processing tool written in language C was developed for the adjustment and the validation of the genetic identification mono-module. A similar tool will have developed for the method of analysis of the structured systems.

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