1*intercorso FIA domande aperte

Fornire una definizione completa di Intelligenza Artificiale.

La definizione di Intelligenza Artificiale comprende diversi aspetti e, pertanto, esistono più definizioni capaci di descriverla.

PENSARE UMANAMENTE Il tentativo di far sì che i computer arrivino a pensare. L’automazione delle attività che associamo al pensiero umano, come il processo decisionale, la risoluzione di problemi, l’apprendimento e altro.

PENSARE RAZIONALMENTE Lo studio delle facoltà mentali attraverso l’uso di modelli computazionali. Lo studio dei processi di calcolo che rendono possibile percepire, ragionare e agire.

AGIRE UMANAMENTE L’arte di creare macchine che eseguono attività che richiedono intelligenza quando vengono svolte da persone. Lo studio di come far eseguire ai computer le attività a cui, al momento, le persone sono più brave.

AGIRE RAZIONALMENTE L’Intelligenza Computazionale è lo studio della progettazione di agenti intelligente. L’Intelligenza Artificiale riguarda il comportamento intelligente negli artefatti.

Descrivere il ruolo della psicologia cognitiva all’interno dell’Intelligenza Artificiale.

Nello specifico l’IA riguarda la psicologia cognitiva. Secondo l’autore Craik, un agente intelligente possiede tre requisiti:
-- ricevere uno stimolo e tradurlo in una rappresentazione interna.
-- manipolare la rappresentazione da processi cognitivi per ottenere nuove rappresentazioni interne
(raffinamento dello stimolo).
-- da tali rappresentazioni devono essere a loro volta trasformate in azioni.

“Se l’organismo porta nella sua testa un modello in scala della realtà esterna e delle proprie possibili azioni sarà in grado di provare varie alternative, decidere quali di esse sia la migliore, reagire a situazioni future prima che si manifestino, utilizzare la conoscenza di eventi passati per gestire quelli presenti e futuri, e sotto ogni aspetto reagire in modo molto più ricco, affidabile e competente alle emergenze che si troverà a fronteggiare.”

Craik morì in un incidente in bicicletta nel 1945. Il suo lavoro fu continuato da Broadbent, il quale fu tra i primi a modellare i fenomeni psicologici basandosi sulla elaborazione dell’informazione, dando vita alla scienza cognitiva, quindi si passa da un concetto umanistico ad uno in cui è possibile misurare.

Entra in gioco Turin, dimostrando che un computer può agire similmente ad un umano, infatti nel 1950 creò un test, che prende il nome di test di Turing, con l’obiettivo di fornire in maniera soddisfacente una definizione operativa dell’intelligenza. Il test è noto anche come il celeberrimo “the imitation game”.

Il test consiste in 3 protagonisti:
-- un uomo (A) (o una macchina)
-- una donna (B)
-- un interrogatore (C), che non conosce l’identità di A e B

L’obiettivo di C è quello di porre le domande, e sulla base delle risposte ottenute, dovrà capire chi tra A e B è la macchina.
B invece, assumerà il ruolo dell’imitatore, ovvero colui che dovrà rispondere come A.
Infatti il solo modo per essere sicuri che una macchina pensa è quello di essere la macchina stessa a sentire se si stesse pensando, ma questo è impossibile…. Pertanto l’intelligenza può essere misurata solo guardando il comportamento esterno, non il ragionamento che ha portato a quel comportamento.

Descrivere il test di Turing.

Descrivere i modelli di rappresentazione del cervello umano.

Quando diciamo che un determinato programma ragiona come un essere umano, dobbiamo prima di tutto determinare come noi pensiamo, ovvero capire quali sono i meccanismi interni del cervello umano. Bisogna ricorda che ad oggi questo campo è totalmente, quindi non possiamo strutturare il pensiero, bensì approssimarlo.
I meccanismi identificati sono:
INTROSPEZIONE
E’ un atto della coscienza che consiste nell’osservazione diretta e nell’analisi della interiorità rappresentata da pensieri, pulsioni, desideri e stimoli prodotti dal
pensiero stesso. La modellazione, in questo caso, consiste nel tentativo di catturare “al volo” i nostri pensieri mentre scorrono.
SPERIMENTAZIONE PSICOLOGICA
E’ la branca della psicologia che mira ad applicare il metodo sperimentale di Newton nell’indagine dei processi cognitivi del cervello= umano. La modellazione, in
questo caso, consiste nell’osservazione dei pensieri, pulsioni, desideri e stimoli di una persona in azione, perché non possiamo dimostrare formalmente, bensì
vedere cosa succede sul campo (ricerca empirica).
IMAGING CELEBRALE
Rappresenta l’utilizzo di tecniche per la mappatura diretta e/o indiretta dalla struttura, della funzione e della farmacologia del sistema nervoso. La
modellazione, in questo caso, consiste nell’osservazione del cervello in azione, così da poter intuirne i meccanismi nervosi interni e trarne conclusioni. In altre
parole non sappiamo quali sono i link dei pensieri, ma sappiamo la struttura del cervello, quindi immaginiamo come lavorano i neuroni e cerchiamo di capire
come pensiamo.

Tutto ciò ha a che fare con la psicologia e la neuroscienza.
PSICOLOGIA
Tenta di spiegare in maniera indiretta come le persone ragionano. È la scienza che studia gli stati mentali e i suoi processi cognitivi, emotivi, sociali e
comportamentali attraverso i componenti consci e inconsci.
NEUROSCIENZA
Tentano di modellare il sistema nervoso tramite l’analisi dei componenti morfo-funzionali; tali componenti vengono spesso studiati con l’utilizzo della
biomedica.

Descrivere i componenti di un problema.

Un problema può essere definito formalmente da cinque componenti:

-- Stato iniziale. Rappresenta il punto di partenza dell’agente.

-- Azioni. L’insieme Azioni include la descrizione delle possibili operazioni attuabili dall’agente.

-- Modello di transizione. Descrive il risultato di ogni azione attuabile dall’agente in s. Utilizziamo anche il
termine successore per indicare qualsiasi stato raggiungibile da uno stato mediante una singola azione

-- Test obiettivo. Questo determina se un particolare stato è uno stato obiettivo. In alcuni casi, esiste un
insieme esplicito di possibili stati obiettivo: in questo caso il test si limiterà a verificare se uno stato s
appartiene all’insieme

-- Costo di cammino. Funzione che determina il costo numerico a ogni cammino.

Stato iniziale, azioni e modello di transizione, definiscono lo stato degli spazi del problema, l’insieme di tutti gli stati raggiungibili da quello iniziale mediate qualsiasi sequenza di azioni.

Descrivere il processo di ricerca.

La ricerca si basa sulla formulazione di un obiettivo e la ricerca di una sequenza di azioni che possa portarci a soddisfare il nostro obiettivo, quindi raggiungerlo.

Formulazione dell’obiettivo: La formulazione dell’obiettivo, basata sulla situazione corrente e sulla misura di prestazione dell’agente, rappresenta necessariamente il primo passo nella risoluzione dei problemi.

Obiettivo: Questo è rappresentato da un insieme ammissibile di stati del mondo. Più in dettaglio, è rappresentato da tutti e soli quegli stati in cui l’obiettivo è soddisfatto.

Sotto queste ipotesi, la soluzione di qualsiasi problema è rappresentata da una sequenza fissata di azioni. In altri termini, una soluzione potrebbe essere implementata come una strategia ramificata che raccomandi azioni future diverse in base alle percezioni giunte.

Il processo che cerca una sequenza di azioni che raggiunge l’obiettivo è detto ricerca.
Nello specifico si ricerca una soluzione per passare dallo stato iniziale ad uno stato obiettivo, dove la qualità della soluzione viene misurata dalla funzione di costo di cammino, e la soluzione ottima è quella che ha il costo minore di tutte.

Un semplice agente risolutore di problemi cerca innanzitutto di risolvere un problema, passare il problema all'algoritmo di ricerca per una soluzione, e dopo aver formulato una soluzione accettabile, esegue la soluzione in termini di azioni che possano soddisfare il problema.

Di conseguenza avviene inizialmente una formulazione del problema, ove si prende in input la percezione corrente dell'agente al fine di ottenere le variabili necessarie per poter risolvere il problema.
Inoltre per il totale funzionamento é necessario istanziare delle variabili le quali: sequenza di azioni effettuate, lo stato corrente, l'obiettivo dell'agente e la formulazione del problema.

Ad ogni azione che l'agente di ricerca effettua, dovra' aggiornare lo stato, la formulazione di obiettivo e quello del problema, ovviamente perché ad ogni azione essi cambiano, e potenzialmente l'agente potrebbe ritrovarsi ad aver effettuato un azione che raggiunge l'obiettivo.

Ad ogni azione si salva la sequenza delle azioni effettuate, al fine di poter salvare la completa lista di azioni tramite la quale é possibile risolvere il problema ottenendo la soluzione, sempre se essa esiste.

Dopo aver effettuato la ricerca di una sequenza di azioni ottimale, l'agente esegue la sequenza.

Mentre l’agente esegue la sequenza di azioni ignora le proprie percezioni, perché le conosce in anticipo, un agente di questo tipo, che porta avanti le proprie azioni ad “occhi chiusi”, deve essere certo di quello che accade. Nella teoria del controllo, si parla di sistema a ciclo aperto, perché ignorando le percezioni si rompe il ciclo tra agente e ambiente.

Riportare i principali passi di un semplice agente risolutore di problemi.

Discutere delle prestazioni (in termini di completezza, ottimalita', complessita' temporale e spaziale) della ricerca in ampiezza.

La ricerca in ampiezza è una semplice strategia di ricerca in cui tutti i nodi di profondità d sono espansi prima di quelli di profondità d+1, che consiste di:
1. Espandere il nodo radice
2. Espandere i nodi generati dalla radice
3. Espandere i loro successori e così via

La ricerca in ampiezza è una strategia sistematica di ricerca, ovvero è in grado di trovare sempre una soluzione, se esiste. E’ inoltre, di trovare sempre la soluzione realizzabile con il cammino più breve: tuttavia, bisogna sottolineare che il cammino più breve non è necessariamente quello con il costo minore.
Da un punto di vista pratico, questa strategia può essere implementata utilizzando una semplice coda FIFO per la frontiera. Di conseguenza, i nuovi nodi (che sono quelli via via più lontani dalla radice) vanno in fondo alla coda e i nodi vecchi (che sono quelli più vicini) vengono espansi per primi.
Ad ogni iterazione, viene espanso il nodo indicato. Si può pensare alla ricerca in ampiezza come un pendolo che, di volta in volta, visita i nodi in maniera orizzontale.

Analizziamo adesso le prestazioni della ricerca in ampiezza, considerando i quattro indicatori precedentemente introdotti. Denotiamo con b il fattore di diramazione (ovvero, il numero massimo di successori); e con d la profondità della soluzione minima.

Completezza: E’ facilmente intuibile che l’algoritmo è completo. Se il nodo obiettivo più vicino alla radice si trova alla profondità d, la ricerca lo troverà dopo aver espanso tutti i nodi che lo precedono.
Ottimalità: Se il costo di cammino è una funzione monotona non decrescente della profondità del nodo, allora possiamo dire che la ricerca è ottimo. Più in generale, però, l’algoritmo non lo è - restituisce la soluzione più vicina, indipendentemente dal costo.
Complessità temporale: Supponiamo di dover ricercare una soluzione in un albero in cui ogni nodo ha b successori. La radice genererà b nodi al primo livello, ognuno dei quali genererà altri b nodi, per un totale di b² al secondo livello. Ognuno di questi genererà altri b nodi, arrivando a b³ al terzo livello, e così via. Nel caso pessimo, la soluzione è l’ultima ad essere analizzata e si trova ad una profondità d.
Quindi la complessità temporale: O(b^d), ovvero esponenziale, perchè navigare tutti i nodi in maniera ordinata si perde un sacco di tempo.
Complessità spaziale: L’algoritmo memorizza ogni noto espanso nell’insieme esplorati: per questa ragione, la complessità sarà sempre una funzione di b. In particolare, la ricerca in ampiezza conserva ogni nodo generato in memoria: avremo così O(b^d-1) nodi nell’insieme esplorato e O(b^d) nodi nella frontiera. Quindi, la complessità spaziale sarà di O(b^d), ovvero è dominata dalla dimensione della frontiera.

Definire il concetto di ricerca a Costo uniforme

è una variante della ricerca in ampiezza che, è capace di trovare sempre la soluzione ottima, piuttosto che espandere il nodo meno profondo, la ricerca a costo uniforme espande il nodo n con il minimo costo di cammino g(n).
Così facendo garantisce l'ottimalità ottenendo il cammino più breve e di costo minore. Semplicemente questo è possibile memorizzando la frontiera come coda a priorità ordinata secondo g- in cima alla coda ci saranno i nodi di costo minore.

Ci sono sostanziali differenze implementative rispetto alla ricerca per ampiezza:
1. Il test obiettivo è applicato ad un nodo non appena è selezionato per l'espansione, e non quando è generato per la prima volta.
2. Si aggiunge un test obiettivo nel caso in cui sia trovato un cammino migliore per raggiungere un nodo che attualmente si trova sulla frontiera.

La differenza sta nel ricordarsi il nodo con costo minimo (o il percorso di costo minimo) fino alla fine, e in caso sia necessario, andare a rinavigare quella scelta al fine di trovare e cercare l'ottimalità.

Completezza ed ottimalità: Possiamo facilmente dire che l'algoritmo è completo, e per natura è anche ottimo.

Complessità temporale e spaziale: La ricerca a costo uniforme è guidata dal costo di cammino e non dalla loro profondità. Consideriamo perciò C*, il costo della soluzione ottima e assumiamo che ogni azione costi almeno ε (£). La complessità temporale e spaziale sarà uguale a O(b^1+[C*+£]).
C*/ε rappresenta il costo di ogni passo fatto dall'algoritmo.

Quindi la ricerca a costo uniforme è, in generale, più efficace di quella in ampiezza ma potrebbe essere addirittura meno efficiente.

Definire il concetto di ricerca in Profondità / Profondità limitata

Strategia di ricerca in cui viene sempre espanso prima il nodo più profondo nella frontiera corrente dell'albero di ricerca, infatti non espande i nodi come un pendolo ma procede analizzando un ramo alla volta dell'albero di ricerca. Raggiunge immediatamente il livello più profondo dell'albero, dove i nodi non hanno successori.
Dopo aver espanso tali nodi li rimuove dalla frontiera, per cui la ricerca torna indietro per riconsiderare il nodo più profondo che ha successori non ancora espansi.
Questo algoritmo utilizza una coda LIFO, inoltre considerando uno pseudocodice, l'algoritmo sarà ricorsivo, in modo da poter viaggiare efficientemente all'interno dell'albero di ricerca.

Purtroppo di base con questo algoritmo si potrebbe incappare in un cammino ridondante e provocherà una non terminazione, di conseguenza di per sé non è completo.
Inoltre potrebbe ritornare un nodo obiettivo molto lontano dalla radice senza tenere conto del costo, per cui non è ottimo.
Sebbene abbia dei vantaggi in termini di complessità spaziale, ha difficoltà nella complessità temporale, la quale è esponenziale, dato che potrebbe impiegare tempo indeterminato se una foglia è troppo in profondità.
Di per sé non è un algoritmo interessante, però le sue varianti possono essere utili, cioè la ricerca in profondità limitata e approfondimento iterativo.

La ricerca a profondità limitata prevede un limite di cammino che non può essere varcato nell'esplorazione, in modo da evitare che l'algoritmo non termini. Di conseguenza l'algoritmo può terminare o per un fallimento o per tramite il valore di taglio. (Soluzione non trovata / entro il limite). Infatti il problema di questa strategia sta nel trovare una soglia ottimale.

Da un punto di vista di performance, la ricerca a profondità limitata:
Completezza: Come già accennato, l’algoritmo non è completo nei casi in cui la soluzione si trova ad una profondità maggiore del limite stabilito.
Ottimalità: Questa strategia non può essere ottima nei casi in cui il limite stabilito sia minore della profondità massima (quindi sempre, altrimenti non sarebbe limitata).
Complessità temporale: La complessità è limitata dalla dimensione dello spazio degli stati. Sia l il limite prestabilito, nel caso pessimo la ricerca genererà O(b^l) nodi.
Complessità spaziale: Rappresenta la peculiarità principale rispetto ai precedenti algoritmi. La ricerca deve memorizzare un solo cammino dalla radice ad un nodo foglia, insieme ai rimanenti nodi fratelli non espansi per ciascun nodo sul cammino. Una volta che un nodo è stato espanso, può essere rimosso dalla memoria non appena tutti i suoi discendenti sono stati esplorati completamente. Per uno spazio degli stati con fattore di ramificazione b e profondità l, la complessità sarà di O(bl).

Definire il concetto di ricerca ad approfondimento iterativo.

La strategia di ricerca ad approfondimento iterativo, ha l’obiettivo di identificare un limite ideale per la ricerca a profondità limitata, tuttavia non compromettendo costo, completezza e ottimalità.
Con questa strategia, il limite viene incrementato progressivamente, finché un nodo obiettivo non è identificato.
Oltre a migliorare la ricerca in profondità, la ricerca ad approfondimento iterativo è analoga a quella in ampiezza, poiché ad ogni iterazione esplora completamente un livello di nodi prima di prendere in considerazione il successivo.
In generale, questo tipo di ricerca è il metodo di ricerca non informata da preferire quando lo spazio di ricerca è grande e la profondità della soluzione non è nota.

Da un punto di vista di performance:

Completezza: In maniera simile alla ricerca in ampiezza, l’algoritmo è completo. Se il nodo obiettivo più vicino alla radice si trova alla profondità d, la ricerca lo troverà dopo aver espanso tutti i nodi che lo precedono.

Ottimalità: Se il costo di cammino è una funzione monotona non decrescente della profondità del nodo, allora possiamo dire che la ricerca è ottimo. Più in generale, però, l’algoritmo non lo è - restituisce la soluzione più vicina, indipendentemente dal costo.

Complessità temporale: Nel caso pessimo, saranno generati O(bd) nodi.

Complessità spaziale: Come per la ricerca in profondità limitata, la ricerca deve memorizzare un solo cammino dalla radice ad un nodo foglia, insieme ai rimanenti nodi fratelli non espansi per ciascun nodo sul cammino. Una volta che un nodo è stato espanso, può essere rimosso dalla memoria non appena tutti i suoi discendenti sono stati esplorati completamente. Per cui, la complessità sarà di O(bd).

Definire il concetto di ricerca Bidirezionale

Strategia di ricerca in cui viene eseguita una prima ricerca in avanti dallo stato iniziale e l’altra all’indietro dallo stato obiettivo.
L’idea alla base è molto semplice: effettuare due ricerche in parallelo: la prima guidata dai dati, la seconda dall’obiettivo.

Perché? Semplicemente, perché O(b^d/2) + O(b^d/2) < O(bd) , sia in termini di complessità temporale che spaziale.
Questo tipo di ricerca è implementata sostituendo il test obiettivo con un controllo che le frontiere delle due ricerche si intersechino: in tal caso, è stata trovata una soluzione.

Non è però così semplice implementarla. Cosa si intende per cercare “all’indietro”?
Predecessore: Definiamo predecessori di uno stato x tutti gli stati che hanno x come successore. Definire i predecessori non è sempre così immediato.

Cosa si intende per “obiettivo” nella ricerca “all’indietro”?
Consideriamo l’esempio del problema delle N regine. L’obiettivo è che “nessuna regina ne attacchi un’altra”: data questa descrizione astratta, è molto difficile definire cosa rappresenti l’obiettivo della ricerca all’indietro.

Descrivere le principali strutture dati necessarie per la formulazione di un algoritmo di ricerca.

Per poter descrivere le strutture dati necessarie bisogna innanzitutto parlare della soluzione di una ricerca: Una soluzione è una sequenza di azioni. Per questo, gli algoritmi di ricerca operano considerando varie possibili di sequenze.

Tali sequenze di azioni formano un albero di ricerca con lo stato iniziale alla radice, i rami sono le azioni e i nodi corrispondono a stati nello spazio degli stati del problema.
Dato lo stato iniziale, il primo passo sarà verificare che l’obiettivo non sia stato raggiunto; dopodiché, si considereranno le varie azioni, espandendo lo stato corrente e generando così un nuovo insieme di stati.

I nodi senza figli vengono definiti foglie. L’insieme di tutti i nodi foglia che possono essere espansi in un dato punto è detto frontiera. La frontiera non fa altro che segnare cosa è stato esplorato e cosa non. Per poter espandere la frontiera bisogna stabilire una strategia che sarà la politica che l’algoritmo utilizzerà per decidere come procedere con la ricerca.

Durante l’esplorazione ci troveremo a perseguire cammini ciclici, ovvero quelli in cui uno stato è ripetuto più volte nell’albero di ricerca, ma questi rappresentano un caso particolare di cammini ridondanti, ciò può trasformare un problema trattabile in uno intrattabile.. Per evitare di addentrarsi in cammini ridondanti, è perciò necessario ricordare dove si è passati. Possiamo quindi migliorare l’algoritmo basa di ricerca introducendo una struttura dati denominata insieme esplorato (o lista chiusa).

Quindi avere una struttura dati ci consente di tener traccia dell’albero ricostruito. Per ogni nodo n dell’albero abbiamo una struttura contenente i quattro seguenti parametri:
n.stato → lo stato dello spazio degli stati a cui corrispondono il nodo;
n.padre → il nodo dell’albero di ricerca che ha generato il nodo corrente;
n.azione → l’azione applicata al padre per generare il nodo;
n.costo-cammino → il costo g(n) del cammino che va dallo stato iniziale al nodo;

Memorizzati i singoli nodi, è necessaria una struttura dove conservare tutti i nodi che saranno generati nell’albero di ricerca. La frontiera deve essere memorizzata in modo da consentire all’algoritmo di ricerca di scegliere facilmente il successivo nodo da espandere in base alla propria strategia. In tal senso, la struttura dati più adatta è una coda.

Quindi le strutture piu' usate sono alberi, code/liste e talvolta array, pero' puo' essere utilizzata qualsiasi struttura si voglia.

Si consideri il percorso tra Sibie e Bucarest raffigurato in Figura 1. Riportare le espansioni dei nodi effettuate da un algoritmo di ricerca in profondita'.

Il nostro algoritmo trovera' come prima soluzione il percorso che percorrera':

Sibiu --> Rimnicu Vilcea --> Pitesti --> Bucharest

In totale avra' un costo di 80+97+101= 278

Da come possiamo notare ha trovato non solo la soluzione e raggiunto l'obiettivo, ma ha anche trovato la soluzione ottimale con il minor costo.

Cio' non e' sempre cosi', infatti abbiamo avuto la fortuna di poter avere il costo minore, se l'albero fosse stato invertito, avremmo avuto come prima soluzione
Sibiu --> Fagaras --> Bucharest, con un costo maggiore di percorso.

Descrivere le caratteristiche dell’algoritmo di ricerca Best First Greedy

Gli algoritmi greedy sono tra i più utilizzati in pratica per problemi di ottimizzazione in diversi contesti.
L’algoritmo cerca sempre di espandere il nodo più vicino all’obiettivo, sulla base del fatto che è probabile che questo porti rapidamente ad una soluzione. Di conseguenza la valutazione dei nodi viene fatta applicando direttamente la funzione euristica f(n) = h(n), con h >= 0.

Vediamo come funziona un algoritmo greedy riconsiderando l’esempio di navigazione da Arad a Bucarest. Una delle possibili euristiche, in questo caso, consiste nel considerare la distanza in linea d’aria tra i nodi di partenza e obiettivo. Chiaramente, per poter utilizzare questa euristica dovremo conoscere a priori tutte le distanze in linea d’aria verso Bucarest (questa è un’informazione che rende, appunto l’algoritmo di ricerca informato).
(Da notare c’è anche il fatto che, per definire un’euristica del genere, bisogna avere consapevolezza di una correlazione tra la distanza in linea d’aria e quella su strada; es sapere quanto traffico c’è o se si stanno effettuando lavori migliorerebbe l’euristica)
Sulla base di queste distanze, possiamo definire l'albero di ricerca che sarà utilizzato dall'algoritmo per trovare una soluzione.

L'algoritmo procede a scegliere la prima via da lui ritenuta più veloce, seguendo sempre la distanza da lui considerata minore.

Tuttavia, la soluzione non è ottima. Esiste un altro cammino, che da Sibiu va a Vilcea e poi a Pitesti che farebbe risparmiare 32 chilometri rispetto al tragitto identificato in maniera greedy. In questo caso, la ricerca trova una soluzione senza mai espandere un nodo che non sia sul cammino della soluzione. Quindi, il costo di ricerca è minimo.

Ecco perché l’algoritmo viene definito “goloso”: ad ogni passo cerca sempre di arrivare più vicino all’obiettivo, non considerando cammini alternativi con stima di costo maggiore che potrebbero portare alla soluzione totale migliore.

Oltre a non essere ottimo, l'algoritmo non è neanche completo, Infatti considerando il problema di andare da Iasi a Fargas.
In pratica, l’algoritmo greedy deciderà di andare a Neamt, finendo in un vicolo cieco poiché il costo é di 87.

L’espansione di Neamt porterà Iasi in frontiera: l’algoritmo tornerà indietro ma tornerà poi nuovamente a Neamt, causando un ciclo infinito. Complessità temporale Nel caso pessimo, l’algoritmo ha complessità O(b^m), dove m è la profondità massima dello spazio di ricerca. Tuttavia, con una buona euristica, è possibile ridurre drasticamente tale complessità. Complessità spaziale Questa sarà nuovamente pari a O(b^m), poiché l’algoritmo conserva tutti i nodi in memoria.

Descrivere le caratteristiche dell’algoritmo di ricerca A*, specialmente in termini di funzione euristica.

La forma più diffusa di ricerca best-first è la ricerca A*, la quale viene eseguita combinando g(n), ovvero il costo per raggiungere il nodo, con h(n), ovvero il costo dal nodo n all’obiettivo. In pratica, f(n) = g(n) + h(n), con h(n) > 0 e h(goal) = 0. Siccome g(n) fornisce il costo del cammino dal nodo iniziale al nodo n ed h(n) rappresenta il costo stimato del cammino più conveniente da n all’obiettivo, allora possiamo riformulare f(n) come: f(n) = costo stimato della soluzione più conveniente che passa per n. Se siamo alla ricerca della soluzione meno costosa, allora è ragionevole provare per primo il nodo con valore più basso di f(n). Da un punto di vista pratico, l’algoritmo è implementato nella stessa maniera della ricerca a costo uniforme: l’unica differenza è che la coda a priorità è ordinata in base ad f(n) = g(n) + h(n) piuttosto che f(n) = g(n). Un paio di casi speciali: Se h(n) = 0, allora f(n) = g(n) —> si ha una Ricerca Uniforme; Se g(n) = 0, allora f(n) = h(n) —> si ha una ricerca Best First Greedy

L’ottimalità di A* dipende da due fattori. 1. La prima è che h(n) sia un’euristica ammissibile, ovvero che non sbagli mai per eccesso la stima del costo per arrivare all’obiettivo. 2. La seconda è che h(n) sia un’euristica consistente. Per ogni nodo n e ogni successore n’ di n generato da un’azione a, il costo stimato per raggiungere l’obiettivo partendo da n non è superiore al costo di passo per arrivare a n’ sommato al costo stimato per andare da li all’obiettivo. In altri termini: h(n) ≤ c(n, a, n’) + h(n’)

Completezza Questa richiede l’esistenza di un numero finito di nodi di costo minore o uguale a C* (la soluzione ottima), una condizione vera se tutti i costi dei passi superano un valore finito ε e se b è finito. Complessità temporale L’algoritmo è ottimamente efficiente. A parità di euristica, nessun altro algoritmo espande meno nodi (senza rinunciare all’ottimalità). I dettagli dell’analisi vanno oltre lo scopo di questo corso, tuttavia possiamo dire che l’algoritmo ha complessità O(b^ε), il ché lo rende più efficiente degli altri algoritmi best-first. Complessità spaziale L’algoritmo tiene in memoria tutti i nodi generati, quindi sarà O(b^m). Quindi, con l’algoritmo A* riusciamo a generare soluzioni con una complessità temporale migliore, non riuscendo tuttavia a migliorare quella spaziale...

EURISTICA. Aspetto del metodo scientifico che comprende un insieme di strategie, tecniche e procedimenti inventivi per ricercare un argomento, un concetto o una teoria adeguati a risolvere un problema dato.

Descrivere le caratteristiche dell’algoritmo di ricerca Simplified Memory Bounded A* (SMA*)

L’idea alla base è quella di utilizzare meglio la memoria disponibile.
Molto semplicemente, SMA* procede come A* fino all’esaurimento della memoria disponibile. Quando questo accade, allora l’algoritmo libera il nodo peggiore, ovvero quello con l’f-valore più alto.

Come RBFS, però, memorizza nel nodo padre il valore del nodo dimenticato.
Questo meccanismo consente all’algoritmo di tenere traccia della radice di un sotto- albero dimenticato, avendo quindi a disposizione l’informazione sul cammino migliore di quel sotto-albero
—> SMA* rigenera un sotto-albero dimenticato solo quando tutti gli altri cammini promettono di comportarsi peggio di quello.

SMA* è completo se la soluzione è raggiungibile, ovvero se d (la profondità del nodo obiettivo più vicino alla radice) è inferiore alla dimensione della memoria espressa in nodi.
SMA* è ottimale se c’è una soluzione ottima raggiungibile.

Il problema di questo algoritmo consiste nel fatto che, per problemi difficili, la ricerca sarà spesso obbligata a passare continuamente dall’uno all’altro tra molti cammini candidati di cui sarà possibile memorizzare solo un piccolo sottoinsieme.
Quando questo accade, il problema potrebbe diventare intrattabile
—> la complessità temporale potrebbe esplodere, rendendo il problema non risolvibile nella pratica.

Quali sono le differenze tra l’algoritmo di ricerca ad approfondimento iterativo standard e la Iterative Deepening A* (IDA*)?

È possibile adottare l’idea dell’approfondimento iterativo al contesto della ricerca euristica: questo da vita all’algoritmo IDA*.
(come A* ma con approfondimento iterativo, la funzione di valutazione è il costo)

La differenza principale tra IDA* e l’approfondimento iterativo standard sta nel valore del taglio, che non è più basato sulla profondità ma sul costo f, ovvero su g+h. Ad ogni iterazione, il nuovo valore di taglio è l’f-costo minimo tra quelli di tutti i nodi che hanno superato il valore di taglio nell’iterazione precedente.

Essendo una estensione di A*, ne mantiene le proprietà di completezza e ottimalità, a patto che sussistano le condizioni di ammissibilità e consistenza.

Il vero vantaggio si ottiene in termini di occupazione di memoria, poiché l’algoritmo mantiene le proprietà dell’algoritmo di ricerca ad apprendimento iterativo standard:
la ricerca dovrà memorizzare un solo cammino dalla radice ad un nodo foglia, insieme ai rimanenti nodi fratelli non espansi per ciascun nodo sul cammino.
Una volta che un nodo è stato espanso, può essere rimosso dalla memoria non appena tutti i suoi discendenti sono stati esplorati completamente.
Per cui, la complessità sarà di O(bd).

Descrivere le caratteristiche dell’algoritmo di ricerca Best First Ricorsiva

Questa rappresenta una variante della ricerca best-first classica, usando tuttavia solo uno spazio lineare.
Ad ogni iterazione, l’algoritmo tiene traccia del miglior percorso alternativo. Invece di fare backtracking in caso di fallimento, interrompe l’esplorazione quando trova un nodo meno promettente (definito sulla base di f).

La struttura dell’implementazione è simile a quella della ricerca ricorsiva in profondità.
Ma invece di continuare a seguire indefinitamente il cammino corrente, si utilizza la variabile f-limite per tenere traccia dell’f-valore del miglior cammino alternativo. Se il nodo corrente supera il limite, la ricorsione torna indietro cosi che l’algoritmo considererà il cammino alternativo. Questa rappresenta una variante della ricerca best-first classica, usando tuttavia solo uno spazio lineare. Ad ogni iterazione, l’algoritmo tiene traccia del miglior percorso alternativo.
Invece di fare backtracking in caso di fallimento, interrompe l’esplorazione quando trova un nodo meno promettente (definito sulla base di f).

In primo luogo, la ricerca Best-First ricorsiva è ottimale se la funzione euristica h(n) è ammissibile (non sbagli mai per eccesso la stima del costo per arrivare all’obiettivo).
La complessità spaziale È lineare nella profondità della più profonda soluzione ottima O(bd) essendo quindi notevolmente migliore rispetto alle alternative precedenti, che presentavano una complessità esponenziale.
La complessità temporale È però difficile da definire. Questa dipende sia dalla funzione euristica sia dalla frequenza dei cambiamenti del cammino ottimo durante l’espansione dei nodi. Nel caso pessimo, però, sarà esponenziale.

Il problema della ricerca Best-First ricorsiva, così come di IDA*, consiste nel fatto che utilizzano troppa poca memoria.
Tra un’iterazione ed un’altra, IDA* ricorda solo il limite corrente all’f-costo, mentre RBFS usa solo uno spazio lineare.
Anche se fosse disponibile più memoria, i due algoritmi non riuscirebbero ad usarla. Entrambi gli algoritmi dimenticano la maggior parte di ciò che fanno, rischiando di espandere più e più volte gli stessi stati già visitati in precedenza.

Descrivere le caratteristiche della Beam Search, indicando le criticita' che non la rendono n´e' completa n´e' ottimale.

La Beam Search è una variante della ricerca best-first che non conserva in memoria tutti i nodi generati, ma tiene ad ogni passo solo i k nodi più promettenti, con k definito come ampiezza del raggio.

L’ampiezza del raggio è definita in base ad una euristica (ad esempio, h(n) potrebbe rappresentare l’euristica); solo i nodi nel raggio vengono conservate e considerate come candidati per la soluzione.

La Beam Search è, quindi, a tutti gli effetti una soluzione greedy alla risoluzione dei problemi, poiché espanderà sempre il nodo che ritiene essere più utile al raggiungimento della soluzione.
Da un punto di vista pratico, ad ogni livello dell’albero di ricerca l’algoritmo genera tutti i successori degli stati a quel livello, ordinandoli in maniera decrescente in base all’euristica scelta.
Conserverà poi solo i primi k di ogni livello, che saranno poi espansi. Chiaramente, maggiore sarà il raggio e minore sarà il numero di nodi potati. L’algoritmo restituirà la prima soluzione identificata.
Sebbene migliori l’occupazione di memoria (in questo caso, la complessità spaziale sarà pari ad O(kd)), l’algoritmo non è completo né ottimale.

Descrivere le principali differenze tra algoritmi di ricerca tradizionali e algoritmi di ricerca locali.

Gli algoritmi tradizionali sono progettati per esplorare sistematicamente lo spazio degli stati: per farlo, tengono in memoria uno o più cammini e registrano quali alternative sono state esplorate in ogni punto del cammino.

Quando viene raggiunto uno stato obiettivo, il cammino verso quello stato costituisce una soluzione del problema. Tuttavia, in molti casi il cammino che porta alla soluzione è irrilevante;
ad esempio, nel problema delle N regine ciò che conta è la disposizione finale delle regine sulla scacchiera, non l’ordine con cui sono state aggiunte.
Questo vale per molti problemi reali. Nel contesto di questa classe di problemi, possiamo considerare algoritmi diversi che ignorano il cammino che porta alla soluzione.

Quindi, in molti problemi di ottimizzazione lo stato obiettivo è esso stesso la soluzione al problema, indipendentemente da come ci si è arrivati. Questa è la differenza con gli algoritmi standard.

In tali casi, si possono utilizzare algoritmi di miglioramento iterativo, i quali mantengono in memoria solo lo stato corrente e tentano di migliorarlo.

ALGORITMI DI RICERCA “TRADIZIONALI”
Considerano interi cammini dallo stato iniziale a quello obiettivo
Hanno una complessità temporale e spaziale generalmente esponenziale
Non possono essere applicati in problemi con spazio degli stati grandi/infiniti

ALGORITMI DI RICERCA LOCALE
Considerano lo stato corrente con l’obiettivo di migliorarlo
Usano poca memoria, molto spesso avendo una complessità costante
Possono trovare soluzioni ragionevoli (sub-ottimali) a problemi complessi

Definire il concetto di struttura dei vicini.

Molti algoritmi di ricerca locale non hanno un test obiettivo ma hanno una funzione obiettivo, perche' a noi ci serve capire quanto miglioriamo nel tempo. Questo e' dato dal fatto che noi supponiamo che ogni possibile soluzione e' candidata ad essere la migliore, e la funzione ci permette di stabilire proprio questo aspetto. Quindi la funzione obiettivo e' fondamentale per l'efficienza, un po' come la funzione euristiche viste in precedenza.

La scelta della funzione obiettivo è fondamentale per l’efficienza del sistema e definisce l’insieme delle soluzioni che possono essere raggiunte da una soluzione s in un singolo passo di ricerca dell’algoritmo.

Tipicamente, la funzione obiettivo è definita attraverso le possibili mosse che l’algoritmo può effettuare. È da notare che la ricerca locale si basa sull’esplorazione iterativa delle “soluzioni vicine” che possono migliorare quella corrente mediante modifiche locali.

Struttura dei vicini (neighborhood): Una struttura dei vicini è una funzione F che assegna a ogni soluzione s dell’insieme di soluzioni S un insieme di soluzioni N(s) sottoinsieme di S.

La soluzione trovata da un algoritmo di ricerca locale non è detto che sia globalmente ottima, ma può essere ottima rispetto i cambiamenti locali, anche meglio dire che la soluzione può essere la migliore possibile date le circostanze.

Fornire una formulazione di un problema di ricerca Locale Online.

Quasi tutti i problemi che consideremo, gli algoritmi possono e non possono trovare soluzioni ottime, perche' l'obiettivo e' passare da una soluzione x ad y che sia migliore, ma ci potrebbe essere la possibilita' di trovare soluzioni sub ottime (cioe' non le migliori possibili). Questo fattore non ci interessa in quanto comunque porta ad una soluzione.
Molti algoritmi di ricerca locale non hanno un test obiettivo ma hanno una funzione obiettivo, perche' a noi ci serve capire quanto miglioramo nel tempo. Questo e' dato dal fatto che noi supponiamo che ogni possibile soluzione e' candidata ad essere la migliore, e la funzione ci permette di stabilire proprio questo aspetto. Quindi la funzione obiettivo e' fondamentale per l'efficienza, un po' come la funzione euristiche viste in precedenza.
Tipicamente, la funzione obiettivo è definita attraverso le possibili mosse che l’algoritmo può effettuare. È da notare che la ricerca locale si basa sull’esplorazione iterativa delle “soluzioni vicine” che possono migliorare quella corrente mediante modifiche locali.
È importante notare che la soluzione trovata da un algoritmo di ricerca locale non è detto che sia globalmente ottima, ma può essere ottima rispetto ai cambiamenti locali. Ad esempio se partissimo da una soluzione non buona, il suo miglioramento porta ad una soluzione non ottima rispetto alle soluzioni globali. In altri termini, la soluzione può essere la migliore possibile date le circostanze.

L’asse delle x rappresenta i vari stati raggiungibili nel processo di ricerca.
L’asse delle y indica il valore della funzione obiettivo per un determinato stato.
Lo stato corrente indica la posizione in cui si trova la ricerca rispetto al
panorama degli stati.
Un punto piatto dello stato degli spazi indica una regione dello spazio dove gli stati
vicini avranno lo stesso valore (anche detto plateau).
Una spalla è il plateau che presenta uno spigolo in salita.
Un massimo locale è una soluzione sub-ottima ad un problema di ricerca.
L’ottimo globale è invece la soluzione al problema migliore in assoluto

Un algoritmo di ricerca locale completo trova sempre un obiettivo, se questo esiste.
Un algoritmo di ricerca locale ottimo trova sempre un minimo/massimo globale.
Banalmente, più è largo il neighborhood più è probabile che un massimo/minimo locale sia anche globale, di conseguenza migliore sarà qualità della soluzione.

Approfondimento. Ricerca Online.

Un problema di ricerca online è un tipo di problema computazionale in cui un algoritmo deve prendere decisioni istante per istante, senza conoscere in anticipo l'intera sequenza di input. In altre parole, l'algoritmo deve fare scelte senza avere informazioni future e deve cercare di ottimizzare un obiettivo o risolvere un problema in tempo reale. Ecco una formulazione generica di un problema di ricerca online:

Problema di ricerca online generico:

Input:

1. Una sequenza di eventi o input in un certo ordine.

2. Un algoritmo che deve prendere decisioni istante per istante basate sugli eventi precedenti e sugli eventi futuri non noti.

Obiettivo:

L'obiettivo dell'algoritmo è ottimizzare una certa funzione di costo o risolvere un problema specifico mentre processa gli eventi uno alla volta. L'obiettivo può variare a seconda del tipo di problema.

Vincoli:

1. L'algoritmo non ha accesso alle informazioni sugli eventi futuri e deve basarsi solo su ciò che è stato osservato fino a quel momento.

2. Le decisioni prese in precedenza possono influenzare le future scelte e possono avere un impatto sulla performance complessiva dell'algoritmo.

Esempio di problema di ricerca online:

Un esempio di problema di ricerca online potrebbe essere il seguente:

Problema del commesso viaggiatore online:

Input:

1. Una sequenza di città che il commesso viaggiatore deve visitare, date una alla volta.

2. La distanza tra le città quando vengono presentate.

Obiettivo:

L'obiettivo del commesso viaggiatore è trovare il percorso più breve possibile per visitare tutte le città nella sequenza. Ogni volta che viene presentata una nuova città, il commesso deve decidere quale città visitare successivamente in modo da minimizzare la lunghezza totale del percorso.

Questo è solo un esempio e i problemi di ricerca online possono variare ampiamente in base all'obiettivo specifico, ai vincoli e al contesto in cui si verificano. In generale, questi problemi richiedono strategie algoritmiche intelligenti per prendere decisioni istante per istante in modo da massimizzare o minimizzare l'obiettivo specifico.

Approfondimento. Differenze tra la ricerca online e Locale

Anche se sia la ricerca locale che la ricerca online coinvolgono processi di ottimizzazione o risoluzione di problemi, sono in realtà due paradigmi molto diversi con obiettivi e approcci distinti:

1. Ricerca Locale:

- La ricerca locale mira a trovare un ottimo locale, ossia una soluzione che sia la migliore all'interno di una regione ristretta dello spazio di ricerca.

- In un problema di ricerca locale, l'algoritmo inizia da una soluzione iniziale e cerca di migliorarla facendo piccoli cambiamenti locali. L'obiettivo è massimizzare o minimizzare una funzione obiettivo.

- La ricerca locale è spesso utilizzata per problemi di ottimizzazione continua o combinatoria, come il problema del commesso viaggiatore o l'ottimizzazione di funzioni continue.

- L'algoritmo tende a convergere a un massimo o minimo locale, ma non garantisce di trovare il massimo o il minimo globale.

2. Ricerca Online:

- La ricerca online è focalizzata su decisioni immediate istante per istante senza conoscere gli eventi futuri. Gli algoritmi di ricerca online reagiscono agli eventi man mano che si verificano.

- In un problema di ricerca online, l'algoritmo cerca di ottimizzare o risolvere un problema mentre elabora gli eventi uno alla volta. Non dispone di una vista completa delle scelte future.

- La ricerca online è utilizzata per problemi in cui la sequenza degli eventi è fondamentale e richiede decisioni rapide e immediate, come problemi di scheduling, gestione di risorse, e giochi in tempo reale.

- L'obiettivo è adattarsi e reagire alle circostanze correnti mentre la sequenza degli eventi si evolve.

In sintesi, sebbene entrambi i paradigmi siano legati all'ottimizzazione e alla risoluzione di problemi, sono progettati per contesti molto diversi. La ricerca locale è orientata verso l'ottimizzazione di soluzioni in uno spazio di ricerca ben definito, mentre la ricerca online si concentra su decisioni immediate e adattamento a eventi in tempo reale senza conoscere il futuro.

Algoritmo di Hill-Climbing + Descrivere le variazioni all’utilizzo di Hill-Climbing per la risoluzione di problemi di ricerca online.

E' l'algoritmo più semplice tra gli algoritmi di ricerca locale e ha l'obiettivo di scalare lo spazio di ricerca per trovare un massimo/minimo globale.
Ad ogni passo fatto da esso il nodo corrente viene rimpiazzato dal vicino migliore, infatti non viene mantenuto un albero di ricerca, per cui memorizza solo quello.

Ha alcuni problemi però, infatti l'algoritmo non guarda oltre e fa miglioramenti solo in base ai passi successivi, di conseguenza potrebbe fermarsi al primo shoulder, quindi con un ottimo locale.
Infatti gli algoritmi Hill climbing che raggiungono un ottimo locale saranno bloccati lì, senza continuare ad esplorare, oppure se raggiungono un plateau potrebbero bloccarsi senza migliorare la situazione corrente, oltre al fatto che esistono anche dei ridge (creste) che portano l'algoritmo a dover fare delle brusche variazioni di percorso dove una serie di massimi locali potrebbero metterlo in difficoltà.

Di conseguenza massimi locali, plateau e creste possono deteriorare le prestazioni degli algoritmi di Hill Climbing.

Esistono diverse altre varianti dell’algoritmo di base dell’Hill-Climbing, le quali vanno sostanzialmente a lavorare sulla probabilità che l’algoritmo riesce ad uscire da un massimo locale ed esplorare lo spazio di ricerca in maniera più efficace. Anche in questi casi, però, l’efficienza degrada. La scelta dell’algoritmo da utilizzare dipende dal tipo di problema da affrontare.

L’Hill-Climbing stocastico sceglie a caso tra tutte le mosse che vanno verso l’alto; a differenza dell’algoritmo di base, non sceglie immediatamente la mossa più conveniente, aumentando le chance di navigare lo spazio di ricerca in maniera più estesa.

L’Hill-Climbing con prima scelta può generare le mosse a caso fino a trovarne una migliore dello stato corrente. Questa strategia è molto buona quando uno stato ha molti (migliaia) successori, poiché l’algoritmo riuscirà a navigare meglio lo spazio di ricerca.

L’Hill-Climbing con riavvio casuale può consentire alla ricerca di ripartire da un punto a caso dello spazio di ricerca - è da notare che generare uno stato casuale in uno spazio degli stati può essere di per sé un problema difficile. Il riavvio casuale consente, in pratica, all’algoritmo di avviare una serie di ricerche hill-climbing. Risulta essere completo perché prima o poi dovrà generare, come stato iniziale, proprio un obiettivo. Più in generale, il successo dell’ultimo algoritmo dipende dalla forma del panorama dello spazio degli stati. Se ci sono pochi massimi locali e plateau, allora troverà una soluzione molto velocemente. Ma purtroppo, non è sempre così.

Algoritmo Simulated Annealing

Un algoritmo creato per combinare una ricerca di Hill-Climbing con un esplorazione casuale, in modo da evitare che la ricerca rimanga bloccata in un minimo/massimo locale, così facendo è possibile migliorare sia efficienza che la completezza dell'algoritmo.

Questo è quello che si propone di fare il Simulated Annealinig, di fatto prende il nome dal processo usato per indurire i metalli, cioè scaldandoli a temperature elevate per poi raffreddarli gradualmente.
Il processo di ricerca che utilizza questo algoritmo è molto simile, per il quale scuoterà molto la ricerca variando di molto il panorama degli stati, per poi man mano ridurre l'intensità di questo meccanismo, concentrandosi quindi su un punto specifico del panorama e cercando una soluzione ottima in quel contesto.

Il parametro velocità_raffreddamento rappresenta una corrispondenza dal tempo alla “temperatura”
La velocità di raffreddamento impatterà la temperatura T ed indicherà quanto T venga ridotto ad ogni passo dell’algoritmo
Il ciclo interno è simile a quello dell’Hill-Climbing, ma questa volta il nodo successore sarà scelto a caso.
Se il successore ha un valore migliore, allora la mossa verrà sempre accettata e l’algoritmo procederà ad esplorare lo spazio intorno a quello stato.
In alternativa, il successore potrebbe essere accettato ugualmente, ma con una qualche probabilità inferiore ad 1.
Nella similitudine con la metallurgia, ΔE rappresenta la variazione di energia

Vale la pena notare che la probabilità decresce esponenzialmente in base alla cattiva qualità della soluzione (ΔE). Inoltre, decresce anche con la temperatura T - questa scenderà costantemente ad ogni passo dell’algoritmo. In altri termini, mosse “cattive” verranno accettate più facilmente all’inizio poiché T sarà alto e diventeranno sempre meno probabili a mano a mano che T si abbassa. Se la temperatura si abbassa abbastanza lentamente, l’algoritmo troverà un ottimo globale con una probabilità tendente ad 1.

Algoritmo Local Beam

Memorizzare un solo nodo può sembrare una reazione estrema ai problemi legati alle limitazioni di memoria. Una variante è rappresentata dalla beam search.

L’algoritmo di ricerca local bean tiene traccia di k stati anziché uno. All’inizio comincia con k stati generati casualmente: ad ogni passo, sono poi generati i successori di tutti i k stati.
Se uno di questi è un obiettivo, la ricerca termina. Altrimenti, scegli i k successori migliori dalla lista e ricomincia.

In linea teorica, potrebbe sembrare simile all’Hill-Climbing con riavvio casuale. Tuttavia, nella ricerca con riavvio casuale ogni processo di ricerca è del tutto indipendente dagli altri.
Nella local beam, invece, la ricerca è “informata”, nel senso che informazione viene passata dall’uno all’altro thread di ricerca paralleli. Questo aumenta le chance di navigare il panorama degli stati verso stati più “promettenti”, possibilmente aumentando le chance di trovare un ottimo globale.

Da un altro punto di vista, la local beam potrebbe soffrire di una carenza di diversificazione tra i k stati, concentrando quindi la ricerca troppo rapidamente in una piccola regione dello spazio.
Un’alternativa è rappresentata dalla ricerca local beam stocastica, che è ispirata ai concetti già discussi con l’Hill-Climbing stocastico. Invece di scegliere i k successori migliori tra i candidati, si scelgono k successori a caso. Tuttavia, ai migliori di questi si assegna una probabilità maggiore di scelta.

Definire il processo generale di definizione di un algoritmo genetico.

“meta-euristica”: questo denota l’uso di un approccio euristico di tipo generale. Meta perché si usa una procedura per determinare l’euristica.
META-EURISTICA. Metodo euristico per la soluzione di una classe molto ampia di problemi computazionali combinando diverse procedure a loro volta euristiche, con l'obiettivo di ottenere una procedura più robusta ed efficiente.

Algoritmi Genetici (GA). Procedura di alto livello (meta-euristica) ispirata alla genetica per definire un algoritmo di ricerca. Facciamo subito attenzione:
GA NON è il nome di un algoritmo di ricerca, ma è una PROCEDURA che ci consente di definire algoritmi di ricerca. Per questo si usa spesso il plurale: ci riferiamo a qualsiasi algoritmo che segue le regole dei GA.

Da queste osservazioni possiamo subito dare alcune proprietà dei GA: 1. I GA non sono problem-specific. Non risolvono una singola classe di problemi di ricerca, ma molteplici, anche di natura molto differente (dai giochi al testing). 2. I GA non garantiscono l’ottimalità. Di norma, producono soluzioni sub-ottimali. 3. I GA non garantiscono l’ottimalità. Di norma, producono soluzioni sub-ottimali.

I quattro aspetti caratterizzanti di un GA sono:
1. Codifica gli individui Possibile soluzione come stringhe di lunghezza finita (NB: Questo è vero da un punto di vista teorico, ma da quello pratico, per ragioni di efficienza e semplicità, qualche volta si codifica in altri modi).
2. E’ population-based Non fa evolvere una singola soluzione, ma un insieme di esse contemporaneamente, passo passo. Questo li contrappone ai tradizionali algoritmi di ricerca locale.
3. E’ cieco La funzione obiettivo (aka funzione di fitness) non necessita di informazioni (Talvolta, pero, qualche informazione di ai basso livello può aiutare la ricerca) di basso livello del problema (i.e., problem-specific) che si sta risolvendo.
4.Ha elementi di casualità che guidano la ricerca Pur non arrivando ai livelli di una random search.

Rispetto agli altri algoritmi di ricerca locale, i GA si distinguono per l’applicazione in sequenza di tre operatori genetici.
Selezione. Una copia di alcuni individui nella successiva generazione.
Crossover. Accoppiamento di individui (parents) per crearne di nuovi (offsprings), da aggiungere alla nuova generazione.
Mutazione. Una modifica casuale di alcune parti del corredo genetico.

Potenzialmente, un GA può “non fallire mai”, nel senso che una soluzione, seppur non ottimale, la può sempre restituire. In realtà, il concetto di fallimento dipende fortemente dal problema che stiamo risolvendo e da come decidiamo di risolverlo. Nell’esempio giocattolo, ci siamo mossi solo nello spazio delle soluzioni ammissibili, ma possono esserci GA che viaggiano in spazi di soluzioni inammissibili. Premesso che il dataset iniziali siano ammissibili allora l’algoritmo è infallibile. I dati di input costituiscono una soluzione perciò è infallibile.

Termini importanti di un algoritmo genetico

Convergenza Per convergenza si intende la capacità (obiettivo) di un GA di migliorare iterativamente le soluzioni candidate verso il punto di ottimo. Quando gli individui tendono a somigliarsi troppo, bloccando troppo presto il progresso globale dell’intera popolazione, parliamo di convergenza prematura.

Diversità Per diversità si intende la capacità di un GA di definire individui che possano navigare il panorama degli stati in maniera efficace, evitando la stagnazione verso punti di ottimo locale e soprattutto bisogna evitare che gli individui siano troppo simili il che porterebbe alla terminazione del GA.

Funzione di fitness Rappresenta un elemento chiave per la definizione di un algoritmo genetico. Formalmente parlando, la funzione di fitness è una funzione in grado di associare un valore a ogni soluzione. Misura il livello di adeguatezza degli individui rispetto al problema considerato e, inevitabilmente, guida il processo di selezione. Chiaramente, la funzione dipenderà dal problema in esame e dovrà ben rappresentare il grado di adeguatezza di una soluzione.

Nulla vieta di combinare più elementi ad esempio, una combinazione lineare di più fattori. In tutti i casi, indipendentemente da come impostiamo la funzione di fitness, stiamo ancora parlando di funzioni mono-obiettivo, in quanto l’obiettivo è formalizzato usando un’unica funzione obiettivo.

Gli algoritmi genetici, parametri 1

1. Size (Popolazione) - Numero individui di ciascuna generazione.
- Se la size è fissa, bisogna decidere il numero;

- Se la size è variabile, è opportuno decidere una dimensione massima. La ricerca potrebbe diventare eccessivamente lenta.

2. Size Mating Pool - Numero di individui selezionati e che partecipano alla riproduzione.
Più grande è la size, più lento sarà l’algoritmo. Più piccola è la size, più limitata sarà la diversità che l’algoritmo garantirà.

3. Probabilità crossover - Con quale probabilità avviene il crossover tra due genitori.
- Possiamo stabilire una probabilità che l’algoritmo userà per valutare se effettuare l’operazione di crossover o meno. Più alta è la probabilità, più spesso i genitori produrranno nuovi individui e, quindi, più diversità ci sarà in termini di soluzioni.

- Anche in questo caso, però, bisogna stare attenti. Più alta sarà la probabilità, più è probabile che l’algoritmo navighi lo spazio di ricerca senza andare a convergenza. Più bassa sarà la probabilità, più è probabile una convergenza prematura.

4. Probabilità mutazione - Con quale probabilità avviene una mutazione.
Considerazioni simili all precedenti.

5. Inizializzazione - Con quale criterio si crea la prima generazione.
- Possiamo creare una popolazione iniziale in maniera totalmente casuale.

- Oppure, possiamo basarci su euristiche. Se riusciamo a rendere i GA meno ciechi (dando informazioni problem-specific) possiamo evitare di iniziare con individui quasi sicuramente pessimi (se non addirittura inammissibili).

- Se possibile, basarsi su euristiche è desiderabile: la ricerca può essere immediatamente guidata verso soluzioni ammissibili/migliori, riducendo il carico computazionale.

6. Rappresentazione individui - Tipo di codifica degli individui.
- Abbiamo visto, nell’esempio, l’uso di una rappresentazione basata su stringa binaria.

- Ma possiamo rappresentare gli individui come meglio crediamo per il problema in esame.

Altre rappresentazioni molto usate sono le stringhe di interi/reali o addirittura gli alberi.

Gli algoritmi genetici, parametri 2

7. Algoritmo di selezione - Come avviene la selezione degli individui.
- Casuale: sconsigliata in molti casi, poiché aumenta le chance di non convergenza.

- Roulette Wheel, visto nell’esempio: gli individui ricevono una probabilità di selezione pari al valore della loro fitness relativa all’intera popolazione. Molto fedele alla natura, ma un individuo “molto forte” verrà selezionato troppe volte, rischiando la convergenza prematura.

- Rank: si compie un ordinamento totale degli individui rispetto alla fitness e si assegna a ciascuno individuo il rango in base alla posizione (e.g., il primo otterrà rango 1, il secondo rango 2, e così via).Ciascun individuo riceve una probabilità di selezione inversamente proporzionata al rango.
- Truncation: si compie un ordinamento totale in maniera analoga ad una Rank Selection, ma la selezione non avviene su base casuale quanto con una selezione rigida dei migliori M (< n) individui. Non possono esserci selezioni ripetute.

Ha vantaggi e svantaggi simili a Rank, ma toglie una componente di casualità, introducendo l’onere di definire il valore di un ulteriore parametro, i.e., M (quale è un valore ottimale?)

- K-way tournament: K (< n) individui sono selezionati casualmente (formando il torneo) e il migliore tra questi K passa la selezione definitivamente. Si ripete finché non si arriva ad M tornei (e quindi M vincitori). Si possono avere selezioni ripetute.

E’ poco complessa ed ha interessanti somiglianze con la natura (legge del più forte, letteralmente), tutti motivi per cui è una scelta molto popolare. Tuttavia impone l’onore di una buona scelta di K ed M.

Si può adottare una pressione di selezione: invece di far vincere sempre il migliore (assoluto) di un torneo, ogni individuo ha una probabilità di vittoria proporzionata alla sua fitness. In sostanza, i singoli tornei diventano delle piccole Roulette Wheel.

Si possono impedire le ripetizioni (in tal caso, se il mating pool è grande quanto la popolazione, ogni individuo ha la garanzia di partecipare ad esattamente K tornei).

Osserviamo che con K=1, si ha una Truncation Selection. Di fatti, si procederebbe selezionando gli individui migliori fino ad M, escludendo gli altri.

Gli algoritmi genetici, parametri 3

8. Algoritmo di crossover Come avviene il crossover tra individui.

- Single Point: visto nell’esempio, si seleziona un punto del patrimonio genetico dei genitori e si procede alla generazione di due figli tramite scambio di cromosomi.

- Two-Point: simile al single point, va a considerare però due punti di incrocio. Aumenta chiaramente la diversità dei geni degli individui generati.

- K-Point: Generalizzazione dei precedenti, è poco utilizzato dal momento che richiede la definizione di una strategia di combinazione dei K cromosomi dei genitori.

- Uniform: Ciascun gene i-esimo viene scelto casualmente tra i due geni i-esimi dei genitori.

Ha il massimo grado di casualità. E’ un particolare caso di K Point con K=Size_Individuo.

- Arithmetic: Ciascun gene i-esimo è il valor medio dei geni i-esimi dei genitori. Valido solo per rappresentazioni numeriche (precisamente, per le rappresentazione per cui ha senso calcolare il mid-point). Ne segue che i due figli saranno gemelli.

—> Per differenziare i due figli, è possibile assegnare un peso (fisso o casuale) ai due genitori e fare la media pesata invece che quella aritmetica. Quindi, il primo figlio usa peso α per il primo genitore e 1-α per il secondo, viceversa per il secondo figlio.

Gli algoritmi genetici, parametri 4

9. Algoritmo di mutazione - Come avviene la mutazione degli individui.
- Bit Flip: visto nell’esempio, consiste nella modifica di un singolo gene binario.

- Random Resetting: cambio casuale di un gene ad un altro valore ammissibile. La distribuzione da cui campionare il valore è a scelta: uniforme/normale/ecc.

- Swap: scambio di due geni, scelti casualmente.

- Scramble: si sceglie un subset di geni in modo casuale e lo si permuta casualmente.

- Inversion: si sceglie un subset di geni in modo casuale e lo si ribalta.

In altri termini, in termini di mutazione abbiamo molta flessibilità. Qualsiasi variazione va bene in linea di principio, ma è bene che la mutazione sia ammissibile (i.e., da un individuo ammissibile si passi ad un altro ammissibile, ovvero che la mutazione non vada a violare i vincoli del problema).

Alcuni algoritmi di mutazione lavorano localmente, ovvero su singoli geni dell’individuo, altri a livello globale. Chiaramente, gli algoritmi globali creano maggiore diversità, ma aumentano il rischio di mancata convergenza.

Tipicamente, gli algoritmi locali sono preferibili proprio perché limitano l’effetto di casualità che la mutazione può avere sulla convergenza dell’algoritmo.

10. Stopping Condition - Con quale criterio decidiamo di terminare l’evoluzione oppure proseguire.
- Tempo di esecuzione: l’evoluzione termina se si è superato un tempo di esecuzione T. Allo stop o si decide di restituire l’ultima generazione ottenuta o la migliore ultima (preferibile).

- Costo: se è presente una funzione di costo (i.e., una funzione---diversa dalla fitness---che associa ad individuo un costo secondo un certo criterio), allora al raggiungimento o superamento di quel costo l’evoluzione termina.

- Numero di iterazioni: si itera per un massimo di X generazioni.

- Assenza di miglioramenti: visto nell’esempio, se per Y generazioni consecutive non ci sono miglioramenti (significativi), allora l’evoluzione termina.

- Ibride: ovvero, basate su una combinazione delle precedenti.

- Problem specific: conoscendo i dettagli del problema, possiamo definire condizioni ad-hoc.

Spesso, invece di parlare esplicitamente di stopping condition, si preferisce la locuzione budget di ricerca (search budget), per indicare meglio il concetto di risorse a

disposizione (tempo/costo/iterazioni/ecc.).

In molti contesti, una stopping condition composta da tempo di esecuzione/costo e assenza di miglioramenti tende ad essere sufficientemente buona.

Gli algoritmi genetici, tecniche di improvement

I GA sono migliorabili sono tantissimi punti di vista.
1. Improvement - Il concetto di elitismo.
In fase di selezione, un individuo con alta fitness ha alte chance di sopravvivenza, ma la selezione può essere comunque crudele contro di lui... Vogliamo davvero
perdere un individuo potenzialmente importante? Elitism. Operazione per la quale salviamo il migliore (o i migliori k) individuo e lo copiamo nella generazione
successiva. In altri termini, evitiamo all’individuo più forte di incappare nel processo di selezione. Questa operazione può essere applicata a prescindere
dall'algoritmo di selezione e garantisce che la nuova generazione non sia peggiore della precedente (rispetto al miglior individuo).

2. Improvement - Uso di euristiche problem-specific.
E’ vero che i GA sono ciechi, ma ciò non toglie che l’utilizzo di informazioni aggiuntive possano rivelarsi utili. Queste possono velocizzare i miglioramenti,
aumentare la diversità e ridurre il rischio di convergenza prematura.

3. Improvement - Problemi multi-obiettivo.
Slide sulla domanda del Fronte di Pareto

4. Improvement - Il concetto di archivio.
Immaginiamo di avere dieci funzioni di fitness non negative. Ad un certo punto dell’evoluzione, otteniamo un individuo x in grado di minimizzare le prime cinque
(dalla 1 alla 5). Nella successiva iterazione perdiamo x ma otteniamo y, che minimizza le funzioni dalla 3 alla 7. Possiamo dire che: abbiamo “perso” la 1 e la 2, per
“guadagnare” la 6 e la 7. Peccato aver perso x, se ci fosse un modo per non perderlo... Archive Strategy. Strategia che mantiene una popolazione aggiuntiva che
non evolve, contenente gli individui che riescono a soddisfare degli obiettivi mai soddisfatti nelle precedenti iterazione.

5. Improvement- Il concetto di dynamic target selection.
In problemi complessi, potrei avere centinaia/migliaia di funzioni di fitness. Il fronte di Pareto inizia ad ingrandirsi; un criterio di preferenza “debole” non mi sarà
di aiuto. In generale, per evitare di avere troppe fitness, è consigliato usare funzioni indipendenti tra loro, ma dove ciò non è possibile si ha situazione del genere:
“se non minimizzo prima f1 non potrà mai sperare di minimizzare f2”. Di conseguenza, se nella mia popolazione non ho alcun individuo che minimizzi f1, a che
serve che nella successiva iterazione consideri anche f2 durante la valutazione? Dynamic Target Selection. Tecnica che, ad ogni iterazione, ci permette di
restringere l’insieme delle funzioni di fitness da valutare a seconda del risultato dell’iterazione precedente.

Descrivere due algoritmi (a scelta) di mutazione applicabili nel contesto di un algoritmo genetico in cui gli individui hanno una codifica in forma di stringa di interi.

Come avviene la mutazione degli individui.
Bit Flip: consiste nella modifica di un singolo gene binario.
Random Resetting: cambio casuale di un gene ad un altro valore ammissibile. La distribuzione da cui campionare il valore è a scelta: uniforme/normale/ecc.
Swap: scambio di due geni, scelti casualmente.
Scramble: si sceglie un subset di geni in modo casuale e lo si permuta casualmente.
Inversion: si sceglie un subset di geni in modo casuale e lo si ribalta.

In altri termini, in termini di mutazione abbiamo molta flessibilità. Qualsiasi variazione va bene in linea di principio, ma è bene che la mutazione sia ammissibile (i.e., da un individuo ammissibile si passi ad un altro ammissibile, ovvero che la mutazione non vada a violare i vincoli del problema). Alcuni algoritmi di mutazione lavorano localmente, ovvero su singoli geni dell'individuo, altri a livello globale. Chiaramente, gli algoritmi globali creano maggiore diversità, ma aumentano il rischio di mancata convergenza. Tipicamente, gli algoritmi locali son preferibili proprio perché limitano l'effetto di casualità che la mutazione può avere sulla convergenza dell'algoritmo.

In questo caso:
Mutazione per inversione di sottostringhe: Questo algoritmo di mutazione coinvolge la selezione casuale di due punti all'interno della stringa di interi e l'inversione della sottostringa compresa tra questi due punti. Questo processo può aiutare a introdurre variazioni significative nella soluzione candidata.

Esempio: Supponiamo che abbiamo la seguente stringa di interi: [1, 2, 3, 4, 5, 6, 7, 8]
Dopo aver selezionato casualmente due punti, ad esempio 3 e 6, invertiamo la sottostringa tra questi punti per ottenere: [1, 2, 3, 7, 6, 5, 4, 8].

Mutazione per scambio di posizioni: Questo algoritmo di mutazione coinvolge la selezione casuale di due posizioni all'interno della stringa di interi e lo scambio dei valori presenti in queste posizioni. Questa mutazione è meno invasiva rispetto all'inversione di sottostringhe ma può comunque introdurre variazioni nelle soluzioni.

Esempio: Supponiamo di avere la seguente stringa di interi: [1, 2, 3, 4, 5, 6, 7, 8]
Dopo aver selezionato casualmente due posizioni, ad esempio 2 e 5, scambiamo i valori in queste posizioni per ottenere: [1, 5, 3, 4, 2, 6, 7, 8].

Descrivere il concetto di fronte di Pareto nel contesto di algoritmi genetici multi-obiettivo.

Fronte di Pareto. Insieme degli individui di una popolazione non migliori tra loro (secondo le due regole suddette) ma migliori di tutti gli individui fuori dal fronte.
Esempio:
(x e y sono nel fronte di Pareto, mentre z no. x e y sono ottimi di Pareto)
Dati due individui nel fronte di Pareto, come decido quale di questi sia il migliore? Tramite il Preference Sorting.

Essa e' una tecnica che permette di fornire un ordinamento totale tra gli individui nel fronte di Pareto attraverso l’uso di una funzione di preferenza. La funzione di preferenza è diversa dalla funzione di fitness.

Esempio
Consideriamo una scatola nera con cinque interruttori. Non sappiamo nulla sull’interno della scatola (è nera!), soltanto che può essere azionata utilizzando le levette on-off di ciascun interruttore. A seconda della configurazione on-off degli interruttori, la scatola produrrà un segnale di output e, quindi, agirà in maniera diversa. Il comportamento della scatola è modellato dalla funzione f(s), dove s è una configurazione degli cinque interruttori. Non sappiamo null’altro di f(s). Il nostro obiettivo è quello di produrre il valore più alto possibile della funzione f(s). In altri termini, vogliamo ottenere una configurazione delle levette tale per cui il valore di payoff risultante sarà massimizzato.

Quasi sempre, il criterio che governa questa funzione deriva necessariamente dalla conoscenza del problema. Nell’esempio delle levette, potremmo definire una funzione di preferenza diversa a seconda del contesto o del periodo storico in cui la scatola nera è usata.

1. Se la scatola fosse utilizzata in un momento storico in cui l’energia elettrica costasse poco, potremmo preferire una soluzione principalmente focalizzata sul valore di output.
2. Altrimenti, potremmo voler “accontentarci” di una soluzione con valore minore ma che rappresenti un compromesso migliore.

Possiamo introdurre quanti criteri di preferenza vogliamo. Tutto dipende da quante informazioni riusciamo a ricavare dal problema e da ciò che desideriamo.

Elaborare sui principali vantaggi e svantaggi degli algoritmi genetici.

Siamo i proprietari della Premiata Pasticceria Rossi. Da un’analisi dell’Istituto Superiore di Sanita', risulta che il numero di bambini diabetici e' in aumento. Pertanto, vogliamo creare una nuova torta che apporti un significativo quantitativo di nutrienti e che risulti dolce al palato ma con pochi zuccheri. Abbiamo a disposizione i seguenti ingredienti: farina, zucchero, gocce di cioccolata, crema, panna, burro, sale, olio, frutti di bosco. Progettare un algoritmo genetico che possa rispondere agli obiettivi del problema. Definire quindi (1) codifica degli individui, (2) procedura di inizializzazione della popolazione, (3) funzione di fitness, (4) eventuali vincoli del problema, e (5) gli operatori genetici. E’ necessario descrivere brevemente il razionale dietro ognuna delle scelte proposte. NB: Le caratteristiche degli ingredienti sono volutamente lasciate alla personale interpretazione. Usa la testa: 100g di farina non possono essere piu' dolci di 100g di zucchero.

Per affrontare il problema di creare una nuova torta con pochi zuccheri ma ancora dolce al palato e ricca di nutrienti utilizzando un algoritmo genetico, dobbiamo definire vari aspetti dell'algoritmo. Ecco come potremmo affrontare ciascun elemento:

1. Codifica degli individui:

La codifica degli individui rappresenta come ciascuna ricetta (soluzione candidata) è rappresentata all'interno dell'algoritmo genetico. Una possibile codifica potrebbe essere una lista di quantità di ciascun ingrediente. Ad esempio, potremmo rappresentare una ricetta come [quantità di farina, quantità di zucchero, quantità di gocce di cioccolata, quantità di crema, quantità di panna, quantità di burro, quantità di sale, quantità di olio, quantità di frutti di bosco].

2. Procedura di inizializzazione della popolazione:

La popolazione iniziale dovrebbe consistere in un insieme di ricette iniziali casuali. Queste ricette iniziali possono essere generate assegnando quantità casuali di ciascun ingrediente, purché rispettino vincoli di base, come il totale delle quantità non deve superare una certa soglia (per evitare ricette impossibili).

3. Funzione di fitness:

La funzione di fitness valuterà quanto una ricetta è "buona" in base agli obiettivi del problema. Nel vostro caso, potrebbe essere una funzione che tiene conto del contenuto di zucchero, della quantità di nutrienti e del sapore complessivo. La funzione di fitness dovrebbe premiare le ricette con meno zucchero e più nutrienti, ma ancora gustose.

4. Eventuali vincoli del problema:

I vincoli del problema dovrebbero garantire che le ricette generate siano realistiche. Ad esempio, potrebbero includere:

- La somma delle quantità di tutti gli ingredienti non può superare un valore massimo per evitare ricette non praticabili.

- La quantità di zucchero deve essere inferiore a una certa soglia per garantire che la torta abbia pochi zuccheri.

- La quantità di nutrienti deve superare una certa soglia per garantire un apporto nutrizionale adeguato.

5. Operatori genetici:

Gli operatori genetici saranno utilizzati per generare nuove ricette (individui) dalla popolazione esistente. Ad esempio, è possibile implementare crossover (incrocio) per combinare le quantità di ingredienti da due ricette genitoriali, e mutazione per apportare piccole modifiche casuali alle quantità di ingredienti in una ricetta.

Il razionale dietro queste scelte è quello di rappresentare le ricette come individui, valutare quanto sono buone in base agli obiettivi del problema, rispettare i vincoli di fattibilità e utilizzare operatori genetici per esplorare nuove ricette. In questo modo, l'algoritmo genetico può esplorare diverse combinazioni di ingredienti per creare una torta con pochi zuccheri ma ancora gustosa e nutriente. La funzione di fitness è cruciale per guidare l'ottimizzazione verso risultati desiderati.

Preambolo ricerca con avversari

Iniziamo a discutere di ambienti competitivi, in cui gli obiettivi degli agenti sono in conflitto. Questo origina i problemi di ricerca con avversari, i quali vengono tipicamente indicati come giochi.

La teoria dei giochi è una branca dell’economia che considera ogni ambiente multi-agente come un gioco, indipendentemente dal fatto che l’interazione sia cooperativa o competitiva, a patto che l’influenza di ogni agente sugli altri sia significativa. Ogni agente deve considerare le azioni degli altri per ottimizzare il proprio obiettivo Curiosamente, gli ambienti con quantità molto grande di agenti sono spesso considerate economie piuttosto che giochi.

Esistono diverse tipologie di giochi:
Classificazione 1: Condizioni a Scelta
Giochi con informazione “perfetta”. Giochi in cui gli stati del gioco sono completamente espliciti agli agenti.
Giochi con informazione “imperfetta”. Giochi in cui gli stati del gioco sono solo parzialmente esplicitati.

Classificazione 2: Effetti della Scelta
Giochi deterministici. Giochi in cui gli stati del gioco sono determinati unicamente dalle azioni degli agenti
Giochi stocastici. Giochi in cui gli stati del gioco sono determinati anche da fattori esterni (ad esempio, tutti i giochi in cui c’è un dado).

Altre classificazioni tengono conto della composizione degli ambienti, ad esempio se questi sono discreti, statici, episodici, ed altro.
I giochi più comuni, sono quelli che vengono definiti a somma zero e con informazione perfetta.
Questi sono i giochi in cui due giocatori, a turno, effettuano azioni che influenzano l’ambiente così come il comportamento dell’altro giocatore. Nella nostra terminologia, parliamo di ambienti multi-agente, deterministici ecompletamente osservabili, in cui due agenti agiscono alternandosi e in cui i valori di utilità, alla fine della partita, sono sempre uguali ma di segno opposto. Se un giocatore vince, l’altro deve necessariamente perdere.
Questa opposizione ci fa parlare di “avversari”. I giochi hanno da sempre catturato l’interesse degli studiosi, anche e soprattutto perché, a differenza dei problemi giocattolo che abbiamo visto (ad esempio, le N-regine) sono facilmente rappresentabili ma estremamente difficili da risolvere.

Parliamo di strategia ottima.
Una strategia ottima porta ad un risultato che è almeno pari a quello di qualsiasi altra strategia, assumendo che si stia giocando contro un giocatore infallibile. L’assunzione porta che la soluzione ottima che vale per un giocatore infallibile, sarà ancora ottima contro un giocatore che può fallire.

Descrivere il concetto di Equilibrio di Nash e contestualizzarlo nel contesto del Dilemma del Prigioniero.

Il concetto di "Equilibrio di Nash" è un concetto chiave nella teoria dei giochi e rappresenta una situazione in cui i partecipanti in un gioco prendono decisioni razionali, tenendo conto delle scelte degli altri giocatori, e non hanno incentivi a deviare dalla loro strategia corrente. In altre parole, è una situazione in cui nessun giocatore può ottenere un vantaggio migliorando la propria strategia senza che gli altri reagiscano adeguatamente.

Secondo la teoria di Adam Smith, ogni azione individuale accresce la ricchezza complessiva del gruppo. Ma questo viene confutata dalla teoria dei giochi, perchè se ogni componente del gruppo fa ciò che è meglio per sé, il risultato cui si giunge è, in generale, un equilibrio di Nash che però non rappresenta la soluzione migliore per la ‘società’ e può inoltre rappresentare un'allocazione inefficiente delle risorse.

Ottimo Paretiano. Wilfredo Pareto (1848-1923) fu un famoso economista, noto per alcuni fondamentali concetti come quello di ottimo paretiano (vedi algoritmi genetici). Si ha un ottimo paretiano quando si è raggiunta una situazione in cui non è possibile migliorare la condizione di una persona senza peggiorare la condizione di un’altra. L’ottimo paretiano si raggiunge se si collabora, a differenza che nell’equilibrio di Nash, anche se nessuno accetta di peggiorare neppure di poco la propria situazione.

Il "Dilemma del Prigioniero" è un classico esempio in cui il concetto di Equilibrio di Nash può essere applicato. Il Dilemma del Prigioniero è un gioco in cui due prigionieri, detenuti separatamente, devono decidere se cooperare o tradire l'altro. Le possibili scelte sono:

1. Cooperare: Entrambi i prigionieri rimangono in silenzio (cooperano tra loro).

2. Tradire: Un prigioniero tradisce l'altro (collabora con la polizia).

3. Tradire entrambi: Entrambi i prigionieri tradiscono l'altro.

Le condanne dei prigionieri dipendono dalle scelte reciproche:

- Se entrambi cooperano, ricevono una condanna minore.

- Se entrambi tradiscono, ricevono una condanna maggiore.

- Se uno tradisce e l'altro coopera, il traditore riceve la sentenza più leggera, mentre il cooperante riceve la sentenza più pesante.

Il Dilemma del Prigioniero ha una soluzione che rappresenta un Equilibrio di Nash. In questo caso, l'Equilibrio di Nash è raggiunto quando entrambi i prigionieri tradiscono. Anche se entrambi ricevono condanne più lunghe rispetto alla cooperazione reciproca, nessuno dei due ha incentivi a cambiare la propria strategia in modo unilaterale. Se uno dei prigionieri decidesse di cooperare mentre l'altro tradisce, il traditore otterrebbe la condanna più leggera, creando un disincentivo per il cooperante a rimanere in silenzio. Di conseguenza, entrambi tradiscono, anche se la soluzione ottimale dal punto di vista collettivo sarebbe quella di cooperare.

Il Dilemma del Prigioniero è un esempio di situazione in cui gli individui possono finire in un Equilibrio di Nash che non è socialmente ottimale. In questo caso, il risultato dell'Equilibrio di Nash è subottimale poiché entrambi i prigionieri finiscono con condanne più lunghe rispetto a quelle che otterrebbero se cooperassero. Tuttavia, l'auto-interesse individuale porta a questa soluzione, dimostrando un aspetto importante della teoria dei giochi e dell'equilibrio di Nash: il fatto che le decisioni razionali degli individui possono portare a risultati non sempre ottimali a livello collettivo.

Descrivere il concetto di Equilibrio di Nash e contestualizzarlo nel contesto del Dilemma del Prigioniero. 2

Dilemma del Prigioniero. Due criminali vengono accusati di aver commesso di porto abusivo di armi e, per questo, gli investigatori li arrestano e li chiudono in due celle diverse, impedendo loro di comunicare. Ad ognuno di loro vengono date due scelte: collaborare, oppure non collaborare.
Gli investigatori spiegano ad entrambi le varie opportunità: Se solo uno dei due collabora accusando l'altro, chi ha collaborato evita la pena; l'altro viene però condannato a 7 anni di carcere; Se entrambi accusano l'altro, vengono entrambi condannati a 6 anni. Se nessuno dei due collabora, entrambi vengono condannati a 1 anno, perché comunque già colpevoli di porto abusivo di armi.

Visto che l’obiettivo e’ minimizzare la propria condanna, conviene collaborare, e questo vale anche per il semplice motivo che loro stanno in due celle diverse e non possono sapere cosa sceglierà l’altro. Questo equilibrio viene detto Equilibrio di Nash. (esempio di beautiful mind sulle slide)

Secondo la teoria di Adam Smith, ogni azione individuale accresce la ricchezza complessiva del gruppo. Ma questo viene confutata dalla teoria dei giochi, perchè se ogni componente del gruppo fa ciò che è meglio per sé, il risultato cui si giunge è, in generale, un equilibrio di Nash che però non rappresenta la soluzione migliore per la ‘società’ e può inoltre rappresentare un'allocazione inefficiente delle risorse.

Ottimo Paretiano. Wilfredo Pareto (1848-1923) fu un famoso economista, noto per alcuni fondamentali concetti come quello di ottimo paretiano (vedi algoritmi genetici). Si ha un ottimo paretiano quando si è raggiunta una situazione in cui non è possibile migliorare la condizione di una persona senza peggiorare la condizione di un’altra. L’ottimo paretiano si raggiunge se si collabora, a differenza che nell’equilibrio di Nash, anche se nessuno accetta di peggiorare neppure di poco la propria situazione.

Nell’esempio precedente, ogni soluzione è un ottimo paretiano, in quanto ogni cambio di decisione influisce in modo negativo sugli altri. Quindi le strategie egoistiche non portano MAI ad una soluzione ottimale per la società né se non ci si cura di quanto succede agli altri (come nell’equilibrio di Nash) ma neppure se si è disposti a collaborare a patto di non avere svantaggi (come nella ricerca dell’ottimo di Pareto). E’ possibile che per ottenere la situazione migliore si debba imporre a qualcuno di rinunciare a qualche cosa

Dinamiche Dominanti. Parliamo di dinamiche dominanti quando un giocatore fa il meglio che può indipendentemente da ciò che farà l’altro.

Analizzare le prestazioni dell’algoritmo Minimax in termini di completezza, ottimalita', complessita' spaziale e temporale.

L'algoritmo Minimax è una tecnica utilizzata nella teoria dei giochi e nell'intelligenza artificiale per la decisione in ambienti competitivi a somma zero, come il gioco degli scacchi, il tris o il poker. L'algoritmo cerca di determinare la mossa migliore per un giocatore (massimizzando) considerando le contromosse dell'avversario (minimizzando).

Valore Minimax. Il valore minimax di un nodo corrisponde all’utilità di trovarsi nello stato corrispondente, assumendo che entrambi gli agenti giochino in modo ottimo da lì alla fine della partita. Il valore minimax di uno stato terminale si riduce alla sua utilità. Inoltre, avendone la possibilità, MAX preferirà muoversi in uno stato di valore minimax massimo, MIN in uno di valore minimax minimo.

Tirando le somme, la ricerca minimax non è altro che una ricerca in profondità e, pertanto, eredita molti degli aspetti già visti nelle precedenti lezioni.
Completezza: L’algoritmo è completo se l’albero è finito - molti giochi, inclusi gli scacchi, hanno regole specifiche per garantire il termine del gioco.
Ottimalità: L’algoritmo è ottimo nel caso in cui l’avversario è ottimo, questa strategia ottima per MAX presume che anche MIN giochi in modo ottimo: in altri termini, la strategia massimizza il risultato di MAX nel caso pessimo. Se MIN non gioca ottimamente, allora MAX farà sicuramente meglio, massimizzando ancora di più i suoi valori minimax.
Complessità temporale: La complessità è governata dalla dimensione dell’albero di gioco. Sia m la profondità massima, nel caso pessimo la ricerca genererà O(b^m) nodi.
Complessità spaziale: La ricerca deve memorizzare un solo cammino dalla radice ad un nodo foglia, insieme ai rimanenti nodi fratelli non espansi per ciascun nodo sul cammino. Una volta che un nodo è stato espanso, può essere rimosso dalla memoria non appena tutti i suoi discendenti sono stati esplorati completamente.
Per un albero di gioco con fattore di ramificazione b e profondità m, la complessità sarà di O(bm).

Per i giochi reali, questa complessità temporale è improponibile!

Descrivere il funzionamento dell’algoritmo Minimax con potatura alfa-beta.

Abbiamo visto che il problema principale è la complessità temporale, e non applicabile nella realtà. Quindi dobbiamo migliore l’usabilità e l’efficienza. Sfortunatamente, non possiamo eliminare l’esponente, ma possiamo almeno dimezzarlo: è di fatti possibile calcolare la decisione minimax corretta senza guardare tutti i nodi dell’albero di gioco. Dato che ogni nodo è etichettato con il valore minimax, e dato che abbiamo un obiettivo, possiamo limitare l’esplorazione dei nodi tramite la potatura. La specifica tecnica che esamineremo è chiamata potatura alfa-beta, che applicata ad un albero minimax restituisce lo stesso risultato della tecnica minimax standard, ma “pota” i rami che non possono influenzare la decisione finale.
Questo ci consente di tagliare interi sotto-alberi e sicuramente non vanno ad intaccare le scelte di minimax. Questa semplice modifica migliora di tantissimo le prestazioni.
Il principio generale è questo: consideriamo un nodo n da qualche parte dell’albero tale che il giocatore abbia la possibilità di spostarsi in quel nodo. Se esiste una scelta migliore m a livello del nodo padre o di qualunque nodo precedente, allora n non sarà mai raggiunto in tutta la partita. Di conseguenza, possiamo potare n non appena abbiamo raccolto abbastanza informazioni per poter giungere a questa conclusione.

Alfa. Il valore della scelta migliore (quella con il valore più alto) per MAX che abbiamo trovato sin qui in un qualsiasi punto di scelta lungo il cammino.
Beta. Il valore della scelta migliore (quella con il valore più basso) per MIN che abbiamo trovato sin qui in un qualsiasi punto di scelta lungo il cammino.

La procedura di base è la stessa dell’algoritmo standard.
Aggiungiamo però il codice necessario ad aggiornare alfa e beta e il codice necessario per passare alfa e beta da una procedura ad un’altra. Lo stesso vale per la funzione VALORE-MIN.
Vale la pena notare che l’algoritmo, nel caso di MAX, stoppa l’esecuzione quando il valore dello stato corrente è superiore o uguale all’attuale beta —> abbiamo trovato uno stato migliore e pertanto non è conveniente proseguire l’esplorazione.

L’efficacia della potatura alfa-beta dipende strettamente dall’ordinamento in cui gli stati sono esaminati. Nel caso peggiore, non farà peggio dell’algoritmo standard.

Continuo del discorso nella domanda successiva -->

Descrivere i principali metodi di ordinamento delle mosse, spiegando inoltre il vantaggio che questi portano alle prestazioni della potatura alfa-beta.

Quindi potrebbe essere una buona idea quella di esaminare per prima i successori più promettenti — ovvero, usando una strategia best-first.
Se questo può essere fatto la ricerca alfa-beta dovrà esaminare “solo” nodi - piuttosto che . La scelta del nodo più promettente dipenda dalla euristica che andremo ad applicare.
Una modifica di questo tipo consente alla ricerca alfa-beta di risolvere un albero profondo il doppio di quello che può risolvere minimax nello stesso lasso di tempo.

Talvolta, decidere un ordinamento è “semplice”. Negli scacchi, questa potrebbe essere una funziona tale che la ricerca abbia come obiettivo quello di catturare pezzi, poi di minacciarli, poi le mosse in avanti ed infine quelle all’indietro.

A seconda dell’euristica, potremmo adottare un ordinamento dinamico proprio in base al valore di quest’ultima calcolato in determinato di tempo per condizionare la ricerca. Ad esempio, possiamo provare per prima cosa le mosse che si sono rivelate le migliori in passato, che ci porta vicino al limite teorico.

Un modo per ottenere informazioni dalla mossa corrente è quello di utilizzare una ricerca ad approfondimento iterativo.
Ricerca ad approfondimento iterativo: Con questa strategia, il limite viene incrementato progressivamente, finché un nodo obiettivo non è identificato. Con questa strategia, si cerca innanzitutto uno strato in profondità e si registra il miglior cammino di mosse. Poi si cerca uno strato ancora in profondità, ma si utilizza il cammino registrato allo scopo di fornire informazioni per l’ordinamento delle mosse. Le mosse migliori sono spesso chiamate mosse killer e si parla di euristica della mossa killer quando queste vengono provate per prime. Adesso, però, la domanda vera è: come utilizzare la ricerca ad approfondimento iterativo per l’ordinamento delle mosse? Ricordate che la ricerca ad approfondimento iterativo è analoga a quella in ampiezza, poiché ad ogni iterazione esplora completamente un livello di nodi prima di prendere in considerazione il successivo. Quindi, possiamo esplorare i nodi in ampiezza e decidere come variare l’ordinamento in base ai valori minimax!

Un altro modo è quello di considerare le trasposizioni, che portano l’albero di gioco a contenere cammini ridondanti (stati ripetuti più volte nello spazio degli stati che possono determinare un aumento esponenziale del costo di ricerca).
La trasposizione mira a catturare l’equivalenza degli stati. Quindi, vale la pena memorizzare la valutazione di una configurazione in una tabella hash la prima volta che questa viene incontrata. La tabella viene chiamata tabella delle trasposizioni: in essenza, questa è identica alla lista esplorati che abbiamo visto con gli algoritmi di ricerca non informata. Proprio perché identica alla lista esplorati , possiamo decidere di ordinare le mosse successive sulla base della conoscenza già acquisita esplorando una trasposizione. Dall’altra parte, se l’albero di gioco avesse milioni di stati, si arriverà necessariamente a dover mantenere in tabella solo alcune delle trasposizioni. Diverse strategie sono disponibili per selezionare le trasposizioni da mantenere in memoria. Una strategia potrebbe essere derivata tramite la definizione di una funzione euristica.

Descrivere la variazione, in termini di formulazione del problema e cambiamenti implementativi, richiesta per poter consentire all’algoritmo Minimax di prendere decisioni imperfette in tempo reale.

Ricollegandoci alla domanda precedente, tutto bello ma abbiamo comunque un problema. Entrambe le versioni richiedono che dobbiamo arrivare in fondo all’albero e poi fare una ricerca bottom up, e visto che i giochi sono complessi, quindi con tanti livelli, minimax potrebbe mai concludere. Quindi se la profondità è ingestibile, dobbiamo trovare una soluzione che sia ragionevole in termini temporali, e non abbiamo nessun altro modo che affidarci a funzioni euristiche.
Claude Shannon (lo stesso Shannon della formulazione di entropia) nel 1950 propose che i programmi “tagliassero” la ricerca prima di raggiungere le foglie applicando una funzione di valutazione euristica agli stati, in altri termini dato uno stato la funzione euristica ci dice la probabilità vittoria se proseguiamo. In questa formulazione del problema, i nodi non terminali diventano foglie, perchè se nel minimax andiamo a calcolare sullo stato terminale, qui andiamo a calcolare su uno stato intermedio. Il minimax viene modificato in due punti: La funzione di utilità viene sostituita da EVAL, che fornisce una stima dell’utilità della posizione raggiunta. Il test di terminazione viene sostituito con un test di taglio (cutoff test), che decide quando applicare EVAL.

La funzione euristica corrisponde al modo di giocare di un giocatore, quindi come nei giochi reali che ogni player ha un suo modo di interpretare lo stato e eseguire mosse che potrebbero portarlo alla vittoria. Questa funzione euristica deve: ordinare gli stati terminali nello stesso modo della funzione di utilità. Gli stati che sono vittorie devono avere una valutazione migliore dei pareggi, che a loro volta devono essere migliori delle sconfitte. essere veloce da calcolare (altrimenti, non avrebbe senso sostituire la funzione di utilità!) avere una forte correlazione con la probabilità reale di vincere la partita La maggior parte delle funzioni di valutazione si basano sulle caratteristiche di uno stato: ad esempio, negli scacchi avremo come caratteristiche il numero di pedoni bianchi, il numero di pedoni neri, di regine bianche, di regine nere, e così via. Ogni classe di equivalenza può contenere diversi stati che portano alla vittoria, al pareggio e alla sconfitta. La funzione di valutazione non potrà sapere quali sono, ma potrà restituire un singolo valore che riflette la proporzione di stati che portano ad ogni risultato.

Adesso parliamo dei giochi stocastici. Nella vita reale si verificano molti eventi esterni che ci mettono in situazioni impreviste. Molti giochi modellano questa imprevedibilità includendo elementi casuali, come ad esempio l’uso di un dado. Si parla dei giochi stocastici. Nel gioco del backgammon un giocatore deve lanciare due volte un dado per decidere quali mosse sono lecite. In questo caso, chiaramente, l’algoritmo minimax o la ricerca alfa-beta non sarebbero utilizzabili nella loro forma base. Possiamo però complementare gli algoritmi visti finora in maniera da introdurre dei nodi possibilità accanto a quelli di scelta. Così facendo, nel calcolare i valori di MIN e MAX dovremo tener conto delle probabilità dell’esperimento casuale. In altri termini, non andremo più a calcolare i valori di massimo e minimo, ma i valori di massimo e minimo attesi. Da un punto di vista pratico, i nodi assumeranno un valore corrispondente alla somma del valore su tutti i risultati pesati in base alla probabilità di ciascuna azione.
In questa categoria di giochi, l’incertezza sullo stato di gioco nasce interamente all’impossibilità di accedere alle scelte fatte dall’avversario. Ad esempio, i giochi di carte in cui le carte iniziali dell’avversario non sono note. Intuitivamente, potremmo pensare a questi giochi come un caso particolare dei giochi stocastici: potremmo avere un dado con tantissime facce all’inizio della partita ed esprimere i nodi possibilità per ogni possibile azione dell’avversario.
Sebbene l’analogia non è corretta, può servire per definire un algoritmo efficace. Consideriamo tutte le possibili distribuzioni di carte nascoste e risolviamo una per una come se fossero un gioco completamente osservabile. A quel punto, basterà scegliere la mossa che ha il miglior risultato calcolato in media su tutte le distribuzioni. Purtroppo però, in molti casi, il numero di possibili distribuzioni è troppo grande. Una soluzione consiste nell’applicazione di un’approssimazione Monte Carlo: invece di sommare tutte le distribuzioni, prendiamo un campione casuale di N distribuzioni in cui la probabilità di s di apparire nel campione è proporzionale alla probabilità P(s).

La Rossi IT Solutions, un’azienda informatica specializzata nella programmazione di sistemi software, puo' investire 50.000 euro per co-finanziare un progetto di ricerca dell’Universita' degli Studi di Salerno. Il potenziale ritorno d’immagine aziendale e' di 75.000 euro. L’azienda dovrebbe pero' riconoscere all’Universita' le sue competenze tramite un premio di 10.000 euro. Tuttavia, l’Universita' potrebbe tirarsi fuori dall’accordo di collaborazione, preferendo un coinvolgimento in un progetto che porterebbe un riconoscimento di entita' maggiore (90.000 euro) con una azienda competitor della Rossi IT Solutions. A quel punto, l’investimento fatto dall’azienda verso l’Universita' degli Studi di Salerno sarebbe perduto—in un caso reale, non tutto l’investimento sarebbe perduto, ma consideriamo il caso piu' semplice in cui venga perso completamente. C’e' sempre la possibilita' che la Rossi IT Solutions non proceda con l’investimento. L’Universita' potrebbe tuttavia essere comunque coinvolta nel progetto di ricerca del valore di 90.000 euro, nonostante abbia difficolta' a dimostrare le sue competenze. Se un competitor dovesse coinvolgere l’Universita', allora la Rossi IT Solutions avrebbe una perdita d’immagine quantificabile in 5.000 euro.
Definire il problema in termini di gioco tramite forma tabellare, usando la notazione del Dilemma del Prigioniero. Identificare quindi l’Equilibrio di Nash e gli eventuali Ottimi Paretiani. Descrivere, infine, le scelte piu' convenienti da fare da parte della Rossi IT Solutions.