Abstract

Questo articolo descrive tecniche volte al mantenimento della diversità negli algoritmi genetici al fine di migliorarne l'efficienza e di ridurre il rischio di prematura convergenza e stagnazione. Questo articolo è rivolto ai lettori già in possesso di una conoscenza di base della teoria e del funzionamento degli algoritmi genetici.

Introduzione

La prematura convergenza delle soluzioni è un comune problema degli algoritmi genetici. Affichè un'evoluzione possa avvenire, le soluzioni con maggiore fitness devono avere una maggiore probabilità di sopravvivere e riprodursi. Questa selezione può tuttavia portare l'algoritmo genetico a favorire sproporzionalmente una soluzione non ottimale sopprimendo tutti i concorrenti. L'aumentare del numero di individui identici porta dall'evoluzione alla stagnazione. Infatti, il crossover fra due soluzioni uguali non può che generare un clone. A causa delle ristrette dimensioni delle popolazioni di possibili soluzioni, gli algoritmi genetici, se non programmati adeguatamente, portano ad una stagnazione dopo poche generazioni. Non appena nasce una soluzione migliore delle altre (ma non necessariamente ottimale), tende a prevalere su tutte le altre riducendo le probabilità di ulteriori miglioramenti.

Questo articolo è volto a introdurre alcune semplici tecniche volte ad evitare questo fenomeno.

Definizione di somiglianza

Prima di cominciare è indispensabile determinare quali individui possano portare ad una stagnazione. Un semplice esempio di confronto può essere un'operazione XOR sulle stringhe binarie di DNA.

Algoritmi di selezione ed elitismo

Gli algoritmi di selezione puntano a favorire gli individui con fitness più alto. Tuttavia la presenza di soluzioni simili o identiche aumenta eccessivamente la probabilità di un determinato genotipo di diffondersi. Gli algoritmi di soluzione tendono a favorire le soluzioni più ricorrenti piuttosto che quelle migliori. Pertanto, qualora un nuovo individuo più evoluto nascesse in una popolazione stagnante (per esempio a causa di una mutazione), verrebbe comunque rapidamente soppresso.

L'elitismo potrebbe sembrare una soluzione a questo problema, in quanto avvantaggia la migliore soluzione presente. Questa tecnica in realtà accelera la diffusione di soluzioni solo relativamente buone, portando di nuovo alla stagnazione.

Crossover

Anche gli algoritmi di crossover giocano un ruolo importante nel mantenimento della diversità. Per esempio un crossover con taglio a due punti sulle stringhe dei genitori garantisce una maggiore rimescolamento dei geni rispetto ad un taglio ad un punto solo.

Crowding

La tecnica del crowding consiste nel selezionare, in base al fitness, una percentuale della popolazione destinata a produrre n figli. Successivamente n individui devono essere selezionati, in base alla somiglianza con la nuova generazione, per morire.

Questa tecnica è ispirata alla competizione naturale per determinate nicchie ecologiche. In natura infatti, individui simili tra loro hanno bisogni simili e combattono per il controllo delle risorse di cui hanno bisogno. Individui diversi invece possono coesistere senza interferenze.

Eliminazione sistematica degli individui simili

La tecnica del crowding non può prevenire completamente lo sviluppo di individui identici. Una soluzione più drastica è la distruzione di tutti i cloni di ogni soluzione. Al termine di questa pulizia, solo soluzioni diverse fra loro potranno riprodursi. Se questa tecnica viene applicata fin dalle prime generazioni (quando la popolazione è altamente differenziata), lo sviluppo di individui simili viene troncato sul nascere. Questo fa di essa non solo una cura, ma anche un'ottima prevenzione.

Performance

Il confronto di tutte le soluzioni può portare ad un rallentamento dell'algoritmo genetico.

Ovviamente non tutte le soluzioni vanno confrontate, ma solo quelle con uguale fitness. Infatti se due soluzioni hanno fitness diverso ovviamente non possono avere gli stessi geni.

Se il numero di confronti rimane comunque considerevole si pensi che creare migliaia di generazioni di individui identici fra loro sarebbe uno spreco di risorse molto meno giustificato.

Contrastare la deriva genetica

A questo punto non bisogna tuttavia dimenticare l'altro fattore evolutivo indispensabile: il favorimento degli individui migliori. Se la popolazione viene mantenuta forzatamente varia, si rende impossibile alle soluzioni migliori affermarsi sulle altre e far procedere l'evoluzione.

Selezioni a troncamento, elitismo e fitness non lineari sono solo alcuni esempi di algoritmi di selezione che possono spingere l'evoluzione nella direzione giusta, contrastando la deriva genetica causata dalla forzata diversità.

Conclusione

Il giusto equilibrio tra diversità e favorimento delle soluzioni più adatte è indispensabile per il successo degli algoritmi genetici. Questo articolo non vuole essere che un'introduzione a questo complesso problema ed uno stimolo ad approfondirlo. L'interesse per questo argomento mi è sorto durante lo sviluppo e la sperimentazione di Blob Universe (disponibile sul sito www.pierotofy.it). Durante lo sviluppo di questo progetto la prematura convergenza delle soluzioni ha rappresentato un'interessante sfida. Consiglio a coloro che volessero vedere un esempio pratico delle tecnice precedentemente esposte di scaricare l'ultima versione di Blob Universe. Nella speranza che questo articolo possa essere stato utile ed interessante vi invito a contattarmi per domande e correzioni.

Approfondimenti

Mahfoud, S. W. (1992). Crowding and Preselection Revisisted

Cedeño, W. (1995). The Multi-Niche Crowding Genetic Algorithm: Analysis and Applications

Mauldin, M. L. (1984). Maintaining Diversity in Genetic Search