Evoluzione genetica applicata agli alberi di classificazione
6. Gli operatori genetici, il sampling, e il problema del bloat

Crossover

Il crossover ha il compito di combinare le informazioni di due cromosomi per crearne di nuovi. La struttura dati ad albero impone forme di crossover più complesse rispetto a quelle degli algoritmi genetici. Il crossover viene implementato come scambio di sottoalberi; il tipo di crossover più utilizzato è il subtree crossover, di cui si riporta una descrizione.

Il modo più semplice per scegliere i punti di taglio è utilizzare una distribuzione di probabilità uniforme, ma esistono anche altre strategie che permettono di influenzare la forma degli alberi prodotti.

Se glialberi sono generati casualmente, tendono ad avere un numero molto alto di foglie e quindi una scelta di punti di taglio uniforme comporterebbe in molti casi un semplice scambio di foglie. Per aggirare questo problema è possibile forzare la selezione dei sottoalberi a scegliere nodi non terminali con una percentuale fissata di probabilità ( Koza propone 90% non terminali ).

Mutazione

La mutazione ha il compito di introdurre nuovo materiale genetico, non presente nei cromosomi, modificandoli. Esistono diversi modi per implementare la mutazione nel caso della programmazione genetica, i più diffusi sono:

Strategie di selezione (Sampling)

*Si può desumere che ci sono solo due fattori primari (e probabilmente solo due fattori) nella ricerca genetica: diversità della popolazione e pressione selettiva […]. Molti dei vari parametri che che si utilizzano per “tarare” la ricerca genetica sono modi indiretti per influenzare la diversità della popolazione e la pressione selettiva. Se la pressione selettiva è incrementata la ricerca si concentra sugli individui migliori della popolazione ma a causa di questa “exploitation” la diversità genetica si perde. Riducendo la pressione selettiva (o utilizzando una popolazione più grande) si aumenta la “esplorazione” in quanto più genotipi e di conseguenza più schemi sono coinvolti nella ricerca *[cit. whitley:icga89 ]

I termini exploitation e exploration sono difficili da rendere in italiano.

Per exploration (traducibile in “esplorazione”) si intende la facoltà dell’algoritmo di esaminare nuove aree nello spazio di ricerca.

Per exploitation (traducibile malamente in “sfruttamento”) si intende la facoltà dell’algoritmo di trarre la massima quantità di informazione dalle aree che si conoscono per poterne trovare di migliori.

E’ evidente che i due fattori siano in contrapposizione, un buon algoritmo genetico deve bilanciare i due fattori per convergere verso buone soluzioni.

Selezione “elitaria”

La selezione elitaria (o etilist) è il tipo più semplice di selezione, dove la probabilità di selezione del singolo cromosoma è funzione del suo fitness non riscalato rispetto alla media o al massimo nel pool genetico. Il difetto fondamentale di questo approccio è che non si tiene conto della distribuzione dei fitness all’interno del pool e si introduce una pressione selettiva eccessiva che aumenta con le generazioni, in quanto la media delle fitness tende a salire. Come vedremo in seguito viene utilizzata nell’algoritmo di programmazione genetica proposto (GAIT).

Selezione a fitness proporzionale e selezione a roulette

Nella selezione a fitness proporzionale si fa in modo che ogni cromosoma abbia una probabilità di riprodursi proporzionale alla percentuale che rappresenta il suo fitness all’interno della somma dei fitness della popolazione. Nella SFP i fitness vengono scalati attraverso la media del fitness per la popolazione attuale, ottenendo un vettore di probabilità la cui somma è 1 . Attraverso la somma cumulativa di questo vettore si può applicare la cosiddetta “selezione a roulette”:

FOR n:=1 TO N DO
    x=numero casuale in [0-1]
    i=indice del primo elemento >x nel vettore somma
    seleziona l`elemento i-esimo
END

Eseguendo questa procedura (con reimmissione del cromosoma) si fa in modo che cromosomi con alto fitness possano essere selezionati più volte rispetto a cromosomi con fitness basso. Visivamente è come se i cromosomi fossero piazzati sulla ruota di una roulette occupando un numero di caselle proporzionale alla loro fitness, lanciando la pallina si ha quindi più probabilità di estrarre cromosomi a fitness maggiore.

Selezione SPF

Selezione basata sul rank

Una pressione selettiva eccessiva può comportare una convergenza prematura della popolazione verso un ottimo locale, determinato unicamente dai cromosomi migliori. Si vengono così a creare dei super-cromosomi con un fitness molto superiore alla media della popolazione che tendono ad avere un numero di figli molto alto, impedendo ai cromosomi con fitness minori di contribuire all’evoluzione e finendo per eliminarne il materiale genetico dall’ecosistema. Un modo per aggirare questo problema è selezionare i cromosomi non in base al loro fitness, ma in base alla loro posizione nella classifica dei cromosomi migliori (rank). Esistono molti modi per associare al rank un numero di figli; per esempio si può definire una funzione lineare $$p(rank)=q-(rank-1) \cdot r$$ Per fare in modo che sia una funzione di probabilità ∑p(i)=1 e quindi q è definito come $$q=\frac{r(pop_{size}-1)}{2} + \frac{1}{pop_{size}}$$

In questo modo la variazione del parametro r da 0 a $$\frac{2}{pop_{size}(pop_{size}-1)}$$ permette di incrementare la pressione selettiva. [cit. michalewicz1996genetic ]

Selezione a torneo

Un altro modo per evitare che i super-cromosomi possano dominare troppo velocemente l’evoluzione è la selezione a torneo. Nella selezione a torneo ogni cromosoma da far riprodurre viene scelto come il cromosoma migliore tra k cromosomi estratti a caso dal pool genetico. In questo modo il parametro k determina la pressione selettiva.

Il problema del ridimensionamento nelle popolazioni non ordinate

Nelle implementazioni che hanno vincoli sulla numerosità della popolazione sono necessarie delle tecniche per riportare tale numerosità entro i limiti. La tecnica più semplice è eliminare gli elementi peggiori; nel caso il resto dell’algoritmo non imponga di mantenere un ordinamento all’interno della popolazione (nella selezione a torneo per esempio), questo approccio comporta un rallentamento nell’algoritmo. Un approccio alternativo è estrarre gruppi di cromosomi a caso, tipicamente due, ed eliminare il peggiore, ripetendo iterativamente la procedura fino a riportare la popolazione alla numerosità richiesta. Questo metodo non garantisce di eliminare gli elementi peggiori, il che paradossalmente in alcuni contesti può essere positivo perché allenta la pressione selettiva.