Questo tipo di algoritmi, quindi, consente di valutare diverse soluzioni di partenza come se fossero diversi individui di una popolazione, ricombinandole ed introducendo mutazioni casuali, e producendo quindi nuove soluzioni. Una soluzione prende il nome di cromosoma. Un insieme di soluzioni, o cromosomi, è detto popolazione.
La fitness di una soluzione (o cromosoma) è definita come il numero di discendenti fertili, che in senso più ampio è la valutazione di quella specifica soluzione. La fitness media cresce al crescere del numero di iterazioni e tende a raggiungere quella dell’individuo migliore. Quando si avvicina sufficientemente, l’algoritmo può essere arrestato.
Quando si mescolano le soluzioni esistenti, si crea una nuova soluzione detta crossover. Questa soluzione può essere di gran lunga migliore delle due di partenza, ma non può generare tratti non presenti in nessuno dei dui genitori. Questo crossover permette di esplorare aree anche molto distanti dallo spazio di ricerca.
Similmente al crossover, esiste la mutazione, che altera alcuni tratti di un individuo. Si può applicare in due diversi modi:
- la soluzione crossover viene mutata in una posizione casuale
- un genitore viene mutato e poi si genera il figlio
La scelta dei genitori in base alla fitness è quella più vicina alla realtà, ma ha lo svantaggio di poter far sparire individui molto performanti, e si potrebbe avere una convergenza prematura se un individuo è molto superiore alla media. Per migliorare l’algoritmo, si può ad esempio implementare un meccanismo di scelta dei genitori, come ad esempio l’elitismo, che garantisce la sopravvivenza degli individui con fitness più alta. Questo approccio copia gli individui peggiori della generazione precedente senza applicare mutazioni o crossover, permettendo di evitare la perdita di individui con alto fitness per colpa della casualità. Un altro approccio può essere lo scaling, dove la probabilità di essere selezionato non è proporzionata alla fitness, ma piuttosto ad una funzione correlata.
Gli algoritmi genetici sono quindi un tipo di algoritmo euristico usato per problemi di ottimizzazione generali.
Uno degli svantaggi degli algoritmi genetici è la non possibilità di sapere se si convergerà ad una soluzione ottima o se si verificherà una convergenza ad una soluzione non ottimale. Anche se converge ad una soluzione ottima non è detto si riesca a capire il perché abbia funzionato.
Questi algoritmi si ispirano quindi al principio della selezione naturale di Darwin, che applica alla biologia la teoria economica di Malthus: Due specie che occupano lo stesso luogo competono per le stesse risorse, e gli abitanti totali sono , dove e , dove a sopravvivere è quella che riesce a crescere più velocemente.
In un modello evolutivo esistono una popolazione composta da individui, un sistema di valutazione della fitness di ogni individuo, un meccanismo per generare nuovi individui a partire da quelli con fitness più elevata e un meccanismo che introduce novità.