Recherche Tabou en Algorithmes

Les algorithmes de recherche locale sont des algorithmes d'optimisation qui cherchent à trouver la meilleure solution parmi un espace de solutions possibles en explorant uniquement les solutions voisines de la solution courante.

True

<p>La recherche Tabou a été développée dans un cadre particulier par Glover en 1986 et indépendamment par Hansen en 1986. Elle a ensuite été généralisée en 1989-90.</p> Signup and view all the answers

<p>Le principe de base de la recherche Tabou est de poursuivre la recherche de solutions même lorsqu'un optimum local est rencontré. Elle permet des déplacements qui n'améliorent pas la solution actuelle et utilise le principe de mémoire pour éviter les retours en arrière (mouvements cycliques).</p> Signup and view all the answers

<p>La liste tabou représente un ensemble de mouvements ou de solutions qui sont temporairement interdits. Son rôle évolue au cours de la résolution: diversification (exploration de l'espace des solutions) vers intensification.</p> Signup and view all the answers

<p>False</p> Signup and view all the answers

<p>La fonction d'aspiration est un critère qui permet de lever l'interdiction pour une solution si elle est considérée comme prometteuse. Elle permet d'explorer une nouvelle région voisine de s si elle est plus prometteuse que les solutions actuelles. La solution s' doit être voisine de s et avoir une valeur inférieure à la solution actuelle s.</p> Signup and view all the answers

<p>Un mouvement non améliorateur est un mouvement qui nous sortirait d'un minimum local en nous amenant à une solution voisine pire que l'actuelle.</p> Signup and view all the answers

<p>Le problème du <em>job shop</em> est un problème d'ordonnancement sur plusieurs machines. Il est souvent résolu en utilisant la recherche Tabou pour trouver une bonne solution car il est impossible de tester toutes les combinaisons possibles.</p> Signup and view all the answers

<p>L'algorithme de recherche Tabou comprend plusieurs étapes : 1) choisir une solution initiale, 2) appliquer la liste tabou et les critères d'aspiration, 3) choisir la meilleure solution voisine, 4) mettre à jour la liste tabou et les critères d'aspiration, et 5) vérifier la condition d'arrêt.</p> Signup and view all the answers

<p>Le nombre d'itérations successives sans amélioration de la solution dépasse un seuil.</p> Signup and view all the answers

<p>L'intensification vise à explorer plus attentivement les régions prometteuses de l'espace de recherche, tandis que la diversification vise à explorer de nouvelles régions qui n'ont pas été explorées auparavant.</p> Signup and view all the answers

<p>Les techniques d'intensification incluent : geler les éléments bons de la solution courante, augmenter la taille de l'échantillon quand on utilise une méthode de recherche probabiliste, ou modifier l'algorithme interne ou ses paramètres.</p> Signup and view all the answers

<p>Les techniques de diversification incluent : la diversification radicale, qui consiste à forcer l'inclusion d'éléments peu fréquents dans la solution courante, et la diversification continue, qui consiste à biaiser l'évaluation des mouvements en fonction de la fréquence des éléments.</p> Signup and view all the answers

Signup and view all the answers