5. Generatore di numeri casuali e Simulazione Montecarlo

5. Generatore di numeri casuali e Simulazione Montecarlo

Nel seguente capitolo vengono brevemente esposti alcuni concetti riguardanti la Teoria dei numeri casuali e le metodologie con le quali è possibile affrontare problemi legati al concetto di caso. La generazione dei numeri casuali è stata affrontata tramite il codice di calcolo Matlab: sono state utilizzate alcune routine già presenti in libreria, mentre altre sono state costruite sulla base dello specifico problema in esame.

5.1 Introduzione alla generazione di numeri pseudo-casuali

I numeri casuali vengono generalmente utilizzati per costruire simulazioni di natura probabilistica di fenomeni fisici, di problemi decisionali e finanziari e problemi di informatica. Un possibile modo per ottenere tali simulazioni si basa sull’impiego del Metodo Montecarlo. L’idea di utilizzare in modo sistematico questo tipo di simulazioni probabilistiche per risolvere problemi di natura fisica, viene generalmente attribuita al matematico polacco Stanislaw Ulam.

Il concetto di numero casuale risulta essere di una certa familiarità: un semplice esempio è quello del lancio del dado in cui l’imprevedibilità del numero ottenuto conferisce una forma di casualità. Una domanda lecita può essere quella di chiedersi come un calcolatore, e quindi una macchina puramente deterministica e con ciò prevedibile, possa generare una sequenza di numeri casuali. In effetti un calcolatore può solo generare numeri pseudo-casuali, ossia numeri generati da

algoritmi numerici deterministici in grado di superare una serie di test statistici che conferiscono a tali numeri un’apparente casualità.

Nei primi anni dell’epoca del computer, John Von Neumann suggerì la metodologia middle-square per generare una sequenza di numeri pseudo-casuali con distribuzione uniforme. Tale metodologia richiede un valore iniziale, detto seme, dal quale vengono generati i successivi valori. Tuttavia, poiché ogni numero della sequenza viene generato dal suo predecessore, tale successione non potrà mai essere casuale, ma avrà solo il carattere di apparente casualità. Infatti tale sequenza prima o poi inizierà a ripetersi e, l’insieme dei numeri che viene generato prima che intervenga la ripetizione prende il nome di periodo. La lunghezza di tale periodo misura la bontà del generatore di numeri pseudo-casuali. Un’altra richiesta fondamentale nel valutare la bontà del generatore è l’assenza di correlazione tra i numeri generati dall’algoritmo. In altre parole, data la sequenza

{ }

xk non deve

emergere nessun legame tra xk e xk+1 ∀ >k 0.

Da allora numerosi algoritmi e generatori sono stati implementati tramite svariati codici di calcolo e molti di essi sono disponibili in commercio.

5.2 Generatore lineare congruenziale

L’algoritmo più diffuso di generatore di numeri casuali è stato il generatore lineare congruenziale (LCG), la cui formulazione venne attribuita a D.H.Lehmer nel 1948. Questo tipo di generatore necessita di tre parametri interi costanti, a, c, m, accompagnati da un valore iniziale x0, detto seme. L’algoritmo viene così definito:

(

)

1 mod

k k

x₊ = ax +c m (5.1)

in cui mod m significa che axk+c viene diviso per m, e xk+1 viene posto uguale al resto intero della divisione. La limitazione di tale procedimento è insita nel suo periodo, e quindi il problema della scelta dei parametri a, c, m, risulta essere un punto cruciale per stabilire la bontà del generatore. Il parametro m dovrà essere grande e, fissato m, i parametri a e c dovranno essere tali che la sequenza abbia periodo massimo. In genere ci si può restringere ai generatori moltiplicativi, c=0, che sono i più veloci. Una delle scelte più adottate è la seguente:

31

2 1

m= − 5 7

a= c=0 (5.2)

che garantisce un periodo pari a 31

2 −1. Tutte le prime versioni Matlab, fino alla quarta, utilizzavano tale generatore.

5.3 Algoritmo di Marsaglia

A partire dalla quinta versione di Matlab, è stato introdotto un generatore di numeri casuali di natura completamente diversa rispetto al precedente. Questo algoritmo, dovuto al lavoro di George Marsaglia, professore della Florida State University, è stato utilizzato per lo svolgimento della seguente Tesi. In accordo con quanto indicato in [8], il generatore di Marsaglia non utilizza l’algoritmo di Lehmer, ma si basa su una complessa combinazione di operazioni di spostamento di registri e manipolazioni sui bit che non richiedono nessuna operazione di moltiplicazione o divisione (chiamata shift register random generator), combinato con un particolare generatore ritardato di Fibonacci, in modo tale da rendere il generatore efficiente. Tale algoritmo è stato progettato proprio al fine di generare numeri a virgola mobile (nella letteratura specifica, floating-point values) distribuiti uniformemente nell’intervallo

[ ]

0,1 . La teoria che sta alla base di questo generatore è piuttosto complessa per cui di seguito verranno esposti esclusivamente i punti salienti che la caratterizzano.

In primo luogo si analizzerà brevemente come opera il generatore ritardato di Fibonacci, e, successivamente, si darà una breve introduzione riguardo i concetti legati allo shift register random generator.

La funzione Matlab utilizzata è rand: ogni volta che viene chiamata rand viene generato un numero casuale. L’algoritmo utilizzato in questa funzione richiede uno stato (state) per iniziare e questo viene ottenuto dal clock della CPU del computer. Se, ad esempio, con il comando rand(‘state’,k) viene dichiarato lo stato k del generatore, digitando n volte rand si ottiene una sequenza di n valori numerici; se poi, ripetendo lo stesso comando rand(‘state’,k) viene ripristinato lo stato k , digitando n volte rand si ottiene nuovamente la sequenza di prima.

Lo stato è caratterizzato da 35 elementi (detti words) tali che i primi trentadue elementi costituiscono un insieme di numeri a virgola mobile, z_i, compresi tra 0 e 1, che vengono memorizzati in una posizione temporanea ma di veloce accessibilità che

è la cache. Questi vengono trattati in modo da creare una sequenza ciclica: se, ad esempio, i=32, allora si avrà che zi+1 =z33 =z1. I rimanenti tre elementi sono così costituiti:

• il trentatreesimo elemento è detto flag ed è indicato con b : può assumere solo due valori, 0 oppure 53

2− . Tale quantità è la metà della costante Matlab eps che rappresenta la precisione di macchina (pari a 52 16

2− ≃2.22 10⋅ − ) e viene generalmente indicata come ulp (unit in the last place);

• il trentaquattresimo elemento è l’indice intero i che rappresenta l’indice della sequenza ciclica zi: è variabile in maniera progressiva da 0 a 31 ogniqualvolta

venga digitato rand, per poi ripetersi;

• il trentacinquesimo elemento è un numero intero j utilizzato anch’esso per definire lo stato corrente del generatore.

Quindi, impostato inizialmente lo stato del generatore con il comando rand(‘state’,k), ogni volta che viene digitato rand si ottiene la creazione di zi e la

variazione della terna

(

b i j, ,

)

e lo stato del generatore si aggiorna in modo tale da generare un nuovo numero casuale. Il tutto può essere facilmente visualizzato digitando, ad esempio, s=rand(‘state’) nella command window di Matlab.

Al posto del generatore di Fibonacci espresso nella sua forma più semplice, ossia non ritardata, come:

1 2 0 1 1 k k k z z z z z − − = +   = =  (5.3)

in ambiente Matlab si sfrutta, invece, l’algoritmo nella sua versione ritardata. Si supponga ora di voler creare una sequenza

{

x1,..., ,...,xi xn

}

di numeri casuali. La loro

generazione è strettamente legata alla generazione della sequenza

{ }

zi . La

generazione dell’ i−esimo numero a virgola mobile zi della sequenza ciclica è

affidata ad una particolare operazione (indicata in gergo tecnico come subtract with borrow generator), in cui il numero presente nella memoria cache alla posizione

i−esima viene rimpiazzato dalla seguente differenza:

i i p i q

in cui si prende p=20 e q=5. Ad ogni passo della sequenza, la quantità b viene definita dal passo precedente, secondo tale schema:

0 0 i i z z ≥   <  ⇒ ⇒ 53 0 2 b b − = = , , 1 i i i i z z z z = = + (5.5)

Quindi, con riferimento al passo i−esimo, se il valore calcolato di zi risulta positivo,

allora b viene posto pari a 0 per il passo successivo, mentre se zi risulta negativo

viene prima reso positivo semplicemente sommando 1 e poi b viene posto pari a 53

2− per il passo successivo. Continuando in questo modo, passo dopo passo, al variare di i si aggiorna sempre la sequenza ciclica

{ }

zi presente nella cache, varia la

terna

(

b i j, ,

)

e, grazie ad ulteriori operazioni che per motivi di semplicità di esposizione verranno qui tralasciati, si ottiene infine la sequenza di numeri pseudo-casuali cercata

{ }

xi .

Questo particolare tipo di algoritmo risulta quasi completamente soddisfacente, presentando infatti un periodo estremamente lungo, stimato pari a 1492

2 . Tuttavia esiste un unico difetto, che in questa sede viene solo accennato: tutti i numeri generati sono il risultato di addizioni e sottrazioni di un insieme di numeri presenti nella cache iniziale, per cui risultano tutti essere multipli interi di 53

2− . Di conseguenza alcuni numeri a virgola mobile dell’intervallo

[ ]

0,1 non sono rappresentati nelle sequenze generate.

Nelle ultime versioni Matlab, e come indicato precedentemente, nell’ottica di limitare l’insorgere di questi problemi di generazione, è stato scelto di abbinare all’algoritmo ritardato di Fibonacci una particolare applicazione degli LFSR (Registri di Traslazione a Retroazione Lineare) per migliorare la qualità della sequenza generata. Gli LFSR sono dei registri di traslazione i cui dati di ingresso sono prodotti da funzioni lineari ad un singolo bit: le funzioni scelte sono lo XOR e lo XNOR, perciò si ottiene un registro di traslazione i cui bit in ingresso sono prodotti dall’OR esclusivo di alcuni bit memorizzati all’interno di registri.

Il valore iniziale di un LFSR è anch’esso chiamato seme: l’operazione è deterministica per cui la sequenza di valori generati dal registro è completamente definita dal suo stato corrente. Il registro possiede un numero finito di possibili stati, per cui i valori in uscita si ripeteranno a partire da un certo punto in poi. Tuttavia, scegliendo un LFSR con un’opportuna funzione di retroazione, si può produrre una

sequenza di bit con un periodo molto lungo. Per ulteriori approfondimenti, si cita tra tutti [9].

Per il seguente lavoro di Tesi, è stato scelto, dunque, di utilizzare il generatore Matlab rand: la scelta è stata dettata dal compromesso tra disponibilità, agevole implementazione del software di calcolo e bontà dell’algoritmo di generazione.

5.4 Simulazione Montecarlo

La simulazione consiste in generale nello studio del comportamento di un sistema, attraverso la sua riproduzione in un contesto controllabile, sia nel caso in cui si considerino processi deterministici, sia nel caso in cui i processi siano stocastici. Nel secondo caso, il comportamento del sistema è influenzato dalla presenza di un certo numero di fenomeni casuali per cui, dopo averne definito un opportuno modello matematico, tramite il calcolatore elettronico si effettua una grande serie di simulazioni virtuali che consentano di raccogliere informazioni per poter formulare possibili previsioni sul comportamento del sistema in esame. Quest’approccio è oramai ampiamente diffuso in molti campi scientifici, dall’Ingegneria all’Economia e prende il nome di Simulazione Montecarlo, formalizzato negli anni ’40 da John Von Neumann e Stanislaw Ulam.

Fissato un generico sistema in analisi, dati un insieme di input in ingresso dei quali si conoscono le distribuzioni di probabilità e il comportamento, e un insieme di output in uscita, la Simulazione Montecarlo consente in generale di ottenere stime sulla distribuzione di probabilità dell’output. Si elencano di seguito tutti gli elementi principali di tale tecnica e in Figura 5.1 si riporta un breve schema:

• Parametri: sono gli input deterministici specificati dal progettista, e quindi sono controllabili.

• Variabili di input esogene: sono delle variabili di ingresso che dipendono da eventi che non sono sotto il controllo del decisore e il cui andamento è descrivibile in termini probabilistici. In linea teorica esistono infinite realizzazioni per ognuna di queste variabili.

• Variabili di output: rappresentano i risultati della simulazione e, a causa della natura aleatoria delle variabili in ingresso, rappresentano anch’essi un processo stocastico.

• Modello: equazioni matematiche che definiscono il legame tra le variabili di output e quelle di input.

Figura 5. 1

La Simulazione Montecarlo è stata applicata nell’ambito di questo lavoro e l’obiettivo è stato quello di generare delle sequenze temporali a partire da densità spettrali di potenza assegnate. Tali PSD sono relative a fenomeni dinamici aleatori che agiscono su un generico componente strutturale. Il campo di tensione presente nel componente è schematizzabile quindi come un processo aleatorio e la variabile presa in considerazione sarà la componente di tensione

σ

( )

t .

Come si vedrà in seguito nel Capitolo 6, dalle densità spettrali di potenza si possono ottenere in modo biunivoco informazioni solo sulle ampiezze e sulle frequenze delle costituenti sinusoidali del segnale, mentre per le fasi questo non è possibile. Conseguentemente si pone il problema di dare delle stime probabilistiche sul valore assunto dalla fase per ogni componente sinusoidale. In quest’ottica, la Simulazione Montecarlo trova la sua ragion d’essere poiché viene utilizzata per generare i valori delle fasi e creare sistematicamente gli andamenti temporali delle sequenze di carico.

I parametri, ossia gli input controllabili, sono dati dai valori delle ampiezze A e delle frequenze f che sono direttamente ricavabili dalle densità spettrali di potenza. Le variabili di tipo aleatorio in ingresso sono date dalle fasi ϕ che vengono ottenute tramite il generatore di numeri casuali. La variabile di tipo aleatorio in uscita è data, invece, dal processo

σ

( )

t . Si veda allo scopo la Figura 5.2.

Figura 5. 2

5.4.1 Implementazione della Simulazione Montecarlo

Si osserva prima di tutto come l’oggetto in analisi sia il processo aleatorio

(

_i;t

)

( )

t

σ ω

=

σ

rappresentativo dello stato di tensione presente nel sistema strutturale in analisi. Per ogni realizzazione del processo

σ

( )

t è necessario generare una sequenza di fasi

{ }

ϕ

k per le k costituenti sinusoidali del segnale. A sua volta il

processo che permette di ottenere le sequenze

{ }

ϕ

k risulta essere casuale poiché ogni

sequenza

{ }

ϕ

k è soggetta alla probabilità di occorrenza dell’evento

ω

i appartenente

allo spazio campione Ω che rappresenta l’insieme di tutti gli infiniti possibili eventi. Nella fattispecie gli eventi

ω

i rappresentano la definizione dello stato iniziale del

generatore di numeri casuali.

Sulla base di quanto detto nel Capitolo 3, si può dare una descrizione analitica dello spazio di probabilità

(

Ω Φ, , P

)

che rappresenta il processo aleatorio di definizione delle sequenze delle fasi

{ }

ϕ

k .

• In linea teorica lo spazio campione Ω dovrebbe essere costituito da infiniti eventi

ω

_i. In realtà, lavorando con il calcolatore, l’infinito è solamente un’astrazione per cui si sceglie di creare Ω come un insieme molto grande ma finito di eventi. In questo modo si cerca di rappresentare nel modo più efficiente possibile la caratteristica di casualità. Allo scopo si sceglie 9

10

n= e

{ }

ω

i

Ω = dove

ω

i =i ∀ =i 1,...,n (5.6)

• La

σ

-algebra Φ di parti di Ω è data da Φ = Ω ∅

{

, ,

{ } { }

ω

1 ,...,

ω

n

}

, in cui

9 10

n= .

• La legge di probabilità scelta è stata la seguente:

{ }

1 : 0 1 i P n

ω

_{Ω →}  ∅ →   _→  ∀ =i 1,..,n (5.7)

Il tutto può essere schematizzato secondo il seguente schema, Figura 5.3:

Figura 5. 3

La procedura con la quale è stata intrapresa la Simulazione Montecarlo può essere riassunta nei seguenti punti salienti. E’ importante ricordare che ad ogni stato iniziale (inteso come evento

ω

i) corrisponde una sequenza

{ }

ϕ

k e il cuore della

Simulazione Montecarlo consiste proprio in una estrazione casuale degli stati-eventi

i

ω

.

Come si vedrà nel Capitolo 6, sono state scelte sette PSD da analizzare: queste variano tra loro per forma e fattore di irregolarità

γ

, ma presentano tutte lo stesso contenuto energetico, e possono essere considerate come input controllabili del problema. Per motivi di tempo e di risorse di calcolo per ogni

PSD viene estratta un numero grande ma limitato di realizzazioni (ossia funzioni campione) tale che:

PSD

γ

Numero di realizzazioni, m 1 0.994 1000 2 0.95 1000 3 0.8 1000 4 0.7 1000 5 0.6 1000 6 0.53 10000 7 0.35 1000 Tabella 5. 1

Per ogni PSD e tramite la routine state.m, viene creato un opportuno vettore, detto vettore degli stati. Questo vettore presenta un numero di componenti pari al numero di funzioni campione che si vuole generare, m. Ogni componente è un valore numerico che permette di ripristinare lo stato del generatore. In sostanza ogni elemento di questo vettore permette l’inizializzazione del generatore e ad ognuno di essi corrisponde poi in uscita un’unica sequenza di fasi

{ }

ϕ

k . Il vettore degli stati viene creato in modo

casuale mediante il comando Matlab rand(‘state’,sum(100*clock)) e, in virtù di questo, può essere considerato il cuore della presente Simulazione Montecarlo. Questa operazione corrisponde all’operazione di estrazione degli eventi

ω

i di cui si è parlato sopra.

La fase viene interpretata e scelta come una variabile aleatoria con una distribuzione di probabilità uniforme nell’intervallo [− +π π, ].

E’ di fondamentale importanza ricordare che, una volta inizializzato lo stato, il generatore crea una propria sequenza

{ }

ϕ

k di numeri casuali (ossia di fasi)

con un periodo estremamente lungo e che tale sequenza si ripete in modo esatto ogni qual volta venga ripristinato questo stesso stato. Questo è necessario per creare delle simulazioni casuali che siano però facilmente ricreabili quando ritenuto opportuno. Se vogliamo, la vera casualità non è da ricercarsi all’interno della sequenza (che quindi è riproducibile ogni qual volta

lo si desideri), ma è insita nella fase precedente quando, effettivamente in modo casuale, o meglio pseudo-casuale, è stato creato il vettore degli stati.
Tale vettore degli stati viene salvato successivamente in un opportuno file di

dati, in modo tale da essere sempre disponibile per eventuali analisi future.

Nel suo complesso, l’intera Simulazione Montecarlo può essere così visualizzata in Figura 5.4:

Figura 5. 4

Il modello matematico verrà richiamato nel Capitolo 6, dando così una metodologia per creare a partire da un insieme di ampiezze, fasi e frequenze, l’andamento nel dominio del tempo del segnale cercato.