Visto l' ottimo interesse suscitato, sia all' interno della community che all' esterno ( due tesisti mi hanno contattato dopo aver letto i miei post sul Machine Learning), voglio presentarvi un metodo molto interessante che viene utilizzato per risolvere problemi di ottimizazzione: gli Algoritmi Genetici (AG). Gli algoritmi genetici costituiscono un sottoinsieme degli Algoritmi Evolutivi, termine generico che indica una gamma di sistemi di risoluzione dei problemi che riproducono il processo evolutivo cosi come descritto nella teoria Darwiniana.

Tra la fine degli anni '50 e l'inizio degli anni '60 alcuni ricercatori cominciarono a interessarsi ai sistemi naturali nella convinzione che potessero fornire le fondamenta per costituire un modello utilizzabile all' interno di algoritmi di ottimizzazione. Dopo le prime fasi di ricerca  incentrate sulla riproduzione assessuata, in cui solo un genitore contribuisce alla creazione di un figlio, il matematico John Holland evidenzio, nei primi anni '80, l' importanza della riproduzione sessuata enfatizzando maggiormente la teoria evoluzionistica di Darwin. Il concetto darwiniano di evoluzione prevede che, considerati due genitori di una qualunque specie aventi caratteristiche genetiche dominanti, la probabilità che anche i figli mantengano tali caratteristiche è maggiore di quella che si avrebbe se i genitori non avessero simili qualità. Gli Algoritmi Genetici generano inizialmente una serie casuale di numeri (generalmente binari),
producendo successivamente nuove generazioni che molto probabilmente sono composte da individui migliori delle precedenti; la bontà o meno di un individuo viene misurata mediante una funzione di fitness che rappresenta una sorta di indice di varianza tra il valore ideale (quello
da raggiungere, noto a priori) e quello ottenuto dai numeri casuali creati ed evolutisi. Un algoritmo genetico in definitiva produce iterativamente nuove generazioni cercando di massimizzare la funzione di fitness;

Ogni soluzione del problema da risolvere (individuo) è rappresentata da un insieme di elementi (cromosoma). Ogni elemento del cromosoma è chiamato gene
e ad ogni cromosoma, che rappresenta un punto nello spazio di ricerca, viene associato un valore di fitness. Si definisce come Popolazione un gruppo di individui che rappresenta una generazione della specie, una sorta di campionamento temporale durante la propria evoluzione.

Selezione

All'interno di una popolazione, ad ogni individuo è associata una probabilità di selezione legata al valore di fitness. In generale, la selezione non può basarsi solamente sul cromosoma con più alto valore di fitness, poichè questo potrebbe essere lontano dalla soluzione ottima, ma è necessaria una selezione che produca dei cromosomi che possano portare, durante il processo evolutivo, ad un miglioramento della popolazione. Tra le tecniche più comuni di selezione possiamo citare la Roulette-wheel selection: il principio di funzionamento è analogo a quello di una ruota girevole viene divisa in n settori ciascuno corrispondente ad un cromosoma. La dimensione dell’i-esimo settore è proporzionale alla probabilità di selezione pi del cromosoma xi.La probabilità pi viene calcolata con la seguente formula:

dove F è la somma del valore di fitness dell' intera popolazione mentre f(xi) è il valore di fitness dell' elemento iesimo. La ruota viene fatta girare n volte. Ogni volta si sceglie un cromosoma che viene copiato nella popolazione; le buone prestazione che offre questo metodo di selezione derivano dal fatto che non vengono perse informazioni genetiche che in futuro potrebbero mostrare tutte le loro potenzialità. I cromosomi migliori, infatti, potrebbero contenere al loro interno dei geni non ancora ottimizzati, geni che invece potrebbero già aver raggiunto un valore ottimo in un individuo con un valore momentaneo di fitness ancora non elevato e di cui quindi non si deve perdere il patrimonio genetico 

Riproduzione e CrossOver

Esistono due tipologie di riproduzione:

1. Asessauta: comporta la partecipazione di un solo genitore prevedendo quindi solamente una sottofase di mutazione
2. Sessuata: prevede l' utilizzo di una fase di CrossOver e una di mutazione

L’operatore di crossover svolge il ruolo giocato dalla riproduzione in natura.Produce un nuovo individuo mescolando l’informazione contenuta in 2 individui
genitori è difatti un operatore tipicamente binario che permette di combinare i geni di due individui per produrre nuovi individui che mantengano il corredo genetico dei genitori

Vengono presi due individui, e si dividono i rispettivi cromosomi in qualche posizione scelta a caso (crossover point), per produrre due segmenti "testa" (head)} e due segmenti "coda" (tail). I segmenti coda sono poi scambiati per produrre due nuovi cromosomi di lunghezza completa.Il cosiddetto operatore di crossover one point è applicato n/2 volte per ottenere n discendenti in base ad una prefissate probabilità p. Nel caso in cui il crossover non sia applicato, i discendenti coincidono con i genitori.  Il crossover uniforme prevede che per ogni coppia di genitori si genera una stringa binaria della stessa lunghezza chiamata maschera. Il discendente viene generato copiando il bit del padre o quello della madre a seconda che nella corrispondente posizione della maschera via sia uno 0 o un 1.

Mutazione

La mutazione è un operatore unario che reintroduce nella popolazione materiale genetico perduto (processo di entropizzazione). In base a una probabilità piccola p, viene cambiato il valore dei bit di ogni individuo (da 0 a 1 e viceversa)

Come in natura, la mutazione aggiunge un "rumore" o una certa casualità all'intera procedura, in modo da assicurare che partendo da una popolazione generata casualmente non vi siano punti dello spazio delle soluzioni che non vengano esplorati; a seguito di una mutazione assistiamo ad un piccolo spostamento nello spazio di ricerca.

Elitismo

L’elitismo è una strategia evolutiva che va a completare il processo di sostituzione della popolazione iniziato dall’operatore selezione.Quando creiamo una nuova popolazione con crossover e mutazione abbiamo una grande probabilità di perdere il miglior cromosoma. L’elitismo semplice è un metodo che prima copia il miglior cromosoma  (o i pochi migliori) nella nuova popolazione e poi prosegue con la logica espressa in precedenza. L’elitsmo può far crescere rapidamente le performance del GA perché evita la perdita della migliore soluzione trovata.

Convergenza

Durante il processo evolutivo, a causa dell’applicazione degli operatori, può accadere che la mappa cromosomica presenti un valore di fitness globale minore rispetto alla generazione precedente. Bisogna ricordare altresì che una delle caratteristiche degli algoritmi genetici è proprio la loro natura di ottimizzatori globali multi-oggetto, questo permette loro di esaltare magari il patrimonio genetico di cromosomi attualmente non totalemente adattati nelle successive generazioni. Se il GA è correttamente implementato, la popolazione evolverà in molte generazioni in modo che il fitness del miglior individuo e la media in ogni generazione cresca verso l'ottimo globale. Solitamente la condizione del criterio di arresto di convergenza viene stabilita dal progettista in base a delle specifiche di progetto o in base a un numero prefissato di generazioni

Riflessioni

Le tecniche evoluzionistiche alla base dei GA sono ottimizzatori globali e devono quindi ricercare la regione in cui si trova l' ottimo all’interno del dominio; nel fare ciò devono realizzare un tradeoff tra exploitation della miglior soluzione ed exploration dello spazio di ricerca. La pressione selettiva imposta dall’algoritmo privilegia l’exploitation rispetto all’exploration portando l' algoritmo a convergere ad una soluzione di ottimo locale. Sono state introdotte alcune tecniche per ridurre la prematura convergenza dell' algoritmo quali Fitness Sharing e Clustering.

Come al solito consigli, suggerimenti sono ben accetti...A questa prima parte teorica di introduzione farò seguire una parte di implementazione, preparata proprio ad hoc prima di partire per le vacanze... qualcuno magari ha già capito l' esempio di implementazione a cui mi riferisco... 

Ad maiora...