Algorithme d'optimisation
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Les algorithmes d’optimisation cherchent à déterminer le jeu de paramètres d’entrée d’une fonction donnant à cette fonction la valeur maximale ou minimale. On cherchera par exemple la découpe optimale d’une tôle pour en fabriquer le plus grand nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de boîtes de conserve possible (ou d’un tissu pour en faire le plus grand nombre de chemises possibles, etc.). Cette optimisation peut se faire sans contrainte ou sous contrainte, le second cas se ramenant au premier dans le cas des fonctions dérivables par la méthode du multiplicateur de Lagrange (Le multiplicateur de Lagrange est une méthode permettant de trouver des points stationnaires (maximum, minimum...) d'une fonction dérivable d'une ou plusieurs variables.) (et des fonctions non-dérivables par l’algorithme d’Everett).

Le problème est bien entendu insoluble en tant que tel si l’on ne connaît rien de la fonction (il existe peut-être une combinaison (Une combinaison peut être :) très particulière de valeurs d’entrées lui donnant ponctuellement une valeur extrêmement haute ou basse, qui pourrait échapper à l’algorithme. Aussi existe-t-il plusieurs classes d’algorithmes liés aux différentes connaissances qu’on peut avoir sur la fonction. Si celle-ci est dérivable, l’une des plus performantes est celle du gradient conjugué (En mathématiques, le conjugué d'un nombre complexe z est le nombre complexe formé de la même partie réelle que z mais de partie imaginaire opposée.).

Aucune méthode connue en 2004 (à part bien entendu l’énumération exhaustive ou l’analyse algébrique) ne permet de trouver avec certitude un extremum (L'expression « élément extremum » signifie « élément maximum » ou « élément minimum ».) global d’une fonction. Les extrema déterminables sont toujours locaux à un domaine, et demandent souvent même en ce cas quelques caractéristiques à la fonction, par exemple dans certains cas la continuité (En mathématiques, la continuité est une propriété topologique d'une fonction. En première approche, une fonction est continue si, à des variations infinitésimales de la variable x, correspondent des variations...).

Les métaheuristiques sont une classe d’algorithmes d’optimisation qui tentent d’obtenir une valeur approchée de l’optimum global dans le cas de problèmes d’optimisation difficile. Elles ne donnent cependant aucunes garanties sur la fiabilité (Un système est fiable lorsque la probabilité de remplir sa mission sur une durée donnée correspond à celle spécifiée dans le...) du résultat.

Détails

  • Soit A l’algorithme du problème d’optimisation associé au problème de décision (En logique mathématique, on appelle problème de la décision le fait de déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique égalitaire du...) P.
  • Opt(i) est la solution optimale pour l’instance i du problème P.
  • Cout(i) est la valeur k' de la solution j.
  • A est polynomial et on a :
  • A : I(P)\rightarrow S : i\rightarrow j \in s(i), tel que CP(i,j) = oui.
  • \exist c, constante ne dépendant pas de i, telle que:

\forall i \in I(P), \frac{Cout(A(i))}{Opt(i)} \leq c

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