Conception d'un système informatique mémétique pour résoudre le problème du voyageur de commerce : Application à la cartographie physique du génome

Abstract

La première partie de la thèse aborde l'étude des différentes approches pour la résolution des problèmes d'optimisation combinatoire discrète et les théories de l'évolution naturelle et artificielle. Cette étude porte sur les méthodes d'échanges locaux comme l'algorithme glouton, les méthodes r-opt, le recuit simulé (méthode et algorithme), la méthode Tabou, la recherche dans un voisinage variable (l'algorithme RVV, les réseaux des neurones artificiels, les colonies de fourmis artificielles et la programmation dynamique (méthode et algorithme). Elle se penche aussi sur l'étude du modèle de la sélection naturelle élaborée par Charles Darwin et sur toutes ses composantes, telle que la sélection naturelle et l'adaptation. Dans l'évolution artificielle, nous parlons de solutions potentielles, de population initiale, de sélection, de descendants et de modification de descendants, tout en gardant en vue les analogies avec les phénomènes biologiques. Le vocabulaires utilisé dans l'évolution artificielle et directement calqué sur celui de la théorie de l'évolution génétique. La deuxième partie est consacrée à la construction et à l’implémentation de notre système informatique mémétique. Nous expliquons dans cette partie les étapes d’élaboration de ce système. D’abord nous développerons un système à base d’algorithmes génétiques, Nous choisissons de coder les gènes du chromosomes par les entiers, codage qui nous semble le plus approprié pour nos deux applications. La population initiale du système possède deux caractéristiques : la taille et la diversité de ses individus. La taille de la population de notre système est petite, 40 individus pour la population initiale (la puissance du logiciel sur lequel nous avons travaillé était limitée). Pour préserver la diversité malgré la petite taille de la population initiale, nous avons établi un algorithme nommé « algorithme de préservation de la diversité ». Cet algorithme établit que la probabilité que deux individus se ressemblent au sein de la même population est faible. La sélection, dans notre travail, est traitée par la sélection par le tournoi, car cette manière de sélectionner les individus a donné les meilleurs résultats. Pour résoudre un problème d’optimisation, les autres méthodes énumèrent, construisent et améliorent la totalité de la solution. L’idée originale de ce travail suit une démarche différente. Elle procède d’abord à la segmentation de la solution par le croisement et mène généralement le système vers une optimisation locale. Elle cherche ensuite à optimiser chaque partie de la solution par une méthode exacte (programmation dynamique) et, d’une manière récursive, le système considère chaque partie comme un gène et finit par construire une solution optimale. La dernière partie est consacrée aux applications scientifiques : le problème du voyageur de commerce (TSP) et la cartographie physique du génome. L’application de notre algorithme mémétique sur TSP constitue un test de la capacité de notre méthode. Cependant, le choix de la cartographie du génome comme domaine d’application réside dans sa capacité à localiser les gènes responsables des maladies héréditaires et de baliser le génome. Elle constitue, aussi, un outil qui peut nous informer sur les coordonnées exactes de chaque gène dans le génome.