Recherche Avec Tabous

Recherche Avec Tabous

Recherche tabou

La recherche tabou est une métaheuristique d'optimisation présentée par Fred Glover en 1986. On trouve souvent l'appellation recherche avec tabous en français.

Cette méthode est une métaheuristique itérative qualifiée de recherche locale au sens large.

Sommaire

Principe

L'idée de la recherche tabou consiste, à partir d'une position donnée, à en explorer le voisinage et à choisir la position dans ce voisinage qui minimise la fonction objectif.

Il est essentiel de noter que cette opération peut conduire à augmenter la valeur de la fonction (dans un problème de minimisation) : c'est le cas lorsque tous les points du voisinage ont une valeur plus élevée. C'est à partir de ce mécanisme que l'on sort d'un minimum local.

Le risque cependant est qu'à l'étape suivante, on retombe dans le minimum local auquel on vient d'échapper. C'est pourquoi il faut que l'heuristique ait de la mémoire : le mécanisme consiste à interdire (d'où le nom de tabou) de revenir sur les dernières positions explorées.

Les positions déjà explorées sont conservées dans une file FIFO (appelée souvent liste tabou) d'une taille donnée, qui est un paramètre ajustable de l'heuristique. Cette pile doit conserver des positions complètes, ce qui dans certains types de problèmes, peut nécessiter l'archivage d'une grande quantité d'informations. Cette difficulté peut être contournée en ne gardant en mémoire que les mouvements précédents, associés à la valeur de la fonction à minimiser.

Comportement

Les démonstrations de convergence (capacité de l'algorithme à trouver le minimum global si le temps imparti tend vers l'infini) pour la recherche tabou existent, mais supposent des conditions strictes, rarement présentes en pratique.

De nombreuses variantes existent, principalement au niveau de la définition du voisinage et de la manière de gérer la mémoire.

Références

Sources

  • (fr) Dreo J.; Pétrowski A.; Siarry P.; Taillard E., Métaheuristiques pour l'optimisation difficile ; recuit simulé, recherche tabou, Eyrolles, 2003.
  • (en) Glover, F. ; Laguna, M. ; Tabu search, 1997, Kluwer Academic Publishers, Dordrecht.
Ce document provient de « Recherche tabou ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Recherche Avec Tabous de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Recherche avec tabous — Recherche tabou La recherche tabou est une métaheuristique d optimisation présentée par Fred Glover en 1986. On trouve souvent l appellation recherche avec tabous en français. Cette méthode est une métaheuristique itérative qualifiée de recherche …   Wikipédia en Français

  • Recherche taboue — Recherche tabou La recherche tabou est une métaheuristique d optimisation présentée par Fred Glover en 1986. On trouve souvent l appellation recherche avec tabous en français. Cette méthode est une métaheuristique itérative qualifiée de recherche …   Wikipédia en Français

  • Recherche tabou — La recherche tabou est une métaheuristique d optimisation présentée par Fred Glover en 1986. On trouve souvent l appellation recherche avec tabous en français. Cette méthode est une métaheuristique itérative qualifiée de recherche locale au sens… …   Wikipédia en Français

  • Recherche religieuse — Religion Une religion est un ensemble de rites, croyances généralement théistes[Note 1], composé de règles (éthiques ou pratiques), de récits, de symboles ou de dogmes adoptés comme conviction par une société, un groupe ou une personne. Par… …   Wikipédia en Français

  • Metaheuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Méta-heuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Métaheuristique — Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence artificielle) pour lesquels on ne… …   Wikipédia en Français

  • Métaheuristiques — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • OCÉANIE - Histoire — Les îles de l’Océanie, du fait de leur situation «au bout du monde» par rapport à l’Europe d’où sont venus les découvreurs, du fait aussi de leur isolement dans des immensités maritimes qui occupent près du tiers de la surface du globe, ont été… …   Encyclopédie Universelle

  • Bouclier d'or — Censure de l Internet en République populaire de Chine Article principal : Censure en République populaire de Chine. L Assemblée nationale populaire de la République populaire de Chine a voté des lois sur la censure de l Internet. Avec ces… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”