Implementazione dell’Ottimizzatore

Al fine di individuare i valori ottimali di ampiezza delle impronte , tasso di evaporazione e soglia di attivazione utilizzando l’algoritmo di Evoluzione Differenziale, è necessario eseguire il modello un numero relativamente elevato di volte. Effettuare questa operazione manualmente risulta assai complicato e scomodo in quanto ogni volta sarebbe necessario avviare l’interfaccia grafica di Repast Simphony, impostare i nuovi parametri ed avviare la simulazione. Repast offre in questo caso due possibili soluzioni: la modalità Batch Run e la modalità Batch.[20]

MODALITA’ REPAST BATCH RUN

E’ possibile infatti effettuare quello che nell’ambiente Repast è detto Batch Run, ossia l’esecuzione simultanea di più modelli sulla base di un pool di parametri predefinito. Il numero di esecuzioni simultanee è pari al numero delle combinazioni dei parametri.

La modalità Batch Run itera sullo spazio delle combinazioni dei parametri e avvia una simulazione del modello per ogni combinazione possibile.

53

Il modello di architettura della modalità Batch Run è quello dei processi master-client. Il processo master avvia i processi client che effettuano le simulazioni; il processo master quindi li interroga periodicamente per sapere se essi hanno terminato l’esecuzione. Al termine di tutti i processi client, il processo master raccoglie quindi i risultati delle simulazioni e li combina in un output unitario. La modalità Batch Run può essere eseguita sia su una singola macchina che su diverse macchine connesse in rete, aumentando in questo modo la capacità computazionale del sistema.

Poiché l’inizializzazione del pool di parametri deve essere fatta manualmente e le soluzioni ottime del problema potrebbero non trovarsi all’intero di tale pool poiché tutte le esecuzioni del modello sono effettuate sulla base di combinazioni dei parametri del pool, l’esecuzione in modalità Batch Run così come offerta da Repast Simphony non rappresenta la soluzione completa al problema. Inoltre al termine delle simulazioni non viene effettuata nessuna verifica dei risultati per poter elaborare un nuovo pool di parametri.

MODALITA’ REPAST BATCH

A causa dei motivi elencati nella sezione precedente, si passa a utilizzare Repast in modalità Batch; in questa modalità non esiste più l’interfaccia grafica ma ci si limita ad effettuare le simulazioni dei modelli. Sarà successivamente compito di MATLAB inizializzare i modelli e analizzare i loro risultati per elaborare i nuovi parametri sulla base dell’algoritmo di Evoluzione Differenziale.

E’ possibile riportare, in forma di pseudo codice e basandoci sulle considerazioni precedenti, le operazioni che MATLAB dovrà eseguire per la procedura di ottimizzazione dei parametri del Modello di Traffico.

MATLAB è in grado di interfacciarsi con una Java Virtual Machine grazie all’ausilio di alcune classi C; in questo modo è possibile invocare metodi di classi Java direttamente dall’ambiente di programmazione MATLAB. Tuttavia MATLAB usa però una propria implementazione di JVM e così si rende necessario verificare che quest’ultima sia compatibile con quella utilizzata da Repast. In accordo a quanto è stato illustrato precedentemente, Repast verrà lanciato in modalità Batch per lo scopo preposto eseguendo così una sola simulazione per volta con un set di parametri determinati.

DEFINE repast_parameters DO:

results = execRepast(repast_parameters) fitness_val = evaluate_fitness(results)

repast_parameters = update_params(fitness_val) WHILE fitness_val <= TARGET_FITNESS OR STOP_CONDITION

54 Invocazione di Repast

Per invocare l’esecuzione di Repast direttamente da MATLAB si fa uso del metodo

system(cmd) che permette di eseguire un comando da terminale. Viene invocata la macchina virtuale java specificando le librerie per l’avvio e il file dei parametri necessari all’esecuzione del modello.

La funzione invoca il metodo modify_params() per aggiornare i parametri del modello; si analizza il valore di ritorno di tale metodo per decidere se proseguire o meno nell’esecuzione. Se infatti il metodo di aggiornamento dei parametri dovesse ritornare esito negativo, questo significherebbe che il file dei parametri si trova in uno stato inconsistente e quindi sarebbe impossibile per Repast lanciare il modello. Successivamente si invoca il metodo system(arg) per lanciare Repast in modalità Batch e anche in questo caso si analizza il valore di ritorno per decidere se proseguire o meno. Se la funzione è stata eseguita correttamente allora si copiano gli output del modello nella cartella di esecuzione dello script per le analisi successive.

La funzione che invoca Repast da MATLAB avrà quindi il seguente codice:

function[ris] = invokeRepast (parsvector)

%* modifica il file XML inserendo i parametri da aggiornare

%* lancia repast

%* restituisce true o false per indicare la corretta/errata terminazione

batch_params_xml=’<path>\batch\batch_params.xml'; x=modify_params(parsvector,batch_params_xml); if(x==false) ris=false; return; end

%prima di lanciare repast controllo di aver effettivamente modificato i parametri

arg='java ……'; status= system(arg); if ~exist(‘<path>\output.txt', 'file'); status=1; end if(status==0) ris=true;

%leggo il num di jam

fileID = fopen(‘<path>\jamNumber.txt','r'); formatSpec = '%i'; jam_number = fscanf(fileID,formatSpec); for i = 0:jam_number-1 %copio i files file_name=strcat(‘<path>',sprintf('jam%d.csv',i)); copyfile(file_name,sprintf('jam%d.csv',i)); end

copio il num di jam

copyfile(<path>\jamNumber.txt','jamNumber.txt');

else

ris=false;

end

55 Modifica dei Parametri del Modello

Per passare i parametri al modello è sufficiente modificare il file parameters.xml prima di ogni simulazione. Questo file contiene i parametri che, nel caso di questo modello, vengono salvati nella classe statica TJ. Come è stato detto in precedenza solo alcuni dei parametri specificati nel file di configurazione sono interessati da questa procedura di avvio: in particolare saranno presi in considerazione soltanto i parametri EVAPORATION_RATE, MARK_EXTENSION e TRAFFIC_TRESHOLD.

In accordo allo pseudo codice illustrato in precedenza, è necessario che MATLAB produca un file XML corretto e contenente i parametri necessari all’esecuzione del modello. In questo modo è poi possibile lanciare Repast in modalità Batch. Per gestire i files XML MATLAB mette a disposizione le funzioni xmlread e xmlwrite, permettendo in questo modo di lavorare con i documenti XML.

Di seguito viene riportato il codice che viene utilizzato per l’aggiornamento dei parametri di Repast.

Il vettore parsvector, passato come argomento della funzione, contiene i valori dei parametri che è necessario modificare. Poiché, come è stato spiegato in precedenza, siamo interessati a modificare soltanto un piccolo sottoinsieme dei parametri del modello, è stato necessario individuare una tecnica che permettesse a MATLAB di discriminare quale parametri modificare o meno. E’ infatti sufficiente specificare NaN come elemento del vettore che viene passato come argomento alla funzione per ignorare la modifica del rispettivo parametro.

Risulta evidente inoltre che il numero di elementi del vettore dei parametri deve essere coerente con il numero di parametri del modello, così come l’ordine dei suoi valori deve

function[x]=modify_params(parsvector,batch_params_file)

%modifica il file XML inserendo i parametri da aggiornare %apertura del file xml

xDoc=xmlread(fullfile((batch_params_file))); allListItems=xDoc.getElementsByTagName('sweep'); allListItems=allListItems.item(0);

thisListItem=allListItems.getElementsByTagName('parameter');

for i=0:size(parsvector,2)-1 %navigo il file XML

x=thisListItem.item(i);

if~isnan(parsvector(i+1))==true %controllo NaN

str = num2str(parsvector(i+1)); x.setAttribute('value',str);

end

end

xmlwrite(batch_params_file,xDoc); %scrivo le modifiche

x=true; end

56

corrispondere all’ordine dei parametri del modello. In caso contrario si avranno comportamenti indesiderati durante l’esecuzione dell’algoritmo.

Per ogni ingorgo individuato dal modello sono disponibili due o più righe nel file

output.txt contenenti gli istanti temporali in cui l’ingorgo è stato rilevato, un identificatore univoco dell’ingorgo e le posizioni in metri di inizio e di fine dell’ingorgo relativamente al percorso monitorato. In accordo all’ontologia di traffico precedentemente definita, è condizione necessaria che nel file siano presenti almeno due righe in quanto ogni tick rappresenta un minuto nella realtà.

Il generico formato del file output è quindi il seguente :

TICK,ID,S_IN,S_FIN

Tuttavia, ai fini dell’ottimizzazione, poiché si sottoporranno a al modello scenari in cui è presente un solo ingorgo, il parametro ID potrà essere eliminato; l’ottimizzatore quindi procederà verificando la precisione del modello nel descriverlo temporalmente e spazialmente.

Caricamento dei Dati

Il passo successivo è quindi quello di caricare in MATLAB i risultati presenti nei file

jam<i>.csv per poter calcolare il valore della funzione di fitness.

Come è già stato detto, il file di output rispetta il formato CSV e quindi l’operazione di caricamento potrebbe essere effettuata manualmente per mezzo del MATLAB Import Wizard; tale strumento ha però lo svantaggio di necessitare dell’intervento manuale e ciò fa perdere i requisiti di automaticità e di generalità allo script di ottimizzazione.

I dati sono quindi caricati utilizzando la funzione csvread(file) che, se riceve il percorso di un file CSV valido come parametro, restituisce una matrice

N x M

contenente i valori del file, dove N rappresenta il numero di righe del file di output e M il numero di valori separati dalla virgola e cioè le sue colonne.

Il caricamento degli output ( e degli scenari) sarà quindi effettuato con le seguenti istruzioni : … prototype=csvread('prototype<i>.txt '); … simulation=csvread(jam<i>.txt'); …

57 Funzione di Fitness

La funzione obiettivo da passare all’algoritmo di evoluzione differenziale ha quindi il seguente aspetto:

La funzione esegue la simulazione in Repast e, se questa svolge correttamente la propria funzione, restituisce il valore di fitness dei parametri utilizzati nella simulazione; in caso contrario restituisce il massimo valore possibile in MATLAB per un intero affinché l’agente, i cui parametri non hanno permesso di concludere la simulazione correttamente, sia svantaggiato e molto probabilmente scartato per la scelta della futura popolazione.

Possiamo inoltre notare che l’effettivo calcolo del valore di fitness è delegato ad una funzione dedicata calculateFitness(). Tale funzione accetta come parametri le matrici del prototipo e dell’output del modello ripulito della colonna relativa all’ID dell’ingorgo.

function val = TrafficFitness(params) % carico il prototipo di Traffico

prototype_num=4; prototypes={}; for i = 0:prototype_num-1 prototypes{(i+1),1}=csvread(sprintf('prototype%d.csv',i)); end % carico i parametri parameters = nan([1,9]);

parameters(1,2) = params.evaporation(1); % evaporation rate

parameters(1,6) = params.width(1); % semiampiezza dell'impronta

parameters(1,9) = params.threshold(1); % semiampiezza dell'impronta

% invoke Repast Symphony model

val=0; if invokeRepast(parameters) for i = 0:prototype_num-1 try simulation=csvread(sprintf('jam%d.csv',i)); prototype=prototypes{(i+1),1};

val= val+ calculateFitness(prototype,simulation);

catch err

disp(err);

val = val + intmax;

end

end

val=val/prototype_num;

mkdir(strcat('output',num2str(val),'-',num2str(params.evaporation(1)),'- ',num2str(params.width(1)),'-',num2str(params.threshold(1))));

%leggo il num di jam

fileID = fopen('jamNumber.txt','r'); formatSpec = '%i'; jam_number = fscanf(fileID,formatSpec); for i = 0:jam_number-1 %copio i files %copyfile(sprintf('jam%d.csv',i),strcat('output',num2str(val),'- ',num2str(params.evaporation(1)),'-',num2str(params.width(1)),'-

58

Il codice relativo alla funzione che calcola il valore di fitness è il seguente :

In accordo alla metrica definita, il valore di fitness è formato da due addendi, Resp_T che rappresenta la Responsiveness temporale e Resp_S che rappresenta la Responsiveness spaziale. La funzione riceve come parametri i valori reali dell’ingorgo e quelli ottenuti dalla simulazione espressi sotto forma di matrici come specificato in precedenza.

La Responsiveness temporale è calcolata nella prima parte della funzione, in cui vengono anche calcolati gli istanti di inizio e fine dell’ingorgo che saranno poi utilizzati nella parte spaziale.

Ricordiamo brevemente la definizione che avevamo dato riguardo alla Responsiveness temporale :

𝑅𝐸𝑆𝑃(𝑆

𝑖

)

𝑇

=

|𝑡

_{𝑠𝑡𝑎𝑟𝑡}

− 𝑡

′_{𝑠𝑡𝑎𝑟𝑡}

| + |𝑡

_{𝑠𝑡𝑜𝑝}

− 𝑡

′_{𝑠𝑡𝑜𝑝}

|

|𝑡

_{𝑠𝑡𝑜𝑝}

− 𝑡

_{𝑠𝑡𝑎𝑟𝑡}

|

function val = calculateFitness(prototype,simulation) % calcolo la Responsiveness temporale

tstart = prototype(1,1);

tstop = prototype(size(prototype,1),1); tstartS = simulation(1,1);

tstopS = simulation(size(simulation,1),1);

Resp_T = (abs(tstart-tstartS) + abs(tstop-tstopS))/(abs(tstop-tstart)); % calcolo la Responsiveness Spaziale

Resp_S = 0; for k=tstart:tstop, sin = prototype(k-tstart+1, 2); sfin = prototype(k-tstart+1, 3); found = 0; for j=1:size(simulation,1), if simulation(j,1) == k found = 1; sinS = simulation(j, 2); sfinS = simulation(j, 3);

Resp_S = Resp_S + (abs(sin-sinS)+abs(sfin-sfinS))/abs(sfin-sin);

end

end

if found == 0

Resp_S = Resp_S + (sin + sfin)/(sfin - sin);

end

end

%ritorno il valore

val=Resp_T+(Resp_S/(abs(tstop-tstart))); end

59

La componente relativa alla Responsiveness Spaziale è calcolata nella parte finale della funzione; essa rappresenta la media della Responsiveness spaziale ad ogni istante di tempo in cui l’ingorgo si è presentato nella realtà. Se in un dato istante di tempo il simulatore non avesse individuato l’ingorgo i valori di

S’

IN e

S’

FIN sono impostati a 0.

Anche in questo caso ricordiamo la definizione matematica di Responsiveness Spaziale :

𝑅𝐸𝑆𝑃(𝑆

_𝑖

)

_𝑆

=

1

|𝑡

_{𝑠𝑡𝑜𝑝}

− 𝑡

_{𝑠𝑡𝑎𝑟𝑡}

|

∑

|𝑠

_𝐼𝑁

(𝑡) − 𝑠

′ 𝐼𝑁

(𝑡)| + |𝑠

𝐹𝐼𝑁

(𝑡) − 𝑠

′𝐹𝐼𝑁

(𝑡)|

|𝑠

𝐹𝐼𝑁

(𝑡) − 𝑠

𝐼𝑁

(𝑡)|

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

Algoritmo di Evoluzione Differenziale

L’algoritmo di evoluzione differenziale è implementato utilizzando lo script messo a disposizione da Markus Buehren ed implementa l’algoritmo di evoluzione differenziale così come descritto e programmato dagli stessi autori Price e Storn sul sito dell’Università della California, Berkeley. La funzione che invoca l’algoritmo di evoluzione differenziale ammette 8 parametri caratteristici; modificando anche solo uno di questi parametri è possibile influenzare la qualità di ottimizzazione.

…

% calcolo la Responsiveness temporale

tstart = prototype(1,1);

tstop = prototype(size(prototype,1),1); tstartS = simulation(1,1);

tstopS = simulation(size(simulation,1),1);

Resp_T = (abs(tstart-tstartS) + abs(tstop-tstopS))/(abs(tstop-tstart)); …

…

% calcolo la Responsiveness Spaziale

Resp_S = 0; for k=tstart:tstop, sin = prototype(k-tstart+1, 2); sfin = prototype(k-tstart+1, 3); found = 0; for j=1:size(simulation,1), if simulation(j,1) == k found = 1; sinS = simulation(j, 2); sfinS = simulation(j, 3);

Resp_S = Resp_S + (abs(sin-sinS)+abs(sfin-sfinS))/abs(sfin-sin);

end

end

if found == 0

Resp_S = Resp_S + (sin + sfin)/(sfin - sin);

end

end

val=Resp_T+(Resp_S/(abs(tstop-tstart))); …

60

In dettaglio la funzione di invocazione dell’algoritmo si presenta nella seguente forma:

[bestmem, bestval, bestFctParams] = differentialevolution(DEParams, paramDefCell, objFctHandle, objFctSettings, objFctParams, emailParams, optimInfo);

Analizziamo adesso più nel dettaglio il parametri che è necessario passare alla funzione per fare in modo che l’algoritmo esegua l’ottimizzazione:

 DEParams : una struttura che descrive i parametri dell’algoritmo fra cui: - NP: specifica la dimensione della popolazione.

- CR: specifica la probabilità di crossover.

- maxiter, maxtime, maxclock: specificano le condizioni di stop dell’algoritmo.

- minimizeValue: specifica se il valore funzione di fitness da inseguire è il minimo o il massimo.

 paramDefCell : permette di definire i parametri da ottimizzare. Si tratta di una matrice di massimo quattro colonne che specificano per ogni parametro:

- il nome;

- il range di validità. - la quantizzazione. - il valore iniziale.

 objFctHandle : specifica la funzione obiettivo dell’algoritmo e deve restituire un valore numerico.

% get default DE parameters

DEParams = getdefaultparams;

% set number of population members (often 10*D is suggested)

DEParams.NP = 10;

% set optimization to minimize fitness value

DEParams.minimizeValue = 1;

% do not use slave process here

DEParams.feedSlaveProc = 0;

% set times

DEParams.maxiter = 20;

DEParams.maxtime = 86400; % in seconds

DEParams.maxclock = [];

% set display options

DEParams.refreshiter = 1; DEParams.refreshtime = 600; % in seconds paramDefCell = { 'evaporation', [0 1], 0.01 'width', [1 20], 1 'threshold', [50 150], 1 };

% specify objective function

61

 objFctSettings: eventuali parametri di configurazione da passare alla funzione obiettivo.

 objFctParams: i valori iniziali dei parametri.

 emailParams: rappresenta una struttura che permette di configurare l’invio di email durantel’esecuzione e al termine dell’algoritmo.

 optimInfo: rappresenta una struttura che contiene delle informazioni generiche sull’ottimizzazione che si sta eseguendo come un titolo e un sottotitolo che saranno salvati nel file dei risultati generato dall’algoritmo.

In definitiva, la forma della funzione che rappresenta il cuore dell’Algoritmo di Evoluzione Differenziale ha la seguente forma:

% set single additional function parameter

objFctSettings = {};

% set initial parameter values in struct objFctParams

objFctParams.evaporation = 0.7; objFctParams.width = 10; objFctParams.threshold = 58; % send E-mails emailParams = []; % set title

optimInfo.title = 'Traffic Detector Model Optimization with Differential

Evolution'; function TrafficDetector addpath('differentialevolution\'); clc; clear all; javaaddpath(pwd);

% Traffic Detector with DIFFERENTIALEVOLUTION.

% See http://www.mathworks.com/matlabcentral/fileexchange/18593-differential- evolution for further documentation

% set title

optimInfo.title = 'Traffic Detector Model Optimization with Differential

Evolution';

% specify objective function

objFctHandle = @TrafficFitness;

% define parameter names, ranges and quantization:

paramDefCell = {

'evaporation', [0 1], 0.01 'width', [1 20], 1

'threshold', [50 150], 1 };

62

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 52-62)