Il caso della programmazione genetica

Come accennato precedentemente, nella programmazione genetica si evolvono programmi capaci di svolgere un task con risultati misurabili.

Questo implica tipicamente l’utilizzo di strutture dati, e di conseguenza operatori, più complessi rispetto al caso degli algoritmi genetici.

Le strutture dati tipiche della programmazione genetica sono gli alberi sintattici, questo implica che il programma non sarà costituito da una sequenza di istruzioni atomiche come in un linguaggio imperativo, ma come un annidamento di funzioni l’una dentro l’altra similmente all’approccio funzionale. Non a caso il primo linguaggio utilizzato per la programmazione genetica fu il Lisp.

La struttura dei cromosomi

Come detto precedente, i cromosomi sono tipicamente strutturati come alberi. In questo caso essi rappresentano una grammatica in un linguaggio libero dal contesto e si deve quindi stabilire un insieme di simboli terminali e di operatori,definendo poi una grammatica che regoli la struttura degli alberi garantendone la consistenza dei tipi e la calcolabilità delle operazioni. La scelta della grammatica è fondamentale: si devono strutturare gli alberi in modo che abbiano una struttura sufficiente a rappresentare le soluzioni valide.

Creazione della popolazione iniziale

Si può creare la popolazione iniziale sia a caso, senza quindi utilizzare nessuna conoscenza espressa nel dataset, sia con algoritmi non genetici che analizzano i dati.

Nel primo caso la creazione della popolazione non necessita di utilizzare il dataset, nel secondo invece una parte del dataset verrà utilizzata come trainingset. Nel caso particolare degli alberi di decisione una strategia tipica è disporre di un trainingset per creare la popolazione iniziale, di uno scoringset per effettuare le misurazioni durante il processo evolutivo e di un testset per effettuare le misurazioni finali.

Inizializazione di popolazioni casuali

Nel caso della generazione casuale della popolazione ci si basa sulle regole grammaticali definite dalla struttura dei cromosomi per generare degli alberi con la forma desiderata. I modi più diffusi per generare gli alberi sono 3:

Calcolo del fitness

Il fitness è una misura dell’efficienza del cromosoma nel risolvere il problema e permette inoltre di stabilire un ordinamento nella popolazione. Il calcolo della fitness può dover tener conto di più parametri, ad esempio nel caso degli alberi di classificazione potrebbero essere:

il numero di errori di classificazione, il tempo necessario al cromosoma per produrre un risultato, la corrispondenza della struttura del cromosoma rispetto alla struttura desiderata.

Quando il fitness si basa su un singolo parametro si parla di fitness semplice, quando si basa su più di un parametro si parla invece di fitness multiobiettivo.

Fitness semplici

Il caso di una singola variabile da ottimizzare è il caso più semplice. Una funzione di fitness deve essere una funzione non decrescente veloce da calcolare; può essere utile limitarla in [0-1] per poterla trattare come una funzione di probabilità.

Fitness multiobiettivo

Nel caso di più variabili da ottimizzare, si possono utilizzare i seguenti due metodi:

Funzioni in più variabili

Si definisce una funzione $$f:\mathbb{R}^n\rightarrow \mathbb{R}$$ in modo da definire il seguente ordinamento: $$x,y\in R^{ n }, x> y \Longleftrightarrow f(x)>f(y).$$

Tipicamente la funzione è una combinazione lineare di funzioni non decrescenti nelle singole variabili, ovvero di fitness semplici. Assume quindi la forma

dove fᵢ sono le singole fitness semplici e wᵢ sono le componenti di un vettore “peso”, che permette di assegnare un’importanza diversa alle singole componenti di f. Questa forma prende il nome di “aggregate scalar fitness function”. La norma, tuttavia, non induce un ordinamento stretto, ovvero possono esistere vettori diversi con lo stesso valore di fitness.

Pareto dominance

Un approccio alternativo è cercare di mantenere separate le singole variabili. Per fare questo ci si basa sulle seguenti due definizioni:

Si può quindi affermare che se un vettore a è pareto dominante non esiste un altro vettore b che abbia componenti superiori senza averne di peggiori.

All’interno dell’insieme dei vettori, dunque, nessuna componente può essere migliorata senza peggiorarne un’altra.

Applicando la definizione di dominanza all’insieme delle soluzioni si ottiene un ordinamento parziale. La ricerca delle soluzioni migliori viene ricondotta alla ricerca del pareto set o di un’approssimazione di esso costituita da vettori mutuamente non dominanti.

Illustrazione del pareto front nel caso bidimensionale, A e B non sono mutuamente dominanti ma sono dominate da 1,2,3