Méta-heuristiques
Dans le cas de problèmes très
difficiles, les méta-heuristiques peuvent permettre d'atteindre
une solution. Trois méthodes principales sont alors utilisées
: le recuit simulé, les algorithmes génétiques et
la recherche tabou.
-
Le recuit simulé minimise de manière
stochastique une fonction de coût. C'est une méthode de recherche
locale dans la mesure où l'algorithme procède par de petites
modifications de la solution courante, en autorisant éventuellement
une dégradation temporaire de la qualité de la solution.
-
Les algorithmes génétiques
nécessitent un codage des solutions potentielles semblable
à l'identité génétique. L'algorithme procède
par mutation et croisement de ces codes en sélectionnant les solutions
de qualité élevée.
-
La recherche tabou est une méthode
déterministe qui repose sur une gestion dynamique de deux types
de mémoires : l'une à court terme assure une exploration
intensive, l'autre à long terme assure une diversification. La mémoire
contient des caractéristiques dites tabou i.e. que l'on s'interdit
pour les futures solutions. L'objectif premier est d'éviter une
exploration cyclique pour augmenter l'efficacité de la recherche.