5.4.3. Choix des
paramètres
Pour l'algorithme AS, les auteurs préconisent
que, bien que la valeur de Q ait peu d'influence sur le
résultat final, cette valeur soit du même ordre de grandeur qu'une
estimation de la longueur du meilleur trajet trouvé. D'autre part, la
ville de départ de chaque fourmi est typiquement choisie par un tirage
aléatoire uniforme, aucune influence significative du placement de
départ n'ayant pu être démontrée.
En ce qui concerne l'algorithme ACS, les auteurs conseillent
d'utiliser  , ou  est le nombre de villes et  la longueur d'un tour trouvé par la méthode du plus
proche voisin.
Le nombre de fourmis m est un paramètre
important ; les auteurs suggèrent d'utiliser autant de fourmis que de
villes (i.e. m = n) pour de bonnes performances sur le
problème du voyageur de commerce. Il est possible de n'utiliser qu'une
seule fourmi, mais l'effet d'amplification des longueurs différentes est
alors perdu, de même que le parallélisme naturel de l'algorithme,
ce qui peut s'avérer néfaste pour certains problèmes. En
règle générale, les algorithmes de colonies de fourmis
semblent assez peu sensibles à un réglage fin du nombre de
fourmis.
5.4.4.
Formalisation d'un algorithme de colonie de fourmis
5.4.4.1. Représentation du
problème
Le problème est représenté par un jeu de
solutions, une fonction objective assignant une valeur à chaque solution
et un jeu de contraintes. L'objectif est de trouver l'optimum global de la
fonction objectif satisfaisant les contraintes. Les différents
états du problème sont caractérisés comme une
séquence de composants. On peut noter que, dans certains cas, un
coût peut être associe à des états autres que des
solutions[51,52,53].
Dans cette représentation, les fourmis construisent des
solutions en se déplaçant sur un graphe G = (C; L), ou
les noeuds sont les composants de C et où l'ensemble L
connecte les composants de C. Les contraintes du problème sont
implémentées directement dans les règles de
déplacement des fourmis (soit en empêchant les mouvements qui
violent les contraintes, soit en pénalisant de telles solutions).
5.4.4.2. Comportement des
fourmis
Les fourmis artificielles peuvent être
caractérisées comme une procédure de construction
stochastique construisant des solutions sur le graphe G = (C; L). En
général, les fourmis tentent d'élaborer des solutions
faisables mais, si nécessaire, elles peuvent produire des solutions
infaisables. Les composants et les connexions peuvent être
associés à des pistes de phéromone  (mettant en place une mémoire adaptative décrivant
l'état du système) et à une valeur heuristique  (représentant une information a priori sur le problème,
ou venant d'une source autre que celle des fourmis ; c'est bien souvent le
coût de l'état en cours). Les pistes de phéromone et la
valeur de l'heuristique peuvent être associées soit aux
composants, soit aux connexions figure (5-4)).
Chaque fourmi dispose d'une mémoire utilisée
pour stocker le trajet effectué, d'un état initial et de
conditions d'arrêt. Les fourmis se déplacent d'après une
règle de décision probabiliste fonction des pistes de
phéromone locales, de l'état de la fourmi et des contraintes du
problème. Lors de l'ajout d'un composant à la solution en cours,
les fourmis peuvent mettre à jour la piste associée au composant
ou à la connexion correspondante. Une fois la solution construite, elles
peuvent mettre à jour la piste de phéromone des composants ou des
connexions utilisées. Enfin, une fourmi dispose au minimum de la
capacité de construire une solution du problème.
Fig. (5-4) : Dans un algorithme de colonie de fourmis,
les piste de phéromone peuvent être associées aux
composants (a) ou au connections (b) du graphe représentant le
problème à résoudre.
| 
