Per l’esecuzione dei test descritti nella precedente sezione sono stati utilizzati svariati software.
Matlab
Matlab (Matrix laboratory) `e un ambiente di calcolo numerico multipiatta- forma che mette a disposizione dell’utente una vasta gamma di strumenti matematici, oltre a consentire l’implementazione di algoritmi ed altre utilit`a. Sviluppato utilizzando i linguaggi di programmazione C e Java, nonostante sia nato come strumento di puro calcolo numerico la successiva implemen- tazione di svariati pacchetti software ne ha consentito l’utilizzo anche per il calcolo simbolico, la simulazione grafica e la progettazione basata su model-
li. `E possibile richiamare da Matlab algoritmi scritti in differenti linguaggi di programmazione (come ad esempio i linguaggi C e C++).
In questo lavoro di tesi Matlab `e stato utilizzato nella sua funzione pri- maria, ovvero il calcolo numerico. Sono stati implementati svariati algoritmi al fine di semplificare e velocizzare l’esecuzione dei test, sfruttando la capa- cit`a del software di manipolare le matrici numeriche. Gli algoritmi sono stati implementati sia per popolare automaticamente le matrici di utilit`a dei due giocatori al variare dei parametri del gioco sia per effettuare uno dei test atti al ritrovamento degli equilibri del gioco, sfruttando una ricerca dicotomica sui grafici che rappresentano le utilit`a stesse.
AMPL
AMPL (A Mathematical Programming Language) `e un linguaggio di program- mazione per la descrizione e la risoluzione di problemi matematici complessi, sviluppato in modo tale da avere una sintassi estremamente simile alla nota- zione matematica per la definizione dei problemi di ottimizzazione (e quindi da facilitare la scrittura e la lettura della descrizione dei problemi). La soluzio- ne di un problema richiede la preparazione di due file, uno con la descrizione del problema stesso e l’altro contenente i dati numerici da utilizzare nel cal- colo, che vengono utilizzati come input per un risolutore, un software che ha il compito per l’appunto di risolvere il problema. AMPL supporta svariati risolutori, come ad esempio CPLEX e MINOS.
AMPL `e stato utilizzato per la risoluzione del gioco rappresentante il test di Shewhart, rappresentato in tre diversi problemi di ottimizzazione (relati- vi alla formulazione del gioco in forma normale, come gioco bayesiano e per la ricerca di un equilibrio leader-follower). I file contenenti i dati numerici sono stati generati tramite l’implementazione di un algoritmo in Matlab, che ha poi richiamato lo stesso AMPL per la risoluzione del problema associato, utilizzando il risolutore CPLEX.
Algoritmo di Lemke-Howson
Infine `e stata utilizzata una implementazione in linguaggio C dell’algoritmo di Lemke-Howson, funzionante sulle piattaforme Unix e derivate. L’imple- mentazione utilizzata modifica leggermente l’algoritmo originale, introducen- do un elemento di casualit`a e ripetizione che migliora le prestazioni generali dell’algoritmo. Di nuovo, come nel caso dell’utilizzo di AMPL, questa imple- mentazione richiede un file di input contenente i dati numerici che descrivono il gioco, anche in questo caso generati dal medesimo codice Matlab.
Durante le prime esecuzioni dei test `e stato riscontrato un errore di in- stabilit`a numerica dovuta alla scelta della precisione nella rappresentazione
dei numeri manipolati dall’algoritmo. Un’ulteriore versione dell’algoritmo, implementata con una maggiore precisione, ha risolto questo problema.
Capitolo 4
Test di Shewhart
Il test di Shewhart [13] `e un CDT (Change Detection Test) sviluppato nei primi anni ’10. Nella sua concezione originale, `e un test di controllo di qualit`a in un processo produttivo.
4.1
Formalizzazione del test
Gli articoli prodotti vengono modellati con una serie di variabili casuali i.i.d. X generate da una distrubuzione di probabilit`a nota. Vengono quindi selezio- nate una o pi `u caratteristiche della distribuzione di probabilit`a (ad esempio la media e la varianza) e viene impostata una fascia di controllo centrata nel valore nominale di tale caratteristica.
Ad intervalli prefissati vengono calcolati i valori campionari relativi agli articoli prodotti. Questi vengono poi confrontati con la fascia di controllo im- postata: se i valori rilevati non sono contenuti nella fascia di controllo viene segnalata un’anomalia comportando un blocco del sistema produttivo.
Se l’anomalia fosse il risultato dell’intervento di un agente esterno, il cui scopo `e quello di modificare il normale andamento del sistema, il test di Shewhart pu `o essere formalizzato sotto forma di gioco strategico.
In questo caso il giocatore relativo all’anomalia, chiamato giocatore Attac- cante, ha l’obiettivo di modificare i parametri della distrubuzione che gene- ra le variabili Xi, e le sue azioni nel gioco indicheranno di quanto intende
modificare i parametri di detta distribuzione.
Il giocatore relativo al test invece, chiamato giocatore Difensore, tenta di in- dividuare l’intervento del giocatore Attaccante impostando la soglia di accetta- bilit`a per i parametri campionari; le sue azioni esprimono la distanza dei bordi della fascia dal valore nominale del parametro. Ovviamente, poich`e la segna- lazione di un’anomalia implica il blocco del sistema produttivo, il giocatore Difensore deve prestare attenzione ad impostare la fascia di controllo in modo
Segnalazione NoSegnalazione ∆µ >0 AttaccanteCatturato VittoriaAttaccante ∆µ= 0 FalsoPositivo StatusQuo
Tabella 4.1: Esiti del gioco.
tale da non segnalare come anomalie eventuali articoli prodotti normalmente ma con valori particolarmente alti (o bassi).
Supponendo che il test si limiti a controllare la media campionaria, quindi, il giocatore Attaccante imposta un valore ∆µ con cui andr`a a modificare la media del processo produttivo, mentre il giocatore difensore imposta la soglia di accettabilit`a h. Se il valore della media campionaria sar`a esterno ai limiti della fascia di accettabilit`a, verr`a segnalata la presenza dell’agente esterno. Il gioco sopra descritto ha, quindi, quattro possibili esiti a seconda dei valori scelti dai due giocatori. I suddetti esiti sono riportati in Tabella 1.1.
A seconda dell’esito del gioco, i due giocatori ricevono un diverso valore di ritorno. Pi `u precisamente, il giocatore Difensore ricever`a un ritorno positi- vo qualora indichi correttamente la presenza di un’anomalia (o non ne indichi in assenza di anomalia) e nullo altrimenti, mentre il giocatore Attaccante ri- cever`a un ritorno positivo qualora riesca ad agire sul processo senza essere individuato.
Indicando con UD l’utilit`a del difensore e con UA quella dell’attaccante, e
con R il responso del giocatore difensore (A per indicare che il giocatore Di- fensore ha indicato la presenza del giocatore Attaccante, N A per indicarne il caso contrario) quindi, si avr`a:
UD = n 1 ∆µ > 0, R = A 1 ∆µ = 0, R = N A 0 altrimenti UA = n 1 ∆µ > 0, R = N A − altrimenti
Quanto descritto finora prende ovviamente come certa la presenza di un giocatore Attaccante (che pu `o comunque decidere se giocare o meno). Non `e per `o detto che un giocatore Attaccante sia effettivamente presente nel gioco. La formalizzazione del Test di Shewhart assume quindi la forma di un gio- co Bayesiano, non a somma zero, in cui i giocatori possono appartenere ad uno specifico tipo. Nel caso del test di Shewhart, per il giocatore Attaccante possono essere definiti due tipi θ1 e θ2 che descrivono la presenza o meno del-
l’Attaccante all’interno del gioco. In questo caso, i valori sopra descritti per le utilit`a dei due giocatori saranno validi unicamente per il caso in cui il tipo θA del giocatore Attaccante sia θ1, ovvero per il caso in cui sia presente. Con
UD =
n 1 R = N A −γ R = A UA= 0
I valori indicati con e γ indicano due fattori di penalit`a che vengono as- segnati ai giocatori: il giocatore Attaccante ricever`a una penalit`a pari a − nel caso in cui venga individuato dal giocatore Difensore; il giocatore Difensore, invece, ricever`a una penalit`a pari a −γ a seguito di un falso positivo.
Quanto appena descritto rappresenta un singolo turno del gioco, e viene ri- petuto ad intervalli regolari lungo una finestra temporale di durata prefissata (indicata con il numero di intervalli, T). Ad ogni turno il giocatore Difenso- re esegue un controllo sui valori campionari da considerare, per decidere se segnalare o meno la presenza di un’anomalia.