Evoluzione genetica applicata agli alberi di classificazione
7. Il problema del Bloat

Il problema del bloat

Un problema di cui ci si è resi conto molti anni dopo l’introduzione delle tecniche evolutive (1990) e che ne costituisce una limitazione è il problema del Bloating. Si parla di bloat quando i cromosomi crescono in lunghezza senza ottenere in cambio significativi miglioramenti nel fitness. Il bloat ha significativi risvolti pratici: cromosomi inutilmente lunghi sono computazionalmente più pesanti da trattare, eseguire ed evolvere e possono produrre soluzioni poco generalizzabili.

Cosa causa il bloat?

Secondo le teorie classiche, quando il fitness raggiunge uno stato di stagnazione il successo di un nuovo cromosoma è la somiglianza funzionale alla generazione precedente. Questo tende ad annullare la spinta evolutiva e a produrre figli mediamente più grandi. Se pensiamo ai cromosomi come alberi (il caso della programmazione genetica quindi) possiamo suddividere i nodi in due tipi: i nodi attivi e i nodi inattivi.

Un nodo attivo è un nodo che viene effettivamente percorso spesso nella valutazione, un nodo inattivo al contrario è un nodo che non viene percorso ma rimane nell’albero. Un crossover che modifica zone inattive produce un albero con prestazioni identiche ai genitori, ma mediamente di dimensioni superiori. Inoltre più zone inattive ci sono, più si alza la probabilità di avere crossover interni a queste zone.

Controllare il bloat

L’origine del Bloat è rimasta misteriosa per più di un decennio [cit. poli2008field ], ma nonostante questo si sono sviluppate sin da subito strategie per cercare di limitarlo.

Limitare la complessità

Il primo e più rudimentale modo per controllare il bloat consiste nell’imporre un limite massimo di complessità ai cromosomi ed eliminare istantaneamente i figli che superano questo limite. Questo approccio, oltre a costringere a cercare limiti specifici per ogni problema, ha il difetto di tendere a saturare la popolazione di cromosomi con lunghezze immediatamente inferiori a quella limite.

Operatori genetici anti-bloat

E’ possibile progettare gli operatori di crossover in modo che ostacolino il bloat producendo alberi di dimensioni non troppo superiori ai propri genitori. Un metodo diffuso per farlo nel caso del crossover semplice è scegliere casualmente il punto di inserzione e poi scegliere il sottoalbero da inserire in modo che produca un albero di dimensioni non troppo superiori. Questa tecnica è detta "‘size-fair crossover"’ [cit. langdon:1999:fairxo ]

Selezione anti-bloat

E’ possibile scegliere i candidati al crossover in modo da ridurre il bloat, questo può avvenire in modi diversi:

1. Ottimizzazione multiobiettivo: è possibile definire una funzione di fitness che penalizzi gli alberi troppo grandi, rendendone meno probabile la riproduzione.

2. Metodo Tarpeian: si selezionano alcuni alberi più lunghi della media e li si esclude temporaneamente dalle selezioni per la riproduzione. Aumentando il numero di alberi e la frequenza di applicazione del metodo si può modularne l’intensità.