DAA - Hill Climbing Algorithm

Gli algoritmi discussi nei capitoli precedenti vengono eseguiti in modo sistematico. Per raggiungere l'obiettivo, è necessario memorizzare uno o più percorsi esplorati in precedenza verso la soluzione per trovare la soluzione ottimale.

Per molti problemi, il percorso verso l'obiettivo è irrilevante. Ad esempio, nel problema N-Queens, non dobbiamo preoccuparci della configurazione finale delle regine e dell'ordine in cui le regine vengono aggiunte.

Arrampicata in collina

Hill Climbing è una tecnica per risolvere alcuni problemi di ottimizzazione. In questa tecnica, iniziamo con una soluzione subottimale e la soluzione viene migliorata ripetutamente fino a quando alcune condizioni non vengono massimizzate.

L'idea di partire con una soluzione subottimale è paragonata a partire dalla base della collina, migliorare la soluzione è paragonata a camminare su per la collina, e infine massimizzare alcune condizioni è paragonata al raggiungimento della cima della collina.

Quindi, la tecnica dell'arrampicata in collina può essere considerata come le seguenti fasi:

  • Costruire una soluzione subottimale obbedendo ai vincoli del problema
  • Migliorare la soluzione passo dopo passo
  • Migliorare la soluzione fino a quando non sono più possibili miglioramenti

La tecnica Hill Climbing viene utilizzata principalmente per risolvere problemi computazionalmente complessi. Guarda solo lo stato attuale e lo stato futuro immediato. Quindi, questa tecnica è efficiente in termini di memoria in quanto non mantiene un albero di ricerca.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Miglioramento iterativo

Nel metodo di miglioramento iterativo, la soluzione ottimale si ottiene facendo progressi verso una soluzione ottimale in ogni iterazione. Tuttavia, questa tecnica può incontrare i massimi locali. In questa situazione, non esiste uno stato vicino per una soluzione migliore.

Questo problema può essere evitato con metodi diversi. Uno di questi metodi è la ricottura simulata.

Riavvio casuale

Questo è un altro metodo per risolvere il problema dell'ottimo locale. Questa tecnica conduce una serie di ricerche. Ogni volta parte da uno stato iniziale generato casualmente. Quindi, la soluzione ottimale o quasi ottimale può essere ottenuta confrontando le soluzioni delle ricerche eseguite.

Problemi di tecnica di arrampicata in collina

Maxima locale

Se l'euristica non è convessa, Hill Climbing può convergere ai massimi locali, invece che ai massimi globali.

Creste e vicoli

Se la funzione target crea una cresta stretta, lo scalatore può solo salire la cresta o scendere il vicolo a zig-zag. In questo scenario, lo scalatore deve compiere passi molto piccoli che richiedono più tempo per raggiungere l'obiettivo.

Altopiano

Si verifica un plateau quando lo spazio di ricerca è piatto o sufficientemente piatto che il valore restituito dalla funzione di destinazione è indistinguibile dal valore restituito per le regioni vicine, a causa della precisione utilizzata dalla macchina per rappresentarne il valore.

Complessità della tecnica di arrampicata in collina

Questa tecnica non soffre di problemi legati allo spazio, poiché guarda solo allo stato attuale. I percorsi esplorati in precedenza non vengono memorizzati.

Per la maggior parte dei problemi nella tecnica dell'arrampicata in collina con riavvio casuale, è possibile ottenere una soluzione ottimale in tempo polinomiale. Tuttavia, per i problemi NP-Complete, il tempo di calcolo può essere esponenziale in base al numero di massimi locali.

Applicazioni della tecnica di arrampicata in collina

La tecnica Hill Climbing può essere utilizzata per risolvere molti problemi, dove lo stato corrente consente una funzione di valutazione accurata, come il flusso di rete, il problema del venditore in viaggio, il problema delle 8 regine, la progettazione del circuito integrato, ecc.

L'arrampicata in collina viene utilizzata anche nei metodi di apprendimento induttivo. Questa tecnica viene utilizzata nella robotica per il coordinamento tra più robot in una squadra. Ci sono molti altri problemi in cui viene utilizzata questa tecnica.

Esempio

Questa tecnica può essere applicata per risolvere il problema del venditore ambulante. Per prima cosa viene determinata una prima soluzione che visita tutte le città esattamente una volta. Quindi, questa soluzione iniziale non è ottimale nella maggior parte dei casi. Anche questa soluzione può essere molto scarsa. L'algoritmo Hill Climbing inizia con una tale soluzione iniziale e apporta miglioramenti ad essa in modo iterativo. Alla fine, è probabile che si ottenga un percorso molto più breve.