3.6.2.1 Les heuristiques
Définition 3.6.1. Une heuristique
est un algorithme approché qui permet d'identifier en temps polynomial
au moins une solution réalisable rapide, pas obligatoirement
optimale.
L'usage d'une heuristique est efficace pour calculer une
solution approchée d'un problème et ainsi accélérer
le processus de résolution exacte. Généralement une
heuristique est conçue pour un problème particulier, en
s'appuyant sur sa structure propre sans offrir aucune garantit quant à
la qualité de la solution calculée. Parmi elles, on cite :
méthode de recherche locale,méthodes gloutonnes,...
3.6.2.2 Les méta-heuristiques
Face aux difficultés rencontrées par les
heuristiques pour avoir une solution réalisable de bonne qualité
pour des problèmes d'optimisation difficiles, les
méta-heuristiques ont fait leur apparition [10].
Définition 3.6.2. Les
méta-heuristiques sont plus complets et complexes qu'une simple
heuristique,elles permettent généralement d'obtenir une solution
de très bonne qualité des problèmes dont on ne connait pas
de méthodes exactes pour les traiter ou bien quand la résolution
du problème nécessite un temps élevé ou une grande
mémoire de stockage.
Plusieurs d'entre elles sont souvent inspirées par des
systèmes naturels dans de nombreux domaines tels que : la biologie
(algorithmes évolutionnaires et génétiques) la physique
(recuit simulé), et aussi l'éthologie (algorithmes de colonies de
fourmis).
| 
