Optimisation combinatoire
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

L’optimisation combinatoire est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. On parle également d’optimisation discrète.

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.)

Un problème 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, l'algorithmique et la théorie de la...) consiste à trouver la meilleure solution dans un 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...) discret dit ensemble des solutions réalisables. En général, cet ensemble est fini mais compte un très grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'éléments, et il est décrit de manière implicite, c'est-à-dire par une liste, relativement courte, de contraintes que doivent satisfaire les solutions réalisables.

Pour définir la notion de meilleure solution, une fonction, dite fonction objectif, est introduite. Pour chaque solution, elle renvoie un réel et la meilleure solution (ou solution optimale) est celle qui minimise ou maximise la fonction objectif. Clairement, un problème d'optimisation combinatoire (En mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements.) peut avoir plusieurs solutions optimales.

Exemple

  • Le problème du plus court chemin entre deux sommets A et B d'un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) est un exemple classique de problème d'optimisation combinatoire. L'ensemble des solutions réalisables est l'ensemble des chemins entre A et B tandis que la fonction objectif est la longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa...) du chemin.
  • Un autre problème d'optimisation combinatoire consiste à trouver le meilleur coup dans une position donnée (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un...) au jeu d'échecs ou au jeu de dame.

Résolution

Trouver une solution optimale dans un ensemble discret et fini est un problème facile en théorie : il suffit d'essayer toutes les solutions, et de comparer leurs qualités pour voir la meilleure. Cependant, en pratique, l'énumération de toutes les solutions peut prendre trop de temps ; or, le temps (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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...) de la solution optimale est un facteur très important et c'est à cause de lui que les problèmes d'optimisation combinatoire sont réputés si difficiles. La théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en informatique. Elle se distingue de la théorie de la calculabilité qui s'attache à savoir si un problème...) donne des outils pour mesurer ce temps de recherche. De plus, comme l'ensemble des solutions réalisables est défini de manière implicite, il est aussi parfois très difficile de trouver ne serait-ce qu'une solution réalisable.

Quelques problèmes d'optimisation combinatoire peuvent être résolus (de manière exacte) en temps polynomial par exemple par un algorithme glouton (Le Glouton ou Carcajou (Gulo gulo) est une espèce de mammifère omnivore, mais dans une plus grande mesure carnivore, de la famille des mustélidés. Il ressemble à un petit ours (10 à 15 kg) ayant...), un algorithme de programmation dynamique (Inventée par le professeur Richard Bellman, la programmation dynamique permet de résoudre au moyen d'un ordinateur tout problème d'optimisation dont la fonction objectif se décrit comme la somme...) ou en montrant que le problème peut être formulé comme un programme linéaire en variables réelles.

Dans la plupart des cas, le problème est NP complet et, pour le résoudre, il faut faire appel à des algorithmes de branch and bound (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...), à la 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...) en nombres entiers ou encore à la 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...) par contraintes. En pratique, on se contente très souvent d'avoir une solution approchée, obtenue par une heuristique (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :) ou une métaheuristique. Pour certains problèmes, on peut prouver une garantie de performance, c'est-à-dire que l'écart entre la solution obtenue et la solution optimale est borné.

Page générée en 0.056 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