Algorithme génétique : définition et apport en machine learning

En machine learning, il est fréquent d'utiliser des modèles évolutionnistes, inspirés de la sélection naturelle, pour résoudre des problèmes dans un temps raisonnable. Parmi eux, on trouve l'algorithme génétique, qui sert notamment à résoudre le problème du voyageur de commerce ou du sac à dos.

Un algorithme génétique, c'est quoi ?

L’algorithme génétique est une méthode d’optimisation, issue du processus de sélection naturelle, développée dans les années 70 par John H. Holland. Elle 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 objectif ou score à atteindre. A l’issue du test, seuls les algorithmes ayant le mieux réussi 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 en génération, pendant un certain temps. Avec ce double processus de mutation et de sélection, des algorithmes de plus en plus performants finissent par émerger, quasi de façon "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.

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 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". Dans cet univers, le but est de passer par un ensemble de points (de villes) en parcourant la distance globale la plus faible possible. Bien que l’énoncé de ce 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, ils obtiennent une bonne approximation en monopolisant assez peu de ressources.

Dictionnaire de l'intelligence artificielle