Les algorithmes génétiques
Un voyageur de commerce doit visiter toutes les villes éparpillées sur un territoire donné. Pour minimiser les
coûts, il désire connaître le chemin le plus court qui les relie. Comment calculer ce trajet?
Concocté en 1857 par le mathématicien irlandais William Rowan Hamilton, ce problème paraît simple en apparence, mais il est des plus complexes. Il n'existe pas de méthode simple et logique pour
trouver la solution : il faut tester chaque solution individuellement – une tâche qui peut devenir pénible même pour un ordinateur - et la difficulté s'accroît de façon exponentielle lorsqu'on
ajoute des villes et des routes entre elles.
Les algorithmes génétiques ont été imaginés pour résoudre ce type de problèmes mathématiques. Le qualificatif «génétique» vient du fait que ce genre d'algorithme s'adapte parfaitement à la
théorie de l'évolution des espèces de Charles Darwin. Dans un premier temps, l'algorithme génétique crée, au hasard, des solutions possibles. Ensuite, il les laisse «évoluer» jusqu'à obtenir les
résultats les mieux adaptés au problème.
Les solutions candidates possèdent chacune un «patrimoine génétique», c'est-à-dire une chaîne de «chromosomes» écrits sous forme de 0 et de 1. Faisant office de «sélection artificielle»,
l'algorithme génétique favorise la «survie» des solutions les plus correctes. Celles-ci peuvent alors se reproduire entre elles et transmettre leur bagage génétique à la prochaine génération.
Pour favoriser encore plus la diversité, au moment de la reproduction, l'algorithme crée des mutations de façon aléatoire, ce qui provoque l'apparition de « mutants » issus des meilleurs parents.
Ainsi les générations successives deviennent de mieux en mieux adaptées à la résolution du problème.
Un algorithme génétique est capable de résoudre des problèmes dont on ne connaît pas de méthode de résolution ou dont la solution exacte est trop complexe pour être calculée en un temps
raisonnable.
On utilise ce genre de calculs pour planifier des tournées de livraison, constituer des équipes de travail, implanter de manière optimale des points de vente dans une région, gérer des
portefeuilles financiers et même, en design industriel, trouver la meilleure forme à donner à la turbine d'un réacteur nucléaire.