Introduction

Il arrive très souvent que les sciences et les techniques imitent les mécanismes de la nature. Par exemple, le sonar ou le radar sont inspirés des techniques d'écholocation des dauphins ou des chauve-souris, la texture de la peau de requin a été imitée pour fabriquer des matériaux hydrodynamique... Les algorithmes génétiques (AG) proposent de reproduire les mécanismes d'évolution et d'adaptation génétique de la vie pour optimiser des problèmes complexes dont les données peuvent varier au cours du temps. La vie a besoin en permanance de s'adapter : à un nouvel environement, à un nouveau prédateur, ou à de nouvelles proies. Le vocabulaire et les intuitions des algorithmes génétiques appartiennent en partie au vocabulaire et aux intuitions de la biologie. Ces algorithmes fabriquent des chromosomes qui codent chacun une solution potentielle à un problème donné. A chaque étape (appelée génération), ces chromosomes se combinent, mutent, et sont selectionnés en fonction de leur qualité à répondre au problème. De même, dans la nature, selon la thèse darwinienne, seule la succession de croisements et de mutations aléatoires suffisent à expliquer l'adaptation des êtres vivants à leur milieu naturel (problème qui serait trop complexe à comprendre dans son ensemble). Dans les AG, la succession des croisements et des mutations permet d'arriver à une solution, qui sans être nécessairement optimale, peut être très satisfaisante. On obtient alors certains phénomènes que rencontre l'évolution biologique, comme la convergence de l'évolution, la stagnation, l'influence de la pression sélective...

Notre but est d'adapter les algorithmes génétiques pour résoudre le problème classique du voyageur de commerce (PVC). Ceux-ci s'adaptent très bien au PVC. Il s'agit d'optimiser le coût d'un parcours dans un graphe complet possédant un grand nombre de sommets, en passant une et une seule fois par chacun. Des méthodes déterministes existent déjà pour résoudre le problème, mais le temps de calcul est très long : elles reviennent à parcourir toutes les solutions possibles et à déterminer la moins coûteuse. Les algorithmes génétiques donnent très rapidement une solution acceptable.

Cet article expose dans un premier temps le problème du voyageur de commerce. Il introduit ensuite les algorithmes génétiques : leurs principes de fonctionnement (population, hybridation, mutation,...), les différentes méthodes de sélection. La troisième partie traite de l'application des AG au PVC, des choix d'implantation faits pour résoudre efficacement le PVC, ainsi que d'une autre méthode d'implantation : les séquences de Bean. Dans la quatrième partie, nous développons des méthodes pour restreindre l'espace de recherche. Et, dans la dernière partie, nous exposons d'autres méthodes pour résoudre le PVC.