Separation et evaluation

Separation et evaluation

Séparation et évaluation

Un algorithme par séparation et évaluation, également appelé selon le terme anglo-saxon branch and bound, est une méthode générique de résolution de problèmes d'optimisation, et plus particulièrement d'optimisation combinatoire ou discrète. C'est une méthode d'énumération implicite : toutes les solutions possibles du problème peuvent être énumérées mais, l'analyse des propriétés du problème permet d'éviter l'énumération de larges classes de mauvaises solutions. Dans un bon algorithme par séparation et évaluation, seules les solutions potentiellement bonnes sont donc énumérées.

Le branch and bound est parfois comparé à une autre technique de recherche de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle, alors que le branch and bound est plutôt dédié aux problèmes de recherche opérationnelle.

Sommaire

Présentation de la méthode

La méthode est volontairement présentée dans un cadre relativement simple pour éviter des problèmes techniques qui nuiraient à la clarté de l'exposé.

Soit S un ensemble fini mais de « grande » cardinalité qu'on appelle ensemble (ou espace) des solutions réalisables. On dispose d'une fonction f qui, pour toute solution réalisable x de S, renvoie un coût f(x). Le but du problème est de trouver la solution réalisable x de coût minimal. D'un point de vue purement existentiel, le problème est trivial : une telle solution x existe bien car l'ensemble S est fini. En revanche, l'approche effective du problème se confronte à deux difficultés. La première est qu'il n'existe pas forcément un algorithme simple pour énumérer les éléments de S. La seconde est que le nombre de solutions réalisables est très grand, ce qui signifie que le temps d'énumération de toutes les solutions est prohibitif (la complexité algorithmique est en général exponentielle).

Dans les méthodes par séparation et évaluation, la séparation permet d'obtenir une méthode générique pour énumérer toutes les solutions tandis que l'évaluation évite l'énumération systématique de toutes les solutions.

Séparation

La phase de séparation consiste à diviser le problème en un certain nombre de sous-problèmes qui ont chacun leur ensemble de solutions réalisables de telle sorte que tous ces ensembles forment un recouvrement (idéalement une partition) de l'ensemble S. Ainsi, en résolvant tous les sous-problèmes et en prenant la meilleure solution trouvée, on est assuré d'avoir résolu le problème initial. Ce principe de séparation peut être appliqué de manière récursive à chacun des sous-ensembles de solutions obtenus, et ceci tant qu'il y a des ensembles contenant plusieurs solutions. Les ensembles de solutions (et leurs sous-problèmes associés) ainsi construits ont une hiérarchie naturelle en arbre, souvent appelée arbre de recherche ou arbre de décision.

Évaluation

L'évaluation d'un nœud de l'arbre de recherche a pour but de déterminer l'optimum de l'ensemble des solutions réalisables associé au nœud en question ou, au contraire, de prouver mathématiquement que cet ensemble ne contient pas de solution intéressante pour la résolution du problème (typiquement, qu'il n'y a pas de solution optimale). Lorsqu'un tel nœud est identifié dans l'arbre de recherche, il est donc inutile d'effectuer la séparation de son espace de solutions.

À un nœud donné, l'optimum du sous-problème peut être déterminé lorsque le sous-problème devient « suffisamment simple ». Par exemple, lorsque l'ensemble des solutions réalisables devient un singleton, le problème est effectivement simple : l'optimum est l'unique élément de l'ensemble. Dans d'autres cas, il arrive que par le jeu des séparations, on arrive à un sous-problème dans lequel les décisions « difficiles » ont été prises et qui peut ainsi être résolu en temps polynomial.

Pour déterminer qu'un ensemble de solutions réalisables ne contient pas de solution optimale, la méthode la plus générale consiste à déterminer une borne inférieure pour le coût des solutions contenues dans l'ensemble (s'il s'agit d'un problème de minimisation). Si on arrive à trouver une borne inférieure de coût supérieur au coût de la meilleure solution trouvée jusqu'à présent, on a alors l'assurance que le sous-ensemble ne contient pas l'optimum. Les techniques les plus classiques pour le calcul de bornes sont basées sur l'idée de relaxation de certaines contraintes : relaxation continue, relaxation lagrangienne, etc.

Détails

La qualité de l'exploration repose grandement sur le choix d'une heuristique dont on suppose qu'elle aura plus de chance de faire venir le meilleur résultat dans les premiers. Par exemple, dans un problème du voyageur de commerce, on ne choisit pas en priorité de passer d'une ville à la ville la plus éloignée ! De cette manière, on augmente la probabilité de trouver de bonnes solutions réalisables dès le début de la recherche.

Le programme mémorise aussi la croissance ou décroissance de la fonction objectif au fil du temps, afin de suggérer éventuellement des temps d'exploration plus longs si des gains importants ont été obtenus vers la fin de la période de recherche.

On peut, bien que ce ne soit pas obligatoire, mémoriser aussi les meilleures solutions trouvées au fur et à mesure qu'on les trouve. La suite des réorganisations conduisant à de meilleurs résultat peut en effet à son tour aiguiller vers de nouvelles heuristiques.

Il est également possible de munir le programme d'un test de clé pupitre, d'interaction utilisateur par le moyen du clavier ou de chronométrage assurant qu'il s'arrêtera au bout d'un temps compatible avec le budget, et en imprimant alors le meilleur résultat trouvé à ce moment-là (les résultats sont souvent imprimés ou affichés au fur et à mesure, ce qui permet de savoir quand s'arrêter).

Perfectionnements

  • Pour pallier l'imperfection des heuristiques, le programme est souvent muni de métaheuristiques permettant d'abandonner momentanément une exploration quand elle ne donne pas le rendement souhaité (par exemple chemin plus long en 5 étapes qu'en 25 étapes par un chemin antérieur, ce qui n'augure pas forcément bien de la suite).
  • Lorsque l'exploration d'arbre se fait contre un joueur adverse, on utilise un autre court-circuit d'esprit voisin qui est l'élagage alpha-beta (parfois nommée coupure P-Q).

Champs d'application

Cette technique est très couramment utilisée dans le domaine de la recherche opérationnelle pour résoudre les problèmes de la classe NP. Elles sont en particulier au cœur des solveurs de programmation linéaire en nombres entiers et de programmation par contraintes.

Ce document provient de « S%C3%A9paration et %C3%A9valuation ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Séparation et évaluation — Un algorithme par séparation et évaluation, également appelé selon le terme anglo saxon branch and bound, est une méthode générique de résolution de problèmes d optimisation, et plus particulièrement d optimisation combinatoire ou discrète. C est …   Wikipédia en Français

  • Separation kernel — A separation kernel is a type of security kernel used to simulate a distributed environment. The concept was introduced by John Rushby in a 1981 paper.John Rushby, The Design and Verification of Secure Systems, Eighth ACM Symposium on Operating… …   Wikipedia

  • Psychology (The separation of) from philosophy — The separation of psychology from philosophy Studies in the sciences of mind 1815–1879 Edward S.Reed THE IMPOSSIBLE SCIENCE Traditional metaphysics The consensus of European opinion during and immediately after the Napoleonic era was that… …   History of philosophy

  • Commission nationale d'évaluation — La Commission nationale d évaluation (CNE), créée par la loi du 30 décembre 1991, est chargée, en France, d’évaluer les résultats des recherches sur la gestion des déchets radioactifs de haute activité à vie longue. Sommaire 1 Missions… …   Wikipédia en Français

  • Cyclonic separation — A simple cyclone separator Cyclonic separation is a method of removing particulates from an air, gas or liquid stream, without the use of filters, through vortex separation. Rotational effects and gravity are used to separate mixtures of solids… …   Wikipedia

  • Spider-Man & Venom: Separation Anxiety — Spider Man Venom: Separation Anxiety Spider Man Venom Separation Anxiety Éditeur Acclaim Développeur Software Creations Date de sortie 1994 Genre beat them all Mode de jeu …   Wikipédia en Français

  • Spider-Man and Venom: Separation Anxiety — Spider Man Venom: Separation Anxiety Spider Man Venom Separation Anxiety Éditeur Acclaim Développeur Software Creations Date de sortie 1994 Genre beat them all Mode de jeu …   Wikipédia en Français

  • Spider-Man & Venom: Separation Anxiety — Spider Man Venom Separation Anxiety Éditeur Acclaim Développeur Software Creations Date de sortie 1994 Genre beat them all Mode de jeu Un joueur …   Wikipédia en Français

  • Trusted Computer System Evaluation Criteria — (TCSEC) is a United States Government Department of Defense (DoD) standard that sets basic requirements for assessing the effectiveness of computer security controls built into a computer system. The TCSEC was used to evaluate, classify and… …   Wikipedia

  • DNA separation by silica adsorption — is an important method of DNA separation that is used in novel technologies that use micro channels. The principle behind this type of separation relies on DNA molecules binding to silica surfaces in the presence of certain salts and under… …   Wikipedia

Share the article and excerpts

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