Depuis la nuit des temps, les êtres vivants ont démontré leur aptitude à s’adapter à leur cadre de vie en constante évolution et à s’améliorer de génération en génération.
Cette capacité à converger vers des solutions de plus en plus optimales inspire justement les mathématiques. Et notamment l’algorithme génétique qui découpe les processus de sélection naturelle pour résoudre des problèmes complexes.
Comprendre les étapes de l’algorithme génétique
Né dans les années 60 à l’initiative du chercheur John Holland, l’algorithme génétique applique les différentes étapes de l’évolution naturelle à la résolution de problèmes complexes.
La création de la population initiale
La première étape de l’algorithme génétique consiste à créer une population initiale amenée à évoluer. Celles-ci regroupent des solutions potentielles à un problème donné. Appelées individus ou chromosomes, elles peuvent être générées de manière aléatoire. Ce qui permet d’apporter davantage de diversité.
À ce stade, il ne s’agit pas de trouver LA bonne solution. Mais surtout d’identifier un nombre suffisant de solutions capables de répondre à la problématique. D’ailleurs, plus la population initiale est variée, plus il sera possible de concevoir les meilleures solutions possibles.
Par exemple, si vous cherchez le chemin entre un point A et un B, il ne s’agit pas de trouver le chemin le plus court, mais tous les chemins permettant d’arriver à destination. Peu importe si vous devez y passer 10 minutes ou 3 heures, à pied ou en voiture, devant une boulangerie ou un garagiste.
Bon à savoir : la taille de la population n’a pas besoin d’être démesurée. Simplement suffisante. En moyenne, 100 ou 150 individus permettent déjà d’aboutir à un résultat satisfaisant à l’issue de toutes les étapes de l’algorithme génétique.
L'évaluation des individus
Suite à la création de la population, il est temps d’évaluer chaque individu en fonction de sa capacité à résoudre le problème. Le data scientist est libre d’évaluer les individus comme bon lui semble. Cela dit, il vaut mieux leur attribuer une note afin d’identifier ceux qui sortent du lot. Ce sont eux qui participent à l’amélioration de notre population.
Attention, cette phase de l’algorithme génétique peut s’avérer complexe, car il est parfois difficile de comparer deux individus entre eux. C’est particulièrement vrai pour les problèmes multicritères où la solution optimale dépend de plusieurs paramètres, sans qu’un ne soit meilleur que l’autre.
La sélection
Après avoir évalué les individus, il convient de sélectionner les meilleurs. Dans la nature, cela correspond au processus de sélection naturelle (ou la loi du plus fort) où les espèces les mieux adaptées à leur environnement survivent, alors que les autres meurent.
En mathématique, il est possible d’utiliser plusieurs méthodes pour sélectionner les meilleurs. Voici les plus courantes :
- La roulette : comme avec la loterie, il s’agit de tourner la roue pour sélectionner les individus. Mais attention, car chaque individu est associé à un secteur sur une roue en fonction de sa qualité. Plus l’individu a de “valeur”, plus son secteur est important. Ainsi, lorsqu’on tourne la roue, les probabilités de tomber sur les individus de meilleure qualité augmentent.
- La sélection par tournoi : il s’agit d’une rencontre aléatoire entre différents individus de la population. Le vainqueur est celui qui a la meilleure qualité. Bien évidemment, il est possible de sélectionner plusieurs vainqueurs.
- L’élitisme : il s’agit simplement de sélectionner les meilleurs individus en fonction de leur qualité. Si cette méthode est plus rapide à implémenter, elle ne permet pas de prendre en compte toute la diversité possible.
Les croisements
Si les espèces naturelles ont été capables de s’améliorer au fil du temps, c’est grâce à l’enrichissement des populations au fil du temps. L’algorithme génétique reprend le même principe. Pour faire évoluer la population, les data scientist combinent des paires d’individus sélectionnés, créant ainsi de nouveaux individus : ce sont les descendants. Pour ce croisement, l’expert data sélectionne certaines caractéristiques de chaque individu parent.
Il est possible de réaliser des croisements aléatoires, et même d’utiliser un même individu pour créer plusieurs descendants. Les caractéristiques non utilisées permettent, en effet, de générer d’autres descendants.
Les mutations
À la place des croisements, l’algorithme génétique prévoit aussi les mutations. C’est-à-dire que les individus subiront des changements mineurs et aléatoires pour explorer de nouvelles possibilités.Les mutations aléatoires sont aussi très efficaces pour obtenir un maximum de diversité et d’envisager des combinaisons innovantes.
Bon à savoir : il s’agit de modifications légères. Autrement dit, une seule caractéristique est changée afin de ne pas dénaturer totalement l’individu initial. Mais même parfois, ces petits changements peuvent aboutir à une évaluation totalement différente.
Les nouvelles générations
Pour trouver les meilleures solutions au problème, de nouvelles générations apparaissent, avec des descendants, des individus modifiés et des individus non modifiés. Chacun doit participer à l’amélioration de la population.
C’est pourquoi, le data scientist réitère le processus de l’algorithme génétique sur plusieurs générations, afin d’améliorer continuellement la solution au problème. Progressivement, la population se réduit de plus en plus jusqu’à trouver la solution optimale.
Bon à savoir : il est important de conserver quelques individus initiaux (non modifiés), car rien ne dit que les nouvelles populations sont forcément meilleures.
Utiliser l’algorithme génétique en science des données
L’algorithme génétique est souvent utilisé pour des problèmes d’optimisation où il y a de nombreuses solutions possibles. Cela dit, il nécessite souvent de nombreux calculs pour parvenir à un résultat satisfaisant. Pour cette raison, de nombreux data scientists se tournent vers d’autres algorithmes d’optimisation dont le temps de calcul est plus court.
Quoi qu’il en soit, il est primordial de connaître les différents modèles de machine learning afin de réaliser des analyses pertinentes. D’où l’intérêt de se former avec DataScientest.
