Ricerca Ambienti Complessi Flashcards
Ricerca Locale
Gli algoritmi di ricerca locale operano cercando a partire da uno stato iniziale e procedendo verso gli stati adiacenti senza tenere traccia dei cammini, né degli stati già raggiunti.
Hanno due vantaggi:
1. usano pochissima memoria
2. spesso riescono a trovare soluzioni ragionevoli in spazi degli stati grandi o anche infiniti per cui usare algoritmi sistematici non sarebbe praticabile.
Ricerca hill climbing
L’algoritmo di ricerca hill climbing tiene traccia di un solo stato corrente e a ogni iterazione passa allo stato vicino con valore più alto, cioè punta nella direzione che presenta l’ascesa più ripida, senza guardare oltre gli stati immediatamente vicini a quello corrente
l’hill climbing rimane bloccato per le seguenti ragioni:
* massimi locali: picco più alto degli stati vicini, ma inferiore al massimo globale. Rimarranno bloccati lì senza poter andare altrove.
*creste: una sequenza di massimi locali
*plateau: area piatta del panorama dello spazio degli stati. Può essere un massimo locale piatto, da cui non è possibile fare ulteriori progressi, oppure una spalla, da cui si potrà salire ulteriormente.
Simulated annealing
Algoritmo che sceglie gli stati iniziali in maniera casuale e mano mano trova una stabilità in base alla conoscenza dell’ambiente
Algoritmi evolutivi
Caratteristiche in un algoritmo evolutivo:
*La dimensione della popolazione.
*La rappresentazione di ciascun individuo.
*Il numero di genitori, ρ, che si riuniscono a generare la prole.
*Il processo di selezione per selezionare gli individui che diventeranno i genitori della generazione successiva (scelti casualmente o tramite un valore di adeguatezza detto fitness)
*La procedura di ricombinazione: selezionare a caso un punto di crossover (incrocio) per suddividere ognuna delle stringhe genitori e poi ricombinare le parti per formare due figli
*Il tasso di mutazione, che determina la frequenza con cui la prole presenta mutazioni casuali della loro rappresentazione.
*La formazione della nuova generazione.
Cosa succede in un ambiente parizialmente osservabile e non deterministico
In ambienti parzialmente osservabili e non deterministici, la soluzione di un problema non è una sequenza ma un piano condizionale che specifica che cosa fare in base alle percezioni ricevute dall’agente durante l’esecuzione del piano
Chiamiamo stato-credenza un insieme di stati fisici che l’agente ritiene siano possibili
Alberi di ricerca AND-OR
Sono composti da
Nodi OR: eseguo una opzione [ è l’agente che sceglie]
Nodi AND: possono accadere i seguenti scenari [risultati che dipendono dall’ambiente]
Una soluzione per un problema di ricerca AND–Or è un sottoalbero dell’albero di ricerca completo che ha un nodo obiettivo in ogni foglia, specifica una sola azione in ognuno
dei suoi nodi Or e include ogni ramo uscente da ognuno dei suoi nodi AND.
Cosa succede in assenza di osservazioni
Quando le osservazioni dell’agente non forniscono alcuna informazione, abbiamo un problema senza sensori.
La soluzione di un problema senza sensori è una sequenza di azioni, non un piano condizionale (perché non vi è percezione), ma la ricerca viene effettuata nello spazio degli stati credenza e non degli stati fisici.
