Da algoritmi classici ad algoritmi genetici
Ogni sviluppatore normalmente è abituato a risolvere problemi.
Le tecniche tradizionali di implementazione vanno bene per:
- elaborare di moli di dati;
- gestire casi ben definiti: si analizza il problema, lo si identifica e si adotta una soluzione nota;
- ripetere deterministicamente delle operazioni.
Ma come ci comportiamo quando si devono riconoscere dei pattern (comportamentali ad esempio) o dobbiamo lavorare con informazioni incomplete? Oppure quando si ha la necessità di sviluppare soluzioni che devono evolvere nel tempo?
Prendiamo spunto dalla natura
Gli organismi si sono nella storia evoluti, sopravvive chi meglio si adatta. Il sociologo inglese Herbert Spencer coniò l’espressione
Survival of the fittest
ovvero Sopravvivenza del più idoneo, che venne usata per descrivere il modello di selezione naturale descritto da Darwin.
Tornando all’espressione di Spencer, fit significa idoneo e fittest il più idoneo. Da fit si deriva la parola fitness che in ambito genetico definisce il successo riproduttivo di un individuo o di un certo genotipo. Con il termine genotipo ci si riferisce all’insieme di tutti i geni che compongono il DNA di un organismo o di una popolazione.
Quando due o più assortimenti di caratteri ereditari conferiscono ai rispettivi organismi un diverso successo riproduttivo, allora si dice che presentano una fitness diversa.
La fitness si misura per mezzo del successo riproduttivo, ovvero dal numero medio dei figli in grado, a loro volta, di riprodursi.
Algoritmi genetici
Nel 1975 Holland propose per la prima volta gli algoritmi genetici che implementano tecniche di ricerca e ottimizzazione basate sul principio di selezione naturale.
Sono algoritmi particolarmente adatti a trovare nuove soluzioni per problemi difficili dove non si ha conoscenza completa dello spazio di ricerca. Partendo da una soluzione iniziale, la si modifica, combina con altre soluzioni per cercare di evolverla e quindi trovare un risultato migliore per il problema.
I dati vengono rappresentati mediante una codifica biologica, quindi si parla di geni -> cromosomi -> genotipo -> fenotipo e fitness. Per fenotipo si intende l’insieme di caratteristiche osservabili di un organismo o popolazione.
Differenze tra algoritmi genetici e algoritmi classici
Rispetto agli algoritmi classici, gli algoritmi genetici:
- lavorano con una codifica dei dati, non con i dati stessi;
- si basano su una popolazione di soluzioni tra le quali effettuare una ricerca, e non su un’ unica soluzione;
- trasportano informazioni nel tempo quando vengono applicati degli operatori; nuove informazioni possono essere generate oppure perse;
- utilizzano regole probabilistiche, non deterministiche.
Nel paragrafo successivo vengono introdotti gli elementi base di un algoritmo genetico e le fasi che lo compongono.