Recherche tabou - Tabu search
La recherche tabou est une méthode de recherche métaheuristique employant des méthodes de recherche locales utilisées pour l'optimisation mathématique . Il a été créé par Fred W. Glover en 1986 et officialisé en 1989.
Les recherches locales (de quartier) prennent une solution potentielle à un problème et vérifient ses voisins immédiats (c'est-à-dire des solutions similaires à l'exception de très peu de détails mineurs) dans l'espoir de trouver une solution améliorée. Les méthodes de recherche locales ont tendance à se coincer dans des régions sous-optimales ou sur des plateaux où de nombreuses solutions conviennent également.
La recherche Tabu améliore les performances de la recherche locale en assouplissant sa règle de base. Premièrement, à chaque étape, des mouvements de détérioration peuvent être acceptés si aucun mouvement d'amélioration n'est disponible (comme lorsque la recherche est bloquée à un strict minimum local ). De plus, des interdictions (désormais le terme tabu ) sont introduites pour décourager la recherche de revenir sur des solutions précédemment visitées.
La mise en œuvre de la recherche taboue utilise des structures de mémoire qui décrivent les solutions visitées ou des ensembles de règles fournis par l'utilisateur. Si une solution potentielle a été précédemment visitée dans une certaine période à court terme ou si elle a enfreint une règle, elle est marquée comme " tabu " (interdit) afin que l' algorithme ne considère pas cette possibilité à plusieurs reprises.
Arrière-plan
Le mot tabu vient du mot tongan pour désigner des choses qui ne peuvent pas être touchées parce qu'elles sont sacrées.
La recherche tabu (TS) est un algorithme métaheuristique qui peut être utilisé pour résoudre des problèmes d' optimisation combinatoire (problèmes où un ordre et une sélection d'options optimaux sont souhaités).
Les applications actuelles de TS couvrent les domaines de la planification des ressources , des télécommunications, de la conception VLSI , de l'analyse financière, de la planification, de la planification de l'espace, de la distribution d'énergie, du génie moléculaire, de la logistique, de la classification des modèles , de la fabrication flexible, de la gestion des déchets, de l'exploration minérale, de l'analyse biomédicale, de la conservation de l'environnement et des dizaines d'autres. Ces dernières années, des revues dans une grande variété de domaines ont publié des articles de tutorat et des études computationnelles documentant les succès de la recherche taboue en étendant la frontière des problèmes qui peuvent être traités efficacement - produisant des solutions dont la qualité dépasse souvent de manière significative celle obtenue par les méthodes précédemment appliquées. Une liste complète des applications, y compris des descriptions récapitulatives des gains obtenus grâce aux implémentations pratiques, peut être trouvée dans les développements récents de TS et les applications peuvent également être trouvées dans Tabu Search Vignettes .
Description de base
La recherche Tabu utilise une procédure de recherche locale ou de quartier pour passer de manière itérative d'une solution potentielle à une solution améliorée dans le voisinage de , jusqu'à ce qu'un critère d'arrêt soit satisfait (généralement, une limite de tentative ou un seuil de score). Les procédures de recherche locales restent souvent bloquées dans les zones à faible score ou dans les zones où les scores plafonnent. Afin d'éviter ces écueils et d'explorer des régions de l' espace de recherche qui seraient laissées inexplorées par d'autres procédures de recherche locales, la recherche tabou explore attentivement le voisinage de chaque solution au fur et à mesure de la progression de la recherche. Les solutions admises dans le nouveau voisinage ,, sont déterminées par l'utilisation de structures de mémoire. À l'aide de ces structures de mémoire, la recherche progresse en passant de manière itérative de la solution actuelle à une solution améliorée dans .
La recherche Tabu présente plusieurs similitudes avec le recuit simulé , car les deux impliquent de possibles descentes de collines. En fait, le recuit simulé pourrait être considéré comme une forme spéciale de TS, où nous utilisons la "tenure graduée", c'est-à-dire qu'un mouvement devient tabou avec une probabilité spécifiée.
Ces structures de mémoire forment ce que l'on appelle la liste taboue, un ensemble de règles et de solutions interdites permettant de filtrer les solutions qui seront admises dans le voisinage à explorer par la recherche. Dans sa forme la plus simple, une liste tabou est un ensemble à court terme de solutions qui ont été visitées dans un passé récent (moins qu'il y a des itérations, où est le nombre de solutions précédentes à stocker - est également appelé la tenure tabu). Plus communément, une liste taboue se compose de solutions qui ont changé par le processus de passage d'une solution à une autre. Il est commode, pour faciliter la description, de comprendre une «solution» à coder et à représenter par de tels attributs.
Types de mémoire
Les structures de mémoire utilisées dans la recherche taboue peuvent être divisées en trois catégories:
- Court terme: la liste des solutions récemment envisagées. Si une solution potentielle apparaît dans la liste tabou, elle ne peut pas être réexaminée tant qu'elle n'a pas atteint un point d'expiration.
- Intermédiaire: règles d'intensification destinées à biaiser la recherche vers des zones prometteuses de l'espace de recherche.
- À long terme: règles de diversification qui conduisent la recherche dans de nouvelles régions (c'est-à-dire concernant les réinitialisations lorsque la recherche est bloquée dans un plateau ou dans une impasse sous-optimale).
Les souvenirs à court, moyen et long terme peuvent se chevaucher dans la pratique. Au sein de ces catégories, la mémoire peut en outre être différenciée par des mesures telles que la fréquence et l'impact des modifications apportées. Un exemple de structure de mémoire à moyen terme est celle qui interdit ou encourage les solutions qui contiennent certains attributs (par exemple, des solutions qui incluent des valeurs indésirables ou souhaitables pour certaines variables) ou une structure de mémoire qui empêche ou induit certains mouvements (par exemple basée sur la mémoire de fréquence appliquées à des solutions partageant des caractéristiques communes avec des solutions peu attrayantes ou attrayantes trouvées dans le passé). Dans la mémoire à court terme, les attributs sélectionnés dans les solutions récemment visitées sont étiquetés «tabu-active». Les solutions contenant des éléments tabu-actifs sont interdites. Des critères d'aspiration sont employés qui remplacent l'état tabou d'une solution, incluant ainsi la solution autrement exclue dans l'ensemble autorisé (à condition que la solution soit «assez bonne» selon une mesure de qualité ou de diversité). Un critère d'aspiration simple et couramment utilisé est de permettre des solutions meilleures que la meilleure solution actuellement connue.
La mémoire à court terme peut suffire à elle seule à obtenir des solutions supérieures à celles trouvées par les méthodes de recherche locales conventionnelles, mais des structures intermédiaires et à long terme sont souvent nécessaires pour résoudre des problèmes plus difficiles. Recherche Tabu est souvent établie par rapport à d' autres métaheuristiques méthodes - telles que le recuit simulé , algorithmes génétiques , des algorithmes d'optimisation de colonie de fourmis , l' optimisation de recherche réactive, guidée Recherche locale , ou avide recherche adaptative aléatoire . De plus, la recherche taboue est parfois combinée avec d'autres métaheuristiques pour créer des méthodes hybrides. L'hybride de recherche tabu le plus courant survient en joignant TS avec Scatter Search, une classe de procédures basées sur la population qui a des racines communes avec la recherche taboue, et est souvent utilisée pour résoudre de grands problèmes d'optimisation non linéaire.
Pseudocode
Le pseudocode suivant présente une version simplifiée de l'algorithme de recherche tabou comme décrit ci-dessus. Cette implémentation a une mémoire à court terme rudimentaire, mais ne contient aucune structure de mémoire intermédiaire ou à long terme. Le terme «aptitude» se réfère à une évaluation de la solution candidate, telle qu'elle est incorporée dans une fonction objective pour l'optimisation mathématique.
sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
sNeighborhood ← getNeighbors(bestCandidate)
bestCandidate ← sNeighborhood[0]
for (sCandidate in sNeighborhood)
if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
bestCandidate ← sCandidate
end
end
if (fitness(bestCandidate) > fitness(sBest))
sBest ← bestCandidate
end
tabuList.push(bestCandidate)
if (tabuList.size > maxTabuSize)
tabuList.removeFirst()
end
end
return sBest
Les lignes 1 à 4 représentent une configuration initiale, créant respectivement une solution initiale (éventuellement choisie au hasard), définissant cette solution initiale comme la meilleure vue à ce jour et initialisant une liste tabou avec cette solution initiale. Dans cet exemple, la liste tabu est simplement une structure de mémoire à court terme qui contiendra un enregistrement des éléments des états visités.
La boucle algorithmique principale commence à la ligne 5. Cette boucle continuera à rechercher une solution optimale jusqu'à ce qu'une condition d'arrêt spécifiée par l'utilisateur soit remplie (deux exemples de telles conditions sont une simple limite de temps ou un seuil sur le score de fitness). Les solutions voisines sont vérifiées pour les éléments tabu à la ligne 9. De plus, l'algorithme garde la trace de la meilleure solution dans le voisinage, qui n'est pas tabu.
La fonction de fitness est généralement une fonction mathématique, qui renvoie un score ou les critères d'aspiration sont satisfaits - par exemple, un critère d'aspiration pourrait être considéré comme un nouvel espace de recherche est trouvé). Si le meilleur candidat local a une valeur de fitness plus élevée que le meilleur actuel (ligne 13), il est défini comme le nouveau meilleur (ligne 14). Le meilleur candidat local est toujours ajouté à la liste tabu (ligne 16) et si la liste tabu est pleine (ligne 17), certains éléments pourront expirer (ligne 18). En général, les éléments expirent de la liste dans le même ordre où ils sont ajoutés. La procédure sélectionnera le meilleur candidat local (bien qu'il ait une moins bonne forme que le sBest) afin d'échapper à l'optimum local.
Ce processus se poursuit jusqu'à ce que le critère d'arrêt spécifié par l'utilisateur soit satisfait, à quel point la meilleure solution vue pendant le processus de recherche est renvoyée (ligne 21).
Exemple: le problème du voyageur de commerce
Le problème du voyageur de commerce (TSP) est parfois utilisé pour montrer la fonctionnalité de la recherche taboue. Ce problème pose une question simple - étant donné une liste de villes, quel est l'itinéraire le plus court qui visite chaque ville? Par exemple, si la ville A et la ville B sont côte à côte, tandis que la ville C est plus éloignée, la distance totale parcourue sera plus courte si les villes A et B sont visitées l'une après l'autre avant de visiter la ville C.Depuis trouver une solution optimale est NP-hard , les méthodes d'approximation heuristiques (telles que les recherches locales) sont utiles pour concevoir des solutions proches de l'optimales. Pour obtenir de bonnes solutions TSP, il est essentiel d'exploiter la structure du graphe. La valeur de l'exploitation de la structure des problèmes est un thème récurrent dans les méthodes métaheuristiques, et la recherche tabou est bien adaptée à cela. Une classe de stratégies associées à la recherche taboue, appelées méthodes de chaîne d'éjection, a permis d'obtenir efficacement des solutions TSP de haute qualité.
En revanche, une simple recherche tabou peut être utilisée pour trouver une solution satisfaisante au problème du voyageur de commerce (c'est-à-dire une solution qui satisfait un critère d'adéquation, mais pas avec la haute qualité obtenue en exploitant la structure du graphe). La recherche commence par une solution initiale, qui peut être générée aléatoirement ou selon une sorte d' algorithme du plus proche voisin . Pour créer de nouvelles solutions, l'ordre dans lequel deux villes sont visitées dans une solution potentielle est inversé. La distance totale parcourue entre toutes les villes est utilisée pour juger dans quelle mesure une solution est idéale par rapport à une autre. Pour éviter les cycles - à savoir, à plusieurs reprises visiter un ensemble de solutions - et pour éviter d' être coincé dans optima locaux , une solution est ajoutée à la liste de Tabu si elle est acceptée dans le quartier de solution, .
De nouvelles solutions sont créées jusqu'à ce qu'un critère d'arrêt, tel qu'un nombre arbitraire d'itérations, soit satisfait. Une fois que la simple recherche tabou s'arrête, elle renvoie la meilleure solution trouvée lors de son exécution.