Lo Spatial Simulated Annealing (SSA) sceglie la distribuzione ottimale basandosi su un indicatore chiamato fitness function che nel caso in esame si riferisce alla distanza fra i punti campione ed i restanti punti del dominio.
Questa procedura di ottimizzazione consente di avere una distribuzione tale che concorre a minimizzare l’errore, minimizzando la distanza fra ogni punto non campionato del dominio e il punto di campionamento più vicino, grazie alla ottimizzazione di una fitness function φ.
Si minimizza la fitness function ±+·.: ;o À dove Sn è il dominio ed n il numero di punti. L’ottimizzazione parte con una distribuzione casuale ;A ;o si induce una sequela di perturbazioni casuali Si+1 che ha probabilità di essere accettata =Ö+;¸ ;¸À .. Tale trasformazione è realizzata secondo il criterio Metropolis:
µ=Ö+;¸ ;¸À . 1 ±+;¸À . ! ±+;¸. =Ö+;¸ ;¸À . P
"+dì.{"+dìßà.
Ö ±+;¸À . ±+;¸.Õ 5.1
In cui c è un parametro positivo di controllo, che risulta via via ribassato durante il prosieguo dell’ottimizzazione, valutabile secondo le equazioni proposte da Aarts e Korst nel 1989:
ö\À ö\ 5.2
con k numero naturale che rappresenta il numero di elaborazioni svolte dell’ottimizzazione ed
α parametro di “uso e scelta” assunto generalmente chiuso ad 1.
Se Si+1 è accettata servirà come punto di partenza per l’iterazione successiva Si+2 ed il processo continua in modo similare (Aarts e Korst, 1989).
La fitness function φ rappresenta una stima del grado di accettabilità di una soluzione in base alla distribuzione spaziale dei suoi punti ed alle distanze possibili fra i punti non campionati ed il campione più vicino ad ogni punto. Il criterio di Metropolis, enunciato, permette di scegliere la soluzione che presenta l’indicazione della distanza minima assegnandogli di volta in volta una probabilità di accettazione elevata.
Alcuni criteri di ottimizzazione sono stati introdotti nell’approccio SSA come applicazione di fitness function. In questa tipologia di studi sono sostanzialmente dominanti due tipologie di fitness function: il criterio MMSD e il criterio di kriging ordinario.
Il criterio MMSD (Minimized Means of Shortest Distances) basa sull’ottimizzazione sulla minimizzazione della media delle distanze di ogni punto del dominio dal punto di campionamento ad esso più vicino, la fitness function che ne indica l’entità si esprime:
±#+;¸. ¿$% w ÂT+%.$ Q 5.3
±+;¸. M &((((% w ÂZ' TN((((%O&Z' mZ oâ þ 5.4
Il criterio del kriging ordinario minimizza la media della varianza di kriging ordinario sul dominio, la fitness function che ne stima l’entità è data da:
±#ýú+;¸. ¿ ýú +A|;¸. Q 5.5
che in un dominio di tipo GRID elaborato da raster come quello in esame diventa:
±ýú+;¸. Mýú R Zþ);¸` mZ oâ þ 5.6
dove Zþ il generico nodo raster e n è il numero dei nodi. Tale criterio permette di ottimizzare tenendo in conto le anisotropie del suolo, ma appunto per questo c’è bisogno di conoscere i parametri geostatistici che ne indicano l’entità, come il tipo di variogramma, le condizioni al contorno, il sill, il nugget ed altri. Per conoscere tali parametri è indispensabile avere uno studio preliminare che ne indichi una stima.
Questi due criteri sono quelli maggiormente utilizzati, ma ve ne sono molti altri, che in casistiche specifiche possono rappresentare soluzioni sensibilmente migliori. Alcune di queste non sono ancora completamente sviluppate, altre non sono ancora fruibili con strumenti di calcolo automatico. Un criterio utilizzabile in alcuni ambienti di calcolo è il WMSD (Weightd Means of Shortest Distances) che è una versione pesata del criterio MMSD, utile per domini con aree in cui si deve investigare con più accuratezza di altre e pertanto si assegna una funzione peso che conferisce alle aree da conoscere con maggiore dettaglio un peso maggiore cosicché la distribuzione vi investirà più punti, arrivando ad una fitness function che si scrive:
±#*+d+;¸. ¿ ,+%.$% w ÂT+%.$ Q 5.7
che in un dominio di tipo raster come quello in esame diventa:
±#*+d+;¸. M , N((((%O&Z' ((((% w ÂZ' TN((((%O&Z' mZ oâ þ 5.8
La funzione peso va fissata in base alle caratteristiche del territorio o a peculiarità di studi precedenti.
Nell’approccio SSA la perturbazione casuale, che consente di cambiare soluzione di distribuzione, consiste nella trasformazione di tali distribuzioni casuali in un vettore di lunghezza e direzione casuale. Si considera un vettore ù¸o, dove n è il numero degli elementi. Ad ogni iterazione si assegna ad un elemento casuale un valore casuale ed a tutti gli altri si assegna il valore nullo. Il
preliminari che restano fisse all’interno del vettore. La procedura di ottimizzazione prevede che al vettore ù¸o siano applicate perturbazioni tali da generare configurazioni successive fino ad ottenere un vettore accettabile, scelto secondo il criterio Metropolis esposto in precedenza.
In questo criterio la distribuzione dei punti durante l’elaborazione si comporta come la configurazione delle particelle nella materia durante un processo di decadimento della temperatura – visto che in natura i sistemi tendono alla energia minima ed all’entropia massima – che di distribuzione in distribuzione diminuiscono la “mobilità”, da una configurazione a quella successiva, da una trasformazione e quella successiva. In conclusione di questo processo si hanno trasformazioni quasi impercettibili fino ad avere configurazioni pressoché identiche in prossimità di quella ottimale, similmente al “congelamento” delle particelle nella formazione di un solido non cristallino. Tale procedimento conferisce alla distribuzione il massimo grado di disordine e di espansione nel dominio, generando, così, la migliore soluzione di distribuzione.
L’analogia della temperatura è molto comoda da utilizzare, per cui è usata nella definizione e nella implementazione di queste metodologie, al fine di usufruire del programma di calcolo automatico con l’approccio SSA in modo semplificato.