|
Le
réseau
Prenons le cas du voyageur de commerce: les villes
sont les nœuds du graphe et les trajets les arêtes.
Tous les trajets entre villes sont possibles: le graphe
est complètement connecté.
On tient compte de la longueur entre villes,
représentée par la distance entre nœuds.
On fera vivre une valeur d'intensité de phéromone pour
chaque arête pour refléter l'expérience accumulée par les fourmis le long du
réseau.
La méthode de recherche des chemins optimums se fait en
lâchant une colonie de fourmis dans le réseau.
L'exploration
Chaque fourmi part d'une ville au hasard. Elle choisit
les villes les plus proches.
Chaque fourmi conserve une mémoire de son passage en
déposant des phéromones lors du trajet de retour (stigmergie).
Une fourmi tient une solution lorsqu'elle est passée
par toutes les villes (nœuds) une seule fois.
Au tour suivant (construction d'une nouvelle solution),
une fourmi choisit un trajet selon un tirage au hasard biaisé par l'intensité
des phéromones.
Actualisation
Quand toutes les fourmis ont réalisé leur construction,
les intensités des phéromones sont mises à jour:
toutes les valeurs sont décrémentées d'un point et
seules celles correspondant à des parcours de qualité
(distances courtes, par exemple) sont augmentées, et cela autant de fois que
de bons parcours construits.
Finalisation
La procédure de construction par les fourmis est
répétée jusqu'à satisfaction d'un critère de fin.
Implémentation
En logiciel, la fourmi est remplacé par un agent logiciel (une fourmi artificielle;
software agent). Il s'agit donc d'un algorithme multi-agents réactifs.
Algorithme assez général (métaheuristique) pour convenir
à de nombreuses applications sans changement profond de la procédure
d'optimisation.
On notera la similitude avec les réseaux neuroniques à
apprentissage où les recherches pertinentes sont récompensées et conservées.
|
