Algoritmi genetici
Possono essere usati per cercare il valore massimo di una data funzione, o quando non è nota la funzione da analizzare.
Gli algoritmi genetici si ispirano ai sistemi naturali, che sono in grado di apprendere e di evolversi. Il nome genetico è dato dal fatto che questi algoritmi implementano meccanismi concettualmente simili a quelli dei processi biochimici scoperti dalla genetica.
Le specie apprendono implicitamente alcune caratteristiche del proprio ambiente, ma i cambiamenti che vengono acquisiti durante la vita non sono ereditabili. Le specie si evolvono perché ci sono differenze casuali negli individui e l’ambiente favorisce i portatori di caratteri vantaggiosi.
Due specie che occupano lo stesso territorio, competono per le stesse risorse e per questo una delle due prima o poi sparirà o si evolverà.
Se tutti i discendenti si riproducessero, le risorse finite finirebbero in breve tempo.
I geni vengono trasmessi in maniera discreta. Il DNA è costituito da una sequenza di nucleotidi, che a loro volta contengono una base azotata (A, C, G, T), e contiene le informazioni per sintetizzare l’RNA e le proteine, che svolgono un ruolo strutturale e controllano le attività chimiche nella cellula.
Meccanismi casuali determinano le mutazioni, e prevale l’ipotesi di cambiamenti graduali.
Evoluzione ed apprendimento sono molto simili:
- evoluzione: una specie apprende le caratteristiche dell’ambiente in modo implicito.
- apprendimento: processo di generazione di diversi comportamenti alternativi e di selezione di quelli più adatti.
fitness
Ogni individuo ha un certo numero di discendenti fertili, detto fitness. Un vantaggio in termini di fitness tra due popolazioni nello stesso ambiente causa la colonizzazione. 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.
Un insieme di soluzioni è detto popolazione. Una sequenza di 0 e 1 è detta cromosoma. Ogni cromosoma codifica un particolare insieme di valori, e ad ogni insieme di valori è associata la fitness.
È necessario codificare soluzioni come individui, e utilizzare come fitness di un individuo una misura di qualità della soluzione che esso rappresenta. Per imitare la selezione naturale si esegue:
- valutare gli individui della popolazione
- selezionare i più adatti
- ricombinarli
- mutarli
- generare la nuova popolazione
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 due genitori. Questo crossover permette di esplorare aree anche molto distanti dallo spazio di ricerca di partenza, ma è limitato.
È proprio per le limitazioni del crossover che esiste la mutazione puntuale, 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
Uno schema è un insieme di individui che hanno una parte in comune, ed è definito da una stringa di lunghezza L di elementi appartenenti all’alfabeto {1, 0, #} (esempio: {#111##10, 1101#1#0}), dove # è indifferente.
Il crossover può eliminare uno schema buono, ed è per questo che si preferiscono schemi corti con fitness elevata. Senza crossover, gli individui si replicherebbero senza mutazioni, e si arriverebbe ad avere una popolazione di individui tutti uguali, detta convergenza prematura.
Rallentare la convergenza:
- scegliere i genitori in proporzione alla fitness. Può però far scomparire gli individui più performanti e convergere prematuramente se un individuo è di molto superiore alla media.
- elitismo: si garantisce la sopravvivenza di individui con fitness più alta.
- torneo: si scelgono n individui (uno può essere scelto più volte) con fitness alta. Tra questi n individui si prende quello con la fitness più alta, e si itera fino a generare n nuovi individui.
Crossover ad un punto si considerano due soluzioni adatte. Si tagliano in un punto casuale, così da avere due teste e due code, e si ricombinano scambiandole.