Epistasis
Il termine epistasi è stato definito dai genetisti per
indicare il fatto che linfluenza 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 leffetto
di un altro gene in un altro locus (per locus si intende la
posizione allinterno del cromosoma). 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 ci sono catene di influenza 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 cè
un considerevole numero di interazioni tra geni nel corso della
produzione del fenotipo, benché i genetisti non possano
riferirsi a questo come epistasi.
Quando i ricercatori di GA 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. Comunque possiamo dire che lepistasi
è linterazione tra due differenti geni in un cromosoma.
Questo estende il concetto che il valore di un gene (fitnees)
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 aspettiamo un
cambiamento risultante nel fitness nel cromosoma. Questo
cambiamento può variare in accordo con i valori degli altri geni.
Per fare una breve classificazione distinguiamo tre livelli di
interazione tra i geni a seconda delleffetto 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 nel segno e
magnitudine, in base al valore di altri geni.
Un esempio di problema a livello zero è il semplice problema del
contare i bit 1, dove il fitness è proporzionale al
numero di 1 nella stringa binaria. Un esempio del livello 1 è la
funzione plateau, dove tipicamente cinque bit sono
decodificati in modo che il fitness sia 1 se tutti i bit sono 1,
e 0 se sono tutti 0.
Quando i ricercatori di GA usano il termine epistasi
si vogliono generalmente riferire al livello 2 e anche noi
useremo questa definizione.
Problemi nei quali tutti i geni sono di tipo 0 o 1 possono essere
risolti semplicemente con varie, semplici tecniche come lo scalatore
non richiedono un GA. Gli algoritmi genetici 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 GA
è che ci deve essere una bassa epistasi. Questo suggerisce che i
GA non saranno efficienti nei problemi dove non sono necessari.
Chiaramente, lepistasi è un argomento chiave per i
ricercatori. Ci serve sapere come evitarla oppure come costruire
un GA che lavorerà bene con alta epistasi.
Deception (inganno)
Uno dei fondamentali principi dei GA è che i cromosomi che
contengono schemi che sono contenuti nellottimo globale
cresceranno in frequenza (questo è vero soprattutto per schemi
piccoli e di ordine basso, noti come building block).
Eventualmente, per via del processo del crosover, questi schemi
ottimi arriveranno assieme e il cromosoma dellottimo
globale sarà costruito. Ma se gli schemi che non sono contenuti
nellottimo globale crescono in frequenza più rapidamente
di quelli che vi sono contenuti, il GA si allontanerà dallottimo
globale invece di avvicinarsi. Questo è noto come deception ed
è uno speciale caso di epistasi (infatti la prima è
strettamente collegata agli effetti dannosi dellepistasi- le.
è una condizione necessaria ma non sufficiente per la deception).
Statisticamente uno schema crescerà in frequenza su una
popolazione se il suo fitness è più alto della media di tutti
gli altri (per fitness di uno schema si intende la media o
il valore atteso- dei cromosomi che contengono quello schema).
Un problema è detto deceptive (ingannevole) se
il fitness medio degli schemi che non sono contenuti nellottimo
globale è più alto della media di quelli che vi sono contenuti.
Inoltre un problema è definito completamente ingannevole
se tutti gli schemi di basso ordine contenenti una soluzione sub-ottima
sono migliori degli altri schemi che competono.
I problemi ingannevoli sono difficili da risolvere, ma G. ha
dimostrato che non ci troviamo sempre in questo caso.
Affrontare lepistasi.
Il problema dellepistasi può essere affrontato in due
maniere: come un problema di codifica, o come un problema teorico
dei GA. Se trattato come problema di codifica la soluzione è
trovare una differente codifica (rappresentazione ) e un metodo
di decodifica che non esibisce epistasi. Questo permetterà di
usare un GA convenzionale. Se questo non può essere fatto si usa
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 nellinventare questa codifica sarà
considerevole e costituirà effettivamente la soluzione del
problema iniziale.
La teoria tradizionale dei GA 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. Lispirazione
deve venire ancora una volta dalla genetica della natura dove lepistasi
(nel senso dei GA) è molto comune.
Per ridurre lepistasi nel cromosoma si è
trovato che è utile convertire il problema in
un altro basato sullordine. Per esempio si converte un
problema bin-packing, dove deve essere trovata lottima
disposizione di rettangoli nello spazio, in un problema di
ordine, dove invece deve essere trovato lordine
del packing dei rettangoli.
Però ogni volta che facciamo questa conversione bisogna
modificare la teoria dei GA ad esempio G. ha suggerito come la
teoria tradizionale può essere adattata per trattare problemi
basati sullordine introducendo lidea di schemi
di ordine processati con il PMX crossover in analogia al
crossover tradizionale e ai normali schemi.