Algorithmes de fourmis artificielles : applications à la classification et à l'optimisation

Nous inspirons de la strategie de recherche de nourriture d'une espece de fourmis (Pachycondyla apicalis) pour resoudre des problemes d'optimisation globale pendant ce travail de these.

Abstract

In this thesis, we present works inspired by real ants for the resolution of well known problems in computer science. We propose two supplementary approaches to these new biomimetic inspirations. The first resumes works on clustering and widens their principles in several directions. The AntClass algorithm, developed for occasion, is hybrid in the way that the artificial ants search for the number of clusters and a classic classification algorithm, the K-means algorithm, is used to reduce classification errors inherent to a stochastic method such as artificial ants. After underlying similarities and differences between the evolutionnary approaches and those based on a population of ants, we propose a common model. We finally use the Pachycondyla apicalis ants' strategy to search for food to solve global optimization problems. The contribution of this adaptation mainly lies in its simplicity. We apply the ensuring algorithm, called API, to various problems such as the optimization of numerical functions, the learning of hidden Markov models, the learning of the weights of an artificial neural network, or also to a classical combinatorial optimization problem: the traveling salesman problem.