Ci accingiamo a poter definire le procedure operative di un algoritmo genetico. Prima però é necessario procedere a una fase di setup, in cui si deve rappresentare il problema, definire gli obiettivi, e infine, codificare l‘algoritmo. In questo articolo verranno analizzate queste fasi.

Introduzione

Dopo avere effettuato la selezione dei genitori ed averli posizionati nella mating pool, devono essere effettuate tutte le operazioni per permettere l’evoluzione della specie. Queste operazioni possono essere messe in atto attraverso i cosiddetti operatori di riproduzione: questi operatori sono il crossover e la mutazione. La loro modalità operativa è ispirata alla genetica classica, e viene descritta in seguito.

CrossOver

Dopo la selezione dei genitori, all’interno del mating pool viene scelto un punto di taglio, detto punto di crossover: le porzioni di genotipo alla destra del punto di crossover sono scambiate generando due discendenti.

Figura 1 – Single Point Crossover

Single Point Crossover

L’algoritmo genetico tradizionale, come è stato già descritto prima, usa il single point crossover in cui i due cromosomi che si accoppiano sono entrambi tagliati in punti corrispondenti e la sezione dopo i tagli è cambiata. Comunque, sono stati inventati molti diversi algoritmi di crossover, che spesso coinvolgono più di un punto di taglio.
DeJong ha studiato l’efficienza del crossover multipoint ed è arrivato alla conclusione che il two-point crossover genera un miglioramento; invece aggiungere più punti crossover riduce le prestazioni dell’algoritmo. Il problema, con l’aggiunta di più punti crossover è che i building blocks sono più facili da spezzare. Comunque, un vantaggio di avere molti punti crossover è che nello spazio del problema si può fare una ricerca più accurata.

Two Point Crossover

In questa tecnica (e in generale nel multi-point), piuttosto che stringhe lineari, i cromosomi possono essere considerati come circoli formati dall’unione degli estremi insieme, come mostrato in figura 2.

Per cambiare un segmento da un circolo con un altro proveniente da un altro ciclo, si richiede la selezione di due punti crossover. In questa figura il single point crossover può essere visto come un two-point crossover, con uno dei punti di taglio fissato all’inizio della stringa. Quindi il two-point opera come il one-point, ossia cambiando un solo segmento, ma è più generale. Un cromosoma, considerato come un circolo, può contenere più building blocks, poiche’ sono in grado di avvolgersi alla fine della stringa.
I ricercatori attualmente sono d’accordo che il two-point crossover è generalmente migliore del one point.

Crossover uniforme

Questa tecnica è completamente differente dal one-point crossover: ciascun gene nei figli è creato tramite una copia del corrispondente gene da uno dei due genitori, scelto in accordo a una maschera di crossover creata a sua volta in maniera casuale.

Come si può vedere dalla figura 3, dove c’è un 1 nella maschera, il gene è copiato dal primo genitore, e dove c’è uno 0, il gene è copiato dal secondo genitore. Il processo è ripetuto con i genitori scambiati per produrre un secondo figlio.
Per ciascuna coppia di genitori, viene generata casualmente una nuova maschera crossover: il figlio quindi contiene una miscellanea di geni provenienti da ciascun genitore. Il numero degli effettivi punti crossover non è fissato, ma supererà L/2, dove L è la lunghezza del cromosoma.

Altre tecniche di crossover

Negli anni sono state suggerite numerose altre tecniche di crossover. L’idea che il crossover dovesse essere più forte in certe posizioni sulla stringa piuttosto che in altre ha qualche fondamento in natura, e alcuni di questi metodi che sono stati descritti. Il principio generale è che l’algoritmo genetico impara adattativamente quali siti dovrebbero essere favoriti per il crossover. Questa informazione è registrata in una stringa punteggiatura, che è essa stessa parte del cromosoma, e quindi viene incrociata e passata ai discendenti. In questo modo le stringhe punteggiatura che vanno in direzione della migliore discendenza saranno esse stesse propagate attraverso la popolazione.
Goldberg descrive un operatore crossover abbastanza diverso che si chiama Partially Matched Crossover (PMX), per l’uso in problemi basati sull’ordine. Nel PMX non sono incrociati i valori dei geni, ma l’ordine con cui appaiono; i figli hanno geni che ereditano ordinando informazioni da ciascun genitore. Questo elimina la generazione di figli che violano i vincoli del problema.

Confronto tra le tecniche di crossover

Il dibattito su quale sia la migliore tecnica di crossover è ancora in corso. Syswerda argomenta in favore dell’uniforme: infatti, in questa modalità gli schemi che hanno un particolare ordine hanno la stessa probabilità di essere distrutti, a prescindere dalla lunghezza definita.
Con il two-point è la lunghezza definita dello schema che determina la sua predisposizione alla distruzione, non il suo ordine. Questo significa che, riguardo al crossover uniforme, gli schemi con lunghezze definite corte hanno maggiori probabilità di essere distrutti, mentre le più lunghe sono distrutte meno facilmente.
Syswerda inoltre dice che il numero totale delle distruzioni degli schemi è comunque alta. Il crossover uniforme ha il vantaggio che l’ordinamento dei geni è del tutto irrilevante e questo significa che gli operatori di riordinamento come l’inversione, discussa in seguito, non sono necessari, e non bisogna preoccuparsi di posizionare i geni per migliorare i buiding blocks.
L’efficienza dell’algoritmo che usa il two-point decade drasticamente, se non sono rispettate le raccomandazioni della building block hypothesis. Il crossover uniforme d’altra parte, continua a lavorare bene almeno quanto un two-point usato con un cromosoma ordinato correttamente. Comunque l’uniforme sembra essere la tecnica più robusta.
Eshelman fornisce una comparazione estesa di differenti operatori di crossover, incluso 1-2-point, multi-point e uniforme: questi sono analizzati teoricamente in termini di deviazione di posizione e distribuzione, e empiricamente su alcuni problemi. Nessuno prevale sugli altri e infatti c’erano non più di circa 20% di differenza nella velocità delle tecniche. Spears e DeJong sono molto critici riguardo il multi-point e l’uniform crossover, mentre sono d’accordo con le analisi teoriche che mostrano che 1 e 2 point crossover sono ottimi: tali studiosi affermano infatti che il crossover a due punti lavorerà male quando la popolazione è ampiamente convergente, e ciò dovuto alla ridotta produttività del crossover. Si tratta della capacità dell’operatore crossover di produrre nuovi cromosomi che nello spazio di ricerca campionano punti differenti. Quando due cromosomi sono simili, i segmenti scambiati dal two-point crossover è probabile che siano identici, e portano a figli che sono identici ai genitori. Questo è meno facile che succeda con l’uniform crossover: loro descrivono un nuovo operatore two-point crossover che, se produce due figli identici, sceglie due nuovi cross-point per variare i figli successivi. Questo operatore era stato cercato per lavorare meglio del crossover uniforme in un problema test, ma le prestazioni erano solo leggermente superiori.
In una pubblicazione successiva hanno concluso che il two-point modificato è migliore per grandi popolazioni, ma che la maggiore distruzione del crossover uniforme è benefica se la dimensione della popolazione è piccola, confrontata con la complessità del problema, e quindi dà una performance più robusta.

Inversione e ordinamento

È stato già detto che l’ordine dei geni in un cromosoma è critico perch��� la building block hypothesis funzioni efficientemente. Sono state quindi suggerite delle tecniche per riordinare le posizioni dei geni durante l’esecuzione: una di queste tecniche è l’inversione, che lavora invertendo l’ordine dei geni tra due posizioni scelte casualmente all’interno del cromosoma. Quando vengono utilizzate queste tecniche, i geni devono trasportare con loro alcuni tipi di etichette in modo che possano essere identificati correttamente, non curandosi quindi delle altre posizioni all’interno del cromosoma.
Il fine dell’ordinamento è di cercare di trovare ordinamenti di geni che hanno potenziale evolutivo migliore. Molti ricercatori hanno usato l’inversione nei loro lavori, sebbene non abbiano mai giustificato abbastanza o quantificato l’effettivo contributo del suo utilizzo. Goldberg e Bridges hanno analizzato un operatore di riordinamento in un task molto piccolo e hanno mostrato che questo può portare vantaggi, sebbene abbiano comunque concluso che i loro metodi non potrebbero portare gli stessi vantaggi in un task più grande.
Il riordinamento non ha effetti in presenza di una bassa epistasis, quindi non può aiutare per quanto riguarda le altre richieste del building block hypothesis, e nemmeno aiuta se la relazione tra i geni non consente un semplice ordinamento lineare. Se si usa il crossover uniforme, l’ordine del gene è irrilevante, quindi non è necessario il riordinamento.
Il riordinamento espande lo spazio di ricerca in modo molto grande: non solo l’algoritmo cerca dei buoni set di valori di geni, ma simultaneamente cerca di ordinarli in maniera opportuna, e quest’ulitmo risulta un problema molto più difficile da risolvere; infatti, il tempo speso cercando ordinamenti di geni migliori è tempo portato via alla ricerca di migliori valori di geni.

In natura ci sono molti meccanismi tramite i quali la disposizione dei cromosomi si può evolvere, l’inversione è solo una di questi. In breve, gli organismi saranno favoriti se si evolveranno in modo da adattarsi meglio al loro ambiente. Ma più precisamente le specie hanno più probabilità di sopravvivere se la loro evoluzione cariotipica li porterà a essere più facilmente adattati alle nuove condizioni, come ad esempio i cambiamenti ambientali. La valutazione del genotipo prende posto velocemente in ciascuna generazione, ma quella del cariotipo prende spazio molto lentamente, forse dopo migliaia di generazioni.

Negli algoritmi genetici, in genere l’ambiente circostante viene espresso tramite la funzione di fitness, e risulta quindi statico; questo comporta che l’evoluzione karyotype, presente in natura, diventa di poca importanza. Nonostante ciò, l’evoluzione del cariotipo può essere rappresentata nei casi un cui la funzione di fitness cambia dopo poco tempo, e l’algoritmo ha comunque l’obiettivo di fornire una soluzione che può adattarsi all’ambiente che cambia.

In un ambiente statico se si vuole realmente determinare il miglior ordinamento di geni, si potrebbe provare a usare un meta-algoritmo. Un meta-algoritmo ha una popolazione dove ciascun membro è esso stesso un algoritmo genetico. Ciascun individuo è configurato per risolvere lo stesso task ma usando parametri differenti . Il fitness di ciascun individuo è determinato dall’esecuzione dell’algoritmo e guardando quanto velocemente converge. I meta-algoritmi sono ovviamente molto costosi da eseguire a livello computazionale, e sono più utili solo se i risultati che producono possono essere utilizzati più volte.

Conclusioni

In questo articolo si è affrontato l’operatore di crossover. Nel prossimo articolo verrà presentato l’operatore di mutazione e alcuni problemi che derivano dall’applicazione di questi operatori nell’esecuzione dell’algoritmo.

Riferimenti

[1]    D.B. Fogel, “Evolutionary computation: toward a new philosophy of machine intelligence”, IEEE Press, NewYork, 1995, ISBN 078035379X

[2]    J.R Koza, “Genetic programming: on the programming of computers by means of natural selection”, MIT Press, Cambridge, MA, 1992, ISBN 0262111705

[3]    Alden H. Wright, “Genetic Algorithms for Real Parameter Optimization”, 1991