Théorie des graphes et algorithmes

Structure générale des méthodes d'amélioration par voisinage

Dans cette partie, nous allons tout d'abord définir la notion de voisin, puis nous présentons les différents schémas d'algorithmes d'amélioration par voisinage en commençant par les heuristiques simples et en terminant par les méta-heuristiques.

Comme pour les algorithmes génétiques, nous nous intéressons à la résolution de problèmes d'optimisation et nous souhaitons explorer l'ensemble des solutions de manière à en extraire une solution aussi bonne que possible sans garantie que la meilleure solution trouvée soit optimale.

DéfinitionVoisin

Voisin est un opérateur unaire qui à une solution S fait correspondre une solution v(S), en appliquant une modification (généralement locale) à la solution S.

Une solution S peut avoir plusieurs voisins.

V(S) est l'ensemble des voisins de S.

v(S) est un des voisins de S (choisi, par exemple, de manière aléatoire).

Présentation intuitive et algorithmique des méthodes de voisinage

Pour présenter les méthodes par voisinage, nous allons illustrer l'approche en nous appuyant sur la démarche d'un aveugle ou d'un mal voyant qui doit rechercher le point le plus bas d'une montagne.

Espace des évaluations de l'espace des solutions

La montagne ci-contre représente les variations du niveau de la fonction à minimiser en supposant que l'on peut étaler les solutions du problème sur une surface et représenter les valeurs de la fonction à minimiser par une altitude en chaque point de la surface.

L'objectif est de trouver le fond de la vallée.

Exploration locale de l'espace des solutions : solution initiale

Un aveugle est parachuté en un point de départ quelconque xo sur la surface.

L'aveugle est muni d'un appareil lui permettant de mesurer son altitude (valeur de la fonction objective à minimiser au point où il se trouve), son positionnement (paramètres décrivant la solution associée au point où il se trouve) et capable en outre de transmettre ces mesures à un système central.

Il est également muni d'une canne qui lui permet de tâter autour de lui de manière à explorer le voisinage du point où il se trouve.

Son voisinage est d'autant plus important que sa canne est grande.

Il est capable d'examiner toutes les solutions de son voisinage qui sont à portée de sa canne et de connaître leur altitude.

Première méthode : méthode de plus forte pente

L'aveugle cherche le point le plus bas de son voisinage et s'y rend s'il est strictement plus bas que le point où il se trouve.

Sinon, il reste où il est et conclut qu'il a atteint le point le plus bas du paysage.

Description de la méthode de plus forte pente

Initialisation

xo est une solution choisie de manière aléatoire ou obtenue en utilisant une heuristique simple construisant une solution.

f(xo) est la valeur de la fonction objective à minimiser au point xo.

FIN = faux ;

Itérations

tantque FIN == faux faire

    FIN = vrai ;

    meilleur = xo ;

    mini = f(meilleur) ;

    pour tout x de V(xo) faire

        nouveau = f(x);

        si (f(x)<mini) alors

            FIN = FAUX ;

            meilleur = x ;

            mini = f(meilleur);

        finsi ;

    fin pour tout x ;

    xo = meilleur;

fin tant que

xo et meilleur contiennent la meilleure solution trouvée

La méthode s'arrête dans un optimum local lorsque aucun point du voisinage n'est strictement meilleur que le point où se trouve l'aveugle.

Si l'aveugle tombe sur un glacier, juste à côté d'une profonde crevasse. Il va rapidement croire qu'il a atteint le bas de la montagne et s'arrêter.

Attention

S'il y a une zone plane autour de l'aveugle, on pourrait penser qu'il pourrait encore progresser si on acceptait qu'il se déplace pour une altitude égale à celle où il se trouve.

Mais dans ce cas, l'algorithme pourrait se mettre à boucler sur un sous-ensemble de solutions voisines qui ont toute la même valeur.

On verra plus loin une méthode qui cherche à éviter type de problème.

Amélioration de toute méthode qui se termine sur un minimum local

On applique la même méthode avec plusieurs points de départ aléatoires.

Ce qui, dans notre présentation intuitive, revient à parachuter un escadron d'aveugles dans des points les plus éloignés possibles les uns des autres sur la montagne.

Remarque

Si le voisinage est grand, cela peut prendre beaucoup de temps pour examiner le voisinage complet d'un point, sauf si on dispose d'une technique pour trouver rapidement le meilleur point du voisinage (sans obligatoirement tout explorer).

C'est pour cette raison que beaucoup de méthodes par voisinage se contente du premier point visité meilleur que le point où on se trouve.

Seconde méthode : Méthode de descente ou "hill climbing"

L'aveugle choisit le premier point qu'il examine lui permettant de diminuer strictement son altitude.

Remarque

Ou bien l'aveugle examine toujours son voisinage de manière systématique et sait quand il a fini d'explorer son voisinage sans avoir obtenu une amélioration.

Ou bien l'aveugle choisit un voisin de manière totalement aléatoire.

En cas de choix aléatoire, on est néanmoins obligé de faire une exploration systématique du voisinage, si, par exemple, après N essais on n'a pas changé de position. Si on ne faisait pas ce test, l'algorithme pourrait boucler sur chercher un voisin du point où on se trouve de manière aléatoire pour essayer d'en trouver un meilleur.

Dans tous les cas, on arrête l'algorithme de la même façon que dans le cas de la méthode de descente.

Description de la méthode de descente

Initialisation

xo est une solution choisie de manière aléatoire ou obtenue en utilisant une heuristique simple construisant une solution.

f(xo) est la valeur de la fonction objective à minimiser au point xo.

FIN = faux ;

J = 0;

Itérations

tantque FIN == faux faire

    FIN = vrai ;

    x = v(xo) ;

    si(f(x)<f(xo) alors

        FIN = FAUX;

        J = 0 ;

        xo = x ;

    sinon

        J = J+1;

        si J > N alors

              vérification pour voir si on est dans un optimum local

            meilleur = xo ;

            mini = f(meilleur) ;

            pour tout x de V(xo) (tant que FIN == VRAI) faire

                nouveau = f(x);

                si (f(x)<mini) alors

                    FIN = FAUX ;

                    meilleur = x ;

                    mini = f(meilleur);

                finsi ;

            fin pour tout x ;

            xo = meilleur;

        fin si ;   fin de la vérification pour voir si on est dans un optimum local

    fin si ;  fin du cas initialement non améliorant

fin tant que  fin de la progression d'un pas de l'aveugle

xo et meilleur contiennent la meilleure solution trouvée

Troisième méthode : marche stochastique

Cette méthode n'est en général pas enseignée, nous la présentons ici car c'est en fait une méthode intermédiaire entre la méthode précédente et la méthode du recuit simulé que nous verrons ensuite.

Nous ne décrivons pas l'algorithme correspondant.

L'aveugle erre de manière totalement aléatoire, on retient la meilleure position visitée.

Arrêt par fatigue (après avoir visité N points).

Inconvénient : si la surface a des régularités avec des pentes vers les positions les plus basses, on ne profite absolument pas de la configuration du paysage.

Avantage : on n'est jamais piégé dans un optimum local.

Quatrième méthode : Marche stochastique hybridée de plus forte pente.

Cette méthode n'est en général pas enseignée, nous la présentons ici car elle a été expérimentée avec un certain succès un problème d'optimisation.

Nous ne décrivons pas l'algorithme correspondant.

En alternance, on choisit un voisin aléatoire et en alternance on retient la meilleure solution visitée

Arrêt par fatigue (après avoir visité N points).

Elle corrige partiellement l'inconvénient de la méthode précédente.

Avantage : on n'est jamais piégé dans un optimum local.

Cinquième méthode : le recuit simulé

Au départ l'aveugle est plein d'énergie et il accepte aléatoirement de remonter si la remontée n'est pas trop forte et si son énergie est suffisante.

L'aveugle perd progressivement son énergie et on termine par une méthode de descente lorsqu'il n'a plus d'énergie.

Cette méthode est issue de la thermodynamique en recherchant à reproduire un recuit simulé dans un algorithme.

Inspiration à partir de la thermodynamique

Pour que la structuration finale d'un corps soit harmonieuse, il est nécessaire qu'il passe par des phases intermédiaires moins favorables pour atteindre son état final, état qu'il ne pourrait peut-être jamais atteindre si on cherchait une suite d'états qui tendent de manière uniforme et régulière vers l'état souhaité.

A haute température, le corps passe par de nombreux stades de transformation qu'il atteint facilement grâce à l'énergie liée à la température,

plus la température baisse et plus les transformations sont régulières et orientées vers l'état final.

Notations utilisées dans l'algorithme

  • une température T qui décroît par paliers de longueur N de manière exponentielle, par l'utilisation du paramètre a (0<a<1).

  • un générateur aléatoire de voisins VOISIN(x) qui fournit au hasard une solution (admissible) dans le voisinage de la solution (admissible) x.

  • une fonction objective f(x) que l'on cherche par exemple à minimiser.

  • la meilleure solution trouvée depuis le début xm et sa valeur fm.

  • un nombre maximal d'itérations sans amélioration Q

  • on répète P fois l'algorithme avec un nouveau point de départ aléatoire.

Schéma général du refroidissement

pour k de 1 à P faire

  un essai

  Initialisation de l'essai

  xo:=solution aléatoire;  Solution de départ

  fm:=f(xo);  Initilisation meilleure valeur

  J:=0;  Initialisation compteur arrêt

  T:=To;  Initialisation Température

 Déroulement de l'essai

  tantque J ≤ Q faire

    Palier température

    I:=0; Initialisation compteur palier

    Boucle sur les essais élémentaires au sein du palier   

    ........................

    ........................

    (les détails sont dans le listing suivant)

    Fin palier température

    T:=T*a;

  fintantque

  retenir fm , xm;

finpour (k) Fin essai

Le résultat est lameilleure solution trouvée par l'ensemble des essais.

Boucle interne à température constante

tantque I ≤ N et J ≤ Q faire

  x1:=VOISIN(xo); une tentative de progression

  I:=I+1; incrémentation du compteur pour le palier de température

  J:=J+1; incrémentation du compteur pour l'arrêt final d'un essai

  si f(x1) < f(xo) alors

      xo:=x1;

      si f(xo)<fm alors

          xm:=xo;

          fm:=fo;

          J:=0;

      finsi;

  sinon

      ∆f:=f(x1)-f(xo);

      U:=Uniforme(0,1);

      si U ≤ exp (- ∆f / T) alors

            xo:=x1

      finsi

  finsi;

fintantque

Remarque

Si le point x1 est strictement meilleur que le point xo. Il remplace xo et si la solution est meilleure que la meilleure solution trouvée dans l'essai, on corrige la meilleure solution trouvée et on remet à 0 le compteur de fin.

Si le point x1 n'est pas strictement meilleur que le point xo. Il remplace xo avec la probabilité exp(-perte/température).

La probabilité d'accepter de passer à un point plus mauvais est donc d'autant plus grande que la perte est faible et que la température est grande.

Sixième méthode : La méthode Taboue et ses variantes

Comme le recuit simulé, la méthode Taboue permet d'accepter des solutions plus mauvaises de manière à éviter de se faire piéger dans un optimum local.

La méthode Taboue utilise la mémoire de manière à éviter de repasser plusieurs fois par les points visités.

On accepte de remonter pour pouvoir quitter les optima locaux, mais pour ne pas y retomber, on place des « tabous » qui empêchent de retourner aux points déjà visités.

Sur notre présentation intuitive, nous avons ajouté un petit chien qui peut renifler et refuser que l'aveugle repasse là où il est déjà passé.

Avantage : la méthode ne peut pas boucler.

Inconvénient : si on garde la description de toutes les solutions déjà visitées, le besoin en mémoire peut être très grand et en outre, on passe de plus en plus de temps à tester si la nouvelle solution a déjà été visitée en la comparant à toutes celles qui sont en mémoire.

Phénomène de blocage de la méthode Taboue

Si lorsque l'on atteint un point, on a visité auparavant tous ses voisins, alors la méthode s'arrête sur ce point puisqu'on ne trouve plus de voisins non visités du point courant.

Première variante de la méthode Taboue

Pour éviter d'encombrer inutilement la mémoire et de perdre trop de temps à comparer un point avec tous les points déjà visités, on limite à L le nombre de points visités que l'on conserve en mémoire et on appelle cette liste de L points la liste Taboue L.

Remarque

Le fait de limiter à L la taille de la liste Taboue ne fait pas totalement disparaître les problèmes de blocage, sauf si L est vraiment très petit.

Phénomène de bouclage

Si L est trop petit, le fait que les points les plus anciennement visités disparaissent fait que l'on peut retomber sans cesse dans le même optimum local.

Deuxième variante de la méthode Taboue

Souvent, la méthode VOISIN possède un inverse.

Par exemple, pour le codage binaire : si on a inversé la valeur du gène i, alors on revient au point précédent en inversant à nouveau le gène I.

De même, pour le codage de permutation : si on a échangé la valeur des gènes i et j, alors on revient au point précédent en échangeant à nouveau la valeur des gènes i et j.

Une variante de la méthode Taboue consiste à mettre dans la liste Taboue, non pas des solutions, mais la liste des mouvements inverses qui permettraient de revenir aux solutions précédentes (en les suivant dans l'ordre).

C'est une variante très utilisée.

En général, cette méthode ne conduit à aucun blocage, par contre, on peut boucler.

PrécédentPrécédentSuivantSuivant
AccueilAccueilImprimerImprimerRéalisé avec Scenari (nouvelle fenêtre)