1.3 1. LES FOURMIS ARTIFICIELLES
Une fourmi artificielle est une entité simple dotée
d'un comportement similaire ou
étendu à celui de la fourmi réelle. Ce
comportement doit être élémentaire, restreint et
donc facile à programmer. A l'intérieur d'une
colonie, les fourmis sont concurrentes et
asynchrones, elles coopèrent inconsciemment ensemble
pour la résolution du problème
considéré. Les fourmis artificielles communiquent
entre elles indirectement par
stigmergie via des modifications de leur environnement (par
exemple par dépôt de
traces de phéromone artificielle) qui représente
la mémoire collective de la colonie.
Elles ont été de plus enrichies des contraintes
et de comportements qu'on ne trouve pas
dans leurs congénères réelles mais qui
sont spécifiques au problème qu'elles
résolvent. [59,60,61,62,63,64,65].
5.1.12. Un problème combinatoire :
Un problème combinatoire est toute situation dont on
cherche d'avoir une solution
tout en respectant la présence d'un ensemble de
contraintes. La solution c'est un
résultat de faire combiner ces contraintes ensemble
d'une manière qu'on maximise
quelques uns et on minimise les autres, ces contraintes ont une
caractéristique
primordiale, c'est que chaque contrainte influe sur les autres
soit quand on minimise sa
valeur ou on la maximise, dans un autre terme on dit que les
contraintes sont
conflictuelles. Par exemple, le schéma suivant
présente une situation de problème
combinatoire: où on veut acheter une voiture dans la
mode et en même temps avec un
prix raisonnable qui ne peut pas dépasser certaine
limite. Si on maximise la première
contrainte (une bonne voiture) on va avoir un prix maximale,
dans le contraire on va
aboutir à une mauvaise voiture mais avec un prix
minimale dans les limites; on constate
dans cet exemple que c'est difficile d'arranger ces deux
contraintes dans nos besoins
[66,67 ,68,69].
Figure 48:Une figure illustrant un problème
combinatoire
1.32. ANT COLONY SYSTEM « ACS »
L'algorithme « Ant Colony System » a été
introduit par « Dorigo » et «
Grambardella » en 1996 pour améliorer la
performance de AS [55] .ACS est basé
essentiellement sur As mais se distingue de lui par les points
suivants : Le déplacement
de la fourmi suit une autre règle de transition dite
règle proportionnelle pseudo-
aléatoire ;Deux méthodes sont utilisées
pour la mise à jour :Une mise à jour locale est
effectuée à chaque fin de cycle d'une fourmi. Une
mise à jour globale est faite une fois
que toutes les fourmis ont terminé leurs cycles. Seule
la fourmi qui a trouvé la meilleure
solution est autorisée à renforcer la
phéromone sur tous les arcs constituant son tour .La
mise à jour globale évite de se bloquer dans des
solutions sous optimal(minimums
locaux).Tandis que la mise à jour locale a pour effet de
réduire, de moins en moins,
l'interactivité des arcs déjà
visités par d'autres fourmis, et donc de favoriser l'émergence
de d'autres solutions que celle déjà
trouvées pendant les prochains cycles de
l'algorithme.
| 
