Crea sito

Algoritmi Genetici

Si tratta di una famiglia di algoritmi pensati per risolvere i problemi di ottimizzazione. Sono particolarmente efficaci nel trovare rapidamente una possibile soluzione in spazi di ricerca particolarmente ampi non esplorabili attraverso al ricerca a forza bruta (leggi backtracking).

Iniziamo con un esempio banale: proviamo ad applicare un algoritmo genetico al gioco del master mind.

Regole: si tratta di indovinare una combinazione di quattro chiodi di sei possibili colori diversi in massimo dieci tentativi.

Gli algoritmi genetici prevedono i seguenti elementi:

  • cromosoma: possibile soluzione del problema
  • geni: in un cromosoma rappresentano lo stato del problema
  • popolazione: insieme di possibili soluzioni del problema (cromosomi)

Operatori genetici

  • mutazione: modifica di un gene del cromosoma
  • crossover: incrocia due cromosomi (padre e madre) e restituiscono un nuovo cromosoma (figlio)

Funzione di valutazione (fitness): verifica la corrispondenza dell’ipotesi alla soluzione del problema.