3.2.4 Dynamique
Dans le but d'utiliser efficacement les composantes
précédentes, des paramètres dynamiques ont
été inclus. Premièrement, les caractéristiques
d'une fourmi peuvent évoluer tout au long de la résolution du
problème. Quand le coût de la solution d'une fourmi dépasse
la valeur de la meilleure solution trouvée d'un coefficient fixé,
la fourmi est supprimée, avant même son retour au
dépôt. Ce coefficient est donné par 1.5 + (nombre de
produits + nombre de marchés)/100. Cette formule propose un bon
compromis entre la suppression de fourmis qui ont tendance à trouver de
mauvaises solutions et la préservation de la diversité quand les
instances sont importantes. Quand une fourmi est supprimée, elle perd un
point et repart du dépôt. Chaque fourmi reçoit initialement
10 points. Quand une fourmi a épuisé son stock de points, elle
est définitivement supprimée et une nouvelle fourmi est
créée. Cette nouvelle fourmi est définie comme un clone de
la fourmi ayant trouvé la meilleure solution connue, avec de
légères variations dans ses paramètres (d, a, s, v), afin
d'éviter une convergence trop rapide vers un ensemble de fourmis
identiques. Le nombre de points est augmenté de 50 quand une fourmi
améliore la meilleure solution connue. De cette façon, les
meilleures fourmis sont préservées, et les fourmis visitant des
espaces de recherche peu intéressants sont supprimées.
Deuxièmement, une amélioration pour l'aspect
Multi-Dimensional est d'avoir un nombre variable d'étages. Chaque fois
qu'une fourmi est supprimée, l'étage où elle se trouve
perd un point. Le stock de points est ramené à sa valeur
initiale, 100, quand une fourmi de cet étage améliore la
meilleure solution connue. Quand un étage de phéromone a
épuisé son stock de points, cet étage est supprimé.
Cela permet de concentrer l'effort de recherche sur les étages les plus
prometteurs. Néanmoins, le processus
de suppression des étages est arrêté
lorsque le nombre d'étages est égal à 10, afin de
préserver une diversité dans les solutions. À ce
moment-là, au lieu d'être supprimés, les étages sont
fusionnés avec l'étage de phéromone sur lequel la
meilleure solution connue a été trouvée. La fusion
consiste en l'addition des quantités de phéromones pour chaque
arc. On peut noter que lorsqu'un étage est supprimé, les fourmis
évoluant sur cet étage sont aussi supprimées. La figure 4
présente l'algorithme de la procédure DMD-ATA.
Algorithme 4 : Algorithme DMD-ATA
1 Initialisation: Calculer une première
solution réalisable et en mémoriser le coût;
2 tant que la limite de temps n'est pas
dépassée faire
3 pour chaque étage de
phéromone k faire
pour chaque chaque fourmi j sur chaque
étage k faire
Déplacer j vers le prochain marché;
si j retourne au dépôt
alors
Ajouter de la phéromone sur la route de j selon
la qualité de la solution trouvée;
si j a trouvé une meilleure solution
que la meilleure solution connue alors Mémoriser
j;
Relancer j; sinon
si j n'est pas efficace
alors
Supprimer j;
Enlever un point de j;
si j a épuisé son stock de
points alors
Supprimer j et cloner la meilleure fourmi actuelle;
Relancer j;
Évaporer la phéromone sur l'étage
k;
si l'étage k a épuisé
son stock de points alors
si il y a plus de 10 étages de
phéromone alors Supprimer k;
sinon
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
Fusionner k avec le meilleur étage;
|
| 
