Les algorithmes évolutionnaires, un exemple de vie artificielle

Par leurs implications philosophiques, les tentatives de re-création de la vie illustrent le côté le plus fascinant de la vie artificielle. Dans la pratique, ces travaux sont pourtant loin d'être les plus importants, ni les plus représentatifs de la « discipline ». Zoom sur les algorithmes évolutionnaires.

Construction d'un algorithme. © Sergey Nivens, Shutterstock

La vie artificielle ne se limite pas aux seules tentatives de constructionconstruction de nouvelles instances de la vie ou à la biologie théorique. Elle s'inspire des propriétés du vivant pour proposer des constructions originales, tant algorithmiques que physiquesphysiques, dotées de capacités étonnantes et aptes à résoudre des problèmes difficiles vis-à-vis desquels les approches plus traditionnelles rencontrent de graves difficultés. C'est le vaste domaine des artefacts biomimétiquesbiomimétiques (algorithmiques et robotiques).

Les algorithmes évolutionnaires, domaine des artefacts biomimétiques. © DR

Naissance des algorithmes évolutionnaires

Les biologistes utilisent le concept de paysages adaptatifs pour représenter l'ensemble des combinaisons génétiquesgénétiques et les niveaux d'adaptation correspondants. Par exemple, dans un diagramme en trois dimensions, la hauteur (z) représente le niveau d'adaptation de l'ensemble des configurations génétiques (x, y).

Paysage adaptatif. © DR

Les mécanismes évolutifs ont montré leur efficacité, leur capacité à rejoindre les points les plus « élevés » des différents paysages adaptatifs. C'est cette capacité qui a inspiré les chercheurs en informatique qui en ont pris modèle pour proposer des algorithmes originaux. Cette branche de la science informatique est devenue l'algorithmique évolutionnaire.

Principe des algorithmes évolutionnaires : les populations 

De nombreux problèmes d'optimisation (classiquement non linéaires) ou de recherches au sein de vastes espaces (explosion combinatoire) n'ont pas de « solutions mathématiques » directes. Des méthodes très diverses ont été proposées qui vont de l'exploration systématique à l'exploration aléatoire. Les plus récentes utilisent souvent le « hasard guidé », c'est-à-dire qu'à des procédures plus ou moins empiriques sont associées des procédures aléatoires permettant de sortir des optima locaux. On a proposé ainsi d'utiliser des mécanismes s'inspirant directement de la théorie darwinienne. L'idée consiste tout simplement à construire une « population » aléatoire de solutions potentielles au problème posé. Les « individus » sont ensuite testés (calcul de la fitnessfitness) afin de favoriser la « reproduction » des plus aptes, c'est-à-dire ici de ceux qui s'approchent le plus de la solution. Les mécanismes de reproduction, de croisement des individus les plus adaptés et de mutations permettent progressivement d'approcher la solution recherchée.

Par exemple, pour résoudre le fameux problème du voyageur de commerce (il s'agit de trouver le chemin le plus court pour relier un certain nombre de villes). Malgré son apparente simplicité, il s'agit là d'un exemple classique de ces problèmes dits « NP » (dont la complexité croît plus vite que n'importe quelle puissance de la variable), qui posent des questions fondamentales à l'informatique théorique. On construit une population représentant un ensemble de parcours aléatoires. On sélectionne ensuite les meilleurs (les plus courts) que l'on croise entre eux pour obtenir une nouvelle population de parcours et ceci aussi longtemps qu'on le souhaite pour approcher le parcours optimum. Les résultats obtenus montrent que les algorithmes évolutionnaires sont particulièrement adaptés à ce type de problème.

Domaines d'application des algorithmes évolutionnaires

Les algorithmes évolutionnaires ont maintenant fait leurs preuves. On les retrouve par exemple dans des domaines aussi divers que l'industrie (optimisation des allocations de ressources, programmation de robots...), la conception (optimisation de formes...) ou encore la bourse. Plus encore, des environnements de programmation dédiés, destinés à faciliter l'appropriation de ces méthodes par les non-spécialistes, sont en cours de développement, notamment en France avec le langage EASEA de Pierre ColletCollet (Collet P., Lutton E. et al., « Take it EASEA », Parallel Problem Solving from Nature VI, vol. 1917, Paris, Springer, 09/2000, p. 891-901.). En 2010 par exemple, l'équipe de Pierre Collet a participé aux 20^e Journées évolutionnaires à Paris VI.