Séparation et évaluation
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (L’optimisation combinatoire est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle,...) 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 (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...), seules les solutions potentiellement bonnes sont donc énumérées.

Le branch and bound est parfois comparé à une autre technique de recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension métonymique, la recherche...) de solution, l'algorithme A*, très souvent utilisé en intelligence artificielle (L'intelligence artificielle ou informatique cognitive est la « recherche de moyens susceptibles de doter les systèmes informatiques de capacités intellectuelles comparables à celles des êtres humains ».), alors que le branch and bound est plutôt dédié aux problèmes de recherche opérationnelle (La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l'ensemble des méthodes et techniques rationnelles d'analyse et de...).

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 (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) mais de " grande " cardinalité (En linguistique, les nombres entiers naturels zéro, un, deux, trois, etc. s'appellent des adjectifs numéraux cardinaux. En mathématiques, un nombre cardinal est une extension de cette notion pour dénombrer les ensembles, y compris...) qu'on appelle ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise...) (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 (Graphie) de vue (La vue est le sens qui permet d'observer et d'analyser l'environnement par la réception et l'interprétation des rayonnements lumineux.) 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 ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du...) est que le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de solutions réalisables est très grand, ce qui signifie que le temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) d'énumération de toutes les solutions est prohibitif (la complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en sociologie, en informatique ou en...) algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de processus...) est en général exponentielle).

Dans les méthodes par séparation (D'une manière générale, le mot séparation désigne une action consistant à séparer quelque chose ou son résultat. Plus particulièrement il est employé...) 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 (En sciences de la vie et en histoire naturelle, la systématique est la science qui a pour objet de dénombrer et de classer les taxons dans un certain ordre, basé sur des principes divers....) de toutes les solutions.

Séparation

La phase (Le mot phase peut avoir plusieurs significations, il employé dans plusieurs domaines et principalement en physique :) 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 (Un recouvrement d'un ensemble X est un ensemble P de sous-ensembles non vides de X tel que l'union de ces sous-ensembles soit égal à X. Autrement dit...) (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 (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide...), 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éalisable 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 (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du sur-ensemble B. Il peut par contre y avoir des...) 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 (L'exploration est le fait de chercher avec l'intention de découvrir quelque chose d'inconnu.) repose grandement sur le choix d'une heuristique (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :) 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 par priorité de passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) d'une ville (Une ville est une unité urbaine (un « établissement humain » pour l'ONU) étendue et fortement peuplée (dont les habitations doivent être à moins de 200 m chacune, par opposition aux villages) dans...) à la ville la plus éloignée ! De cette manière, on augmente la probabilité (La probabilité (du latin probabilitas) est une évaluation du caractère probable d'un évènement. En mathématiques, l'étude des...) 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 (Fur est une petite île danoise dans le Limfjord. Fur compte environ 900 hab. . L'île couvre une superficie de 22 km². Elle est située dans...) 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 (Un budget est un document comptable prévisionnel distinguant les recettes et les dépenses.), 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 mathématiques, les problèmes de programmation linéaire (PL) sont des problèmes d'optimisation où la fonction objectif et les contraintes sont toutes linéaires. Néanmoins, la plupart des résultats présentés ici sont...) en nombre entiers et de programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une étape importante de la conception de logiciel (voire de...) par contraintes.

Page générée en 0.092 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique