2.3.1.4 Algorithme de Descente
En se basant sur les opérateurs de changement, les
algorithmes de descente permettent d'intensifier la recherche de meilleurs
voisins en partant de S0. Ils permettent ainsi l'obtention des
minimums locaux.
L'Algorithme 2.1 décrit une descente (en
considérant un problème de minimisation) :
Présentation des méthodes de résolution
38
Algorithme 2.1: Algorithme de descente
Soit F : La fonction objectif
Fixer So;
Scourante <-- So ;
répéter
Chercher Ssuivante Tel que
F(Ssuivante) < F(Svoisine)
V Svoisine E VScourante
si F(Ssuivante) <
F(Scourante) alors
Scourante <--- Ssuivante
jusqu'à(F(Scourante)
< F(Ssuivante); SFinale <--
Scourante
2.3.1.5 Critères d'arrêt
Il évident que la méta-heuristique
nécessite un critère prédéfini pour arrêter
la recherche. Ce critère peut être :
- Un nombre maximal d'itérations.
- Un taux d'amélioration donné.
- Un nombre donnéd'itérations sans
amélioration.
Les critères qu'on a adoptéseront décrits
dans les sections 3.2.1.3 et 3.2.2.3.
2.3.2 Recherche Taboue
Cette méta-heuristique a
étéproposée parmi les premières et «elle se
montre très performante sur un nombre considérable de
problèmes d'optimi-sation combinatoire, en particulier les
problèmes d'ordonnancement» [51]. Le principe consiste à
générer le voisinage à partir d'une solution de
départ et à enregistrer momentanément ses traces ( ou
encore l'historique des derniers mouvements) afin de ne pas y revenir, à
chaque itération elle retient le meilleur voisin (non
nécessairement meilleur que la solution de départ) et elle
examine le nouveau voisinage pour en retenir un autre meilleur voisin.
La recherche taboue, et comme indique son nom, est
basée sur la gestion des listes taboue. Plusieurs méthodes et
approches on étéabordées pour gérer ces listes que
se soit en ce qui concerne leurs modes d'actualisation ou encore leurs
longueurs. On a adoptédeux méthodes de gestion de la liste taboue
qu'on illustrera dans le paragraphe suivant.
Présentation des méthodes de résolution
39
2.3.2.1 Gestion de la liste taboue
Une bonne gestion de la liste taboue est primordiale pour
qu'elle puisse bien remplir son rôle. On a fait le choix d'adopter deux
méthodes de gestion de la liste taboue à savoir l'enregistrement
des traces des derniers mouvements et l'enregistrement de la valeur de la
fonction objectif.
Méthode d'interdiction des mouvements :
On enregistre à chaque itération les jobs dont la
permutation a menéà la solution voisine, on illustre la
démarche par l'exemple suivant :
Soit une solution initiale S0 =?
J3J2J1J4
?
Si on travail avec l'opérateur de changement
a-opt (permuter deux jobs voisins) et qu'on retienne la
solution voisine S' 1 =?
J2J3J1J4
?, la liste Taboue de longueur Lliste = 3 étant
initialement vide sera remplie comme suit :
( )
3 . .
Taboue 2 . .
Pour la génération des prochain voisins, si les
deux jobs à permuter sont présents dans la liste sur la
même colonne, on interdit le changement.
Une fois que toutes les cases de la liste ne sont plus vides,
on écrasera le plus ancien élément suivant la règle
FIFO.
Méthode d'interdiction par la fonction objectif:
On utilise la valeur du makespan comme paramètre pour la liste
taboue, de façon d'interdire l'adoption d'un voisin si son makespan se
trouve dans la liste taboue. Exemple :
Soit S' 1 un voisin retenu
avec un makespan = 560. La liste taboue est donc:
Tabouemakespan = (560 . . . .)
Désormais, aucun voisin avec un makespan égale
à 560 ne sera retenu tant que cette valeur est enregistrédans la
liste. Le mode d'actualisation de cette liste est le même que la liste
précédente (règle FIFO).
Après avoir présentéles
différentes propriétés de cette méta-heuristique,
l'Algorithme 2.2 donne l'adaptation retenue.
| 
