L’excellence opérationnelle est devenue le mot d’ordre aujourd’hui pour toute entreprise industrielle.

Chaque industriel doit faire face à une multitude de décisions qui, combinées entre elles, seront des leviers de performance. La combinaison de toutes ces décisions est très volumineuse et complexe à gérer. L’impact de ces décisions sur les performances de l’entreprise sont souvent contradictoires, et la prise de risque élevée pour le décideur. Le décideur fait régulièrement appel à son expertise et à son expérience pour évaluer les solutions qui pourraient lui sembler pertinentes. Finalement, il statue selon un nombre restreint de choix, faute de pouvoir évaluer l’ensemble des possibles.

Dans ces conditions, les algorithmes génétiques appliqués aux outils d’aide à la décision pour l’optimisation de la conception de systèmes, l’industrialisation ou l’ordonnancement peuvent être d’une grande utilité au niveau industriel.



À quoi servent les algorithmes génétiques, et dans quelle mesure les utiliser ?

Les techniques d’aide à la décision issues de la recherche opérationnelle (RO) peuvent accompagner les industriels dans l’analyse des situations complexes et leur permettent de faire des choix plus efficaces et robustes. L’ Association française de recherche opérationnelle et d’aide à la décision définit celle-ci comme une discipline à l’intersection des mathématiques, de l’économie et de l’informatique. La RO propose des outils et méthodes scientifiques permettant de rationaliser, simuler et optimiser tout système. 

Dans le cas d’un problème d’optimisation combinatoire, le nombre de solutions possibles est lié à la dimension du problème à traiter. Même avec la puissance calculatoire des ordinateurs actuels, les problèmes industriels sont encore pour beaucoup trop complexes pour obtenir, dans un temps acceptable par rapport à la temporalité de la décision, la solution optimale. Ainsi nous devons donc utiliser des méthodes approchées, qui vont nous permettre d’obtenir, dans le temps imparti, une « bonne » solution. Parmi ces méthodes approchées, nous distinguons les heuristiques des méta-heuristiques (voir figure ci-dessous).

Une heuristique est une méthode qui traduit une stratégie d’optimisation en s’appuyant sur la connaissance du problème. Elle va permettre de se déplacer intelligemment dans l’espace des solutions de manière à proposer, à la fin du délai imparti, une solution de bonne qualité. Elle est donc spécifique à un problème donné. 

A contrario, les méta-heuristiques sont des méthodes générales, qui peuvent être adaptées à divers problèmes d’optimisation. Deux grandes catégories existent : 

• Les méthodes à solution unique, dites de recherche locale, qui partent d’une solution initiale et qui, en se déplaçant dans un environnement proche à chaque itération, tentent d’améliorer progressivement la performance.
• Les méthodes à population, qui travaillent à chaque itération sur un ensemble de solutions réalisables, le faisant évoluer par des mécanismes souvent inspirés de la nature.

La méta-heuristique à population la plus connue est l’algorithme génétique. Inventés par John Holland dans les années 1970, les algorithmes génétiques découlent du concept de la sélection naturelle mis en évidence par Charles Darwin. 

Le principe de la sélection naturelle est le suivant : dans un environnement où les ressources sont limitées, il existe une compétition entre les individus d’une même population pour leur survie. La survie d’un individu va dépendre de sa capacité d’adaptation à son environnement. Les individus les plus aptes ont plus de chances de survivre et, par conséquent, de se reproduire. L’adaptation aux problèmes d’optimisation a été ensuite appliquée par David Goldberg sur un problème industriel : 

• les individus sont des solutions potentielles au problème donné ;
• l’adaptation de l’individu à son environnement représente la performance à optimiser ; 
• un mécanisme d’évolution est développé à partir d’opérateurs permettant d’éliminer certains individus et de produire de nouveaux individus depuis les individus sélectionnés dans la population courante.

Les applications industrielles sont nombreuses. Nous avons par exemple utilisé ce type d’algorithmes sur des problématiques d’optimisation de gammes de fabrication, d’industrialisation, d’ordonnancement et plus généralement de séquencement de tâches, de répartition de ressources…

Comment fonctionnent les algorithmes génétiques ?

Pour mieux comprendre les algorithmes génétiques, voici quelques explications sur leur fonctionnement :



La population initiale

La population représente l’ensemble d’individus qui constituent 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, à partir desquels on va réaliser un croisement.

Le croisement

Parmi les individus sélectionnés pour le croisement, on va créer des couples dont les individus vont échanger un certain nombre de gènes, 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 servent à éviter que l’algorithme génétique ne converge trop prématurément vers une solution, et que la population n’atteigne des solutions dans un optimum local plutôt que dans un optimum global.

L’ensemble des individus présents avant les étapes de croisement et de mutation et des individus enfants forme une population intermédiaire, sur laquelle vont être sélectionnés 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 à les trier par score décroissant afin de ne conserver que les N « meilleurs » 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. 

Solution retenue à la dernière génération

Après un certain nombre d’itérations (défini au la ncement de l’algorithme), on réalise une dernière étape de sélection sur la dernière génération. Cette sélection peut être une fonction d’évaluation spécifique, ou simplement le choix du meilleur individu selon la fonction d’évaluation des performances.

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 moindres qu’en passant par un solveur simplexe qui assure l’optimalité de la solution.

Cas d’usage dans l’aéronautique : Développement d’un algorithme génétique permettant d’améliorer le temps de traitement des données autour de l’usinage et de l’optimisation des conditions de coupes

Cette approche, appliquée aux problématiques de fabrication industrielle, de fabrication additive ou de fabrication durable, intègre l’ensemble du processus, de la conception jusqu’à la fabrication des pièces. C’est le cas en particulier pour l’aéronautique.

Les clients industriels sont souvent confrontés à un dilemme entre assurer la sécurité des processus et optimiser la performance en prenant un risque calculé. La stratégie proposée consiste à modéliser les indicateurs clés de décision avant d’évaluer un grand nombre de solutions, pour en extraire les meilleures.

Nous avons appliqué cette démarche dans le cas de l’optimisation de processus d’usinage de pièces aéronautiques, de l’optimisation du couple conception/fabrication pour des pièces de structure et pour la comparaison et le choix de procédés dans le cadre d’une fabrication durable.

Agaetis a réalisé l’industrialisation de la solution numérique d’un algorithme génétique pour le rendre accessible au monde industriel. Cette approche nous permet d’élaborer des preuves de concept plus rapidement. 

Nous pouvons ainsi évaluer un grand nombre de solutions, que nous hiérarchisons avec une méthode de prise de décision multicritères : 

• Dans un premier temps, nous modélisons le processus, c’est-à-dire que nous identifions les paramètres fondamentaux et les indicateurs de performance à évaluer. 
• Dans un second temps, nous procédons à une hiérarchisation des critères grâce à des entretiens auprès des métiers. Ces entretiens permettent d’identifier les divergences de point de vue et participent à la construction d’un savoir-faire commun. Ils sont particulièrement instructifs, car il existe peu de structures humaines de décisions dans lesquelles tous les intervenants ont un avis identique.

 Par la suite, nous adaptons le code générique développé par Agaetis pour valider la démarche d’optimisation retenue sur des cas industriels. La méthode est très souple et laisse la décision entre les mains de l’utilisateur final. C’est un accompagnement éclairé.



Cas d’usage dans le secteur de l’industrie navale : Optimisation de la conception d’un système pneumatique

Dans ce cas de figure, il s’agit, grâce aux algorithmes génétiques, d’optimiser le choix de certaines quantités d’un système pneumatique :

• le nombre de composants  ;
• la longueur du circuit  ;
• la masse  ;
• …

Les performances du système dépendent, au premier ordre, de la longueur du circuit, ce qui correspond au  problème du voyageur de commerce  :

“En informatique, le problème du voyageur de commerce, ou problème du commis voyageur, est un problème d'optimisation qui consiste à déterminer, étant donné une liste de villes et les distances entre toutes les paires de villes, le plus court circuit qui passe par chaque ville une et une seule fois. “ S ource

Les algorithmes génétiques sont particulièrement adaptés à ce problème. Ici, il faut également prendre en compte les autres paramètres du système, comme la masse et le coût (surtout s’il s’agit de considérer un graphique orienté), le réseau devant respecter certaines règles de constructions imposées par le client. Le but est de  permettre la génération initiale d’individus viables. 

Dans un second temps, la population d’individus subit les règles de  croisement et de mutation décrites plus haut, selon une fitness composée par le client à partir des paramètres masse, coût, performance, etc. Le résultat est une configuration optimale de disposition et de câblage du système.

En conclusion...

Les algorithmes génétiques sont adaptés pour les sociétés qui souhaitent mieux comprendre le processus décisionnel qui mène à faire des choix de processus de fabrication, ou qui sont confrontées à des compromis cornéliens. Cette approche est facilement adaptable, car elle s’inscrit dans une démarche de co-développement avec l’utilisateur final.

Ces sociétés ont souvent déjà réalisé des optimisations locales ou des innovations incrémentales, et elles se rendent compte qu’elles doivent embrasser l’ensemble du processus pour avancer. Il nous est arrivé de collaborer avec un bureau d’étude et deux bureaux des méthodes de trois sociétés différentes pour conduire une optimisation commune.

Pour compléter votre lecture rendez-vous ici, sur notre précédent article : Data Science, développement et algorithme génétique .