Complexité des problèmes et heuristiques
183
Ce sont quelques une de ces techniques, les plus connues et les plus appliquées en
matière d'optimisation combinatoire, que nous exposons ci-dessous rapidement, en nous
limitant pour chacune d'elle aux grands principes qui la guident.
On exposera trois grands types de méthode : les algorithmes d’Optimisation par
Colonies de Fourmis, les algorithmes gloutons, les méthodes de voisinage, avec deux
variantes : le recuit simulé et la méthode Tabou, et les algorithmes génétiques, cette
classification n'étant pas sans arbitraire (les algorithmes génétiques, notamment, utilisent
la notion de voisinage).
8.2.1. Ant colony optimisation
Les algorithmes d’Optimisation par Colonies de Fourmis sont de nouvelles méthodes
d’optimisation qui s’inspirent du comportement des fourmis qui sont capables de trouver
le chemin le plus court du nid à une source de nourriture et de s’adapter aux
changements de l’environnement et ceci grâce à une substance leur permettant de laisser
une trace sur leur chemin : la phéromone.
Le problème du voyageur de commerce a fait l’objet du premier algorithme de colonies
de fourmis : Ant System (Dorigo et Gambardella, 1997). Dans ce problème, il s’agit de
trouver le chemin le plus court reliant villes données ; chaque ville ne devant être
visitée qu’une et une seule fois. Formellement, soit un graphe connexe,
, où les
sommets représentent les villes et les trajets représentent les arêtes. A chaque itération
chaque fourmi
parcourt au hasard le graphe et
construit une chaîne de n sommets
. A chaque étape, la fourmi se déplace du
sommet vers le sommet en fonction des règles suivantes :
- Sa prochaine destination est choisie dans un ensemble d’arêtes possibles, notée
Il s’agit de la liste des trajets possibles pour une fourmi lorsqu’elle se
trouve dans une ville ,
- la visibilité entre les sommets :
Ce paramètre est employé pour diriger
le déplacement des fourmis vers des sommets proches : plus une ville est
proche, plus elle a de chance d’être choisie.
- La quantité des phéromones déposée sur l’arête reliant deux sommets est
appelée l’intensité de la piste. Il s’agit de l’attractivité du trajet : plus l’intensité
de phéromone disposée sur l’arête entre deux sommets est grande, plus le trajet
aura de chance d’être choisi par les fourmis. La règle aléatoire de transition
proportionnelle proposée par (Bonabeau et al. 99) est la suivante :
183
Ce sont quelques une de ces techniques, les plus connues et les plus appliquées en
matière d'optimisation combinatoire, que nous exposons ci-dessous rapidement, en nous
limitant pour chacune d'elle aux grands principes qui la guident.
On exposera trois grands types de méthode : les algorithmes d’Optimisation par
Colonies de Fourmis, les algorithmes gloutons, les méthodes de voisinage, avec deux
variantes : le recuit simulé et la méthode Tabou, et les algorithmes génétiques, cette
classification n'étant pas sans arbitraire (les algorithmes génétiques, notamment, utilisent
la notion de voisinage).
8.2.1. Ant colony optimisation
Les algorithmes d’Optimisation par Colonies de Fourmis sont de nouvelles méthodes
d’optimisation qui s’inspirent du comportement des fourmis qui sont capables de trouver
le chemin le plus court du nid à une source de nourriture et de s’adapter aux
changements de l’environnement et ceci grâce à une substance leur permettant de laisser
une trace sur leur chemin : la phéromone.
Le problème du voyageur de commerce a fait l’objet du premier algorithme de colonies
de fourmis : Ant System (Dorigo et Gambardella, 1997). Dans ce problème, il s’agit de
trouver le chemin le plus court reliant villes données ; chaque ville ne devant être
visitée qu’une et une seule fois. Formellement, soit un graphe connexe,
, où les
sommets représentent les villes et les trajets représentent les arêtes. A chaque itération
chaque fourmi
parcourt au hasard le graphe et
construit une chaîne de n sommets
. A chaque étape, la fourmi se déplace du
sommet vers le sommet en fonction des règles suivantes :
- Sa prochaine destination est choisie dans un ensemble d’arêtes possibles, notée
Il s’agit de la liste des trajets possibles pour une fourmi lorsqu’elle se
trouve dans une ville ,
- la visibilité entre les sommets :
Ce paramètre est employé pour diriger
le déplacement des fourmis vers des sommets proches : plus une ville est
proche, plus elle a de chance d’être choisie.
- La quantité des phéromones déposée sur l’arête reliant deux sommets est
appelée l’intensité de la piste. Il s’agit de l’attractivité du trajet : plus l’intensité
de phéromone disposée sur l’arête entre deux sommets est grande, plus le trajet
aura de chance d’être choisi par les fourmis. La règle aléatoire de transition
proportionnelle proposée par (Bonabeau et al. 99) est la suivante :