Minimisation de f (x, y) où x et y sont des entiers

Question

Je me demandais si quelqu'un avait des suggestions pour minimiser une fonction, f (x, y), où x et y sont des entiers. J'ai étudié beaucoup de techniques de minimisation et d'optimisation, comme BFGS et d'autres sur GSL, et des choses à partir de recettes numériques. Jusqu'à présent, j'ai essayé d'implémenter quelques schémas différents. Le premier travaille en choisissant la direction de la plus grande descente f (x + 1, y), f (x-1, y), f (x, y + 1), f (x, y-1), et suivez cette direction avec minimisation de ligne. J'ai également essayé d'utiliser une méthode de downhill simplex (Nelder-Mead). Les deux méthodes restent bloquées loin d'un minimum. Ils semblent tous deux travailler sur des fonctions plus simples, comme trouver le minimum d'un paraboloïde, mais je pense que les deux, et surtout le premier, sont conçus pour des fonctions où x et y sont des valeurs réelles (doubles). Un autre problème est que j'ai besoin d'appeler f (x, y) aussi peu de fois que possible. Il parle au matériel externe, et prend quelques secondes pour chaque appel. Toutes les idées pour cela seraient grandement appréciées.

Voici un exemple de la fonction d'erreur. Désolé, je n'ai pas posté cela avant. Cette fonction prend quelques secondes pour évaluer. En outre, les informations que nous interrogeons de l'appareil ne contribue pas à l'erreur si elle est inférieure à notre valeur souhaitée, que si elle est au-dessus

double Error(x,y) 
{ 
    SetDeviceParams(x,y); 
    double a = QueryParamA(); 
    double b = QueryParamB(); 
    double c = QueryParamC(); 
    double _fReturnable = 0; 
    if(a>=A_desired) 
    { 
    _fReturnable+=(A_desired-a)*(A_desired-a); 
    } 
    if(b>=B_desired) 
    { 
    _fReturnable+=(B_desired-b)*(B_desired-b); 
    } 
    if(c>=C_desired) 
    { 
    _fReturnable+=(C_desired-c)*(C_desired-c); 
    } 
    return Math.sqrt(_fReturnable) 
} 

Answer 1

Comment définissez-vous f (x, y)? La minimisation est un problème difficile, selon la complexité de votre fonction.

Les algorithmes génétiques pourraient être un bon candidat.

Ressources:

Genetic Algorithms in Search, Optimization, and Machine Learning

Implementing a Genetic Algorithms in C#

Simple C# GA

Answer 2

Avez-vous regardé des algorithmes génétiques? Ils sont très, très bons pour trouver des minimums et des maximums, tout en évitant les minimum/maximum locaux.

Answer 3

S'il s'agit d'une fonction arbitraire, il n'y a pas de manière simple de le faire.

Supposons que nous avons une fonction définie comme:

f(x, y) = 0 for x==100, y==100 
      100 otherwise 

Comment un algorithme peut trouver de façon réaliste (100, 100) au minimum? Ce pourrait être n'importe quelle combinaison possible de valeurs.

Connaissez-vous quoi que ce soit sur la fonction que vous testez?

Answer 4

Il y a beaucoup, beaucoup de solutions ici. En fait, il existe des livres entiers et des disciplines académiques basées sur le sujet. Je suis en train de lire un excellent article en ce moment: How to Solve It: Modern Heuristics.

Il n'existe pas de solution unique - différentes solutions ont des avantages différents basés sur une connaissance spécifique de votre fonction. Il a même été prouvé qu'il n'y a pas d'heuristique qui fonctionne le mieux dans toutes les tâches d'optimisation.

Si vous savez que votre fonction est quadratique, vous pouvez utiliser Newton-Gauss pour trouver le minimum en une seule étape. Un algorithme génétique peut être un excellent outil polyvalent, ou vous pouvez essayer un recuit simulé, ce qui est moins compliqué.

Answer 5

Ce que vous cherchez généralement s'appelle un optimisation technique en mathématiques.En général, ils s'appliquent à des fonctions à valeur réelle, mais beaucoup peuvent être adaptés pour des fonctions intégralement évaluées. En particulier, je recommande d'examiner non-linear programming et gradient descent. Les deux sembleraient tout à fait appropriés pour votre application.

Si vous pouviez fournir plus de détails, je pourrais vous suggérer quelque chose de plus spécifique.

Answer 6

La réponse de Jon Skeet est correcte. Vous avez vraiment besoin d'informations sur f et c'est dérivés même si f est partout continu. La manière la plus simple d'apprécier les difficultés de ce que vous demandez (minimisation de f en valeurs entières uniquement) est simplement de penser à un f: R-> R (f est une fonction de valeur réelle des réels) d'une variable cela fait de grandes excursions entre les entiers individuels. Vous pouvez facilement construire une telle fonction de sorte qu'il n'y ait AUCUNE corré- lation entre les minimums locaux sur la ligne réelle et les minimums sur les entiers, sans relation avec la dérivée première.

Pour une fonction arbitraire, je ne vois pas d'autre moyen que la force brute.

Answer 7

Désolé, la mise en forme était si mauvaise auparavant. Voici un exemple de la fonction d'erreur

double Error(x,y) 
{ 
SetDeviceParams(x,y); 
double a = QueryParamA(); 
double b = QueryParamB(); 
double c = QueryParamC(); 
double _fReturnable = 0; 
if(a>=A_desired) 
{ 
    _fReturnable+=(A_desired-a)*(A_desired-a); 
} 
if(b>=B_desired) 
{ 
_fReturnable+=(B_desired-b)*(B_desired-b); 
} 
if(c>=C_desired) 
{ 
    _fReturnable+=(C_desired-c)*(C_desired-c); 
} 
return Math.sqrt(_fReturnable) 
} 

Answer 8

Examinons donc votre problème en langage mathématique. Tout cela suppose que je comprends pleinement votre problème. N'hésitez pas à me corriger si je me trompe.

nous voulons réduire au minimum les éléments suivants:

\ sqrt ((a-a_desired)^2 + (b-b_desired)^2 + (c-c_desired)^2)

ou dans d'autres notations || Pos (x - x_desired) || _2

où x = (a, b, c) et Pos (y) = max (y, 0) signifie que nous voulons que la "partie positive" (ce qui explique pour vos déclarations si). Enfin, nous souhaitons nous limiter aux solutions où x est une valeur entière.

Contrairement aux affiches ci-dessus, je ne pense pas que les algorithmes génétiques sont ce que vous voulez du tout.
En fait, je pense que la solution est beaucoup plus facile (en supposant que je comprends votre problème).

1) Exécuter une routine d'optimisation sur la fonction ci-dessus. Cela vous donnera la solution x^* = (a^*, b^*, c^*). Comme cette fonction augmente en ce qui concerne les variables, la meilleure solution entière que vous pouvez espérer est (ceil (a^*), ceil (b^*), ceil (c^*)).

Maintenant, vous dites que votre fonction est peut-être difficile à évaluer. Il existe des outils pour cela qui ne sont pas basés sur des heuristiques. Le go sous le nom Derivative-Free Optimisation. Les gens utilisent ces outils pour optimiser l'objectif à partir de simulations (je même entendu parler d'un cas où la fonction objective est basée sur les rendements Crowing des cultures!)

Chacune de ces méthodes ont des propriétés différentes, mais en général ils tentent de minimiser non seulement l'objectif, mais le nombre d'évaluations de la fonction objective.