CHAPITRE II. METHODES D'OPTIMISATION
pas à pas la solution, en allant d'une ville à
l'autre. Afin de ne pas revenir sur ses pas, une fourmi tient à jour une
liste, disant quelle est similaire à celle de la liste taboue, qui
contient la liste des villes déjà visitées.
Algorithm : ANT_SYSTEM
1 : A ?ensemble dek fourmis
2 : repeat
3 : for i = 1 to k
do
4 : ConstruireTrajet(i)
5 : end for
6 : MettreàJourPheromones()
7 : until (critère d'arrêt)
Dans la procédure ConstruireTrajet(i),chaque
fourmi construit une route en choisissant les villes selon une règle de
transition aléatoire très particulière : Si P
ij(t) est la probabilité
qu'à l'itération t la fourmi k choisisse d'aller de la ville i
à la ville j alors :
|
P ij(t) =
|
?
??
??
|
(ôij(t))á.çâ
>-I ij
.(ôij(t))á.çâ
ij si j ? j i
i?jk
i
0 sinon.
|
12
ôij(t) : Le taux de
phéromone sur la route ij à l'itération t.
çij : L'inverse de la
distance séparant les villes i et j.
á : paramètre contrôlant
l'inférence du taux de phéromone sur le trajet ij
â : paramètre contrôlant l'inférence
de la distance sur le trajet ij.
En d'autres termes, plus il y a de phéromone sur le
trajet reliant deux villes, plus la
probabilité que la fourmi emprunte ce trajet est
grande.
Lorsque toutes les fourmis ont construit une solution, la
procédure MettreaJourPhero-mones() modifie les taux de
phéromone ô sur les routes en fonction des trajets effectivement
empruntés par les fourmis, selon la formule :
Äô ij(t) =
Q Lk(t) si le trajet
ij est dans la tournée de la fourmi k.
Q : est une constante, etL (t) :est la longueur totale de la
tournée de la fourmi k.
Donc plus la route suivie par la fourmi a été
courte, plus la qualité de phéromone laissée
derrière elle est grande.
Pour éviter que des chemins ne se forme trop vite, et
ne convergent trop rapidement vers des optima locaux, on introduit le concept
d'évaporation des pistes de phéromone, au travers du
paramètrep(0 < p < 1) dans la formule complète de mise
à jour suivante :
ôij(t + 1) = (1 -
p).ôij(t) +
Äôij(t). (
Äôij(t) = >-I x=1
Äôx ij et k le
nombre des fourmis).
L'algorithme de colonies de fourmi présenté si
dessus est un algorithme de base qui peut s'adapter à d'autres
problèmes que le voyageur de commerce, en attribuant une signification
plus générale aux facteurs ô et ç.
13
CHAPITRE II. METHODES D'OPTIMISATION
II.2.6 La méthode GRASP
La méthode GRASP (Greedy Randomized Adaptative
Search Procedure) est une Méta- heuristique
développée à la fin des années 90 par Feo et
Resende. Elle est adaptée aux problèmes dont les solutions se
construisent pas à pas.
Son algorithme contient deux phases : une phase pour la
construction et une phase pour l'amélioration des solutions. La phase
d'amélioration sera souvent faite grâce à une autre
méta-heuristique. L'algorithme maintient à jour une liste de
fragments de solutions possibles (RCL, restricted candidate
list). La liste RCL est mise à jour avec des
éléments sélectionnés en fonction d'une heuristique
spécifique, adaptée au problème considéré et
le choix d'un élément dans la RCL pour construire la
solution est aléatoire.
Algorithm: GRASP
1 : s*+- Ø
2 : repeat
3 : s'+- ConstruireSolution(s)
4 : Améliorer(s')
5 : if f(s') < f(s*)
then
6 : s* +- s'
7 : until (critère d'arrêt)
Algorithm : CONSTRUIRE_SOLUTION
1 : s +- Ø
2 : while s n'est pas
complète
3 : RCL +- GenererCandidat(s)
4 : x +- ChoisirAuHasard(RCL)
5 : s+-sU{x}
6 : end
6 : return s
| 
