La mémoire dans les algorithmes à colonie de fourmis : applications à l'optimisation combinatoire et à la programmation automatique

This thesis presents meta-heuristic based on the behaviour of natural ants looking for food. These heuristics are known as Ants Colony Optimization or ACO. We propose to compare the ACO paradigm with other well-known heuristics with regards to the use of the memory. Then, we introduce two applications of the ACO algorithms.The First application, ANTabu is an ACO scheme for the QAP. ANTabu combines the ants' paradigm with a robust local search technique (Tabu search). A parallel model developed for ANTabu is introduced. The second application lies in the machine-learning field. This scheme called AP (Automatic Programming) applies the cooperative behaviour of ants to automatically build programs. This method is then compared to the classical automatic generation of programs : Genetic Programming.Dans ce mémoire, nous presentons les meta-heuristiques inspirées du comportement des fourmis lors de la recherche de nourriture, les OCF. Nous confrontons ces méthodes face aux principales méta-heuristiques connues. Pour cela, nous proposons de nous placer sous le point de vue de l'utilisation de la mémoire et nous présentons taxinomie qui étend celle des AMP. Nous proposons deux nouvelles adaptations du modéle des fourmis. La premiere est l'algorithme ANTabu, il s'agit d'une méthode hybride pour la résolution du PAQ. Il associe l'utilisation des fourmis artificielles et d'une méthode de recherche locale robuste : la recherche tabou. Le parallélisme intrinseque des systèmes de fourmis nous a amene a developper un modele paralléle pour ANTabu.Cette méthode intègre également une puissante fonction de diversification et l'utilisation de bornes qui lui permettent d'eviter d'être piege au niveau d'optima locaux.La seconde application développee est AP, cet algorithme est l'adaptation du modèle de coopération des fourmis a la programmation automatique. Son mécanisme de fonctionnementest simple, puisque à chaque itération on crée une nouvelle population en utilisant l'information emmagasinée par la phéromone. L'intérêt de cette gestion de l'information est qu'elle n'utilise pas de mécanismes complexes. Nous présentons cette méthode face a l'algorithme de base tel que Koza l'a défini