5.1.13. Ant System (AS-TSP)
Élitisme une première variante du "Système
de Fourmis" a été proposée par
[Dorigo 1996] : elle est caractérisée par
l'introduction de fourmis élitistes. Dans cette
version, la meilleure fourmi (celle qui a effectué le
trajet le plus court) dépose une
quantité de phéromone plus grande, dans l'optique
d'accroître la probabilité des autres
fourmis d'explorer la solution la plus prometteuse.
est la liste Tabou pour la fourmi (i).
désigne l'inverse de la distance entre les villes i et
j.
pondèrent l'influence de la phéromone et de la
longueur.
taux de phéromone entre les villes i et j.
5.1.14. Ant-Q
Dans cette variante de AS, la règle de mise à jour
locale est inspirée du Q-learning
[Gambardella and Dorigo, 1995]. Cependant, aucune
amélioration par rapport à
l'algorithme AS n'a pu être démontrée. Cet
algorithme n'est d'ailleurs, de l'aveu même
des auteurs, qu'une préversion du "Ant Colony System".
est une valeur fournie par une heuristique.
donne la valeur de probabilité de choix
(phéromone).
pondèrent l'influence des deux mesures.
est la probabilité d'utiliser la première
équation.
5.1.15. Ant Colony System (ACS)
L'algorithme a été introduit pour améliorer
les performances du premier
algorithme sur des problèmes de grandes tailles [Dorigo
and Gambardella, 1997b,
Dorigo and Gambardella, 1997a]. ACS est fondé sur des
modifications de l'AS :
1- ACS introduit une règle de transition dépendant
d'un paramètre q0 (0~q0~1),
qui définit une balance diversification /intensification
.Une fourmi k sur une ville i
choisira une ville j par la règle :
Et une ville sélectionnée aléatoirement
selon la probabilité :
En fonction du paramètre q0, il y a donc deux
comportements possibles :
si q>q0 le choix se fait de la même façon que
pour l'algorithme AS, et le système
tend à effectuer une diversification ; si , le
système tend au contraire vers une
intensification. En effet, pour , l'algorithme exploite davantage
l'information
récoltée par le système, il ne peut pas
choisir un trajet non exploré.
2- La gestion des pistes est séparée en deux
niveaux : une mise à jour locale et une
mise à jour globale. Chaque fourmi dépose une piste
lors de la mise à jour locale :
Où est la valeur initiale de la piste. A chaque passage,
les arêtes visitées voient
leur quantité de phéromone diminuer, ce qui
favorise la diversification par la prise en
compte des trajets non explorés. A chaque
itération, la mise à jour globale s'effectue
comme ceci :
Ici, seule la meilleure piste est donc mise à jour, ce qui
participe à une
intensification par sélection de la meilleure solution.
| 
