Salut, bienvenue dans cette article consacré à un domaine de l’informatique peu connu et pourtant qui est très passionnant nommé les algorithmes évolutionnaires.

Avant de continuer, je tiens à préciser que cet article est destiné à des gens qui n’ont pas forcément un background solide dans le domaine et aux débutants. l’idée est d’expliquer les choses de la manière la plus simple possible tout en essayant de garder la rigueur scientifique au maximum (ça va être très compliqué mais je vais essayer quand même).

Un petit coup de pub, pour mes travaux (mdr) … la simulation que vous voyez ci-dessus est le résultat de mon tout premier algorithme évolutionnaire que j’ai appliqué sur le célèbre jeu Flappy Bird.

Vous pouvez retrouver le code ici : https://bit.ly/3cgaHrD

Alors, qu’est-ce qu’un algorithme évolutionnaire ?

Un algorithme évolutionnaire est une technique d’optimisation inspirée du fonctionnement de la nature. Cette technique repose sur la théorie de sélection naturelle et d’évolution de Darwin et aussi sur la génétique moderne. En effet, les algorithmes évolutionnaire font parti d’un plus grand domaine du Bio-Informatique appelé “Natural Computing”. D’ailleurs je vous suggère le livre Natural Computing Algorithms de Brabazon Anthony, O’Neill Michael et McGarraghy Sean (voir le lien ci-dessous), qui apporte plus de détails technique sur la compréhension de ce sujet.

https://www.springer.com/gp/book/9783662436301

L’idée fondamentale des algorithmes évolutionnaires est, si la nature arrive à produire des systèmes aussi complexes et optimales que tout ce qu’elle contient (humains, animaux, arbres, …), durant des générations, raison pour laquelle nous devrons pouvoir arriver à l’imiter et à produire des solutions aussi optimales aux différents problèmes que nous rencontrons (un clin d’oeil au fameux problème P = NP).

En d’autres termes, les algorithmes évolutionnaires permettent d’approcher des solutions optimales à des problèmes difficiles en simulant le principe de fonctionnement de la nature.

C’est un processus de “trial-and-error” qui consiste à une amélioration continue de la solution Sn vers une solution Sn+1 en suivant des règles d’évaluation, de sélection et de mutation établies préalablement par l’environnement dans lequel le système évolue.

Au final, un algorithme évolutionnaire n’est rien d’autre qu’un processus assez particulier de recherche de solution. A présent voyons comment ces algorithmes fonctionnent concrètement.

Comment fonctionne un algorithme évolutionnaire ?

Comme tout algorithme, un algorithme évolutionnaire est composé de différentes phases qui constituent exactement les phases décrites dans le processus de la théorie d’évolution des espèces de Darwin. Ci-dessous, nous avons le “flow diagram” de ces phases.

La première phase de tout algorithme évolutionnaire est l’initialisation de la population. Vous pouvez voir cette phase comme étant le début de l’univers (de l’algorithme) avec une apparition des premières espèces. Ici, nos espèces sont l’ensemble des potentielles solutions au problème que nous tentons de résoudre. L’idée étant de rechercher la meilleure d’entre elles. Avec les algorithmes évolutionnaires, tout groupe de solution d’une même génération est appelé population. Et le groupe de solution généré lors de la phase d’initialisation est appelé population initiale. Elle est générée aléatoirement. Une génération n’est rien d’autre qu’une itération de l’algorithme.

Il est important de définir la structure de données utilisée avec les algorithmes évolutionnaires. Cette structure de données est appelée Chromosome. Un chromosome n’est rien d’autre qu’une collection de gènes. Les gènes sont des éléments descriptifs de chaque solution dans la population.

Imaginez que l’on veuille faire un programme d’optimisation qui cherche à approximer la séquence “Maman va au marché”. Notre population sera composé de chromosome contenant 18 gènes et chaque gène sera un caractère de l’alphabet. Ici le 18 représente la taille de la solution. Ainsi un chromosome de la population initiale pourrait ressembler à ça :

Une fois que notre population initiale est générée, la deuxième phase de l’algorithme est celle de l’évaluation. C’est dans cette phase que nous allons déterminer la qualité de chaque solution (chromosome). Pour se faire, il va falloir définir une fonction d’estimation de cette qualité appelée “fitness function”.

Cette fonction doit prendre en entrée une solution (chromosome) et déterminer à quel point elle est optimale. Pour se faire, la fonction renvoi un nombre et plus ce nombre est grand, plus la solution est optimale. Cette fonction est toujours définie par le créateur de l’algorithme et dépend fortement du problème étudié.

Pour le cas de notre exemple précédent, La fonction fitness serait une fonction qui prend en entrée un chromosome et le compare avec la chaîne “Maman va au marché”, caractère par caractère et renvoi le nombre de caractère similaire. Ensuite, cette fonction fitness est appliquée sur l’ensemble des chromosomes de la population et pour chaque chromosome on enregistre la valeur renvoyée. Cette valeur est appelée score.

La phase d’évaluation consiste en réalité en la comparaison de chaque score de chromosome avec la valeur de convergence seuil définie au préalable. Si pour l’un des chromosomes on atteint la valeur seuil, alors, notre algorithme s’arrête et ce chromosome constitue la solution optimale que l’on cherche.

Sinon on passe à la phase de sélection, et dans cette partie, l’idée est de sélectionner un ensemble de chromosome qui devront “survivre” lors de la prochaine génération et d’éliminer les autres. En réalité cette phase varie selon le type d’algorithmes évolutionnaires que l’on utilise, mais le principe reste le même. Cette sélection se fait selon le score des chromosomes. Dans certaines variantes d’algorithmes évolutionnaires, la phase de sélection fait intervenir une sous-phase appelé la phase de reproduction qui consiste à combiner deux chromosomes avec un grand score pour en faire un score encore plus grand et le remettre dans la population. Ce qui augmente littéralement le temps de convergence de l’algorithme. C’est le cas des algorithmes génétiques.

Après la phase de sélection, on se retrouve avec un ensemble de chromosomes réduit que l’on applique des opérations de mutation. C’est quoi une mutation ? Eh bien c’est exactement comme en génétique, on prend un chromosome au hasard et selon une probabilité p définie à l’avance on lui change une partie de ses gènes. Ce processus augmente la chance de convergence de notre algorithme mais aussi permet d’avoir plus de diversité dans la population P de la génération suivante.

Une fois la phase de mutation terminée, les chromosomes ayant survécu plus ceux créés dans la phase de sélection / reproduction sont à nouveau soumis à une procédure d’évaluation ainsi de suite.

Trois sorties sont possible:

1. Convergence de l’algorithme — On trouve un chromosome avec un score assez satisfaisant.
2. Divergence de l’algorithme — Aucun score de chromosome n’est satisfaisant. Dans ce cas il faudra revoir la fonction de fitness et les règles de mutations et de reproductions.
3. Nombre maximum de génération atteint — Penser à augmenter le nombre de génération dans la limite du possible voire même ne pas les limiter.

 

 

Les applications des algorithmes évolutionnaires

De nos jours les algorithmes évolutionnaires sont utilisés dans presque tous les problèmes d’optimisation. En intelligence artificielle, nous avons un domaine tout entier appelé Neuro Evolution qui combine les algorithmes évolutionnaires aux réseaux de neurones. Le Neuro Evolution donne des résultats très satisfaisant et est utilisé par des firmes tels que UberAI (https://eng.uber.com/deep-neuroevolution/) et Google Deepmind (https://deepmind.com/blog/article/how-evolutionary-selection-can-train-more-capable-self-driving-cars).

Les applications les plus courantes de la neuro évolution sont l’apprentissage par renforcement, la robotique évolutive et la vie artificielle. Les exemples d’applications incluent l’évolution des comportements pour les jeux de société et les jeux vidéo, le contrôle des robots mobiles et l’étude de l’évolution des comportements biologiquement pertinents.

Depuis quelques années maintenant, je m’intéresse aux algorithmes évolutionnaires et au neuro-evolution. Et l’un des algorithmes sur lesquels je travail le plus est celui développé par le professeur Kenneth Stanley (https://twitter.com/kenneth0stanley), le Neuro Evolution Of Augmenting Topologies (NEAT), dans cet article : http://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

Dans ce dépôt GitHub : https://github.com/eliaswalyba/neuro-evolution, vous pouvez retrouver l’ensemble des travaux que j’ai eu à faire dans ce domaine.

Nous arrivons à présent à la fin de cet article. Merci beaucoup d’avoir pris le temps de le lire en entier. J’espère au moins que j’ai pu vous éclaircir un peu sur ce domaine qui est aussi vaste que passionnant. Je reviendrais très bientôt pour d’autres articles de ce genre mais d’ici là, je vous met ci-dessous une liste de livres et publications scientifiques que vous pouvez exploiter.

Plus de lecture

https://dl.acm.org/doi/book/10.5555/534133

https://ieeexplore.ieee.org/document/8915890

https://www.mitpressjournals.org/journal/evco?mobileUi=0&

https://www.journals.elsevier.com/swarm-and-evolutionary-computation