Résumé
There are even increasing efforts in searching and developing algorithms that can find solutions to combinatorial optimization problems. In this way, the Ant Colony Optimization Metaheuristic takes inspiration from biology and proposes different versions of still more efficient algorithms. Like other methods, Ant Colony Optimization has been applied to the traditional Traveling Salesman Problem. The original contribution of this master thesis is to study the possibility ofa modification of the basic algorithm of the Ant Colony Optirnization family, Ant System, in its application to solve the Traveling Salesman Problem. In this version that we study, the probabilistic decision rule applied by each ant to determine his next destination city, is based on a modified pheromone matrix taking into account not only the last visited city, but also sequences of cities, part of previous already constructed solutions. This master thesis presents some contribution of biology to the development of new algorithms. It explains the problem of the Traveling Salesman Problem and gives the main existing algorithms used to solve it. Finally, it presents the Ant Colony Optimization Metaheuristic, applies it to the Traveling Salesman Problem and proposes a new adaptation of its basic algorithm, Ant System
| la date de réponse | 2005 |
|---|---|
| langue originale | Anglais |
| L'institution diplômante |
|