Il calcolo dell’energia totale mediante uno dei metodi illustrati nella precedente sezione permette la determinazione della Potential Energy Surface (PES) del sistema fisico sotto indagine. La possibilit`a di calcolare anche il gradiente dell’energia consente una ricerca dei punti stazionari di questa superficie multidimensionale e di individuarne i punti di minimo locale.
Nel caso in cui si voglia determinare il minimo globale, ossia il pi`u profondo fra i minimi locali della superficie, `e necessario eseguire un’indagine completa della PES: questo obiettivo pu`o risultare molto difficile da perseguire, dal momento che il numero di minimi locali aumenta al crescere del numero di atomi componenti il sistema pi`u velocemente di qualsiasi funzione polinomiale (ci sono molte indicazioni che l’aumento sia esponenziale). Una mappatura di tutti i minimi locali mediante una ricerca random sulla PES risulta impossibile per sistemi composti da pi`u di una decina di atomi, perci`o `e necessario sviluppare un algoritmo di ricerca della PES che assicuri una rapida convergenza verso punti di minimo a bassa energia. L’abilit`a dell’algoritmo di ricerca nel trovare il minimo globale dipende inoltre dalla forma della PES, la quale, a seconda del potenziale di interazione scelto, dalla taglia e dalla composizione del sistema, pu`o risultare pi`u semplice da esplorare (nel senso che l’algoritmo converge velocemente verso un minimo a bassa energia, che credibilmente risulta il minimo globale) oppure pi`u difficile (con minimi a bassa energia che vengono raggiunti difficilmente, al punto che alcune esplorazioni possono rimanere bloccate attorno ad una configurazione meno favorevole, la quale `e per`o indicata dall’algoritmo di ricerca come minimo globale del sistema).
A questo punto, `e interessante individuare quali siano le caratteristiche di una PES che permettono una veloce convergenza verso il minimo globale. Innanzitutto, nel momento in cui ci accingiamo a considerare una PES, risulta conveniente eseguire una mappatura dallo spazio configurazionale continuo del sistema ad un insieme discreto di valori determinato dai minimi locali della superficie; questa trasformazione viene eseguita associando ad ogni punto {~r} dello spazio delle fasi il minimo locale pi`u vicino a tale punto, ossia il minimo locale che viene raggiunto da una minimizzazione steepest-descendent che parte da {~r}. Definiamo quindi la nuova superficie di energia potenziale nel modo seguente:
˜
V ({~r}) = min[V ({~r})] (1.45)
dove min significa appunto una minimizzazione steepest-descendent eseguita a partire da {~r}. Questa operazione di trasformazione `e mostrata in Figura (1.14); come si vede chiaramente dalla figura, ˜V ({~r}) risulta una scala (in realt`a multidimensionale).
L’insieme di tutti i punti associati allo stesso minimo α costituiscono il bacino di attrazione del minimo. Tutti i punti di uno stesso bacino sono connessi per definizione. Bacini di attrazione vicini (solitamente appartenenti alla stessa famiglia strutturale) possono essere a loro volta raggruppati in metabacini. Una rappresentazione delle connessioni fra bacini, metabacini, ecc., `e data dai diagrammi di disconnetivit`a, che permettono di capire graficamente quali bacini sono connessi ad un dato valore dell’energia totale del sistema: due bacini sono connessi ad un dato valore dell’energia quando il punto pi`u in alto sul cammino di minima energia che unisce i due bacini possiede un’energia al di sotto di quella stessa energia. Porzioni della PES possono essere classificate in tre diversi tipi a seconda del tipo di connessioni fra i suoi bacini di attrazione:
1. una PES rough o corrugata - Figura (1.15a)
2. una PES con un singolo minimo ed un debole rumore di fondo - Figura (1.15b) 3. una PES con un singolo funnel -Figura (1.15c)
Figura 1.14: trasformazione della PES in una scala multidimensionale
E’ abbastanza intuitivo che il minimo assoluto sar`a raggiunto agevolmente e velocemente nei casi (2) e (3), mentre nei casi (1) e (4) l’algoritmo potr`a tendere ad imbucarsi in un minimo locale non necessariamente corrispondente al minimo globale. In Figura (1.15d) `e riportato il caso del cluster LJ38 (cluster isolato con potenziale atomo-atomo di tipo Lennard-Jones e taglia pari a 38 atomi); la PES di questo sistema presenta due funnel: il primo funnel risulta ampio e raccoglie motivi icosaedrici, ma non corrisponde al minimo globale; il secondo funnel `e molto pi`u stretto ma contiene il minimo globale, che corrisponde ad un motivo di tipo fcc (precisamente un troncottaedro). La natura della PES fa s`ı che un algoritmo di ricerca del minimo resti intrappolato con alta probabilit`a nel primo funnel e quindi non sia in grado di individuare il minimo globale. Tale situazione `e tipica dei cluster, non solo quelli metallici, in quanto, a causa dell’alto rapporto superficie/volume, essi presentano una frazione elevata di atomi coordinativamente insaturi; ma lo stesso problema si trova in generale in tutti i sistemi frustrati, quali sistemi amorfi, sistemi vetrosi ecc. Va inoltre tenuto presente, a questo proposito, che un’esplorazione incompleta dello spazio delle fasi ed un intrappolamento in configurazioni che non corrispondono al vero minimo globale, in taluni casi non risulta un mero artificio dell’approccio computazionale ma corrisponde a fenomeni fisicamente realizzabili di intrappolamento cinetico (come nel caso di sistemi vetrosi in presenza di isteresi).
La ricerca del minimo globale pu`o essere unbiased nel caso in cui la configurazione di partenza `e scelta in maniera del tutto casuale oppure biased o seeded nel caso in cui la procedura di ricerca abbia come punto di partenza un insieme di configurazioni scelte opportunamente (magari appartenenti a diverse famiglie strutturali). Nel secondo caso, la procedura di ricerca del minimo globale `e indirizzata da una conoscenza a priori della struttura della PES, perci`o solitamente l’algoritmo raggiunge il minimo globale in tempi minori; lo svantaggio di questo approccio `e che questa ricerca pu`o tagliare fuori minimi locali inaspettati ma, nonostante ci`o, competitivi. Proprio per quest’ultimo motivo, una ricerca unbiased, sebbene computazionalmente pi`u dispendiosa, `e in grado di fornire risultati maggiormente significativi. Da queste considerazioni, possiamo dire che un efficiente algoritmo di ricerca del minimo deve essere in grado di soddisfare i due seguenti requisiti:
1. da un qualsiasi punto di partenza della PES, l’algoritmo deve essere in grado di trovare il minimo locale ad esso associato; ci`o `e necessario al fine di costruire la mappatura della superficie secondo l’equazione (1.45)
Figura 1.15: esempi di (a) rough PES; (b) PES a singolo minimo con debole rumore di fondo; (c) PES a singolo funnel; (d) PES a doppio funnel. Nel caso di (a-c) sulla destra sono riportati anche i relativi diagrammi di disconnetivit`a
2. l’algoritmo deve essere in grado di eseguire transizioni da un bacino ad un altro, e, pi`u importante ancora, da un metabacino ad un altro. Solo in quest’ultimo caso, infatti, la procedura `e in grado di esplorare PES caratterizzate da pi`u funnel
Fra gli algoritmi che sono stati sviluppati e che soddisfano entrambi questi requisiti, verranno discussi solo il Basin Hopping (sezione 1.2.1), gli algoritmi che utilizzano i Parallel Excitable Walkers (sezione 1.2.2), gli algoritmi Genetici (sezione 1.2.3) ed il Simulated Annealing (sezione 1.2.4).
1.2.1
L’algoritmo Basin Hopping
Gli algoritmi di Basin Hopping (BH) [70] si basano su una simulazione Monte Carlo a temperatura costante sulla superficie di energia potenziale trasformata mediante la mappatura espressa dall’equazione (1.45). Nell’ambito della procedura di BH, l’operazione di mappatura ha lo scopo di abbassare il pi`u possibile le barriere energetiche che separano i diversi bacini di attrazione, lasciando invece inalterati i valori di energia dei minimi locali. La procedura si articola nei seguenti punti:
1. partendo da una determinata configurazione iniziale (random nel caso di unbiased search o sele- zionata opportunamente nel caso di seeded search), corrispondente al punto { ~r1} dello spazio delle fasi, l’algoritmo esegue un’ottimizzazione raggiungendo il minimo locale con energia E1
2. partendo dalla prima configurazione di minimo raggiunta, viene eseguito un passo random sulla superficie di energia potenziale (che corrisponde ad un cambiamento casuale delle coordinate degli atomi del sistema); a partire da questo punto { ~r2}, l’algoritmo esegue una seconda ottimizzazione raggiungendo il minimo locale con energia E2
3. viene valutata la differenza di energia (E2− E1): se questa differenza di energia `e negativa, significa che il secondo minimo `e migliore del primo ed il movimento del punto 2 viene accettato. Altrimenti, viene generato un numero casuale compreso fra 0 ed 1, che denominiamo rndm. Il movimento del
punto 2 viene accettato nel caso in cui (criterio di Metropolis):
e−(E2−E1)kB T > rndm (1.46)
se questa condizione non viene soddisfatta, il movimento del punto 2 viene rifiutato e si procede a generare una nuova configurazione casuale partendo dal minimo locale trovato al punto 1
Al crescere della temperatura T della simulazione, movimenti accompagnati da valori di (E2−E1) positivi sono accettati con maggiore probabilit`a e quindi risulta pi`u facile saltare da un funnel ad un altro, ma anche spostarsi verso minimi locali ad alta energia. Il fatto che le nuove configurazioni siano scelte al punto 2 per movimento casuale fa s`ı che le transizioni possano avvenire in qualsiasi direzione e non solo lungo i cammini che corrispondono ai punti di sella della superficie multidimensionale.
Questo algoritmo unisce un’estrema semplicit`a di implementazione ad una grande efficienza computazio- nale, stimata come sforzo computazionale necessario per individuare il minimo globale.
1.2.2
L’algoritmo Basin Hopping modificato: i Parallel Excitable Walkers
Come abbiamo appena visto, l’algoritmo di BH risulta molto efficiente a trovare il minimo globale della PES nel caso in cui la superficie presenti un unico funnel; nel caso di superfici multi-funnel, l’algoritmo di ricerca pu`o incontrare dei problemi: le barriere che separano i diversi funnel possono essere infatti superate scegliendo un alto valore della temperatura, condizione che per`o diminuisce l’efficienza di individuare il minimo globale all’interno di un determinato funnel; tale problema `e ulteriormente aggravato nel caso in cui uno dei funnel sia stretto perch`e una temperatura eccessiva pu`o portare a saltare in blocco tale funnel o comunque a rendere complessa l’esplorazione dettagliata della sua struttura. In altre parole, le due esigenze (quella di muoversi da un funnel all’altro e quella di trovare il minimo globale di ogni funnel) sono in competizione e rendono complessa l’esplorazione esaustiva della superficie.
Tale problema pu`o essere risolto in vari modi, ad esempio modificando l’algoritmo di BH introducendo un parametro di ordine p(~r) e facendo evolvere in parallelo due o pi`u run di BH (gli walker ) [71]. Due walker i e j sono vicini nello spazio configurazionale del parametro d’ordine nel caso in cui
|p(~ri) − p(~rj)| ≤ δ (1.47)
Le mosse dei due walker sono accettate secondo il criterio di Metropolis esposto nella precedente sezione. Il parametro d’ordine non `e che una grandezza che classifica le configurazioni in base al motivo strutturale a cui esse appartengono. Se uno walker non ha vicini nello spazio del parametro d’ordine, la procedura che governa la sua evoluzione `e quella del BH canonico; al contrario, se lo walker ha almeno un vicino, ∆E = (E2− E1) `e sostituito da:
∆E∗= ∆E − Eexc (1.48)
il che corrisponde ad aumentare l’energia E1 della quantit`a positiva Eexc; in altre parole la presenza di un vicino nello spazio del parametro d’ordine aumenta la probabilit`a con cui il passo di BH pu`o venire accettato: questo significa che il walker pu`o evolvere anche accettando mosse energeticamente alquanto sfavorevoli (se ci`o lo porta verso un altro motivo strutturale), superando le barriere che separano un funnel da un altro. Nel momento in cui uno degli walker si trova in un funnel diverso, esso si trova ad essere caratterizzato da un diverso parametro d’ordine e quindi a non avere pi`u vicini nello spazio del parametro d’ordine: a questo punto l’evoluzione dello walker seguir`a un classico BH che consente di individuare agevolmente il minimo globale di quel particolare funnel. Grazie all’introduzione del parametro d’ordine, `e quindi possibile mantenere bassa la temperatura di esplorazione (eseguendo un sampling accurato delle profondit`a del funnel) e riuscire comunque a superare le barriere di energia potenziale che separano i funnel.
1.2.3
Algoritmi Genetici
Tra i concorrenti del metodo Basin Hopping, i pi`u noti sono dati dagli algoritmi genetici e dal Simulated Annealing: questi algoritmi verranno qui descritti molto brevemente perch`e non utilizzati in questo lavoro di tesi.
Gli algoritmi Genetici [72] sono basati sull’analogia fra la selezione del minimo locale a pi`u bassa energia e la selezione degli individui di una popolazione naturale: in entrambi i casi, la selezione avviene mediante l’associazione dell’individuo con un parametro numerico che misura la sua fitness. Nel caso di selezione del minimo globale, la fitness corrisponde all’energia totale del sistema considerato ed `e questo parametro che deve essere ottimizzato.
Le coordinate degli atomi che costituiscono il sistema sono registrate in una stringa chiamata cromosoma. Al primo passo, l’algoritmo genera la prima generazione della popolazione, i cui individui differiscono per i cromosomi, ossia per le coordinate degli atomi costituenti. Al passo successivo, viene generata una nuo- va popolazione di individui mescolando i cromosomi degli individui della generazione precedente oppure inserendo mutazioni nei loro cromosomi. Gli individui della nuova generazione sono confrontati con gli individui della generazione precedente (confronto fra genitori e figli) ed un’ulteriore generazione nasce dall’incrocio delle due generazioni in base a regole prestabilite, che comunque prevedono la predilezione per la selezione dei cromosomi di individui che possiedono una migliore fitness (ossia una pi`u bassa ener- gia totale). Ad ogni passo, gli individui della nuova generazione dovrebbero essere caratterizzati da una migliore fitness e l’algoritmo dovrebbe infine convergere verso il minimo globale della superficie di energia potenziale.
L’esplorazione dei diversi bacini di attrazione della PES avviene quindi mediante il mixing dei cromosomi, le mutazioni ed anche mediante l’incrocio fra subpopolazioni che si evolvono in parallelo; la valutazione della fitness viene eseguita mediante un’ottimizzazione locale su ogni individuo a partire dal suo cromo- soma originario a dare il suo cromosoma ottimizzato (corrispondente al minimo locale pi`u vicino). Dal punto di vista computazionale, l’implementazione di un algoritmo Genetico richiede uno sforzo no- tevolmente maggiore di quello di un algoritmo di Basin Hopping senza garanzie di maggiore esaustivit`a (problema dell’inefficienza).
1.2.4
Algoritmi di Simulated Annealing
In un algoritmo di Simulated Annealing [73], il sistema evolve a temperatura alta e costante sulla super- ficie non trasformata di energia potenziale secondo una simulazione di classica dinamica molecolare; ad intervalli di tempo fissati, le strutture in cui il sistema si trova vengono estratte e minimizzate localmente mediante un lento raffreddamento; fra i minimi locali cos`ı ottenuti viene selezionato il minimo globale. Il vantaggio di questa procedura `e che essa risulta pi`u fisica delle procedure considerate precedentemente: lo scopo `e infatti quello di mimare il reale raffreddamento del sistema, il quale, se il raffreddamento `e sufficientemente lento, raggiungerer`a la sua configurazione di minima energia.
Se da una parte l’implementazione `e semplice perch´e la stessa di un normale run di dinamica molecolare, lo svantaggio `e che il sistema pu`o facilmente restare cineticamente intrappolato in un minimo locale; come abbiamo gi`a sottolineato, ci`o pu`o, in linea di principio, anche corrispondere ad una reale situazione fisica, che per`o non corrisponde allo scopo che ci siamo prefissi, ossia quello di individuare il minimo globale della superficie di energia potenziale. Ci`o avviene perch´e, a causa delle limitate scale di tempo di una simulazione, le velocit`a di raffreddamento possono risultare di svariati ordini di grandezza superiori a quelle fisicamente realizzabili in un reale esperimento di annealing.
Da queste considerazioni, si pu`o concludere che l’esaustivit`a di questo approccio `e estremamente inferiore a quella del Basin Hopping e degli algoritmi Genetici.
1.2.5
Approcci ibridi potenziale semi-empirico/DFT con riconoscimento strut-
turale
Gli algoritmi discussi nelle precedenti sezioni possono essere utilizzati in linea di principio in modo equivalente sia che la minimizzazione locale venga condotta utilizzando un potenziale semi-empirico di interazione sia che tale minimizzazione venga condotta a livello DFT (o, in generale, con un metodo da principi primi). Chiaramente il costo computazionale varia di diversi ordini di grandezza nei due casi: con le risorse computazionali al giorno d’oggi normalmente disponibili, `e fattibile condurre in tempi ra- gionevoli ottimizzazioni globali utilizzando potenziali semi-empirici su sistemi composti fino a 100/200 atomi. A livello DFT, il numero di atomi costituenti il sistema sotto indagine si riduce di un ordine di grandezza (sistemi costituiti da circa 10/20 atomi). Quando si voglia verificare l’accuratezza delle predi- zioni dei potenziali semi-empirici su sistemi contenenti un numero di atomi superiore alla decina `e quindi necessario utilizzare approcci alternativi, quali, ad esempio, di tipo ibrido potenziale/DFT. In questo tipo di approcci, si conduce un run preliminare di Global Optimization usando potenziali atomo-atomo; da questo run vengono selezionati i minimi pi`u bassi in energia, i quali vengono riottimizzati localmente utilizzando il metodo DFT. Da questo punto di vista, si potrebbe dire che questo approccio `e dal punto di vista del calcolo DFT, una seeded search, in cui la conoscenza a priori della struttura della PES deriva dai calcoli che utilizzano i potenziali semi-empirici, ed in cui vengono condotte solo ottimizzazioni locali. Questo approccio `e stato proposto per la prima volta in [74]: nella letteratura precedente, infatti, la prassi consueta consisteva nel minimizzare solo i minimi pi`u bassi in energia, a prescindere dalla loro classificazione in famiglie strutturali, rendendo quindi il metodo estremamente meno esaustivo. Chiara- mente l’esaustivit`a del metodo dipende fortemente dalla possibilit`a di avere a disposizione un potenziale semi-empirico realistico.
Figura 1.16: procedura ibrida potenziale/DFT per la determinazione dell’ordine energetico dei diversi motivi strutturali
In questo contesto, la nostra esperienza mostra come effetti quantistici (che verranno discussi in seguito) sono in grado di modificare sostanzialmente l’ordine energetico delle diverse famiglie strutturali deter- minato dall’utilizzo del potenziale semi-empirico (vedi Figura (1.16)), e che pertanto il riconoscimento
strutturale risulta decisivo per il successo del metodo. Rispetto a considerare solo i motivi a pi`u bassa energia come emergono dai risultati del potenziale, `e quindi molto pi`u affidabile una procedura che estrae dalla simulazione preliminare alcune configurazioni a pi`u bassa energia per ciascuna famiglia strutturale, minimizza localmente queste strutture con il metodo DFT e verifica se l’ordine energetico dei diversi motivi strutturali risulta invertito oppure no.
In questa prospettiva, l’algoritmo dei parallel excitable walkers risulta particolarmente utile ai fini di una esplorazione esaustiva dell’intero spazio delle fasi e dei diversi motivi strutturali del sistema.