Algorithmes itératifs

Principe


Le principe des métha-heuristiques itératives consiste à prendre une solution initiale (aléatoirement ou en utilisant une heuristique spécialisée) et à améliorer cette solution en cherchant dans son voisinage une solution meilleure.
La notion de voisinage est complexe. Le voisinage d'une solution dépend étroitement de la nature d'une solution.
Si la solution est une séquence, le voisinage d'une solution peut consister en toutes les solutions obtenues par permutation de deux éléments consécutifs (soit [math] (n-1) [/math] permutations si [math]n[/math] est le nombre d'objets de la séquence). Si on cherche un voisinage plus vaste, on peut considérer toutes les permutations de 2 éléments quelconques de la séquence (soit [math] \frac{n \times (n-1)}{2} [/math] permutations).
Si la solution est une partition, le voisinage peut consister en l'ensemble des partitions obtenues en déplaçant un élément.

Descente stochastique


Consiste à appliquer l'algorithme suivant :
  • 1) Choisir une solution initiale,
  • 2) Tant qu'un critère d'arrêt n'est pas atteint faire
  • 3) Choisir aléatoirement une solution voisine
  • 4) Si elle améliore la solution courante, la prendre,
  • 5) Retourner en 2
Le critère d'arrêt est souvent le fait que l'on a testé [math] K [/math] solutions voisines sans une seule amélioration. L'algorithme devient :
  • 1) choisir une solution initiale, n=0
  • 2) tant que [math] n < K [/math]
  • 3) choisir aléatoirement une solution voisine
  • 4) si elle améliore la solution courante, la prendre, et n=0, sinon n=n+1
  • 5) retourner en 2

Cet algorithme élémentaire peut être utilisé pour tester la qualité d'algorithmes spécialisés. Il suffit d'enchaîner des descentes stochastiques successives en choisissant des solutions initiales différentes, durant le temps d'exécution de l'algorithme spécialisé à tester.
Cet algorithme ne garanti évidement pas une solution optimale, mais il ne garanti pas non plus un optimum locale dans le voisinage.

Méthode du gradient


Contrairement à la descente stochastique, la méthode du gradient explore tout le voisinage. L'algorithme simplifié est le suivant :
  • 1) choisir une solution initiale,
  • 2) évaluer toutes les solutions du voisinage
  • 3) choisir la meilleure
  • 4) si elle améliore la solution courante, la prendre, et retourner en 2)
  • 5) fin

Cet algorithme garanti un optimum local, puisqu'aucune solution du voisinage n'améliore la solution. En revanche, cet optimum n'est pas forcément un optimum global. Les méthodes suivantes ont pour but de se sortir des optima locaux.

Méthode Tabou


La méthode Tabou a pour but de permettre de sortir d'un optimum local. Sur le même principe que le gradient, cette méthode va parcourir tout le voisinage, mais elle va accepter d'aller vers une solution moins bonne que la solution courante.
Évidement, si on se contente de cette règle, on va vers un problème, car si la solution [math]S[/math] est un optimum local, et qu'on la quitte pour [math]S'[/math], moins bonne que [math]S[/math], mais la meilleure dans le voisinage, comme par réciprocité [math]S[/math] est dans le voisinage de [math]S'[/math], en quittant [math]S'[/math]on risque fort de revenir sur [math]S[/math] et de boucler. Pour éviter cela, on utilise la liste Tabou: C'est une liste des dernières solutions visitées que l'on s'interdit de reprendre à court terme. C'est en quelque sorte l'historique de la recherche. À chaque itération, une nouvelle solution rentre dans la liste Tabou et la plus ancienne en sort.
Malgré tout, il peut se trouver que la meilleure solution autorisée (donc dans le voisinage de la solution [math]S[/math] moins la liste Tabou) soit de bien moins bonne qualité que la solution courante. On peut alors relaxer la contrainte de la liste Tabou en changeant la solution courante par une solution de la liste tabou (cela revient à revenir en arrière, tout en refusant de refaire les mêmes erreurs (grâce à la liste Tabou).
L'algorithme est donc :
[math]V(S)[/math] = voisinage de la solution [math]S[/math]
[math]T(t)[/math]= Liste Tabou à l'itération [math]t[/math]
  • 1) choisir une solution initiale [math]S(0), t=0, T(0)= \varnothing , best=S[/math]
  • 2) [math]t=t+1[/math]
  • 3) S(t)= la meilleure des solutions dans [math]V(S(t))-T(t)[/math]
  • 4) Si elle détériore trop la solution S(t-1) utiliser la fonction d'aspiration pour déterminer S(t)
  • 5) Mettre à jour [math]T(t),Best [/math] si nécessaire
  • 5) Si le critère de fin est atteint, finir, sinon retourner en 2)

Le critère d'arrêt peut être de ne pas avoir amélioré la solution durant les [math]K[/math] dernières itérations.

Recuit simulé


Cette méthode s'apparente plus à la descente stochastique qu'au recuit simulé puisque l'ensemble du voisinage de la solution courante ne sera pas visité.En revanche, pour ne pas rester dans un optimum local, l'algorithme va accepter de sélectionner un voisin qui détériore la solution courante, avec une probabilité donnée, décroissante au cours du temps.
Algorithme:
initialiser S, Sopt=S, Meilleur=Val(S),k←0
Tant que [math]k <= kmax [/math]

Choisir S' dans V(S), calculer Val(S')
si Val< Meilleur alors Sopt ← S', Meilleur ← Val(S')
si [math] P \left( S', S, k \right)> alea())[/math] alors S←S'
k ← k + 1

retourner Sopt

Cet algorithme utilise comme critère d'acceptation le critère dit de Metropolis qui consiste à accepter la nouvelle solution avec une probabilité P(S', S, T)égale à:

  • 1 si Val(S') < Val(S)
  • [math] exp{\left( \displaystyle \frac {Val(S)-Val(S')}{T} \right)} [/math] sinon.

T est un paramètre qui mesure une température et qui fait qu'à haute température, si T est grand, [math] \displaystyle \frac {Val(S)-Val(S')}{T} [/math] est proche de 1 et donc on aura tendance à accepter de choisir des solutions qui dégradent la solution courante, alors que si la température se rapproche de 0, alors l'algorithme se comportera comme une descente stochastique.
Dans l'algorithme proposé, la température est calculée comme [math]k/kmax[/math]. Elle décroit donc quand k augmente, pour atteindre 1.
Dans d'autre version de cet algorithme, la température décroit par pallier.
Il a été montré que l'algorithme du recuit simulé converge vers la solution optimale, mais la preuve de convergence utilise le fait que l'ensemble des réels est fini lorsque l'on utilise un ordinateur, et que le temps peut être poursuivi à l'infini. Autrement dit, dans la pratique, ce résultat est inutilisable et cette méta-heuristique ne converge pas plus que les autres vers l'optimum global.

Références


http://en.wikipedia.org/wiki/Reactive_search_optimization
Un excellent document sur la recherche Tabou :
http://www.ifi.uio.no/infheur/Bakgrunn/Intro_to_TS_Gendreau.htm
Pour le recuit simulé, attention au site wikipedia français, il contient des erreurs. Voir plutôt; http://en.wikipedia.org/wiki/Simulated_anealing
Kirkpatrick, S.; C. D. Gelatt, M. P. Vecchi (1983-05-13). "Optimization by Simulated Annealing". Science. New Series 220 (4598): 671-680
Granville V., M. Krivánek, J. P. Rasson "Simulated annealing: A proof of convergence". IEEE Transactions on Pattern Analysis and Machine Intelligence 16 (6): 652-656. June 1994