Chapitre 5
Approche de resolution
5.1 Introduction
La notion de complexité des problèmes est
très importante, car si un problème est identiflé comme
facile, on connait un algorithme fini et effi cace pour le résoudre, par
contre s'il est identiflé comme étant un problème complexe
il sera diffi cile de trouver un algorithme effi cace pour le résoudre,
il est alors justiflé de se contenter d'exigences plus limitées:
résolution approchée du problème posé,
résolution d'un problème voisin plus simple.
L'exécution des méthodes dites exactes
(programmation dynamique, séparation et évaluation) pour la
résolution des problèmes NP-Diffciles risque de prendre un temps
de calcul considérable, notamment si la taille du problème est
très grande.
Afin d'éviter ce genre de situation, on se contente
souvent d'une solution dite approchée donnée par certaines
méthodes appelées "méthodes approchées" ou
"heuristiques", et dont la valeur de la fonction objectif correspondante se
rapproche de celle de la solution exacte. Vu qu'on est en présence d'un
problème non linéaire assez complexe, nous proposons d'utiliser
une "heuristique" comme méthode de résolution.
5.2. Heuristiques[9]
5.2 Heuristiques[9]
Definition:
Heuristique (du grec heuriskêin, << trouver
>> ) est un terme de didactique qui signife l'art d'inventer, de faire
des découvertes. C'est en sociologie, une discipline qui se propose de
dégager les règles de la recherche scientifque. En optimisation
combinatoire, théorie des graphes et théorie de la
complexité, une heuristique est un algorithme qui fournit rapidement (en
temps polynomial) une solution réalisable, pas nécessairement
optimale, pour un problème d'optimisation NP-diffcile. Une heuristique,
ou méthode approximative, est donc le contraire d'un algorithme exact
qui trouve une solution optimale pour un problème donné.
L'intérêt de l'heuristique étant que pour les
problèmes NP-diffciles, la plupart des algorithmes exacts connus sont de
complexité exponentielle et donc sans aucun intérêt en
pratique. On utilise une heuristique pour obtenir une première solution
réalisable dans un processus de résolution exacte.
Généralement une heuristique est conçue pour un
problème particulié, en s'appuyant sur sa structure propre, mais
les approches peuvent contenir des principes plus généraux. On
parle de métaheuristique pour les méthodes approximatives
générales, pouvant s'appliquer a des différents
problèmes. La qualité d'une heuristique peut s'évaluer
selon deux critères scientifques :
1) Critère pratique, ou empirique: on
implémente l'algorithme approximatif et on évalue la
qualité de ses solutions par rapport aux solutions optimales (ou aux
meilleures solutions connues). Ceci passe par la mise en place d'un benchmark
(ensemble d'instances d'un même problème accessible a tous).
2) Critère mathématique: il faut s'assurer que
l'heuristique garantit des performances. La garantie la plus solide est celle
des algorithmes approchés, sinon il est intéressant de
démontrer une garantie probabiliste, lorsque l'heuristique fournit
souvent, mais pas toujours, de bonnes solutions.
| 
