3.2 Notre algorithme : le DMD-ATA
L'algorithme DMD-ATA propose une
implémentation originale de l'algorithme d'optimisation par Colonie de
Fourmis. Il reprend entre autres des améliorations proposées
précédemment dans la littérature pour l'optimisation par
Colonie de Fourmis.
Dans nos travaux, une fourmi est un agent qui se
déplace de marché en marché sur un graphe de TPP. Les
fourmis ont tendance à préférer les marchés
connectés par des arcs sur lesquels il y a une grosse quantité de
phéromone et qui sont aussi prometteurs selon un critère
heuristique. Quand une fourmi a acheté tous les produits, elle ne
retourne pas au dépôt immédiatement. Elle a la
possibilité de visiter quelques marchés supplémentaires
tandis que la probabilité de retourner au dépôt augmente.
Quand une fourmi a fini son tour, elle dépose sur les arcs faisant
partie de son tour une quantité de phéromone proportionnelle
à la qualité du tour. De plus, si une fourmi a
amélioré la meilleure solution trouvée jusqu'ici, la
solution correspondante est stockée. L'évaporation de la
phéromone est implémentée en introduisant un coefficient
d'évaporation : à chaque itération, la quantité de
phéromone présente sur chaque arc est réduite de 0.1%.
Les prochaines sections décrivent respectivement les
différents composants de l'algorithme DMD-ATA : TA (Fourmis
Parallèlles ou Traveling Ants), A (Anamorphiques), MD (plans
Multi-Dimensionnels) et D (Dynamiques).
3.2.1 Fourmis Parallèles
Dans l'implémentation originale de l'algorithme
d'optimisation par Colonie de Fourmis, chaque fois qu'une fourmi rentre au
dépôt, une nouvelle fourmi en part. Pour résumer, le
Traveling Ants correspond au fait que les fourmis travaillent en
parallèle. L'idée est d'avoir un ensemble de fourmis, cherchant
en parallèle de bonnes solutions pour le TPP et communiquant par le
biais de la phéromone. Chaque fourmi construit une solution du TPP de
manière itérative : on ajoute un nouveau marché à
sa solution partielle en exploitant les informations acquises par les
expériences et un critère heuristique. L'expérience est
modélisée sous la forme de la phéromone
déposée par les fourmis sur les arcs du TPP.
Quand une fourmi rentre au dépôt, une
quantité de phéromone est déposée sur les arcs qui
ont été visités par la fourmi. La quantité de
phéromone déposée dépend de la qualité de la
solution trouvée par la fourmi. Ce dépôt a posteriori de
phéromone permet d'éviter le dépôt de
phéromone sur des arcs appartenant à des tours de mauvaise
qualité, puisque la phéromone n'est déposée que
lorsque la fourmi rentre au dépôt, et donc que la qualité
de la solution est connue. Au stade initial de la résolution, la
quantité de phéromone est la même pour tous les arcs.
Une fois que la fourmi rentre au dépôt, elle
commence un nouveau tour. Comme les chemins qu'elles empruntent ont des
longueurs différentes (en terme de nombre de marchés), les
fourmis ne sont pas synchronisées. Ce traitement permet un meilleur
contrôle sur les fourmis et des mises à jour des phéromones
plus précises.
| 
