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.