Algorithme D'optimisation

Algorithme D'optimisation

Algorithme d'optimisation

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 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 (et des fonctions non-dérivables par l’algorithme d’Everett).

Le problème est insoluble en tant que tel si l’on ne connaît rien de la fonction (il existe peut-être une combinaison 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é.

Aucune méthode connue en 2004 (à part l’énumération exhaustive ou l’analyse algébrique) ne permet de trouver avec certitude un extremum 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é.

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é du résultat.

Détails

  • Soit A l’algorithme du problème d’optimisation associé au problème de décision 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

Ce document provient de « Algorithme d%27optimisation ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme D'optimisation de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Algorithme proximal (optimisation) — En analyse numérique et plus précisément en optimisation mathématique, l algorithme proximal (ou algorithme du point proximal) est un algorithme itératif de calcul d un minimum d une fonction convexe semi continue inférieurement propre. Si la… …   Wikipédia en Français

  • Algorithme d'optimisation — 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… …   Wikipédia en Français

  • Algorithme Du Simplexe — L algorithme du simplexe de George Dantzig est une technique à la fois fondamentale et très populaire pour les problèmes de programmation linéaire. Ainsi, étant donné un ensemble d inégalités linéaires sur n variables réelles, l …   Wikipédia en Français

  • Algorithme Glouton — Un algorithme glouton est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local, dans l espoir d obtenir un résultat optimum global. Par exemple, dans le problème du rendu de monnaie (donner une somme avec le moins… …   Wikipédia en Français

  • Algorithme De Ford-Fulkerson — L algorithme de Ford Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer un flux (ou flot) de valeur maximale (ou minimale) à partir d un flot constaté. Il s agit donc d un… …   Wikipédia en Français

  • Algorithme MinMax — L algorithme MinMax est un algorithme qui s applique à la théorie des jeux pour les jeux à deux joueurs à somme nulle. Pour une vaste famille de jeux, le théorème du minimax de von Neumann assure l existence d un tel algorithme, même si dans la… …   Wikipédia en Français

  • Algorithme de ford-fulkerson — L algorithme de Ford Fulkerson, du nom de ses auteurs L.R. Ford et D.R. Fulkerson, consiste en une procédure itérative qui permet de déterminer un flux (ou flot) de valeur maximale (ou minimale) à partir d un flot constaté. Il s agit donc d un… …   Wikipédia en Français

  • Algorithme De Levenberg-Marquardt — L’algorithme de Levenberg Marquardt, ou algorithme LM, permet d obtenir une solution numérique au problème de minimisation d une fonction, souvent non linéaire et dépendant de plusieurs variables. L algorithme interpole l algorithme de Gauss… …   Wikipédia en Français

  • Algorithme de levenberg-marquardt — L’algorithme de Levenberg Marquardt, ou algorithme LM, permet d obtenir une solution numérique au problème de minimisation d une fonction, souvent non linéaire et dépendant de plusieurs variables. L algorithme interpole l algorithme de Gauss… …   Wikipédia en Français

  • Algorithme De Nagle — L algorithme de Nagle est un algorithme important pour le fonctionnement de TCP défini par John Nagle dans la RFC 896 (RFC 896). L objectif de cet algorithme est d améliorer l efficacité du protocole en réduisant le nombre de paquets nécessaires… …   Wikipédia en Français

Share the article and excerpts

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