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 (per locus si intende la posizione all’interno 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 l’epistasi è l’interazione 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 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 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,  l’epistasi è 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 nell’ottimo 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 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, il GA si allontanerà dall’ottimo globale invece di avvicinarsi. Questo è noto come deception ed è uno speciale caso di epistasi  (infatti la prima è strettamente collegata agli effetti dannosi dell’epistasi- l’e. è 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 nell’ottimo 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 l’epistasi.

Il problema dell’epistasi 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 nell’inventare 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. L’ispirazione deve venire ancora una volta dalla genetica della natura dove l’epistasi (nel senso dei GA) è molto comune.
Per ridurre  l’epistasi nel cromosoma  si è trovato che è 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 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 sull’ordine introducendo l’idea di schemi  di ordine processati con il PMX crossover in analogia al  crossover tradizionale e ai normali schemi.