La méthode GRASP (Greedy Randomized Adaptative Search Procedure) est un algorithme glouton randomisée.
On va construire des solutions de manière gloutonne, mais en randomisant la décision. C’est-à-dire que comme les autres algorithmes locaux on va choisir la meilleur décision sur l’instant t. Cependant, on a un probabilité de prendre une solutions qui n’est pas optimale au moment t. Lorsque que l’on tombera dans un cas aléatoire, on va choisir une des valeurs aléatoirement.
On va ensuite utiliser la solution gloutonne que l’on vient de construire de manière semi-aléatoire pour effectuer une recherche locale. Cela permet de diversifier nos zones de recherches.
Todo
Changer les photos du cours ci-dessous pour mes propres illustrations
Si , on a une construction purement gloutonne
Si , on a une construction purement aléatoire
Sinon , on a un construction semi-aléatoire
