Pour le dire simplement, un algorithme évolutif ou génétique est une innovation technologique en matière d'intelligence artificielle qui Elle permet de résoudre des problèmes grâce à des processus similaires à ceux observés en biologie chez les êtres vivants. Certains d'entre eux, par exemple, s'apparentent aux processus observés dans la reproduction, la sélection naturelle, la mutation et la recombinaison de l'ADN.
Il s'agit d'un domaine très complexe de l'intelligence artificielle, car pour utiliser les algorithmes évolutifs, il faut disposer de connaissances de base en génétique et en processus biologiques, ainsi qu'une maîtrise avancée des techniques de apprentissage automatique.
À quoi servent les algorithmes évolutifs ?
Au-delà des dilemmes génétiques impliquant de multiples variables, les algorithmes évolutifs permettent de résoudre des problèmes complexes et trouver la meilleure solution possible face à un ensemble de variables.
Comme nous l'expliquerons plus loin, les algorithmes évolutifs examinent plusieurs candidats représentant des solutions possibles aux caractéristiques variées et, dans une certaine mesure, aléatoires. L'objectif de l'algorithme est d'éliminer progressivement les candidats jusqu'à isoler le meilleur, c'est-à-dire de trouver la solution la plus satisfaisante.
Par exemple, imaginons que nous souhaitions concevoir un algorithme pour établir un emploi du temps scolaire. Pour cela, les établissements scolaires doivent tenir compte d’une multitude de facteurs. Un enseignant ne peut pas se trouver dans deux salles de classe à la fois, chacun enseigne une ou plusieurs matières, chaque classe a une capacité d’accueil limitée, entre autres facteurs. Ce problème de combinaisons peut s'avérer être un véritable casse-tête pour de nombreux algorithmes, mais c'est précisément un cas de figure idéal pour un algorithme évolutif.
Les processus biologiques dans les algorithmes évolutifs
Afin de replacer un peu les choses dans leur contexte, nous allons te rafraîchir la mémoire et t'expliquer brièvement quels sont les phénomènes biologiques sur lesquels s'appuient les algorithmes évolutifs :
Sélection naturelle
La sélection naturelle est un mécanisme fondamental de l'évolution, proposé par Charles Darwin. Ce processus repose sur la variabilité observée entre les individus d'une population. Certains de ces individus possèdent des caractéristiques qui leur confèrent une plus grande capacité à survivre et à se reproduire dans leur milieu spécifique.
Au fil du temps, ces caractéristiques avantageuses deviennent plus courantes dans la population car les personnes qui en sont dotées ont plus de chances de survivre et, par conséquent, de les transmettre à leurs descendants. La sélection naturelle est un facteur décisif de survie qui favorise les individus dotés des caractéristiques permettant une meilleure adaptation à l'environnement.
Reproduction
La reproduction est le processus par lequel les organismes donnent naissance à de nouveaux individus, assurant ainsi la pérennité de l'espèce. Dans la reproduction sexuée, Les deux parents apportent leur matériel génétique pour donner naissance à leur progéniture qui contiennent des séquences d'ADN uniques. Cet échange de matériel génétique s'opère par la formation de gamètes (ovules et spermatozoïdes) qui fusionnent lors de la fécondation.
Carrefour
La recombinaison ou le croisement génétique est un processus lié à la reproduction sexuée qui accroît encore davantage la diversité génétique. Lors de la formation des gamètes, il se produit un échange de segments d'ADN entre les chromosomes homologues grâce à un processus appelé « entrecroisement » ou crossing-over. Cela donne lieu à de nouvelles combinaisons de gènes dans les gamètes, ce qui se traduit par une plus grande variabilité génétique chez les descendants.
Mutation
La mutation est un autre processus essentiel à la création de la diversité génétique. Elle consiste à modifications aléatoires qui surviennent dans la séquence d'ADN d'un organisme. Ces changements peuvent résulter d'une erreur survenue lors de la réplication de l'ADN, d'une exposition à des mutagènes (tels que les rayonnements ou certains produits chimiques) ou d'infections virales. Les mutations peuvent être neutres, néfastes ou bénéfiques, selon le contexte environnemental.
Comment fonctionnent les algorithmes évolutifs ?
Les algorithmes évolutifs ne sont ni plus ni moins qu'une simulation d'un scénario de sélection naturelle dans laquelle plusieurs individus présentant des caractéristiques bien définies s'affrontent pour assurer la survie du plus fort. Nous allons maintenant vous expliquer les différentes phases de fonctionnement des algorithmes évolutifs et comment chaque processus biologique décrit précédemment s'y intègre :
Échantillonnage
Comme nous l'avons mentionné précédemment, dans les algorithmes évolutifs On sélectionne un ensemble de candidats choisis au hasard. Ces candidats sont constitués de valeurs pour chaque variable, exprimées sous forme de fonction. Il est important que ces candidats soient suffisamment hétérogènes les uns par rapport aux autres afin que nous puissions explorer toutes les solutions possibles.
Fonction d'évaluation
L'algorithme doit évaluer chaque candidat en fonction du problème à résoudre et lui attribue une note appelée « force » (en anglais, fitness). Plus un candidat fera preuve de force, plus il sera apte à résoudre le problème. Pour cela, il faut créer une fonction d'évaluation (fonction de fitness) qui permette d'évaluer correctement les candidats afin de sélectionner les meilleurs.
Dans les algorithmes évolutifs, on peut également utiliser plusieurs fonctions d'évaluation qui fondent le choix des meilleurs candidats sur des critères disparates, voire contradictoires entre eux. On aboutirait ainsi à un ensemble hétérogène de solutions qui, bien qu’elles soient meilleures à certains égards, ne sont pas beaucoup meilleures les unes que les autres.
Cet ensemble de solutions optimales plausibles est appelé efficacité de Pareto. On établit ensuite un critère plus déterminant pour éliminer progressivement les candidats et réduire le nombre de candidats potentiels.
Croisement et mutation
Une fois que nous avons exécuté l'algorithme un nombre suffisant de fois et obtenu un ensemble de solutions optimales, nous sélectionnons les principaux candidats en fonction de leur valeur de force.
Ces candidats les plus compétents s'appelleront désormais parentaux, et l'objectif de cette phase de l'algorithme évolutif sera de générer une nouvelle descendance combinant les caractéristiques de ses prédécesseurs grâce à la croisement de ces parents.
À partir de là, nous pouvons relancer l'algorithme évolutif jusqu’à obtenir le meilleur descendant. Mais cela ne suffit pas, car il est nécessaire d'introduire du nouveau matériel génétique pour garantir l'hétérogénéité de l'échantillon. Ainsi, les valeurs des descendants sont modifiées de manière aléatoire, de sorte qu'elles ne constituent pas un reflet fidèle et facilement détectable de celles de leurs parents. Ce processus s'appelle mutation, et, tout comme chez les êtres humains, cela relève d'une simple question de probabilité.
Sélection finale
À un moment donné au cours de ce processus, les itérations de l'algorithme évolutif prendront fin. En général, celui-ci cesse automatiquement de fonctionner lorsqu'il a atteint une limite maximale de temps ou de performance. Une fois terminé, l'algorithme doit renvoyer un résultat contenant une solution définitive.
Español 
English (UK) 
Français