4.3 Les méthodes approchées
Face au caractère intraitable de certains
problèmes d'optimisation combinatoire, où la solution optimale de
ces problèmes est souvent hors d'atteinte en raison de l'explosion
combinatoire de leur espace de recherche et vu la nécessité de
fournir des solutions de "bonne" qualité en un temps "raisonnable", les
heuristiques [9] deviennent l'unique moyen d'obtenir une bonne solution en un
temps raisonnable.
4.3.1 Les heuristiques classiques
Heuristique « dérivée de mot grec
heuriskêin, trouver » est un terme de didactique qui signifie
l'art d'inventer, de faire des découvertes.
Une heuristique est une méthode spécifique
développée pour résoudre un problème donnée,
elle lui est intimement liée et conçue pour prendre en charge les
caractéristiques de celui-ci et couvrir les propriétés de
ses différentes instances. Ces méthodes sont
généralement basées sur un raisonnement logique ou
intuitif et se doivent d'être simples, rapide et bien sûr de
fournir des solutions de bonne qualité. La difficulté majeur est
toutefois de déterminer une garantie de performance d'une heuristique,
aussi pour un même problème, il existe souvent plusieurs
heuristiques et selon l'instance traitée, leurs performances peuvent
varier, donc il est impossible de dire qu'une heuristique est meilleure qu'une
autre.
Les heuristiques peuvent être classées en deux
catégories :
· Les heuristiques de construction: sont des
méthodes approchées qui démarrent d'une entité
élémentaire quelconque et construisent de proche en proche une
solution réalisable, par exemple la méthode de plus proche voisin
pour le problème PVC.
· Les heuristiques d'amélioration : sont des
méthodes approchées qui démarrent d'une solution
réalisable (probablement moins intéressante), et
l'améliorent de proche en proche. Par exemple, on trouve la
méthode 2-opt (PVC).
66
4.3. LES MÉTHODES APPROCHÉES
On retrouve en général des principes de base
utilisés dans ces heuristiques tels que :
- Principe glouton: ce principe repose sur le choix
définitif des valeurs de la solution, ce qui interdit toute modification
ultérieure. Autrement dit d'après Sakarovitch [9] « Il
consiste à "manger" les élément de la solution dans un
certain ordre sans jamais remettre en question un choix une fois qu'il est
effectué ».
- Principe de construction progressive : c'est une extension
du principe glouton dans la mesure où l'on s'autorise, cette fois-ci,
à modifier des valeurs déjà assignées. On retrouve
par exemple l'algorithme de Ford pour la recherche des chemins optimaux.
- Principe de partitionnement : ce principe repose sur le fait
que résoudre le problème global se révèle souvent
plus complexe que résoudre la somme des sous problèmes qui le
composent. Toute la difficulté réside alors dans le fusionnement
des solutions de chaque sous problème. On retrouve par exemple
l'algorithme de Dichotomie.
67
4.3. LES MÉTHODES APPROCHÉES
| 
