Simulation de flux, Darwin, production, hasard et génétique

 

Imaginons un cas simple, vous voulez que votre ordinateur puisse écrire tout seul la phrase suivante : « Optiflux, spécialiste en optimisation de flux de production et en performance industrielle ». La solution la plus simple serai de copier/coller directement la phrase mais l’article s’arrêterait ici et il nous faut un exemple facile. Du coup, vous allez devoir écrire un programme.

Quelles sont les solutions de programmation possibles pour mener à bien votre mission ?

 

La Force Brute

 

Un algorithme par force brute est un algorithme qui va tester toutes les solutions existantes jusqu’à trouver la bonne solution.

Concrètement, le programme va tester toutes les combinaisons de caractères ASCII en partant de la phrase ne contenant que des « a » jusqu’à la solution du problème en changeant méthodiquement chaque caractère.

Pour donner un exemple trivial, c’est la solution pour laquelle vous optez lorsque vous avez oublié le code de votre cadenas à 3 chiffres. Vous testez tous les nombres de 000 jusqu’à la solution (en espérant que 999 n’est pas la solution).

 

Si cette méthode fonctionne relativement bien avec votre cadenas et les 1000 combinaisons possibles à tester, dans le cas de notre phrase le résultat est moins probant. En effet, si on considère qu’il y a 128 caractères en ASCII, il faudra donc tester 128⁹⁰ solutions, car il y a 90 caractères dans la phrase recherchée.

 

Certes les ordinateurs sont très rapides mais même à raison 1ms par test, il faudra toujours 1.56×10³⁸s soit environ 1.8×10³³années (sachant que l’univers existe depuis 1.5 x10¹⁰années).

 

Une solution pourrait être d’utiliser un dictionnaire de mot afin de limiter le nombre de combinaisons en utilisant uniquement les mots présents dans le dictionnaire ainsi que les caractères spéciaux (c’est-à dire: / !%£…) mais Optiflux n’étant pas un mot du dictionnaire, il serait dès lors impossible d’obtenir notre phrase.

 

Bref, cette solution n’est pas la plus adaptée à notre problème.

 

Le Paradoxe du singe savant

 

Le paradoxe des singes savants est un théorème selon lequel un singe qui tape suffisamment longtemps sur un clavier au hasard finira par écrire l’intégralité de l’œuvre de Shakespeare (ou de Victor Hugo si l’on choisit un auteur français).

Le principe c’est qu’avec une infinité de temps on finira toujours par trouver une solution avec le hasard.

Pour donner un autre exemple, le chiffre Pi ayant une infinité de décimales, il contient tous les nombres de l’humanité, votre date de naissance, votre numéro sécurité sociale ou votre compte en banque. En cherchant dans les décimales, on peut donc trouver tout ce que l’on veut.

Dans cette configuration, le programme teste aléatoirement toutes les combinaisons possibles de caractères jusqu’à trouver la phrase voulue. La durée pour obtenir la solution peut être très courte si on a de la chance ou encore plus longue que la solution en force brute si on n’a pas de chance.

 

L’algorithme génétique

 

Est-ce que l’on est condamné à soit attendre très longtemps soit compter sur la chance pour résoudre notre petit problème ? Non, c’est là qu’entrent en jeu les algorithmes génétiques.

Les algorithmes génétiques se basent sur le principe du Darwinisme qui – en (très) simplifié nous dit:

«Toute espèce subit des variations aléatoires d’une génération à une autre. Si cette variation procure un avantage concurrentiel, elle a plus de chance d’être reconduite aux générations suivantes. A l’inverse, si la variation est gênante, elle a peu de chance d’être reconduite. »

 

Et dans le cadre de notre problème, ça donne quoi ?!

 

L’algorithme génétique c’est un peu le croisement de la force brute et du hasard. Dans notre programme nous procéderons ainsi :

• Une première génération avec des caractères aléatoires, on va ainsi créer 100 résultats.
• Ensuite on classe ces résultats par % de bonne lettre au bon endroit.
• On garde les 20% les mieux notés, et 5% des autres solutions (le but étant d’éviter un « optimum local »)
• On effectue un croisement en prenant des segments de phrases deux à deux afin de créer une nouvelle phrase. On crée ainsi 25 nouveaux résultats.
• On induit une mutation dans les 25% conservés jusqu’à avoir à nouveau 100 résultats.
• On recommence la boucle, classer, conserver, croiser, muter pendant 10 000 générations.

 

Et ça marche ?!

 

Oui, cela fonctionne très bien ! De générations en générations, notre « top 20% » est de plus en plus proche de la solution. En général, la solution est trouvée autour de 6000 générations, pas mal comparé aux 128⁹⁰ essais de la force brute !

 

L’application dans l’industrie et la simulation de flux

 

En quoi l’algorithmie génétique peut vous aider à produire plus en un temps imparti ? En intégrant cette méthode de codage au sein d’un modèle de simulation de flux.

 

Un modèle de simulation est une copie numérique de votre installation (existante ou futur). L’utilisation « basique » d’un modèle de simulation est de tester des hypothèses et comparer les résultats, de répondre à la question : « what if… ?»

 

En intégrant un algorithme génétique à un modèle de simulation de flux, l’outil d’aide à la décision devient un outil décisionnel vous donnant la meilleure configuration pour votre site de production, la configuration qui dans l’horizon choisit produit le plus par exemple.

Attention toutefois, ce n’est pas une solution miracle, il convient de définir en amont du modèle le nombre de variables pouvant être modifiées ainsi que les plages possibles. Plus ces nombres sont élevés plus la puissance de calcul nécessaire devrait être importante. Pour pallier ce problème, un fonctionnement en « cluster » utilisant plusieurs machines peut être nécessaire.