Ottimizzazione del Modello di Traffico

Il modello fin qui proposto è in grado di individuare situazioni di traffico di varia natura lungo il percorso che è stato scelto come campione, ma non è ancora esente da errori: è infatti necessaria una opportuna configurazione dei parametri fondamentali per fare in modo che le rilevazioni avvengano nel modo più corretto possibile; infatti con le configurazioni originali non c’è certezza del fatto che un evento di traffico sia rilevato correttamente sia dal punto di vista temporale che da quello spaziale.

Figura 15 - Schema di Funzionamento dell'Ottimizzatore

Per accuratezza spaziale si intente la capacità di identificare correttamente per ogni istante di tempo l’intervallo di spazio in cui avviene l’evento di traffico; per accuratezza temporale la capacità di individuare gli istanti di inizio e fine dell’evento.

E’ necessario quindi definire una metrica che permetta di quantificare l’accuratezza spaziale e temporale della rilevazione degli eventi e, sulla base di questa, cambiare i parametri del modello per ottimizzarne il funzionamento come illustrato in Figura 15.

33

A tal fine definiamo in primo luogo quella che per noi sarà l’ontologia di traffico, ovvero la condizione necessaria e sufficiente per poter distinguere una situazione patologica di disagio alla circolazione veicolare da una situazione fisiologica.

Ontologia di Traffico

Al fine di discriminare una situazione di traffico rilevante da una irrilevante per il nostro sistema consideriamo traffico una colonna di auto lunga almeno 100 metri e che perduri per almeno due minuti di tempo. La condizione spaziale indica la presenza di un numero consistente di veicoli che stazionano o si spostano a velocità ridotta influenzando negativamente il normale flusso veicolare; la condizione temporale individua il mantenimento dell’evento e quindi la presenza della situazione di disagio.

Per il singolo veicolo definiamo una soglia di velocità sopra la quale il modello è inattivo e non segnala in alcun modo eventi; la soglia in questione è posta a 20 km/h. Scendere al di sotto di questa velocità è quindi condizione necessaria ma non sufficiente per il rilevamento di eventi. Ricordiamo che il modello è pensato per rilevare eventi in ambito urbano dove il limite di velocità è per legge di 50 km/h e quindi una velocità di crociera pari a 20Km/h non è chiaramente sintomo di ingorgo stradale se elevata a unica misura degli eventi.

Responsività Spaziale e Temporale

La metrica individua un unico evento di traffico lungo il percorso e valuta l’accuratezza spaziale e temporale del modello. Nel nostro caso è sufficiente la classificazione di un evento di traffico in quanto possiamo ripetere la valutazione della metrica più volte per individuare eventi multipli.

La Responsiveness è, in Informatica, un concetto che si riferisce alla capacità specifica di un sistema o di una unità funzionale di completare compiti assegnati entro un dato vincolo temporale.

Per definire la metrica partiamo dalla Responsiveness temporale che valuta l’accuratezza, temporale appunto, di un classificatore in grado di riconoscere l’inizio e la fine di eventi.

Nella formula seguente vediamo come si calcola la Responsiveness di un insieme di eventi 𝑆𝑖 caratterizzati da 𝑁𝑖 coppie inizio e fine 𝑡𝑖,𝑝 rilevate dal classificatore al tempo

𝑡′_𝑖,𝑝 .

𝑅𝐸𝑆𝑃(𝑆

𝑖

) =

∑

𝑁_𝑝=𝑖𝑖

|𝑡

′_𝑖,𝑝

− 𝑡

𝑖,𝑝

|

𝑁

𝑖

34

La metrica per il nostro modello dovrà quindi da un lato tener conto dell’accuratezza nell’identificare correttamente l’inizio e la fine dell’evento di traffico in modo analogo alla Responsiveness temporale sopra descritta, poi, nell’intervallo di tempo indicato, valutare l’accuratezza spaziale. Il funzionamento ottimale del modello si ottiene quando questo è in grado di rilevare l’evento nello stesso momento in cui esso si presenta nella realtà.

Definiamo quindi alcuni parametri :

 𝑡′_{𝑠𝑡𝑎𝑟𝑡} e 𝑡′_{𝑠𝑡𝑜𝑝}: tempo di inizio e fine durante i quali il modello riesce ad

individuare l’ingorgo

 𝑡_{𝑠𝑡𝑎𝑟𝑡} e 𝑡_{𝑠𝑡𝑜𝑝}: tempo di inizio e fine reali durante i quali ha luogo l’ingorgo

 𝑠′(𝑡)𝐼𝑁 e 𝑠′(𝑡)𝐹𝐼𝑁: punto di inizio e fine al tempo t lungo i quali il modello riesce ad

individuare l’ingorgo

 𝑠(𝑡)𝐼𝑁 e 𝑠(𝑡)𝐹𝐼𝑁: punto di inizio e fine reali al tempo t lungo i quali ha luogo

l’ingorgo

Dato un evento di traffico avente come caratteristiche un istante di inizio e uno di fine pari a 𝑡𝑠𝑡𝑎𝑟𝑡 e 𝑡𝑠𝑡𝑜𝑝 e una ampiezza spaziale per ogni istante temporale definita dai valori

𝑠(𝑡)_𝐼𝑁 e 𝑠(𝑡)_𝐹𝐼𝑁 la Responsiveness del sistema si può esprimere in questo modo:

𝑅𝐸𝑆𝑃(𝑆

_𝑖

) = 𝑅𝐸𝑆𝑃(𝑆

_𝑖

)

_𝑇

+ 𝑅𝐸𝑆𝑃(𝑆

_𝑖

)

_𝑆 dove

𝑅𝐸𝑆𝑃(𝑆

_𝑖

)

_𝑇

=|𝑡

𝑠𝑡𝑎𝑟𝑡

− 𝑡

′ 𝑠𝑡𝑎𝑟𝑡

| + |𝑡

𝑠𝑡𝑜𝑝

− 𝑡

′𝑠𝑡𝑜𝑝

|

|𝑡

_{𝑠𝑡𝑜𝑝}

− 𝑡

_{𝑠𝑡𝑎𝑟𝑡}

|

𝑅𝐸𝑆𝑃(𝑆

_𝑖

)

_𝑆

=

1

|𝑡

_{𝑠𝑡𝑜𝑝}

− 𝑡

𝑠𝑡𝑎𝑟𝑡

|

∑

|𝑠

𝐼𝑁

(𝑡) − 𝑠

′ 𝐼𝑁

(𝑡)| + |𝑠

𝐹𝐼𝑁

(𝑡) − 𝑠

′𝐹𝐼𝑁

(𝑡)|

|𝑠

_𝐹𝐼𝑁

(𝑡) − 𝑠

_𝐼𝑁

(𝑡)|

𝑡_{𝑠𝑡𝑜𝑝} 𝑡=𝑡𝑠𝑡𝑎𝑟𝑡

Nella formula precedente possiamo notare come, per un singolo evento di traffico, il primo addendo stima l’accuratezza temporale del modello valutando lo scostamento tra l’inizio e la fine reali e rilevati. Il secondo addendo invece misura, durante l’intervallo di tempo precedente, l’accuratezza dell’intervallo spaziale.

Rispettando l’ontologia di traffico precedentemente definita, viene impedito alla formula della Responsiveness di divergere verso infinito in quanto la differenza tra

35

l’istante temporale di inizio e fine ingorgo è di almeno 2 minuti mentre la differenza tra la posizione spaziale finale e iniziale è di almeno 100m.

Inoltre, la presenza del denominatore in entrambi gli addendi della formula, consente di normalizzare il risultato.

Influenza dei Parametri del Modello sulla Responsività

Il rilascio delle impronte da parte del modello ad agenti avviene all’interno di una griglia di valori sulla base delle posizioni e delle velocità dei veicoli nel mondo reale; ad ogni istante temporale, più precisamente al termine della fase di raccolta delle posizioni dei veicoli, viene analizzata la griglia dei valori alla ricerca di eventuali criticità corrispondenti alla precedente definizione di traffico.

Risulta chiaro che la forma delle impronte e la loro durata di evaporazione influenzano la capacità di individuare temporalmente e spazialmente gli eventi di traffico. Una durata di evaporazione delle impronte eccessivamente prolungata nel tempo porterà il sistema a individuare con più facilità ingorghi anche se questi non si sono manifestati nella realtà, mentre una dimensione di base delle impronte molto piccola porterebbe a poche sovrapposizioni tra le impronte e il sistema si comporterebbe in maniera opposta, cioè eventualmente non riconoscendo eventi di traffico che invece sono presenti nella realtà.

Da questa breve analisi è possibile individuare nella dimensione dell’impronta e nel fattore di evaporazione dell’impronta i parametri che influenzano maggiormente la Responsiveness.

Risoluzione del problema di Ottimizzazione

Una volta stabilito che i parametri che influenzano il funzionamento del modello in termini di Responsiveness sono l’evaporazione delle impronte, la loro semiampiezza e la soglia di attivazione del traffico, si rende necessario studiare un meccanismo di ottimizzazione di tali parametri.

Poiché il problema di ottimizzazione che stiamo considerando è un problema non lineare, non è quindi facilmente risolvibile con algoritmi di ottimizzazione di tipo deterministico; per la sua risoluzione bisogna quindi sfruttare un approccio metaeuristico alla risoluzione del problema.

Una tecnica risolutiva di un problema è detta euristica se il suo procedimento non segue regole o percorsi precisi, ma per ogni scelta necessaria ci si affida all’analisi dello stato attuale, all’esperienza e all’intuito.

36

Ogni volta che si prende una decisione di questo tipo bisogna verificare se ci siamo avvicinati o meno a una soluzione possibile del problema. Anche nel caso in cui ci fossimo allontanati dall’ottimo del problema, le scelte precedentemente effettuate contribuiranno ad allargare la nostra conoscenza del problema.

La metaeuristica è un metodologia per l’appunto di tipo euristico di risoluzione di una classe molto ampia di problemi computazionali la quale prevede di applicare e combinare procedure in parte euristiche e in parte deterministiche con l’obiettivo di individuare procedure robuste ed efficienti.

Per la risoluzione del problema di ottimizzazione sono state prese in considerazione tre tecniche euristiche di valutazione e ottimizzazione di soluzioni: l’algoritmo genetico (GA), l’evoluzione differenziale (DE) e l’ottimizzazione con sciami di particelle (PSO).

L’idea che sta alla base di questi tre algoritmi è la stessa: si parte inizialmente da un gruppo casuale di possibili soluzioni di un problema e si combinano fra loro in modo che dopo una serie di tali combinazioni, scartando le soluzioni meno affini, si arrivi alla soluzione o alle soluzioni ottime o, in alternativa, a soluzioni che risultino qualitativamente migliori delle soluzioni di partenza.

Queste tecniche sono usate soprattutto per individuare soluzioni di problemi di cui non si conoscono algoritmi risolutivi di complessità lineare o polinomiale perché, nonostante non sia possibile stabilire con precisione il tempo necessario a individuare la o le soluzioni ottimali del problema, arrivano in tempi brevi a soluzioni più che accettabili.

Gli algoritmi prevedono tre fasi di esecuzione:

1. Inizializzazione casuale della popolazione di soluzioni.

2. Valutazione della popolazione dei suoi membri attraverso l’utilizzo di una funzione di fitness.

3. Generazione di una nuova popolazione attraverso meccanismi di ricombinazione. 4.

Esaminiamo brevemente le caratteristiche specifiche dei tre algoritmi elencati in precedenza.

ALGORITMO GENETICO

Un algoritmo genetico (GA) è un algoritmo euristico ispirato al principio della selezione naturale ed evoluzione biologica teorizzato nel 1859 da Charles Darwin. L'aggettivo "genetico" deriva dal fatto che il modello evolutivo darwiniano trova spiegazioni nella branca della biologia detta genetica e dal fatto che gli algoritmi genetici attuano dei

37

meccanismi concettualmente simili a quelli dei processi biochimici scoperti da questa scienza.

La vera prima creazione di un algoritmo genetico è tuttavia storicamente attribuita a John Henry Holland che, nel 1975, nel libro Adaptation in Natural and Artificial Systems pubblicò una serie di teorie e di tecniche tuttora di fondamentale importanza per lo studio e lo sviluppo della materia.

E’ necessario premettere che gli Algoritmi Genetici ereditano e riadattano dalla biologia alcune terminologie che vengono qui preventivamente presentate per una successiva maggiore chiarezza espositiva:

 Cromosoma: una delle soluzioni ad un problema considerato. Generalmente è codificata con un vettore di bit o di caratteri.

 Popolazione: insieme di soluzioni relative al problema considerato.

 Gene: parte di un cromosoma. Generalmente consiste in una o più parti del vettore di bit o caratteri che codificano il cromosoma.

 Fitness: grado di valutazione associato ad una soluzione. La valutazione avviene in base ad una funzione appositamente progettata detta funzione di fitness.

 Crossover: generazione di una nuova soluzione mescolando delle soluzioni esistenti.

 Mutazione: alterazione casuale di una soluzione.

Un tipico algoritmo genetico, nel corso della sua esecuzione, provvede a fare evolvere delle soluzioni secondo il seguente schema di base:

1. Generazione casuale della prima popolazione di cromosomi.

2. Applicazione della funzione di fitness ai cromosomi appartenenti all'attuale popolazione.

3. Selezione delle soluzioni considerate migliori in base al risultato della funzione di fitness e della logica di selezione scelta.

4. Applicazione degli operatori di mutazione e crossover per generare delle soluzioni ibride a partire dalle soluzioni scelte al punto 3.

5. Creazione di una nuova popolazione a partire dalle soluzioni identificate al punto 4.

6. Esecuzione della procedura a partire dal punto 2 ed utilizzando la nuova popolazione creata al punto 5.

38

Di seguito è riportata una tabella riassuntiva degli effetti degli operatori di Mutazione, Crossover e Selezione.

Cross–Over

Figura 16 - Esempio di Cross - Over Occorre scegliere due individui genitori e uno

o più punti di taglio. Nel caso di un solo punto di taglio (one-point cross-over), le porzioni di genotipo alla sua destra vengono scambiate tra di loro, generando così due nuovi discendenti il cui genoma deriva dal rimescolamento di quello dei genitori

Mutazione

Figura 17 - Esempio di Mutazione L’applicazione dell’operatore provoca invece

l’alterazione di singoli geni di un cromosoma, aggiungendo alle componenti del genitore, con una piccola probabilità pm, un rumore gaussiano a media nulla

Selezione

La selezione degli individui che parteciperanno ad una nuova riproduzione è subordinata al valore di fitness associata ad ogni individuo. Gli individui con fitness più alta sono quelli che risolvono meglio il problema di ricerca dato e dunque devono essere privilegiati in questa fase, andando a formare la matrice Pi relativa alla i−esima generazione.

Tabella 2 - Caratteristiche principali degli operatori genetici

L'iterazione dei passi presentati precedentemente permette l'evoluzione verso una soluzione ottimizzata del problema considerato.

Poiché questo algoritmo di base soffre del fatto che alcune soluzioni ottime potrebbero essere perse durante il corso dell'evoluzione e del fatto che l'evoluzione potrebbe ricadere e stagnare in "ottimi locali" spesso viene integrato con la tecniche dell'"elitarismo" e con quella delle mutazioni casuali. La prima consiste in un ulteriore passo precedente al punto 3 che copia nelle nuove popolazioni anche gli individui migliori della popolazione precedente, la seconda invece successiva al punto 4 introduce nelle soluzioni individuate delle occasionali mutazioni casuali in modo da permettere l'uscita da eventuali ricadute in ottimi locali.

In sintesi si può dire che gli algoritmi genetici consistono in algoritmi che permettono di valutare delle soluzioni di partenza e che ricombinandole ed introducendo elementi di disordine sono in grado di crearne di nuove nel tentativo di convergere a soluzioni ottime. Queste tecniche vengono di norma utilizzate per tentare di risolvere problemi di ottimizzazione per i quali non si conoscono altri algoritmi efficienti di complessità lineare o polinomiale. Nonostante questo utilizzo, data la natura intrinseca di un

39

algoritmo genetico, non vi è modo di sapere a priori se sarà effettivamente in grado di trovare una soluzione accettabile al problema considerato.

EVOLUZIONE DIFFERENZIALE

L’algoritmo di evoluzione differenziale (DE) è un metodo che ottimizza un problema iterativamente cercando di migliorare una soluzione candidato rispetto ad una determinata misura di qualità. DE è utilizzato per le funzioni a valori reali multidimensionali, ma non usa la discesa del gradiente in fase di ottimizzazione, il che significa che DE non richiede per il problema di ottimizzazione di essere differenziabile come richiesto con metodi di ottimizzazione classici. DE può quindi essere utilizzato anche su problemi di ottimizzazione non continui, rumorosi e variabili nel tempo.[17]

Le prime ricerche su DE sono originariamente dovute Storn e Price nel loro On usage of differential evolution for function optimization.

Il punto di partenza dell’algoritmo è un insieme o popolazione di soluzioni dette agenti. Ad ogni iterazione gli agenti sono tra loro combinati secondo il seguente procedimento:

 per ogni agente V vengono scelti casualmente altri tre agenti A, B, C, diversi tra loro e dall’agente di riferimento

 si sceglie sempre casualmente un numero naturale R tra 1 ed n, con n pari al numero di dimensioni dello spazio delle soluzioni ℝn

 si valuta quindi la nuova posizione (cioè il valore delle sue coordinate nello spazio ℝn_{) dell’agente con valori [v’1, … v’n] nel seguente modo:}



per ogni componente

v’i

della nuova posizione si calcola un numero uniformemente distribuito

ri

≡

U(0, 1)

 se

ri

<

CP

oppure

i = R

allora

v’

i =

a

i

+ F × (b

i

- c

i

)

, altrimenti la

coordinata resta invariata

 se il valore della funzione di fitness della nuova posizione è migliore di quello della vecchia posizione, il vecchio agente viene rimpiazzato da quello nuovo

 si prende l’agente con il migliore valore della funzione di fitness e lo si eleva a migliore soluzione del problema

40

Figura 18 - Inizializzazione della popolazione con DE

Il parametro

CP ∈ ℝ

e compreso tra 0 e 1 è detto probabilità di crossover, dal suo valore dipende il numero di componenti dell’agente che sono forzatamente sostituiti dai corrispettivi del vettore

A + F × (B - C)

.[16]

Il parametro

F

è anch’esso un numero reale, compreso tra 0 e 2 ed è detto peso differenziale, influisce sul valore delle singoli componenti sottoposte a crossover e aggiunge un ulteriore elemento di differenziazione delle soluzioni che tenderanno così a non stagnare nei pressi di minimi locali.

La scelta dei parametri

F

, e

CR

dipende, come nel caso dell’algoritmo genetico, dalla dimensione del problema e dalle risorse temporali e computazionali a disposizione [15]. Un altro aspetto che influisce sulle prestazioni dell’algoritmo è il numero di agenti che compongono una popolazione

NP

, valore intero che deve essere chiaramente superiore a 4.

41

Tuttavia non esiste ad oggi una regola matematica che permetta di individuare i valori ottimali di questi parametri; infatti si ricorre spesso ad applicare altri algoritmi euristici per cercare di risolvere questo problema di ricerca. Questa operazione è detta metaottimizzazione. [14]

OTTIMIZZAZIONE CON SCIAMI DI PARTICELLE

La tecnica di ottimizzazione per sciami di particelle (Particle Swarm Optimisation) è attribuita a Kennedy, Eberhart e Shi, le loro ricerche si sono concentrate sullo studio e la simulazione dei comportamenti sociali, individuando nel movimento coordinato di stormi di uccelli o di barriere di pesci il modello migliore per la loro rappresentazione.[13]

Nel PSO la popolazione iniziale di possibili soluzioni è detta sciame di particelle. Lo spostamento di tali particelle nello spazio di ricerca è regolato da semplici formule matematiche che utilizzano come conoscenza pregressa le migliori posizioni conosciute delle singole particelle e quella della particella che risulta la migliore dello sciame. Lo sciame è composto da un numero S di particelle di cui si conoscono due informazioni: la posizione X e la sua velocità V (entrambe appartenenti a ℝn_).

L’algoritmo prevede una fase di inizializzazione e una di esecuzione.

1. FASE DI INIZIALIZZAZIONE

Per ogni particella i = 1, ..., S eegui i seguenti passi :

 Si inizializza la posizione della particella con un vettore casuale uniformemente distribuito :

x

i ~

U(b

lo

, b

up

)

, dove

b

lo e

b

up sono

rispettivamente il limite inferiore e superiore dello spazio di ricerca.

 Inizializza una seconda variabile detta migliore posizione della particella

p

i =

x

i

 Se

(F(p

i

) < F(g))

allora si aggiorna la variabile contenente la migliore

posizione dello sciame

G

con

p

i dove F è la funzione di fitness  Si inizializza la velocità della particella

vi = U(-|b

up

-b

lo

|, |b

up

-b

lo

|)

2. FASE DI ESECUZIONE

Finché non viene raggiunto un criterio di terminazione (che può essere un massimo numero di esecuzione oppure un adeguata valore della funzione di fitness) si eseguono i seguenti passi:

42

 per ogni particella

i

si scelgono due numeri casuali

R

p e

R

g tra

0

e

1

 per ogni dimensione

d ∈[1, n]

del problema si aggiorna la componente d- esima della velocità

V

i della particella con la seguente formula:

𝑉_𝑖𝑑′ = 𝑂𝑀 ⋅ 𝑉_𝑖𝑑 + 𝐹𝐼_𝑝 ⋅ 𝑅_𝑝 (𝑃_𝑖𝑑 − 𝑋_𝑖𝑑 ) + 𝐹𝐼_𝑔 ⋅ 𝑅_𝑔(𝐺_𝑑− 𝑋_𝑖𝑑)

 si aggiorna la posizione

X

i

= X

i

+V

i

 se

F(X

i

) < F(P

i

)

allora

P

i =

X

i

 se F

(X

i

) < F(G)

allora

G

=

X

i

Al termine di ogni iterazione in G è presente la soluzione migliore finora conosciuta. Come nel caso di DE, anche per PSO i parametri OM, FIp e FIg sono scelti tramite attraverso processi di metaottimizzazione. PSO è facilmente intrappolato in un minimo locale. Questa convergenza prematura può essere evitata, non utilizzando più noto G come posizione dell'intero sciame, ma utilizzando solo la posizione più noto l di un sub- sciame vicino a dove la particella si muove. Tale sub-sciame può essere un geometrico o, più spesso, di tipo sociale; in questo caso si ha un insieme di particelle che non dipende qualsiasi distanza. Se supponiamo che ci sia un collegamento di informazioni tra ogni particella e i suoi vicini, l'insieme di questi collegamenti costruisce un grafo di comunicazione tra particelle vicine.

Figura 20 - Esempio di esecuzione di PSO

COMPARAZIONE DEGLI ALGORITMI [18][19]

In primo luogo GA è l’unico dei tre algoritmi che necessita un ordinamento delle soluzioni come primo step per la generazione della nuova generazione; questo fattore comporta un rallentamento non lineare rispetto all’aumento della cardinalità della popolazione.

DE, a differenza degli altri di GA e PSO, mette immediatamente a disposizione nuove soluzioni appena trovate per la generazione del vettore mutante; al contrario, GA e PSO mettono i nuovi figli a disposizione solo al completamento della fase di generazione.

43

In DE e PSO tutti i membri della popolazione sono presi in considerazione per la generazione della nuova popolazione mentre in GA solo i migliori nel ranking; questa particolare caratteristica di GA può rappresentare un fattore limitante.

Per PSO le nuove soluzioni possono essere molto differenti rispetto alla generazioni precedenti, cosa che è difficile che avvenga in GA; PSO quindi esplora maggiormente lo spazio rispetto che GA e le soluzioni trovate possono essere più vicine tra loro rispetto che GA. Inoltre la migliore particella dello sciame influenza tutte le altre e questo può portare ad eventi di clustering prematuro.

DE, similarmente a PSO, ha una elevata capacità di esplorare lo spazio delle soluzioni; inoltre la miglior soluzione trovata non influenza le altre; infine il vettore mutante è un nuovo vettore generato dalla popolazione e non un vettore della popolazione.

Per tutti gli algoritmi evolutivi spesso la convergenza verso cluster centrati su buone soluzioni porta a situazioni stagnanti che non vengono migliorate.

Alcuni miglioramenti possono essere i seguenti :

 Re-inizializzazione:

o PSO: ha maggiore tendenza a formare cluster e la re-inizializzazione viene effettuata creando sottogruppi di popolazione o mantenendo la particella migliore e modificando le altre.

o GA: il clustering è meno netto ma la re-inizializzazione produce un’iniezione di casualità che aumenta la diversità.

Nel documento Progettazione e realizzazione di un sistema di rilevamento del traffico urbano basato su crowd sensing e stigmergia e caratterizzazione dei problemi basata su social sensing (pagine 32-44)