Complexité des problèmes et heuristiques
185
Plusieurs développements ont été proposés ensuite pour améliorer cette première version
de l’algorithme. D’abord par Dorigo, Maniezzo et Colormi en 1991, consistant à donner
à la meilleure chaîne un poids additionnel sous forme d’une quantité supplémentaire de
phéromone. Bullnheimern, Hartl et Strauss, 1997 ont proposé de ne retenir que les
meilleures fourmis pour la mise à jour des phéromones. D’autres auteurs, Stützle et
Hoos, 1997, ont proposé une mise à jour de phéromone réservée uniquement à la
meilleure fourmi ayant générée la meilleure solution depuis la première itération de
l’algorithme (Best iteration Ant).
En 1997, Dorigo et Gambadella, proposent une règle de transition différente appelée
Pseudo-random Proportional Rule pour compléter les développements précédents. Ainsi,
à partir d’un sommet , la fourmi choisit de se déplacer vers le sommet comme suit :
Depuis, d’autres algorithmes ont été développés pour résoudre de nouveaux problèmes
combinatoires tels que celui du routage de véhicule [Bul, 99], du problème du sac à dos
multidimensionnel [Ala, 04], des problèmes d’ordonnancement [Shy04] [Lio07].
8.2.2. Algorithmes gloutons
Ce sont les plus simples, et ils reposent sur une considération élémentaire : dans un
problème combinatoire, une solution est composée d'un certain nombre d'éléments (des
variables bivalentes pour le problème du sac à dos, des arcs pour le problème du
voyageur de commerce, des arêtes pour le problème de l'arbre de valeur minimale). Une
solution incomplète sera constituée par des éléments spécifiés (des variables égales à
pour le sac à dos), les autres ne l'étant pas.
A chaque itération, on ajoute un ou plusieurs éléments spécifiés, sans remettre en cause
les spécifications précédentes. On complète ainsi progressivement la solution incomplète
de façon à obtenir à la fin (tous les éléments sont alors spécifiés) une solution réalisable
(mais pas obligatoirement optimale).
Nous avons vu déjà deux exemples de tels algorithmes : pour le problème du chemin de
valeur minimale, l'algorithme de Moore est un algorithme glouton : à chaque itération on
ajoute un sommet à l'ensemble des sommets pour lesquels on connaît la solution, sans
remettre en cause les sommets précédemment trouvés. L'algorithme de Kruskal pour
l'arbre de valeur minimale est aussi glouton : on ajoute à chaque fois une arête aux arêtes
déjà introduites pour constituer progressivement l'arbre optimal.
La caractéristique de ces deux exemples est que l'on obtient ainsi la solution optimale.
Ce n'est évidemment pas le cas des procédures gloutonnes que l'on peut imaginer pour
d'autres problèmes. Par exemple, pour le sac à dos, on peut penser introduire
successivement des variables
, en vérifiant à chaque fois que la contrainte reste
satisfaite (si elle ne l'est pas, on pose la variable sous examen égale à et on essaye une
autre). Un ordre intuitif (que nous avons utilisé ci-dessus pour la procédure
arborescente) par lequel on introduit les variables peut être donné en prenant les ratios
utilité/poids par ordre décroissant. Cette méthode ne conduit pas sur de nombreux
185
Plusieurs développements ont été proposés ensuite pour améliorer cette première version
de l’algorithme. D’abord par Dorigo, Maniezzo et Colormi en 1991, consistant à donner
à la meilleure chaîne un poids additionnel sous forme d’une quantité supplémentaire de
phéromone. Bullnheimern, Hartl et Strauss, 1997 ont proposé de ne retenir que les
meilleures fourmis pour la mise à jour des phéromones. D’autres auteurs, Stützle et
Hoos, 1997, ont proposé une mise à jour de phéromone réservée uniquement à la
meilleure fourmi ayant générée la meilleure solution depuis la première itération de
l’algorithme (Best iteration Ant).
En 1997, Dorigo et Gambadella, proposent une règle de transition différente appelée
Pseudo-random Proportional Rule pour compléter les développements précédents. Ainsi,
à partir d’un sommet , la fourmi choisit de se déplacer vers le sommet comme suit :
Depuis, d’autres algorithmes ont été développés pour résoudre de nouveaux problèmes
combinatoires tels que celui du routage de véhicule [Bul, 99], du problème du sac à dos
multidimensionnel [Ala, 04], des problèmes d’ordonnancement [Shy04] [Lio07].
8.2.2. Algorithmes gloutons
Ce sont les plus simples, et ils reposent sur une considération élémentaire : dans un
problème combinatoire, une solution est composée d'un certain nombre d'éléments (des
variables bivalentes pour le problème du sac à dos, des arcs pour le problème du
voyageur de commerce, des arêtes pour le problème de l'arbre de valeur minimale). Une
solution incomplète sera constituée par des éléments spécifiés (des variables égales à
pour le sac à dos), les autres ne l'étant pas.
A chaque itération, on ajoute un ou plusieurs éléments spécifiés, sans remettre en cause
les spécifications précédentes. On complète ainsi progressivement la solution incomplète
de façon à obtenir à la fin (tous les éléments sont alors spécifiés) une solution réalisable
(mais pas obligatoirement optimale).
Nous avons vu déjà deux exemples de tels algorithmes : pour le problème du chemin de
valeur minimale, l'algorithme de Moore est un algorithme glouton : à chaque itération on
ajoute un sommet à l'ensemble des sommets pour lesquels on connaît la solution, sans
remettre en cause les sommets précédemment trouvés. L'algorithme de Kruskal pour
l'arbre de valeur minimale est aussi glouton : on ajoute à chaque fois une arête aux arêtes
déjà introduites pour constituer progressivement l'arbre optimal.
La caractéristique de ces deux exemples est que l'on obtient ainsi la solution optimale.
Ce n'est évidemment pas le cas des procédures gloutonnes que l'on peut imaginer pour
d'autres problèmes. Par exemple, pour le sac à dos, on peut penser introduire
successivement des variables
, en vérifiant à chaque fois que la contrainte reste
satisfaite (si elle ne l'est pas, on pose la variable sous examen égale à et on essaye une
autre). Un ordre intuitif (que nous avons utilisé ci-dessus pour la procédure
arborescente) par lequel on introduit les variables peut être donné en prenant les ratios
utilité/poids par ordre décroissant. Cette méthode ne conduit pas sur de nombreux