En complément de la programmation mathématique, les heuristiques sont des méthodes de résolution purement algorithmiques qui permettent d’obtenir des solutions à n’importe quel problème décisionnel rapidement. En effet, dans certains cas, le prix à payer pour utiliser des méthodes de programmation mathématique peut être une très grande complexité mathématique qui se traduit par des temps de calculs souvent longs. Parce qu’en pratique, une solution à un problème décisionnel doit être proposée dans des temps raisonnables, on sacrifie en partie la qualité de la solution au sens purement mathématique pour accélérer le processus de résolution.
Une heuristique est une stratégie de bon sens pour se déplacer intelligemment dans l’espace des solutions, afin d’obtenir une solution approchée, la meilleure possible, dans un délai de temps raisonnable.
Deux types d’heuristiques sont principalement utilisées : les heuristiques de construction (par exemple les méthodes gloutonnes), qui construisent itérativement une solution, et les heuristiques de descente, qui à partir d’une solution donnée cherchent un optimum local.
Les heuristiques sont dépendantes du problème à résoudre, principalement dans le choix du voisinage (donc dans le déplacement dans l’espace des solutions).
Des heuristiques plus poussées ont été mises au point et ont données naissance à une nouvelle famille d’algorithmes : les méta-heuristiques.
Le but d’une méta-heuristique, est de réussir à trouver un optimum global. Pour cela, l’idée est à la fois de parcourir l’espace de recherche, et d’explorer les zones qui paraissent prometteuses ; mais sans être « piégé » par un optimum local.
Les méta-heuristiques sont souvent inspirées de processus naturels et sont de plus en plus hybridées avec d’autres méthodes de recherche opérationnelle.
Les principales méta-heuristiques utilisées pour résoudre des problèmes à variables discrètes sont :
- le recuit simulé, qui explore l’espace de recherche tout en acceptant de dégrader sa solution afin de sortir des optima locaux. Tout au long du processus, le recuit va de moins en moins accepter ces dégradations, ce qui va le faire converger vers un optimum (que l’on espère) global.
- la recherche avec tabous, qui a l’inverse du recuit simulé est déterministe et a une notion de mémoire. Le choix du meilleur voisin d’une solution pousse l’algorithme à trouver les optima locaux ; et comme l’exploration de l’espace de recherche est effectué en limitant le voisinage de la solution en rendant « tabous » certains mouvements, l’algorithme doit théoriquement visiter l’optimum global.
- les algorithmes évolutionnaires, issus de la théorie de l’évolution de Darwin, qui manipulent plusieurs solutions en même temps, et qui en les combinant forment de nouvelles solutions. Le fait d’avoir une population de solutions facilite l’exploration de l’espace de recherche, et les meilleures solutions seront favorisées pour participer à la création de nouvelles solutions ce qui aura pour effet de favoriser les combinaisons des « bonnes caractéristiques », et donc de trouver un optimum global.