Minimizzazione di f (x, y) dove x e y sono interi

Question

Mi chiedevo se qualcuno avesse qualche suggerimento per minimizzare una funzione, f (x, y), dove x e y sono numeri interi. Ho ricercato molte tecniche di minimizzazione e ottimizzazione, come BFGS e altri di GSL, e cose da ricette numeriche. Finora, ho provato a impiantare un paio di schemi diversi. Il primo funziona selezionando la direzione della più grande discesa f (x + 1, y), f (x-1, y), f (x, y + 1), f (x, y-1) e segui quella direzione con minimizzazione della linea. Ho anche provato a usare un metodo downhill simplex (Nelder-Mead). Entrambi i metodi rimangono bloccati lontano dal minimo. Entrambi sembrano lavorare su funzioni più semplici, come trovare il minimo di un paraboloide, ma penso che entrambi, e specialmente il primo, siano progettati per funzioni in cui xey sono valori reali (doppi). Un altro problema è che ho bisogno di chiamare f (x, y) il minor numero possibile di volte. Parla con l'hardware esterno e impiega un paio di secondi per ogni chiamata. Qualsiasi idea per questo sarebbe molto apprezzata.

Ecco un esempio della funzione di errore. Mi spiace di non averlo postato prima. Questa funzione richiede un paio di secondi per valutare. Inoltre, le informazioni che query dal dispositivo non aggiunge all'errore se è sotto il nostro valore desiderato, solo se è al di sopra

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

Come si definisce f (x, y)? La minimizzazione è un problema difficile, a seconda della complessità della tua funzione.

Algoritmi genetici potrebbero essere un buon candidato.

Risorse:

Genetic Algorithms in Search, Optimization, and Machine Learning

Implementing a Genetic Algorithms in C#

Simple C# GA

Answer 2

Hai guardato algoritmi genetici? Sono molto, molto bravi a trovare minimi e massimi, evitando i minimi/massimi locali.

Answer 3

Se si tratta di una funzione arbitraria, non esiste un modo preciso per farlo.

Supponiamo di avere una funzione definita come:

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

Come può qualsiasi algoritmo realisticamente trovare (100, 100) come il minimo? Potrebbe essere una qualsiasi combinazione possibile di valori.

Sai qualcosa sulla sulla funzione che stai testando?

Answer 4

Ci sono molte, molte soluzioni qui. In effetti, ci sono interi libri e discipline accademiche basati sull'argomento. Ne sto leggendo uno eccellente adesso: How to Solve It: Modern Heuristics.

Non esiste una soluzione corretta: soluzioni diverse presentano vantaggi diversi in base alla conoscenza specifica della funzione. È stato anche dimostrato che non esiste un'euristica che offra il meglio in tutte le attività di ottimizzazione.

Se sai che la tua funzione è quadratica, è possibile utilizzare Newton-Gauss per trovare il minimo in un unico passaggio. Un algoritmo genetico può essere un ottimo strumento per scopi generali, oppure puoi provare la ricottura simulata, che è meno complicata.

Answer 5

Quello che state generalmente cercando è chiamato un optimisation technique in matematica.In generale, si applicano alle funzioni con valori reali, ma molte possono essere adattate per funzioni a valori interi.

In particolare, consiglierei di esaminare non-linear programming e gradient descent. Entrambi sembrerebbero abbastanza adatti alla tua applicazione.

Se potessi fornire ulteriori dettagli, potrei essere in grado di suggerire qualcosa di più specifico.

Answer 6

La risposta di Jon Skeet è corretta. Hai davvero bisogno di informazioni su f e sui suoi derivati ​​anche se f è ovunque continua.

Il modo più semplice per apprezzare le difficoltà di ciò che si chiede (minimizzazione di f solo a valori interi) è solo pensare a un f: R-> R (f è una funzione di valore reale dei reali) di una variabile che fa grandi escursioni tra interi individuali. È possibile costruire facilmente tale funzione in modo che NON ci sia alcuna correlazione tra i minimi locali sulla linea reale e i minimi ai numeri interi e non abbia alcuna relazione con la prima derivata.

Per una funzione arbitraria non vedo alcun modo tranne la forza bruta.

Answer 7

Siamo spiacenti che la formattazione sia stata così brutta in precedenza. Ecco un esempio della funzione di errore

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

Quindi diamo un'occhiata al tuo problema in matematica. Tutto ciò presuppone che capisco perfettamente il tuo problema . Sentiti libero di correggermi se mi sbaglio.

vogliamo ridurre al minimo il seguente:

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

o in altra notazione || Pos (x - x_desired) || _2

dove x = (a, b, c) e Pos (y) = max (y, 0) significa che vogliamo che la "parte positiva" (questo spiega per le tue dichiarazioni if). Infine, desideriamo restringere noi stessi a soluzioni in cui x è valutato intero.

A differenza dei poster di cui sopra, non credo che gli algoritmi genetici siano ciò che si desidera.
In effetti, penso che la soluzione sia molto più semplice (supponendo che io comprenda il tuo problema).

1) Eseguire qualsiasi procedura di ottimizzazione sulla funzione precedente. Questo ti darà la soluzione x^* = (a^*, b^*, c^*). Poiché questa funzione è in aumento rispetto alle variabili , la migliore soluzione per intero che si possa sperare è (ceil (a^*), ceil (b^*), ceil (c^*)).

Ora dici che la tua funzione è forse difficile da valutare. Esistono strumenti per questo che non sono basati sull'euristica. Il go sotto il nome di Derivative-Free Ottimizzazione. Le persone usano questi strumenti per ottimizzare obiettivo sulla base di simulazioni (ho nemmeno sentito parlare di un caso in cui la funzione obiettivo si basa sulle rese delle colture canto!)

Ciascuno di questi metodi hanno proprietà diverse, ma in generale tentano di minimizzare non solo l'obiettivo, ma il numero di valutazioni delle funzioni oggettive.