Principio di funzionamento di un algoritmo genetico

Insieme all’apprendimento automatico, anche la genetica sta avendo un forte sviluppo negli ultimi anni.

Alcuni risultati in questo campo si possono valutare grazie agli Evolutionary Algorithms (EA), ossia algoritmi sull’evoluzione che si sono sviluppati il secolo scorso, ma che stanno avendo un maggiore utilizzo grazie all’elevato miglioramento tecnologico, mai così elevato come ai giorni nostri.

Tra gli EA, di certo non si può escludere l’algoritmo genetico, principale argomento di questo articolo.

Cos’è l’algoritmo genetico?

Per algoritmo genetico si fa riferimento ad una tecnica di ottimizzazione combinatoria basata sulla ricerca, sulla selezione naturale e sui principi della genetica.

In altre parole è uno strumento di calcolo che è nato dall’ispirazione alle leggi Darwiniane sull’evoluzione naturale.

La selezione naturale rappresenta un processo che permette a una popolazione di cambiare nel corso delle generazioni, in conseguenza del fatto che gli organismi dotati di determinati caratteri vantaggiosi hanno più probabilità di sopravvivere e di riprodursi rispetto ad altri individui dotati di tratti diversi.

Gli individui con i tratti ereditati più adatti all’ambiente, ossia che si adattano più facilmente all’ambiente, hanno maggiore probabilità di sopravvivere e riprodursi rispetto agli individui meno adattati.

Altro aspetto chiave dell’algoritmo riguarda la genetica.

La genetica è considerata

la branca della biologia che studia i geni, l’ereditarietà e la variabilità genetica negli organismi viventi (fonte wikipedia).

La genetica nacque intorno al 1860, quando Gregor Mendel, monaco agostiniano, dedusse i principi fondamentali della trasmissione ereditaria studiando gli incroci tra piante di pisello.

Gli studi di Mendel furono essenziali nel determinare come i tratti passano da una generazione ad un’altra. Questi tratti sono chiamati geni (unità base dell’eredità), e sono ereditabili dalla coppia, uno da ogni genitore.

Durante la riproduzione sessuata, il materiale genetico del padre e della madre viene ricombinato in modo da produrre un unico figlio (tale meccanismo è chiamato crossing over). Questo processo permette la modifica della specie, la quale possederà i tratti che più si sono adattati all’ambiente.

Oltre al crossing over anche il processo di mutazione può avvenire: un cambiamento di una caratteristica di un gene può passare ai figli.

Applicazioni

Prima di vedere come funziona un algoritmo genetico, vediamone il campo di applicazione, che può rientrare in uno dei successivi domini:

Pianificazione: include tutti quei problemi in cui si richiede di scegliere il miglior modo alternativo di impiegare un insieme finito di risorse, come ad esempio la pianificazione di rotta di una flotta dei veicoli, la pianificazione della traiettoria di un robot, la pianificazione della produzione di un impianto industriale, ecc.
Progettazione: include quei problemi in cui si richiede di determinare una disposizione ottimale di elementi (componenti elettroniche o meccaniche, elementi architettonici) al fine di soddisfare una serie di requisiti funzionali, estetici e di robustezza.
Simulazione e identificazione: al fine di determinare come un determinato sistema si comporterà. I sistemi studiati possono essere chimici (determinazione della struttura tridimensionale di una proteina, dell’equilibrio di una reazione), economici (simulazione delle dinamiche della concorrenza in un’economia di mercato), medici e così via.
Controllo: che include tutti quei problemi in cui è richiesto di stabilire una strategia di controllo per un dato sistema;
Apprendimento automatico e data mining: nei casi in cui a partire da un insieme di osservazioni, si richiede di costruire un modello del fenomeno sottostante, spesso da utilizzare per scopi di previsione.

Principali definizioni

Vediamo le principali definizioni che ci aiutano a comprendere meglio il funzionamento di un algoritmo genetico:

Spazio di ricerca (search space): rappresenta l’insieme delle possibili soluzioni o valori che un algoritmo genetico può assumere;
Popolazione: insieme ben definito di soluzioni, che vengono chiamate cromosomi. Ogni soluzione è formata da N geni (in cui N non dovrebbe essere un numero né troppo corto, né troppo lungo, e lo si ricava facendo più prove o esperimenti).
Cromosoma: è identificato come un insieme di stringhe, numeri posizionati in modo casuale e che definiscono una soluzione al problema.
Gene: Singolo valore della stringa di un cromosoma, a cui solitamente è associata una variabile decisionale del problema. A seconda dei diversi valori effettivamente assunti dai diversi geni, si ottiene un diverso cromosoma e, quindi, una soluzione differente.
Allele: rappresenta il valore definito da un gene;
Generazione (o iterazione): si intende l’introduzione nella popolazione di nuovi individui, i figli.

Principio di funzionamento

Gli algoritmi genetici partono da una popolazione iniziale di soluzioni (gli individui dei sistemi biologici) e la fanno evolvere iterativamente. Questa popolazione è generata casualmente da un algoritmo.

Ad ogni iterazione, le soluzioni sono valutate da una funzione di fitness e sulla base di questa valutazione, vengono selezionate alcune di esse, privilegiando le soluzioni (genitori) con fitness maggiore.

Le soluzioni selezionate vengono tra loro ricombinate (riproduzione) per generare nuove soluzioni (offspring o figli) che tendono a trasmettere le buone caratteristiche delle soluzioni genitori nelle successive generazioni.

Lo schema generale di un algoritmo genetico è il seguente:

Codifica delle soluzioni dello specifico problema.
Creazione di un insieme iniziale di soluzioni (popolazione iniziale).
Calcola la funzione di fitness;
Ripeti, fino alla soddisfazione di un criterio di arresto:

a) Seleziona coppie (o gruppi) di soluzioni (selezione parentale).

b) Ricombina i genitori generando nuove soluzioni (offsprings).

c) Valuta la fitness delle nuove soluzioni.

d) Rinnova la popolazione, utilizzando nuove soluzioni.

5. Restituisci la migliore soluzione generata.

Come tutte le metaeuristiche, si tratta di uno schema generale che deve essere specificato e reso noto per i diversi problemi.

Codifica delle soluzioni

Ogni soluzione deve essere definita secondo una determinata rappresentazione, che codifica le caratteristiche di una soluzione stessa.

Tra le rappresentazioni più diffuse abbiamo:

Rappresentazione binaria: la più semplice, in cui ogni gene assume solamente valore pari a 0 o a 1. Questo metodo offre l’immediato vantaggio di un calcolo facilitato per l’elaboratore, tuttavia si presenta il problema delle differenze di significato dei vari bit all’interno di un numero binario.

Ad esempio, dalla rappresentazione del numero 7 non si hanno eguali probabilità che una mutazione di questo numero porti ad ottenere un 6 (0110) o un 8 (1000). Nel primo caso basterebbe la modifica di un solo bit, nel secondo di tutti e 4.

Rappresentazione a numeri interi: al posto di valori primari, in questa rappresentazione si utilizzano numeri interi. Ad esempio, se un determinato gene può assumere i valori [giallo, rosso, blu] risulterà efficace rappresentarli come [0,1,2]. Qui la scelta è arbitraria, se invece i valori da codificare presentano un ordine naturale (ad esempio un’intensità) il vantaggio è ancora maggiore.
Rappresentazione reale a virgola mobile: questo metodo viene utilizzato quando si necessita del sistema di rappresentazione più sensibile, come ad esempio quando si deve rappresentare una grandezza continua piuttosto che discreta.
Rappresentazione per permutazione: questa rappresentazione è adatta per quei problemi in cui è importante l’ordine con la quale una serie di eventi si verificano. La caratteristica peculiare è l’impossibilità di una ripetizione dello stesso valore che non rappresenterebbe una permutazione valida.

Creazione della popolazione iniziale

Il metodo base per ottenere la popolazione iniziale è la generazione casuale di un numero N di individui.

Tuttavia, per non lasciare semplicemente al caso il compito di scoprire alcune buone caratteristiche che vorremmo includere nella soluzione, si possono introdurre nella popolazione iniziale alcune soluzioni generate con euristiche eventualmente randomizzate.

È comunque importante che il numero di soluzioni sia limitato, in modo da non condizionare troppo le caratteristiche delle soluzioni che verranno generate nelle successive iterazioni.

Funzione di fitness

La funzione di fitness serve a dare una misura quantitativa dell’idoneità di un individuo. Per questo motivo spesso la si associa al valore della funzione obiettivo (o a una sua misura inversa per problemi di minimo).

Potrebbe però essere utile utilizzare funzioni di fitness differenti, come quelle che permettono di:

Penalizzare soluzioni non ammissibili, se si decide di mantenerle nella popolazione corrente.
Penalizzare soluzioni simili all’ottimo corrente, in modo da privilegiare la selezione di individui diversi da quelli finora generati;
Penalizzare soluzioni troppo dissimili dall’ottimo corrente, in fase di intensificazione.

Una volta che si è valutato ogni cromosoma con la soluzione di fitness si procede con la selezione parentale dei genitori.

Selezione parentale

Tramite questa procedura vengono definiti gli individui che partecipano ai processi riproduttivi. Solitamente la selezione opera su base probabilistica: ciò significa che gli individui con fitness maggiore hanno una maggiore probabilità di essere selezionati per le successive ricombinazioni.

Fissato questo principio è possibile:

Selezionare solamente una coppia di genitori soluzioni (o un gruppo di uno o più individui) per ogni iterazione dell’algoritmo;
Scegliere un sottoinsieme della popolazione corrente e selezionare solo quelli appartenenti a tale sottoinsieme.

Con la selezione proporzionale alla funzione di fitness, si seleziona la probabilità p_i di selezionare l’individuo, proporzionale al valore f_i della sua fitness:

Con k numero di soluzioni, cromosomi, individui.

Un altro metodo per la selezione potrebbe essere la selezione a torneo, utilizzata per gestire valori di fitness negativi (non ci addentreremo maggiormente in questa metodologia in questa sede).

Crossover

Una volta scelti i genitori (che solitamente è un numero maggiore o uguale a 2) è possibile definire gli operatori di ricombinazione, che permettono di generare uno o più figli (detti anche offsprings).

Di tipologie di crossover ce ne sono diverse, tra le principali abbiamo:

Single point crossover: scelti due genitori, un padre e una madre, si sceglie un punto casuale per effettuare lo scambio dei geni. Questo punto viene detto di crossover. I figli avranno materiale genetico prima di un genitore e poi, dopo il punto di crossover dell’altro genitore.

2. Two point crossover: rispetto al single point crossover, i tagli casuali sono due (possono essere anche multipli). Il primo figlio otterrà i geni esterni ai punti di crossover presenti nel cromosoma padre, mentre otterrà i geni interni del cromosoma madre.

Viceversa il secondo figlio, otterrà i geni esterni ai punti di crossover presenti nel cromosoma madre, e quelli interni dal cromosoma padre.

3. Crossover uniforme: secondo questo operatore viene prima di tutto generata una mappa di crossover casuale composta solamente da 0 o 1 (che ha stessa lunghezza dei genitori). Quando ho un gene di valore 1 nella mappa crossover assegno il valore del gene corrispondente del padre al primo figlio; invece se ho valore del gene nella mappa crossover pari a 0 assegno il valore del gene corrispondente della madre al primo figlio. Per il secondo figlio il processo si inverte.

Mutazione

Con il crossover può accadere, dopo un certo numero di iterazioni, che molti individui figli abbiano lo stesso valore per il gene i-esimo dei genitori. Ciò è dovuto al fatto che avviene l’assorbimento genetico, cioè la convergenza casuale di uno o più geni verso lo stesso valore.

Pertanto nell’algoritmo genetico è inserito un nuovo operatore: la mutazione.

Tramite essa viene modificato casualmente il valore di alcuni geni, scelti altrettanto casualmente. In aggiunta, la mutazione contrasta la convergenza prematura della popolazione, in modo da evitare una situazione nella quale tutti gli individui della popolazione sono simili tra loro.

Anche per la mutazione è possibile avere più tipologie:

Bit flip mutation: utilizzata per le codifiche binarie, modifica il valore di un gene (da 0 a 1 o viceversa). Per i numeri interi questa mutazione viene detta Random Resetting.

Swap mutation: si selezionano due posizioni casuali dei geni e si scambiano i valori di tali geni.

Scramble mutation: dall’intero cromosoma, una parte dei geni sono scelti e i loro valori sono scambiati o disposti casualmente.

Inversion mutation: come per la scramble mutation, si sceglie un set di geni, ma a differenza di prima si inverte l’ordine dei geni scelti.

Gestione della popolazione

Ad ogni iterazione, la nuova popolazione è ottenuta considerando la popolazione dell’iterazione precedente ed i figli generati.

Solitamente, il numero di individui nelle varie iterazioni viene mantenuto costante, controllato da un parametro N (anche se tale numero è possibile variarlo dinamicamente).

Altri approcci per gestire correttamente la popolazione sono i seguenti:

Generational Replacement: si generano R = N nuovi individui che sostituiscono gli N vecchi individui (imita i sistemi biologici);
Steady state: al contrario della precedente, rimpiazza solo un minimo numero di elementi della generazione precedente, selezionati con criteri guidati dalla fitness;
Tecniche elistiche: con queste si mantengono alcuni individui della popolazione precedente che presentano fitness maggiore;
Selezione dei migliori: si mantengono nella popolazione corrente gli N migliori individui tra gli N + R. La selezione può essere deterministica o probabilistica.

Possibili criteri di arresto

Come capire quando è il momento giusto per stoppare l’iterazione dell’algoritmo genetico?

Non c’è una risposta univoca per tutte le casistiche, anzi è possibile seguire uno dei successivi casi e testare quale è la soluzione più adatta alla risoluzione dell’algoritmo.

Fissare un numero massimo K_max di iterazioni (o generazioni);
Fissare un tempo di esecuzione limite T_max;
Considerare un massimo numero di iterazioni K’_maxdi generazioni senza ottenere un miglioramento, ossia si ferma l’algoritmo se l’ultimo individuo che migliorava la funzione obiettivo è stato trovato k’_max iterazioni prima;
Convergenza della popolazione: si ferma l’algoritmo quando si vede che esistono molti cromosomi simili o la popolazione presenta una scarsa varianza della fitness.

Conclusione

In questo articolo abbiamo visto cos’è un algoritmo genetico e gli step per il suo funzionamento.

Un algoritmo genetico è più efficace quando si conosce molto poco dello spazio di ricerca.

Tramite l’evoluzione di soluzioni di un problema sulle iterazioni / generazioni che avviene grazie alla competizione tra le soluzioni, come avviene per l’evoluzione delle specie, è possibile determinare i cromosomi migliori e quindi le soluzioni al problema.

Per maggiori informazioni puoi vedere:

Pin2