Algorithme génétique : définition et apport en machine learning
Un algorithme génétique, c'est quoi ?
L’algorithme génétique est une algorithme d’optimisation, reposant le principe de la sélection naturelle, développé dans les années 70 par John H. Holland. Entrant dans la catégorie des algorithmes évolutionnistes, il fait appel à des algorithmes générés aléatoirement, dans un univers défini, qui interagissent entre eux et avec l’univers. Ils ont la capacité d’incorporer des informations présentes au sein de l’univers, et donc d’évoluer (de "muter") en fonction de ces inputs.
Il est important d’insister sur l’aspect aléatoire : ces algorithmes n’ont pas vocation à faire de tâche particulière. Ils se contentent d’exister et d’évoluer en fonction des éléments intégrés. Ces algorithmes sont ensuite confrontés à une sélection, en insérant un score à atteindre. A l’issue du test, seuls les algorithmes les mieux notés sont conservés, et confrontés à de nouveaux algorithmes générés aléatoirement. Le processus est répété de génération d'algorithmes en génération, pendant un certain temps. Avec ce double processus de mutation-sélection, des algorithmes de plus en plus performants finissent par émerger, de façon quasi "spontanée".
Quel est l'apport de l'algorithme génétique en machine learning ?
Dans le domaine du machine learning, le concept d'algorithme génétique permet de développer des solutions très efficaces à un problème donné, dans un temps assez court. Le principal avantage de ces algorithmes est qu’ils n’ont pas besoin d’exemples de départ pour apprendre, aucune base n’est requise pour leur apprentissage. Ils rendent possible le learning non supervisé, sur n’importe quelle tâche, par exemple l'optimisation d'un réseau de points de vente (en termes de géographie, d'effectif, de compétences...).
Néanmoins, il ne s’agit pas d’une solution miracle, visant à remplacer les autres méthodes d’apprentissage. En effet, même si les algorithmes génétiques s’améliorent de manière itérative de génération en génération, rien ne garantit qu’ils parviennent toujours à la solution optimale à un problème...
Algorithme génétique : le problème du voyageur de commerce
L’algorithme génétique peut être utilisé pour résoudre le "problème du voyageur de commerce". La problématique à résoudre ? Passer par un ensemble de points (ou d'adresses) en parcourant la distance globale la plus faible possible. Bien que l’énoncé du problème d’optimisation soit simple, il n’existe pas d'algorithme en temps polynomial permettant de trouver la solution exacte rapidement, dans tous les cas de figure.
C’est pourquoi les informaticiens ont souvent recours à l’algorithme génétique pour résoudre ce problème célèbre. Ses applications directes sont nombreuses dans le secteur logistique et en termes de planification des parcours dans le transport.
Algorithme génétique : le problème du sac à dos
Un autre problème fréquent, qui a recours aux algorithmes génétiques, est celui du "sac à dos" : comment remplir un sac, dont le poids ne peut dépasser un niveau maximal défini à l’avance, avec le plus d’objets possible (chaque objet ayant un poids déterminé). Ici, les algorithmes génétiques obtiennent une bonne approximation en monopolisant assez peu de ressources.