Inversione e Ordinamento
E stato già detto che lordine dei geni in un
cromosoma è critico perché la building block hypothesis
funzioni efficientemente. Tecniche per riordinare le posizioni
dei geni durante lesecuzione sono state suggerite. Una
tecnica è linversione che lavora invertendo lordine
dei geni tra due posizioni scelte casualmente allinterno
del cromosoma (quando queste tecniche sono usate, i geni devono
trasportare con loro alcuni tipi di etichette in modo che loro
possano essere identificati correttamente non curandoci le altre
posizioni allinterno del cromosoma).
Il fine del riordinamento è di cercare di trovare ordinamenti di
geni che anno potenziale evolutivo migliore. Molti ricercatori
hanno usato linversione nei loro lavori, sebbene non lo
abbiano abbastanza giustificato o quantificato il suo
contributo. Goldberg e Bridges analizzano un operatore di
riordinamento in un task molto piccolo e mostrano che questo può
portare vantaggi, sebbene concludono che i loro metodi non
potrebbero portare gli stessi vantaggi in un task più grande.
Il riordinamento non fa niente per una bassa epistasis (vedi
avanti), 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, lordine del gene è
irrilevante quindi non è necessario il riordinamento. Quindi
Syswerda si domanda: perché non insieme allinversione?
Il riordinamento espande lo spazio di ricerca in modo molto
grande. Non solo il GA cerca dei buoni set di
valori di geni, ma simultaneamente cerca di ordinarli in maniera
opportuna. Questo è un problema molto più difficile da
risolvere. 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 (evoluzione
karyotypic), linversione è 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 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.
Per la grande maggioranza delle applicazioni dei GA lambiente
espresso tramite la funzione fitness è statico. Prendendo
esempio dalla natura sembrerebbe che levoluzione karyotype
sia di poca importanza in questi casi. Comunque in applicazioni
dove la funzione fitness varia dopo tempo, e il GA deve fornire
una soluzione che può adattare allambiente che cambia, levoluzione
del cariotipo può valere la pena di essere rappresentata.
In un ambiente statico se noi vogliamo veramente determina re il
miglior ordinamento di geni (forse perché noi abbiamo un
gran numero di problemi, tutti con simili caratteristiche),
potremmo provare a usare un meta-GA, nella stessa maniera che
Grefenstette usa un meta-GA per determinare un buon set di
parametri. Un meta-GA ha una popolazione dove ciascun membro è
esso stesso un GA. Ciascun individuo GA è configurato per
risolvere lo stesso task ma usando parametri differenti (in
questo caso, differenti ordinamenti di geni). Il fitness di
ciascun individuo è determinato dallesecuzione del GA e
guardando quanto velocemente converge. I meta-GA sono ovviamente
molto costosi computazionalmente da eseguire, e sono solo più
utili se i risultati che producono possono essere utilizzati più
volte.