Qu’est ce que les algorithmes évolutionnaires ?

Un homme travaille sur son ordinateur

Autrefois, les êtres humains avaient une queue comme les chiens et les chats. Ce caractéristique a disparu avec le temps. Aujourd’hui, il subsiste sous la forme d’un os légèrement plus proéminent au bas de la colonne vertébrale pour certains d’entre nous. 

17% de la population mondiale a les yeux bleus. Dans les pays occidentaux, entre 10 et 15 % des gens sont majoritairement gauchers. 

Toutes ces caractéristiques génétiques sont le résultat d’années d’évolution biologique. 

La sélection naturelle

Selon Darwin, toutes les espèces naissent et se développent selon un processus sélectif. C’est la sélection naturelle de petites variantes génétiques qui augmentent la capacité de l’individu à survivre et à se reproduire. Les survivants y parviennent grâce à un processus appelé « sélection naturelle ». 

Et ce même processus s’applique aux algorithmes évolutifs. 

La sélection naturelle commence par la sélection au moyen de la survie des éléments les plus forts au sein d’une population. Ils engendrent des descendants qui héritent des caractéristiques des parents. Ces caractéristiques, à leur tour, seront ajoutées à la génération suivante. 

Un algorithme génétique (AG) est une heuristique de recherche inspirée de la théorie de l’évolution naturelle de Charles Darwin. Ce type d’algorithme évolutionniste reflète le processus de sélection naturelle. 

Dans ce contexte, les individus les plus aptes (algorithmes) sont sélectionnés pour la reproduction. L’objectif est de produire des descendants plus robustes pour la prochaine génération. Les algorithmes génétiques sont un sous-ensemble des algorithmes évolutionnaires. 

La sélection naturelle pour les humains fait référence à la survie et à la reproduction de certains individus en raison de différences de phénotype, c’est-à-dire de gènes et de leurs expressions. Il s’agit d’un mécanisme crucial de l’évolution biologique. Certains changements dans les traits d’une population hérités depuis plusieurs générations se transmettent à la suivante. 

En effet, des variations se produisent au sein de toutes les populations d’êtres vivants. Cela a lieu parce que des mutations aléatoires surviennent dans le génome d’un organisme individuel et que leurs descendants peuvent recevoir ces mutations. 

Au cours de la vie des personnes, leurs génomes interagissent avec leur environnement pour induire ces variations. Et les individus présentant des variantes spécifiques d’un trait ont tendance à mieux survivre et se reproduire que d’autres personnes présentant des variantes différentes et moins réussies. En conséquence, la population évolue. 

Le principe d’un algorithme évolutif (EA) est tout à fait compréhensible, dans la mesure où vous vous êtes familiarisé avec le processus de sélection naturelle. Un algorithme évolutif comprend quatre étapes générales : l’initialisation, la sélection, les opérateurs génétiques et la terminaison.

Population et sélection génétique

La sélection naturelle favorise certains phénotypes. Sur de longues périodes d’évolution, ce processus peut aboutir à la spécialisation des populations dans des niches biologiques spécifiques. En conséquence, il peut déboucher à terme sur l’apparition de nouvelles espèces. Autrement dit, la sélection naturelle est un processus indispensable à l’évolution biologique d’une population.

Si les parents sont en bonne santé, leur progéniture sera plus vigoureuse et aura de meilleures chances de survie. Ce processus ne cesse de se répéter. Et à la fin, nous obtiendrons une génération avec les individus les plus aptes.

Nous souhaitons trouver la meilleure association de composants de l’algorithme qui maximise les performances de ce dernier. Nous accepterons une solution finale optimale dans deux cas. Soit une fois que nous aurons exécuté l’algorithme pendant un nombre maximal d’itérations ou atteint un niveau de performance donné. Cette approche n’est pas la seule façon de maximiser un algorithme génétique et évolutif.

Comment évalue-t-on la performance d’un algorithme évolutif ? Nous utilisons une fonction pour mesurer objectivement les performances de l’algorithme. C’est ce qu’on appelle une fonction fitness.

Il s’agit d’une fonction spécifique. Elle synthétise l’écart entre une solution donnée et les objectifs fixés. Les fonctions de fitness servent dans la programmation génétique et les algorithmes génétiques à évaluer la distance d’une descendant à une solution optimale.

Examinons maintenant les algorithmes génétiques. Un « algorithme génétique » (AG) est une technique d’optimisation fondée sur l’exploration d’un grand nombre de solutions. Il permet de trouver des solutions optimales à des problèmes « difficiles », qui autrement seraient longs à résoudre. 

Un « pool » ou une « population » de solutions possibles à une situation donnée est généré de manière aléatoire. Une fonction de fitness est calculée pour chaque fonction générée aléatoirement. 

Certaines des solutions générées au cours de cette première génération deviendront les parents de la génération suivante. Nous effectuons donc un mécanisme de sélection des parents au sein de la population. 

Il permet la reproduction, également appelée recombinaison (« crossover »), pour produire de nouveaux enfants (« la progéniture »). Dans cette population de parents candidats, chaque individu (ou solution candidate) se voit attribuer une fonction de fitness. Les individus les plus en forme ont une plus grande chance de s’accoupler et de produire davantage d’individus « en forme » (« recombinaison ou croisement »). 

Un exemple d’algorithmes évolutifs

Prenons une analogie. Nous voulons créer un modèle 3D de la terre en utilisant des algorithmes génétiques et évolutionnaires. Dans un premier temps, nous générons des formes 3D aléatoires, disons trois cubes : un petit, un moyen et un grand et une sphère : un petit, un moyen et un grand, une étoile : un petit, un moyen et un grand. 

La fonction de fitness consiste à calculer la différence entre le modèle 3D réel de la terre et ces neuf modèles initiaux. Supposons ensuite que les trois sphères soient conservées pour se reproduire à la prochaine génération. Elles génèrent également dix sphères de tailles variables. 

Une mutation est imposée aux sphères, qui ajoutent la couleur verte à certaines d’entre elles. Dans cette deuxième génération, la fonction de fitness sélectionne les plus grosses sphères avec la mutation de couleur verte (parce qu’elle s’est rapprochée du bleu de la terre).

Le croisement (ou la reproduction) se produit entre les parents choisis. Dans la génération suivante, seules des sphères géantes sont générées. Une mutation est introduite, qui transforme les sphères vertes en sphères bleues. 

À ce stade, l’un des descendants peut être une sphère assez géante de couleur bleue, assez proche d’une représentation 3D de la terre. L’algorithme s’arrête. Nous avons un modèle pour générer une version 3D de la planète. Et nous pouvons utiliser ce modèle pour « prédire » l’état futur de la planète.

Les algorithmes évolutifs sont parfaitement adaptés aux problèmes d’optimisation, de classification, de prédiction et d’évaluation. En tant que sous-ensemble du Machine Learning, lui-même un sous-ensemble de l’Intelligence Artificielle, cette méthode d’optimisation est efficace pour résoudre des problèmes complexes. Il s’agit d’une discipline assez ancienne de l’informatique. 

Les algorithmes génétiques (GA) et les approches évolutionnaires ont été définis dans les années 70, tandis que la programmation génétique est apparue au début des années 90. TADA, la plate-forme d’apprentissage automatique de MyDataModels, offre toute la sophistication et la complexité des algorithmes évolutionnaires dans un outil facile à utiliser.

Share
Partager sur linkedin
Partager sur twitter
Partager sur facebook

Start making sense of  your data

Test easily TADA with our test data here

You might also like...

Article Mikhail Kamalov Algorithmes évolutifs

Les algorithmes évolutionnaires appliqués à la classification

Retrouvez Alain Blancquart, notre PDG, sur le plateau de BFMTV !

MyDataModels et CIUS

MyDataModels collabore avec le CIUS dans le cadre d’un programme de recherche international

Apprentissage semi-supervisé pour la classification des documents