Data Science, développement et algorithme génétique

Data Science, développement et algorithme génétique
03 / 11 / 2021Temps de lecture 4 min.
FacebookLinkedInTwitter

Suite à une mission avec une équipe de chercheurs de Sigma Clermont, destiné à aider à la prise de décision dans le domaine de l’usinage de portes d’avions, les membres de l’équipe Agaetis mobilisée sur ce projet ont accepté de répondre à quelques questions afin de mieux comprendre ce projet du point de vue interne.

Ils nous expliquent plus en détail ce qu’est un algorithme génétique, ses intérêts dans le domaine de l’optimisation des usinages et les objectifs fixés pour ce projet !  

Le challenge de cette mission était de partir des éléments de thèse, fournissant, notamment, le code de calcul pour les transformer en une application fonctionnelle. Notre objectif n’était pas de réinventer la roue, mais de retranscrire la vision du client, fruit d’un temps long de recherche et de développement, en un outil de calcul performant, robuste, documenté et compréhensible.

Les algorithmes génétiques

Pour commencer, pouvez-vous nous dire ce qu’est un algorithme génétique ? 

Bertrand Pelletier et Sylvain Fouilloux

Un algorithme génétique est un algorithme inspiré de la théorie de l’évolution de Darwin, qui peut être utilisé pour obtenir une solution approchée d’un problème d’optimisation sous contraintes.

Un des avantages de l’algorithme génétique, par rapport aux historiques méthodes du simplexe et du simplexe révisé, est le temps de calcul inférieur pour avoir une solution approchée de la solution optimale. Une des limites de cet algorithme est que s’agissant d’une heuristique, nous ne sommes pas certain de l’optimalité de la solution proposée.

Pouvez-vous nous expliquer comment ces algorithmes fonctionnent et comment ils peuvent aider le monde industriel ?

Bertrand Pelletier et Sylvain Fouilloux

Le principe général d’un algorithme génétique est de générer un certain nombre de fois, un certain nombre d’individus représentant chacun une solution du problème d’optimisation que l’on souhaite résoudre. Ils seront sélectionnés selon différents critères pour déterminer les individus les plus performants, qui transmettront ainsi leurs « gènes » à la génération suivante. 

Au bout d’un certain nombre de générations, on sélectionne l’individu le plus adapté de la dernière génération, ce qui donne la solution approchée au problème d’optimisation.

Pour cela on effectue plusieurs étapes itératives :

Génération d’une population N → Croisement → Mutation → Population Intermédiaire → Sélection → Population N+1 → …

Explications : 

Pour générer la population initiale :

La population représente l’ensemble d’individus, c’est l’ensemble de « gènes » qui constitue une solution au problème d’optimisation.

Le gène est la valeur prise par une variable du problème pour un individu donné.

Au départ, on génère aléatoirement les individus de la première génération de manière à respecter les contraintes du problème d’optimisation.  On sélectionne ensuite un certain nombre d’individus sur lesquels on va réaliser un croisement.

Le croisement :

Parmi les individus sélectionnés pour le croisement, on va créer des couples d’individus et l’on va échanger un certain nombre de gènes entre chaque individu de chaque couple pour donner 2 individus « enfants » par couple. Donc avec N individus « parents » on obtient N individus « enfants », sur lesquels on va appliquer l’étape de mutation.

La mutation :

Les individus enfants vont passer par une étape de mutation qui consiste à appliquer une légère modification à un ou plusieurs gènes des individus enfants.

Les mutations sont là pour éviter que l’algorithme génétique ne converge trop prématurément vers une solution, et éviter que la population n’atteigne des solutions dans un optimum local plutôt que dans un optimum global.

L’addition des individus présents avant les étapes de croisement et de mutation avec la population d’enfants forme une population intermédiaire sur laquelle il va être réalisé une étape de sélection pour garder les individus les plus performants, c’est-à-dire ceux qui optimisent le mieux le problème.

La sélection :

L’étape de la sélection consiste à appliquer à chaque individu une fonction d’évaluation des performances, leur donnant ainsi un score, et ensuite à trier ces individus par score décroissant pour sélectionner les N premiers individus (N étant la taille de la population initiale).  

Nous gardons ainsi les individus les plus performants, ce qui générations après générations va permettre d’améliorer la performance globale de la population, et ainsi de se rapprocher d’un optimum global. 

La sélection de la solution retenue à la dernière génération :

Après un certain nombre d’itérations défini au lancement de l’algorithme, on réalise une dernière étape de sélection qui consiste soit à prendre le meilleur individu selon la fonction d’évaluation des performances, soit à appliquer une fonction d’évaluation spécifique à la dernière génération.

Bien que l’on n’ait aucune certitude sur l’optimalité de la solution obtenue, en général les temps de calcul pour obtenir une solution en passant par un algorithme génétique sont bien moindre qu’en passant par un solveur simplexe qui assure l’optimalité de la solution.

Projet en partenariat avec SIGMA Clermont

Quels étaient le contexte et les objectifs de ce projet en partenariat avec Sigma ?

Arnaud Ribeyrotte et Alexandre Fiale

SIGMA Clermont souhaitait développer un algorithme générique d’optimisation et de prise de décision basé sur un algorithme de type NSGA II (Non-dominated Sort Genetic Algorithm II) pour le secteur aéronautique. Le développement informatique devait être robuste, paramétrable et efficace.

Les personnes concernées par l’algorithme sont des doctorants, des enseignants-chercheurs, des techniciens et des ingénieurs de l’industrie. Ce logiciel devait donc être paramétrable, avec la possibilité de modifier les variables de décision, les contraintes, les indicateurs de performance ainsi que le nombre et les taux de mutations et de croisements.

Quel a été le rôle de chacun dans ce projet ? 

Bertrand et Sylvain ont d’abord lu et analysé la thèse rédigée par le doctorant de Sigma, puis ont interprété le code MATLAB pour le retranscrire, le corriger et le développer en Python. Le but étant d’industrialiser cet outil issu d’une thèse, il a fallu s’adapter et être flexible. 

Ils ont ensuite fait le lien avec le front/back end géré par une autre équipe, Arnaud et Alexandre, qui se sont occupés de l’architecture globale et de l’intégration de l’algorithme au sein de la solution.

À retenir

Que retenez-vous de ce projet ?

Ces deux domaines ne sont pas forcément habituels pour nous, les apports sont donc multiples.

Travailler dans de nouveaux secteurs comme l’aéronautique et échanger des compétences et des connaissances est toujours très enrichissant pour nous. Cela permet d’élargir notre portfolio et de monter rapidement en compétences sur des métiers très différents — c’est d’ailleurs ce qui fait notre force. 

De plus, les algorithmes génétiques étant utilisés dans beaucoup d’applications, cela a été pour nous l’occasion de tester notre expertise et de nous challenger, chose que l’on apprécie tout particulièrement chez Agaetis. C’était également valorisant de pouvoir appliquer et travailler sur des algorithmes génétiques visant une utilisation concrète.

Cette expérience nous a aussi permis de travailler sur la rigueur des livrables, en reprenant les éléments orientés R&D fournis et en les transformant en une application fonctionnelle. Les équipes de Sigma étaient à l’écoute, disponibles pour les différentes itérations, et nous ont également aidé à fournir une solution sur-mesure ! 

C’était intéressant de pouvoir mélanger les mondes du développement, de la data science et de la recherche, ce n’est pas si courant. Cette mission nous a aussi confirmé que ces différents secteurs métiers peuvent travailler ensemble, et s’il faut retenir quelque chose de ce projet c’est bien ça !

Si vous n’avez pas lu le premier article concernant ce projet : Comment améliorer les temps d’usinage et l’optimisation des conditions de coupes, n’hésitez pas à aller le consulter pour mieux comprendre et avoir la vision client de cette mission !

Un sujet vous intéresse ? Une question ? Contactez-nous !

FacebookLinkedInTwitter
Logo Agaetis
Nos adresses
Clermont-Ferrand
9, allée Evariste Galois
63170 Aubière
Tél. 04 73 35 47 51
Paris
21, rue de la banque
75002 Paris
Tél. 01 44 63 53 13
Lyon
52, Quai Rambaud
69002 Lyon
© 2021 Agaetis - Tous droits réservés

Ce site utilise des cookies à des fins de mesures d'audience, ainsi que pour améliorer votre expérience de navigation