Algorithme de recherche locale
Un algorithme de recherche locale est un algorithme qui permet d’améliorer une solution à un problème d’optimisation en explorant des solutions voisines. Un problème d’optimisation consiste à trouver la meilleure solution parmi un ensemble de solutions possibles, selon un critère de qualité. Par exemple, le problème du voyageur de commerce consiste à trouver le circuit le plus court qui passe par toutes les villes d’une liste. Une solution à ce problème est un circuit, et le critère de qualité est la longueur du circuit. Un algorithme de recherche locale part d’une solution initiale, souvent choisie au hasard, et la modifie légèrement pour obtenir une solution voisine. Si la solution voisine est meilleure que la solution actuelle, selon le critère de qualité, elle devient la nouvelle solution actuelle. Sinon, elle est rejetée. L’algorithme répète ce processus jusqu’à ce qu’il ne trouve plus de solution voisine meilleure, ou qu’il atteigne un nombre maximal d’itérations. L’algorithme de recherche locale ne garantit pas de trouver la solution optimale, mais il peut trouver une solution satisfaisante en peu de temps.
Exemple :
Reprenons l’exemple du problème du voyageur de commerce. Supposons que nous ayons une liste de 5 villes : A, B, C, D et E. Une solution initiale, choisie au hasard, est le circuit A-B-C-D-E-A, qui a une longueur de 20 km. Pour obtenir une solution voisine, nous pouvons échanger deux villes dans le circuit. Par exemple, si nous échangeons B et D, nous obtenons le circuit A-D-C-B-E-A, qui a une longueur de 18 km. Cette solution voisine est meilleure que la solution actuelle, donc elle devient la nouvelle solution actuelle. Nous pouvons continuer à échanger deux villes pour obtenir d’autres solutions voisines, et les comparer à la solution actuelle. Par exemple, si nous échangeons C et E, nous obtenons le circuit A-D-E-B-C-A, qui a une longueur de 16 km. Cette solution voisine est encore meilleure que la solution actuelle, donc elle devient la nouvelle solution actuelle. Si nous ne trouvons plus de solution voisine meilleure, nous arrêtons l’algorithme et nous retournons la solution actuelle comme résultat.
Retourner à l'index du lexique