Algoritmi di backtracking

Da Hacknowledge.

Gli algoritmi di backtracking sono algoritmi utilizzati nell'ambito della ricerca operativa (quindi in ambito prevalentemente matematico, che però ha forti ripercussioni in campo informatico, economico e logistico) per la determinazione del punto di minimo di una funzione $f(\overline{x})$ , dove $\overline{x}$ è un vettore di variabili $\overline{x}={x_1,...,x_n}$ .

Indice

1 Preliminari matematici
2 Strumenti matematici per il calcolo del minimo di una funzione
3 Direzioni di discesa
4 Vincoli sui metodi di discesa - Condizioni di Wolfe
5 Algoritmo di backtracking
6 Implementazione dell'algoritmo in linguaggio C
7 Applicazioni pratiche

[modifica] Preliminari matematici

Data una funzione f calcolata in un punto identificato dal vettore di variabili $\overline{x^*}$ (siamo quindi nel caso di funzioni a due o più variabili) si chiama gradiente di f calcolato in $\overline{x^*}$ , e si indica con $\nabla f(\overline{x^*})$ , il vettore contenente le derivate parziali di f fatte rispetto ad ogni variabile (quindi la derivata di f fatta rispetto a $x 1,..., x n$ ) e calcolato nel punto di coordinate $\overline{x^*}$ :

Il gradiente di una funzione, analogamente alla derivata prima di una funzione di una variabile, indica in che modo la funzione cresce e decresce, e quindi il suo studio è indispensabile per poter stabilire il comportamento della funzione.

Data una funzione f calcolata in un punto identificato dal vettore di variabili $\overline{x^*}$ (siamo quindi nel caso di funzioni a due o più variabili) si chiama matrice hessiana di f calcolata in $\overline{x^*}$ , e si indica con $\nabla^2 f(\overline{x^*})$ , la matrice avente come colonne le derivate parziali miste della funzione calcolate nel punto $\overline{x^*}$ :

[modifica] Strumenti matematici per il calcolo del minimo di una funzione

Per trovare il minimo di una funzione non vincolata, sappiamo che gli strumenti dell'analisi matematica ci dicono che un punto identificato dal vettore di variabili $\overline{x^*}$ è detto punto di minimo di una funzione f quando sono valide entrambe queste proposizioni:

Il gradiente della funzione f calcolato in $\overline{x^*}$ è uguale al vettore nullo, $\nabla f(\overline{x^*})=0$
La matrice hessiana della funzione f calcolata nel punto $\overline{x^*}$ è una matrice definita positiva, ovvero ha autovalori positivi, determinante positivo e il prodotto della matrice per qualsiasi direzione ammissibile $\overline{d^*}$ è un vettore positivo, $\nabla^2 f(\overline{x^*})^T \overline{d^*} > 0$

Nel caso specifico di una funzione f di una variabile, queste condizioni diventano quelle già note dalle basi dell'analisi matematica:

$x *$ è un punto di minimo per f se e solo se

${d \over dx} f(x^*) = 0$

${d^2 \over d{x^2}} f(x^*) > 0$

ovviamente, mi riferisco sempre al caso di una funzione non vincolata.

Questi calcoli per la determinazione di un punto di minimo non sempre sono facili da effettuare. Possono essere fattibili in pochi passaggi nel caso di una funzione di una sola variabile, ma quando il numero di variabili aumenta richiedono il calcolo di vettori gradienti e matrici hessiane, e la determinazione della positività di queste ultime, cosa non sempre di facile calcolo, soprattutto nel caso di funzioni vincolate.

È per questo che in genere in questo campo si ricorre ai cosiddetti algoritmi di backtracking, ovvero algoritmi che partono da un punto qualsiasi della funzione e seguono una direzione di discesa (sempre con metodi sottoposti ad alcuni vincoli che vedremo in seguito), fino a trovare un punto di minimo per la funzione. Questi algoritmi vengono poi implementati in un calcolatore insieme all'equazione della funzione da minimizzare, e ne consentono la minimizzazione, in alcuni casi, in pochi step.

[modifica] Direzioni di discesa

Una direzione $\overline{d^*}=d_1,...,d_n$ si dice di discesa per la funzione $f$ calcolata in $\overline{x^*}$ se risulta valida la seguente disuguaglianza:

$\nabla f(\overline{x^*})^T \overline{d^*} < 0$

ovvero, "appena mi sposto" dal punto $\overline{x^*}$ lungo la direzione $\overline{d^*}$ , la funzione decresce.

$\nabla f(\overline{x^*})$ è il vettore gradiente calcolato nel punto $\overline{x^*}$ :

La direzione di discesa più comune è $\overline{d^*} = - \nabla f(\overline{x^*})$ (e il metodo di discesa corrispondente viene chiamato metodo di discesa ripida). Questo perché, se il gradiente di f calcolato in $\overline{x^*}$ identifica la direzione di salita della funzione, ovvero il verso in cui la funzione cresce, l'opposto del gradiente identificherà una direzione di discesa.

La strategia dei metodi di discesa è quella di generare quindi una successione finita di termini { $\overline{x^{(k)}}$ } tale che $\overline{x_{i+1}} \leq \overline{x_i} \mbox{ } \forall i$ , successione che, ovviamente, convergerà al punto di minimo ricercato $\overline{x^*}$ .

[modifica] Vincoli sui metodi di discesa - Condizioni di Wolfe

È opportuno imporre alcuni vincoli sui metodi di discesa esaminati nel paragrafo precedente. Questo perché la condizione $\nabla f(\overline{x^*})^T \overline{d^*} < 0$ mi assicura che appena mi muovo dal punto $\overline{x^*}$ la funzione f decresce, ma nulla mi assicura che, preso un $\overline{x_{i+1}} = \overline{x_i} + \overline{d^*}$ con $\overline{d^*}$ direzione di discesa, si abbia $\overline{x_{i+1}} \leq \overline{x_i}$ .

Questo perché nella ricerca del minimo è opportuno calibrare il tiro. Se con la mia direzione di discesa mi sposto troppo rischio di 'superare' il punto di minimo, rendendo l'algoritmo di discesa inefficace. Se invece mi sposto troppo poco, rischio di effettuare troppi step per cercare il minimo, rendendo l'algoritmo ridondante.

Per questo l'algoritmo di ricerca del minimo diventa un algoritmo di ricerca in linea così definito:

$\overline{x_{i+1}} = \overline{x_i} + \alpha_i \overline{d_i}$

dove lo scalare $α i > 0$ identifica la lunghezza del passo (ovvero quanto devo calibrare il tiro per avvicinarmi al minimo), $\overline{d_i}$ è la nostra direzione di discesa calcolata in $\overline{x_i}$ e $\overline{x_{i+1}}$ è il generico termine di indice i+1 della successione.

Lo scalare $α k$ va scelto in modo da soddisfare due condizioni fondamentali nella ricerca del minimo, dette condizioni di Wolfe:

$f(\overline{x_i} + \alpha_i \overline{d_i}) \leq f(\overline{x_i}) + c_1 \alpha_i \nabla f(\overline{x_i})^T \overline{d_i} \mbox{ con } c_1 \in [0,1]$

$\nabla f(\overline{x_i} + \alpha_i \overline{d_i})^T \overline{d_i} \geq c_2 \nabla f(\overline{x_i})^T \overline{d_i} \mbox{ con } c_2 \in [c_1,1]$

Senza dilungarci nella dimostrazione di queste due proposizioni, ci basta sapere che

La prima condizione stabilisce quanto piccolo deve essere $α i$ . Infatti, se prendo una lunghezza di passo troppo grande, rischio prima o poi di superare il punto di minimo, rendendo l'algoritmo del tutto inefficace.
La seconda condizione stabilisce quanto grande deve essere $α i$ . Infatti, se prendo una lunghezza di passo troppo piccola, rischio di entrare in un loop molto lungo per la ricerca del minimo, ovvero di effettuare tanti piccoli passi a partire dal punto di partenza senza però effettuare un progresso sostanziale nella ricerca del minimo, e quindi sprecando le risorse del sistema su cui eseguo l'algoritmo.

[modifica] Algoritmo di backtracking

L'algoritmo di backtracking riguarda il calcolo del valore dello scalare $α i$ . Inizialmente si prende uno scalare di partenza arbitrario (es. $\overline{\alpha} = 1$ ), e magari anche relativamente grande, quindi si riduce il valore di questo scalare in ogni ciclo finché non viene soddisfatta la prima condizione di Wolfe.

Ecco i passi di base dell'algoritmo (in metalinguaggio):

set 

while ()
    
end while

[modifica] Implementazione dell'algoritmo in linguaggio C

Ecco una possibile implementazione in linguaggio C dell'algoritmo visto sopra:

// La funzione prende come parametri un vettore di variabili reali,
 // che identifica il punto di partenza per l'algoritmo, e la sua dimensione
 float get_alpha(float *x, int dim)  {
   float alpha=1;
   float rho,c;
   float *arg;
   float *discesa;
   int i;
 
   // La direzione di discesa la pongo uguale, per convenzione
   // (metodo di discesa ripida), a -grad(x)
   discesa = (float*) malloc(dim*sizeof(float));
 
   for (i=0; i<dim; i++)
     discesa[i]=-grad(x)[i];
 
   // Inizializzo il generatore di numeri casuali
   srand ( (unsigned) time(NULL) );
   rho=rand();
   sleep(0.2);
   c=rand();
 
   // rho e c devono essere compresi tra 0 e 1
   rho /= pow(10,10);
   c /= pow(10,10);
 
   // Inizializzo l'argomento della funzione incrementato
   // lungo la direzione di discesa
   arg = sum(x,scal(alpha,discesa(x),dim),dim);
 
   while ( f(arg) > ( f(x)+(c*alpha*prod(grad(x),discesa(x),dim) ) )
     alpha*=rho;
 
   return alpha;
 }

dove ho posto, effettuando un algoritmo di backtracking con il metodo di discesa, il vettore discesa uguale a -grad(x), dove x è la mia variabile vettoriale di partenza. f(x) è la mia funzione da minimizzare, funzione che prende come parametro un vettore di variabili x e ritorna un valore reale, grad(x) è il suo gradiente calcolato sempre nel punto x. scal() è una funzione che non fa altro che moltiplicare un vettore per uno scalare (in questo caso alpha) e ritornare il vettore così modificato:

float* scal(float *v, float s, int dim)  {
   int i;
   float *v1;
 
   v1 = (float*) malloc(dim*sizeof(float));
 
   for (i=0; i<dim; i++)
     v1[i]=v[i]*s;
   return v1;
 }

prod() è una funzione che effettua il prodotto scalare tra due vettori aventi la stessa dimensione e ritorna lo scalare che rappresenta proprio questo prodotto:

float prod(float *v1, float *v2, int dim)  {
   int i;
   float res=0;
 
   for (i=0; i<dim; i++)
     res += (v1[i]*v2[i]);
   return res;
 }

sum è una funzione che somma due vettori aventi la stessa dimensione e ritorna il vettore somma:

float* sum(float *v1, float *v2, int dim)  {
   int i;
   float *v3;
 
   v3 = (float*) malloc(dim*sizeof(float));
 
   for (i=0; i<dim; i++)
     v3[i]=v1[i]+v2[i];
   return v3;
 }

[modifica] Applicazioni pratiche

Gli algoritmi per la ricerca del minimo di una funzione si vanno a collocare tra le strategie della programmazione matematica, e sono un caso più generale (e non necessariamente lineare) del caso particolare rappresentato dalla programmazione lineare (i cui problemi si risolvono generalmente con metodo geometrico o del simplesso).

Le applicazioni della programmazione matematica sono molteplici, soprattutto in campo economico, informatico e logistico, e riguardano tutto ciò che ha a che fare con problemi di ottimizzazione, minimizzazione o massimizzazione. Ad esempio, se un'azienda vuole produrre una certa gamma di prodotti minimizzando i costi di produzione, o massimizzando il guadagno, molto probabilmente dovrà ricorrere alle strategie della programmazione matematica, dove le variabili della funzione possono essere i costi dei singoli prodotti, o il guadagno dei singoli prodotti, o simili.

Anche in informatica vengono attuate strategie di programmazione matematica, soprattutto per quanto riguarda l'ottimizzazione dell'uso della memoria. Ad esempio, nel caso della memorizzazione di n variabili in memoria centrale in modo da minimizzare i tempi di accesso.

Estratto da "http://blacklight.gotdns.org/wiki/index.php/Algoritmi_di_backtracking"

Algoritmi di backtracking

Da Hacknowledge.

Indice

[modifica] Preliminari matematici

[modifica] Strumenti matematici per il calcolo del minimo di una funzione

[modifica] Direzioni di discesa

[modifica] Vincoli sui metodi di discesa - Condizioni di Wolfe

[modifica] Algoritmo di backtracking

[modifica] Implementazione dell'algoritmo in linguaggio C

[modifica] Applicazioni pratiche

Visite

Strumenti personali

Navigazione

Ricerca

Strumenti