Nel precedente articolo si è fatta una panoramica generale sugli algoritmi genetici, evidenziando il parallelismo con la genetica classica. In questo articolo verranno analizzate le basi teoriche su cui si fondano questi algoritmi utili come strumento di risoluzione di problemi complessi.

Introduzione

Esiste pochissima teoria sul funzionamento effettivo degli algoritmi genetici; in particolare, Holland ha tentato di spiegare la distribuzione delle risorse nello spazio di ricerca con il suo famoso Teorema degli Schemi.

Il Teorema degli Schemi

Il Teorema Fondamentale degli Algoritmi Genetici, o Teorema degli Schemi, assicura che, sotto determinate ipotesi, gli individui con alti valori di fitness tendono a crescere esponenzialmente nella popolazione attraverso il meccanismo dell’incrocio, assicurando così la convergenza dell’algoritmo genetico verso una soluzione ottimale.

Questo teorema, dovuto ad Holland, spiega la potenza di un algoritmo genetico in termini di quanti schemi vengono processati: agli individui della popolazione viene data la possibilità di riprodursi, spesso chiamata prova di riproduzione (reproduce trials). Il numero di opportunità che ogni individuo riceve è in proporzione al suo fitness, quindi i migliori individui contribuiscono maggiormente ai geni della generazione successiva: si presuppone che un alto valore di fitness sia dovuto al fatto che l’individuo possiede buoni schemi. Passando i migliori schemi alla generazione successiva, viene aumentata la probabilità di trovare soluzioni migliori. Holland ha dimostrato che la cosa migliore è assegnare prove di riproduzione in numero sempre maggiore agli individui che hanno il fitness più elevato rispetto al resto della popolazione, in modo che i buoni schemi abbiano un numero di prove crescente in modo esponenziale nelle generazioni successive. Ha mostrato, inoltre, che poiche‘ ogni individuo contiene un gran numero di schemi diversi, il numero degli schemi che devono essere effettivamente processati è dell’ordine di n³ in cui n è il numero di individui.

Formalmente, il teorema considera un alfabeto formato dai simboli [0,1,*]; se si ha un genotipo binario di L elementi, uno schema è una stringa di L simboli appartenenti al suddetto alfabeto. Se * può indicare al contempo sia 0 che 1, allora uno schema rappresenta un insieme di stringhe e può essere più o meno adatto a sopravvivere nell’ambiente, a seconda che le stringhe che identifica abbiano una funzione di fitness più o meno elevata. Il crossover e la mutazione alterano gli schemi definiti e possono introdurne di nuovi.

Il teorema degli schemi dimostra, quindi, che, utilizzando una selezione di tipo fitness-proportionate, la distribuzione degli schemi di ricerca, cioè l’aumento o la diminuzione di un particolare schema, avviene in modo molto vicino all’ottimo matematico, ed è indipendente dal problema.

La dimostrazione di questo teorema è basata sull’ipotesi di codifica binaria, ma nel 1991 Wright l’ha estesa al caso di codifica con numeri reali; lo stesso Wright ha mostrato che una codifica reale è da preferirsi nel caso di problemi continui di ottimizzazione. Herrera e Lozano, nel 1998, hanno poi presentato un’ampia rassegna di operatori genetici applicabili a cromosomi codificati mediante numeri reali, compresi vari tipi di crossover.

Sono state però mosse numerose critiche a questo teorema, alcune delle quali vertono sulla reale applicabilità in casi pratici; sono stati sviluppati infatti algoritmi genetici che non soddisfano le condizioni del teorema, ma che ottengono comunque risultati simili all’algoritmo classico. Altre critiche sono state mosse sugli aspetti teorici: in particolare, si è notato che il teorema degli schemi non esplica le correlazioni esistenti tra i padri e i figli.

Terminologia

Uno schema è un cromosoma generalizzato, di lunghezza predefinita, in cui siano specificati i valori assunti da alcune particolari posizioni di bit nella stringa, e siano invece lasciati indefiniti i valori associati alle altre posizioni. Un’istanza di uno schema è un cromosoma contenente un dato schema; all’interno di esso, le posizioni fissate sono le posizioni del cromosoma con valore binario specificato nello schema.

L’ordine di uno schema è il numero di posizioni fissate all’interno di esso, mentre la lunghezza definita è la distanza tra le posizioni fissate più esterne in uno schema. Invece, la lunghezza di uno schema o delle sue istanze è sostanzialmente la lunghezza l delle stringhe.

Il valore medio di idoneità di uno schema viene calcolato come valore medio delle idoneità di tutte le istanze dello schema.

Competizione fra schemi: parallelismo implicito

In un algoritmo genetico, la competizione fra cromosomi può essere equivalente, dal punto di vista teorico, come una competizione fra schemi. È necessario notare però quanto riportato di seguito.

Considerato uno schema di lunghezza l, con k posizioni fissate, esistono 2^k possibili schemi distinti con le stesse posizioni fissate, dato che esistono 2^k possibili permutazioni di k bit;

Ogni insieme di k posizioni fissate genera una competizione tra schemi per la sopravvivenza fra i 2^k schemi che hanno quelle k posizioni fissate;

Poiche‘ è possibile scegliere 2^l distinte combinazioni di posizioni fissate, esistono 2^l distinte competizioni di schema.

L’esecuzione di un algoritmo genetico su stringhe binarie di lunghezza l implica 2^l distinte e simultanee competizioni fra schemi: è questa la caratteristica del parallelismo implicito, che li rende efficaci come tecniche di ricerca.

Se n è la dimensione della popolazione, il numero degli schemi contemporaneamente processati ad ogni generazione è, secondo Holland, dell’ordine di n³ l’algoritmo individuerà il migliore schema possibile associato ad ogni possibile posizione fissata, convergendo gradualmente verso lo schema migliore rispetto a tutte le posizioni fissate. In altre parole, il cromosoma ottimo risulta dalla competizione fra schemi per incrementare il numero delle loro istanze nella popolazione.

Building Block Hypothesis

Pur riconoscendo la validità empirica del teorema dello schema, Goldberg pone la sua attenzione sulla necessità di creare codifiche cromosomiche specifiche per il problema, e fornisce delle raccomandazioni per la codifica, che, anche se comunque empiriche, risultano finalizzate a favorire la convergenza e le alte prestazioni dell’algoritmo.

La potenza degli algoritmi genetici sta nella loro capacità di trovare buoni blocchi di costruzione: questi sono schemi di lunghezza definita corta, formata da bit che lavorano bene insieme e tendono a portare miglioramenti quando sono incorporati nello stesso individuo. Uno schema di codifica ben riuscita è uno schema che incoraggia la formazione di building block, assicurandosi che:

• i geni correlati siano vicini all’interno del cromosoma;
• ci sia poca interazione tra i geni;

L’interazione tra geni, spesso chiamata  epistasis, significa che il contributo di un gene al fitness dipende dal valore degli altri geni nel cromosoma: infatti, c’è sempre una certa interazione in una funzione multimodale; questo è importante, perche esse sono l’unico tipo di funzioni che vengono processate con gli algoritmi genetici, in quanto problemi più semplici possono essere risolti più facilmente con altri metodi.

Se queste regole sono rispettate, l’algoritmo sarà efficiente come predetto dal teorema dello schema. Sfortunatamente le condizioni precedenti sono difficili da incontrare e spesso i geni possono essere correlati in modo che non sia possibile metterli vicino in una stringa monodimensionale (per esempio se sono collegati gerarchicamente). In molti casi, l’esatta natura del legame tra i geni può non essere conosciuto dal programmatore, così anche se sono relazioni semplici, può essere impossibile arrangiare la codifica per mostrarle.

Inoltre, la seconda condizione costituisce una precondizione per la prima: infatti, se il contributo per il fitness totale di ogni gene fosse indipendente dagli altri geni, allora sarebbe possibile risolvere il problema con l’hillclimbing, ossia la ricerca costante della soluzione migliore, cercando su ciascun gene alla volta. Chiaramente non è attuabile in generale: se esistesse la certezza che ogni gene interagisce solo con un piccolo numero di altri geni e questi potessero essere messi vicini nel cromosoma, allora le due precedenti condizioni sarebbero verificate. Ma se c’è molta interazione tra i geni, nessuna delle due condizioni può essere incontrata. Si dovrebbe, quindi, cercare di disegnare gli schemi di codifica in modo da conformarsi alle raccomandazioni di Goldberg, poichè si avrebbe la certezza che l’algoritmo funzionerà nel modo migliore possibile.

Da qui nascono due interessanti domande: se ciò non è possibile, può un algoritmo genetico essere modificato in modo da migliorare il suo funzionamento in queste circostanze? E, se sì, come? Queste domande sono entrambe argomento di ricerca.

Epistasis

Il termine epistasi è stato definito dai genetisti per indicare il fatto che l’influenza di un gene nel fitness di un individuo dipende da quali valori dei geni sono presenti altrove. Più specificatamente i genetisti usano questo termine nel senso di un effetto di mascheramento o di cambiamento. Un gene è detto epistatico quando la sua presenza inibisce l’effetto di un altro gene in un altro locus. I geni epistatici sono alcune volte chiamati geni inibitori, a causa dei loro effetti sugli altri geni che sono descritti come ipostatici.

Generalmente ci saranno interazioni molto più intricate e complesse tra un gran numero di geni che si sovrappongono. In particolare possono esistere le cosidette catene di influenza, in cui la produzione di una proteina è codificata da un gene che è coinvolto con una proteina prodotta da un altro gene per produrre un terzo prodotto, che a sua volta reagisce con altri enzimi prodotti da qualche altra parte… e così via.

Molti geni semplicemente producono proteine intermedie che sono usate da altri processi iniziati da altri geni. Quindi esiste un considerevole numero di interazioni tra geni nel corso della produzione del fenotipo, benche‘ i genetisti non possano riferirsi a questo come epistasi.

Quando i ricercatori di algoritmo genetico usano il termine epistasi, si stanno riferendo generalmente a una forte interazione tra geni, non solo celandone gli effetti, ma anche evitando di dare una precisa definizione. Si può comunque dire che l’epistasi è l’interazione tra due differenti geni in un cromosoma: questa definizione estende il concetto che il valore di un gene, ossia il valore della funzione di fitness, dipende dai valori di altri geni. Il grado di interazione sarà, in generale, differente per ciascun gene in un cromosoma. Se un piccolo cambiamento è dovuto a un gene ci si aspetta un cambiamento risultante nel fitness nel cromosoma, che può variare in accordo con i valori degli altri geni.

Per fare una breve classificazione, si possono distinguere tre livelli di interazione tra i geni a seconda dell’effetto che hanno nel fitness dei cromosomi:

• Livello 0: Nessuna Interazione. Un particolare cambiamento in un gene produce lo stesso cambiamento nel fitness.
• Livello 1: Leggera interazione. Un particolare cambiamento in un gene spesso produce un cambiamento nel fitness dello stesso segno o zero.
• Livello 2: Epistasi. Un particolare cambiamento in un gene produce un cambiamento nel fitness che varia in segno e magnitudine in base al valore di altri geni.

Normalmente, i ricercatori di algoritmi genetici utilizzano il termine epistasis per riferirsi al secondo livello di interazione.

Problemi nei quali tutti i geni sono di tipo 0 o 1 possono essere risolti semplicemente con varie, semplici tecniche, e non richiedono un algoritmo genetico. Questi, invece, possono migliorare tecniche semplici in problemi complessi di livello 2 esibendo molte interazioni tra i parametri, cioè con epistasi significante. Sfortunatamente, in accordo con la building block hypothesis, una delle richieste di base per il successo di un algoritmo è che ci deve essere una bassa epistasi: questo suggerisce quindi che essi non saranno efficienti nei problemi dove non sono necessari.

Deception (inganno)

Uno dei fondamentali principi degli algoritmi genetici è che i cromosomi che contengono schemi che sono contenuti nell’ottimo globale cresceranno in frequenza, come enunciato dalla Building Block Hypothesis. Eventualmente, per via del processo del crosover, questi schemi ottimi arriveranno assieme e il cromosoma dell’ottimo globale sarà costruito.

Ma se gli schemi che non sono contenuti nell’ottimo globale crescono in frequenza più rapidamente di quelli che vi sono contenuti, l’algoritmo si allontanerà dall’ottimo globale invece di avvicinarsi. Questo fenomeno è noto come deception, ed è uno speciale caso di epistasi: infatti la prima è strettamente collegata agli effetti dannosi dell’epistasi, ed è una condizione necessaria ma non sufficiente per la deception.

Un problema è detto deceptive (ingannevole) se il fitness medio degli schemi che non sono contenuti nell’ottimo globale è più alto della media di quelli che vi sono contenuti. Inoltre un problema è definito come completamente ingannevole se tutti gli schemi di basso ordine contenenti una soluzione sub-ottima sono migliori degli altri schemi che competono.

Affrontare l’epistasi

Il problema dell’epistasi può essere affrontato in due modi: come un problema di codifica, o come un problema teorico.

Se trattato come problema di codifica la soluzione è trovare una differente codifica e un metodo di decodifica che non esibisce epistasi: questa soluzione permetterà di usare un algoritmo genetico convenzionale.

Se questo non può essere fatto, è necessario utilizzare il secondo approccio. Vose e Liepins hanno mostrato che in principio alcuni problemi possono essere codificati in maniera che si possano trattare come il semplice problema di contare gli 1. Analogamente alcune codifiche possono essere fatte semplicemente usando crossover e mutazione appropriatamente progettati.

Così è sempre possibile rappresentare alcuni problemi con epistasi assente o piccola. Comunque, per problemi difficili lo sforzo coinvolto nell’inventare questa codifica sarà considerevole e costituirà effettivamente la soluzione del problema iniziale.

La teoria tradizionale degli algoritmi genetici basata sul teorema degli schemi, si basa sulla bassa epistasi. Se i geni in un cromosoma hanno alta epistasi, deve essere sviluppata una nuova teoria e inventati nuovi algoritmi, per agire in queste condizioni. L’ispirazione deve venire ancora una volta dalla genetica della natura dove l’epistasi è molto comune.

Per ridurre l’epistasi nel cromosoma si è trovato utile convertire il problema in un altro, basato sull’ordine. Per esempio si converte un problema bin-packing, dove deve essere trovata l’ottima disposizione di rettangoli nello spazio, in un problema di ordine, dove invece deve essere trovato l’ordine del packing dei rettangoli. Però ogni volta che si effettua questa conversione bisogna modificare la teoria degli algoritmi genetici: ad esempio Goldberg ha suggerito come la teoria tradizionale può essere adattata per trattare problemi basati sull’ordine introducendo l’idea di schemi di ordine processati con il PMX crossover in analogia al crossover tradizionale e ai normali schemi.

Conclusioni

In questo secondo articolo si sono analizzate le basi teoriche su cui si fondano i principi degli algoritmi genetici. Nei prossimo articolo verrà presentato il panorama generale in cui si collocano questo genere di algoritmi. In particolare, effettueremo un confronto tra algoritmi genetici e altre tecniche che affrontano gli stessi problemi.

Riferimenti

[1]    Holland J, “Adaptation in Natural and Artificial Systems”, University of Michigan Press, 1976

[2]    Man K.F, “Genetic Algorithms”, Springer-Verlag London Limited, 1999

Luana Rinaldi

Luana Rinaldi è nata a Napoli nel 1980. Si è laureata in Ingegneria Informatica presso l‘Università degli studi di Roma Tre, portando avanti una tesi di ricerca in bioinformatica.

Dal 2000 si occupa professionalmente di analisi, progettazione e sviluppo di applicazioni in linguaggio Java con una particolare attenzione alle tecnologie open source più innovative.