Sommaire

Synthèse

Ce chapitre a présenté cinq algorithmes classés comme métaheuristiques. Ceux-ci ont tous pour but de trouver l’optimum d’un problème. S’il est préférable de trouver l’optimum global, lorsqu’il n’existe aucune méthode mathématique pour le faire et que tester toutes les solutions serait trop long, ils sont l’alternative idéale, en permettant de trouver de bons optimums locaux, voire l’optimum global.

Le premier est l’algorithme glouton. Il consiste à construire de manière incrémentale une seule solution, en suivant ce qui semble être le plus adéquat pour atteindre l’optimum.

La descente de gradient part d’une solution aléatoire. À chaque itération, on regarde le voisinage de celle-ci, et on suit la direction la plus prometteuse. Lorsque plus aucune amélioration n’est disponible dans le voisinage, c’est que l’optimum local a été atteint. Cet algorithme est simple et fonctionne bien, mais il est souvent bloqué dans des optimums locaux et ne trouve donc pas forcément l’optimum global.

La recherche tabou a été créée pour permettre d’améliorer la recherche de gradient. En effet, au lieu de se déplacer de position en position en suivant une progression, on se déplace vers le meilleur voisin accessible, qu’il soit ou non meilleur que nous. Ainsi, on ne reste ...