186
Recherche opérationnelle
exemples à l'optimum, mais compte tenu du caractère de bon sens du critère utilisé pour
spécifier les variables, on peut penser qu'il ne s'agit pas d'une trop mauvaise solution
(dans la plupart des cas).
De même, pour le problème du voyageur de commerce, des procédures gloutonnes
simple peuvent être utilisées : ainsi, on peut partir d'un sommet et chercher le sommet le
plus proche (arc de valeur minimale), puis faire la même chose à partir du nouveau
sommet, et ainsi de suite (en ne choisissant jamais un sommet déjà rencontré) jusqu'à
« reboucler » sur les sommets de départ. Cela dit, sur de nombreux cas, une telle
méthode intuitive peut aboutir à une solution très éloignée de l'optimum.
Ce sont des algorithmes qui, par définition, sont rapides. Cependant, ils ne sont pas
« sûrs » : la solution obtenue risque fort d'être médiocre. C'est pourquoi ils sont surtout
utilisés pour initialiser les techniques plus sophistiquées que nous allons maintenant
aborder.
8.2.3. Les méthodes de voisinages
Définissons d'abord ce que l'on entend par voisinage d'une solution :
C'est un sous-ensemble
associé à une solution grâce à une fonction de voisinage
.
)
(x
V
x
g
La fonction a un caractère « local », c'est-à-dire elle change marginalement la solution .
Pour bien faire comprendre cette notion, le mieux est de prendre des exemples :
1) Dans le problème de sac à dos ou plus généralement de programmation linéaire en
variables bivalentes, la solution peut être considérée comme codée par une suite de
nombres égaux à
Une fonction possible consiste par exemple à remplacer un
de ces éléments par son complément à .
Ainsi, la solution
devient
, le cinquième élément ayant été
complémenté.
On voit que cette fonction g simple (un élément quelconque complémenté) fournit un
voisinage de comportant éléments.
On peut imaginer évidemment d'autres fonctions (comme celle consistant à intervertir
deux éléments de la liste)
2) Pour le problème du voyageur de commerce non orienté, une transformation connue
consiste à prendre deux arêtes non adjacentes et à les remplacer par deux autres
permettant de reconstituer un cycle hamiltonien. Ainsi :
Recherche opérationnelle
exemples à l'optimum, mais compte tenu du caractère de bon sens du critère utilisé pour
spécifier les variables, on peut penser qu'il ne s'agit pas d'une trop mauvaise solution
(dans la plupart des cas).
De même, pour le problème du voyageur de commerce, des procédures gloutonnes
simple peuvent être utilisées : ainsi, on peut partir d'un sommet et chercher le sommet le
plus proche (arc de valeur minimale), puis faire la même chose à partir du nouveau
sommet, et ainsi de suite (en ne choisissant jamais un sommet déjà rencontré) jusqu'à
« reboucler » sur les sommets de départ. Cela dit, sur de nombreux cas, une telle
méthode intuitive peut aboutir à une solution très éloignée de l'optimum.
Ce sont des algorithmes qui, par définition, sont rapides. Cependant, ils ne sont pas
« sûrs » : la solution obtenue risque fort d'être médiocre. C'est pourquoi ils sont surtout
utilisés pour initialiser les techniques plus sophistiquées que nous allons maintenant
aborder.
8.2.3. Les méthodes de voisinages
Définissons d'abord ce que l'on entend par voisinage d'une solution :
C'est un sous-ensemble
associé à une solution grâce à une fonction de voisinage
.
)
(x
V
x
g
La fonction a un caractère « local », c'est-à-dire elle change marginalement la solution .
Pour bien faire comprendre cette notion, le mieux est de prendre des exemples :
1) Dans le problème de sac à dos ou plus généralement de programmation linéaire en
variables bivalentes, la solution peut être considérée comme codée par une suite de
nombres égaux à
Une fonction possible consiste par exemple à remplacer un
de ces éléments par son complément à .
Ainsi, la solution
devient
, le cinquième élément ayant été
complémenté.
On voit que cette fonction g simple (un élément quelconque complémenté) fournit un
voisinage de comportant éléments.
On peut imaginer évidemment d'autres fonctions (comme celle consistant à intervertir
deux éléments de la liste)
2) Pour le problème du voyageur de commerce non orienté, une transformation connue
consiste à prendre deux arêtes non adjacentes et à les remplacer par deux autres
permettant de reconstituer un cycle hamiltonien. Ainsi :