Une première variante du « Système de
Fourmis » a été proposée : 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éposé 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.
5.4.2.2. Ant-Q
Dans cette variante de AS, la règle de mise à
jour locale est inspirée du « Q learning ».
Cependant, aucune amélioration par rapport a l'algorithme AS n'a pu
être démontrée. Cet algorithme n'est d'ailleurs, de l'aveu
même des auteurs, qu'un pré version du « Ant Colony
System ».
5.4.2.3. Ant Colony System
L'algorithme « Ant Colony System » (ACS)
[47,48,49,50] a été introduit pour améliorer les
performances du premier algorithme sur des problèmes de grandes tailles.
ACS est fondé sur des modifications du AS :
ACS introduit une règle de transition dépendant
d'un paramètre , qui définit une balance diversification/intensification. Une
fourmi k sur une ville i choisira une ville j par la règle :
(5-4)
Ou est une variable aléatoire uniformément distribuée
sur et une ville sélectionnée aléatoirement selon la
probabilité :
(5-5)
En fonction du paramètre , il y a donc deux comportements possibles : si 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é.
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 :
(5-6)
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 :
(5-7)
Où les arêtes appartiennent au meilleur tour T+de longueur L+
et ou. Ici, seule la meilleure piste est donc mise à jour, ce qui
participe à une intensification par sélection de la meilleure
solution.
Le système utilise une liste de candidats. Cette liste
stocke pour chaque ville les plus proches voisines, classées par distances croissantes. Une
fourmi ne prendra en compte une arête vers une ville en dehors de la
liste que si celle-ci a déjà été explorée.
Concrètement, si toutes les arêtes ont déjà
été visitées dans la liste de candidats, le choix se fera
en fonction de la règle (5-5) sinon c'est la plus proche des villes non
visitées qui seront choisies.
, qui définit une balance diversification/intensification. Une
fourmi k sur une ville i choisira une ville j par la règle :
(5-4)
est une variable aléatoire uniformément distribuée
sur 
et 
une ville sélectionnée aléatoirement selon la
probabilité :
(5-5)
, il y a donc deux comportements possibles : si 
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é.
(5-6)
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 :
(5-7)
appartiennent au meilleur tour T+de longueur L+
et ou
. Ici, seule la meilleure piste est donc mise à jour, ce qui
participe à une intensification par sélection de la meilleure
solution.
plus proches voisines, classées par distances croissantes. Une
fourmi ne prendra en compte une arête vers une ville en dehors de la
liste que si celle-ci a déjà été explorée.
Concrètement, si toutes les arêtes ont déjà
été visitées dans la liste de candidats, le choix se fera
en fonction de la règle (5-5) sinon c'est la plus proche des villes non
visitées qui seront choisies.