Barbara
DE LA BIOLOGIE À L’INFORMATIQUE : UNE INTRODUCTION AUX ALGORITHMES GÉNÉTIQUES
Les algorithmes génétiques sont nés de la théorie de l’évolution de Darwin. John Henry Holland a créé en 1975 l’algorithme génétique qui est une amplification des concepts de la sélection naturelle et de l’évolution dans le but de résoudre les problèmes d’optimisation mathématique. En utilisant des processus biologiques pour influencer l’apprentissage machine, tel que Frank Rosenblatt qui a développé en 1958 le réseau de neurones perceptron inspiré par les véritables neurones du cerveau, les algorithmes génétiques ont trouvé leur place dans une multitude de domaines. Ils offrent une approche efficace pour de nombreux problèmes d’optimisation qui ne peuvent pas être résolus à l’aide de la force brute en raison du nombre immense de permutations et de combinaisons possibles. Dans cet article, nous allons plonger dans la théorie, la méthodologie et les utilisations courantes des algorithmes génétiques pour montrer comment ils peuvent être utilisés pour résoudre presque tous les problèmes d’optimisation.
LA THÉORIE : UNE TECHNIQUE D’OPTIMISATION BASÉE SUR LA SÉLECTION NATURELLE
Les algorithmes génétiques sont basés sur la sélection naturelle, la survie des plus aptes, la mutation et le croisement. La première étape de l’algorithme consiste à générer une population initiale pour le problème. Pour assurer la diversité, une gamme de solutions du possible espace de recherche doit être utilisée. Après la génération de la population initiale, il est essentiel de sélectionner des solutions à prendre (parents) afin de produire une descendance pour la prochaine génération en fonction de leur potentiel de croissance. L’objectif est de faire passer les gènes les plus efficaces à la génération suivante pour améliorer la longévité de l’espèce. Certains des outils courants utilisés pour la sélection sont l’élitisme, la roulette et le tournoi. Après la sélection, les gènes des parents sélectionnés sont combinés pour produire une descendance à partir de laquelle une nouvelle génération peut être créée. Les techniques courantes de croisement comprennent le croisement à un point, à deux points, et uniforme. La mutation sert à diversifier la population et à réduire les risques de minima locaux.
LA MÉTHODOLOGIE : APPLICATIONS ET VULNÉRABILITÉS
Les algorithmes génétiques s’appliquent dans des domaines aussi variés que la planification de productions, les problèmes de routage de véhicules, les marchés financiers, l’optimisation de portefeuille, la formation de réseaux de neurones, et le traitement d’image. Cependant, ils ont des vulnérabilités, notamment la durée de calcul qui peut être longue, la difficulté de régler les hyperparamètres tels que la mutation et la sélection, qui peuvent conduire à la non-convergence ou à des résultats inutiles, et le fait qu’ils ne garantissent pas de trouver l’optimum global.
En somme, les algorithmes génétiques ont été influencés par la biologie de Darwin et offrent une approche puissante pour résoudre des problèmes d’optimisation complexes. Ils sont utilisés dans de nombreux champs d’applications, mais peuvent se caractériser par une durée de calcul importante et des difficultés de réglage des hyperparamètres.
Sources :
– Wikipedia, “Algorithme génétique”, consulté le 27/05/2023
– Forbes, “The Power of Evolutionary Computing And How To Apply It To Everyday Problems”, consulté le 27/05/2023.
