Gli algoritmi genetici sono uno strumento di risoluzione di problemi complessi. In questo articolo prendiamo in esame un altro importante operatore di riproduzione, ossia la Mutazione. Questo ci consentirà di mettere infine a punto una codifica dell‘algoritmo.
Introduzione
Un altro importante operatore di riproduzione è la mutazione: consiste di un operatore comunque secondario, in quanto il crossover genera sicuramente molti più cambiamenti evolutivi nella popolazione, ma questo operatore ha il vantaggio di fornire delle soluzioni migliori, anche se queste vengono generate in un maggior numero di operazioni.
In questo articolo si analizza l’operatore di mutazione e vengono presentate alcune questioni legate alle tecniche di riproduzione, come la loro probabilità dinamica, l’elitismo e il problema delle nicchie e specificazioni. Infine viene presentato l’ultimo passo dell’algoritmo genetico, ossia la selezione degli individui da inserire nella popolazione per l’iterazione successiva.
Mutazione
La mutazione è tradizionalmente vista come un operatore secondario, responsabile di una reintroduzione inaspettata di valori di geni perduti, ad esempio alleli recessivi, che prevengono la deriva genetica e forniscono un piccolo elemento di ricerca casuale nella vicinanza della popolazione dove essa è largamente convergente. La mutazione viene considerato un operatore minore, in quanto generalmente si ritiene che sia il crossover la principale forza che guida la ricerca dello spazio del problema.
Figura 1 – Mutazione.
Comunque, gli esempi in natura mostrano che la riproduzione asessuata può produrre creature sofisticate senza il crossover: infatti i biologi considerano la mutazione come la principale fonte di materiale per i cambiamenti evolutivi. Gli esperimenti che sono stati fatti sull’ottimizzazione dei parametri per gli algoritmi genetici hanno mostrato che il crossover produce molti meno effetti di quanto si pensava, mentre l’evoluzione naive, che comprende solo selezione e mutazione, agisce in modo simile all’hillclimb e può essere potente anche senza il crossover. Il crossover infatti produce evoluzioni più veloci rispetto a una popolazione che ha solo mutazione, ma comunque la mutazione alla fine fornisce soluzioni migliori. Infatti Davis puntualizza che mentre la popolazione si avvicina alla convergenza la mutazione diventa più produttiva del crossover.
Nonostante la sua bassa probabilità di uso, la mutazione è un operatore molto importante; Spears ritiene che l’operatore mutazione opportunamente modificato può fare tutto quello che fa il crossover e dice anche che questi due operatori sono in realtà due forme di un più generale operatore di esplorazione.
Probabilità dinamica degli operatori
Durante l’esecuzione, il valore ottimale per la probabilità di ogni operatore può variare. Davis ha tentato variazioni lineari della probabilità di incrocio e mutazione, con l’incrocio decrescente durante l’esecuzione e la mutazione crescente. Una variazione lineare impone una schedulazione fissata, mentre potrebbe essere più vantaggioso usare un tasso di incrocio che varia dinamicamente in funzione della diffusione di idoneità. Quando la popolazione converge, il tasso di incrocio è ridotto per dare più opportunità alla mutazione di trovare nuove variazioni. Questo ha lo stesso effetto della tecnica di Davis, con il vantaggio di essere adattiva.
Davis descrive un’altra tecnica adattiva che è basata direttamente sul successo di un operatore nella produzione di una buona discendenza: viene dato del credito ad un operatore quando esso produce un cromosoma migliore di qualsiasi altro nella popolazione. Una figura di pesatura viene associata ad ogni operatore basandosi sulle prestazioni che questo ha offerto sugli ultimi 50 accoppiamenti: per ogni evento riproduttivo, è selezionato probabilisticamente un operatore singolo, in accordo all’insieme corrente di operatori pesati. Durante l’esecuzione, quindi, la probabilità degli operatori varierà in modo adattivo e dipendente dal problema.
Un grande vantaggio di questa tecnica è che permette ai nuovi operatori di essere direttamente confrontati con quelli esistenti: se un nuovo operatore perde consistentemente peso è probabile che sia meno efficiente di uno già esistente. Questa tecnica sembra avere la capacità di risolvere molti problemi che riguardano i settaggi di probabilità degli operatori.
Nicchia e speciazione
Negli ecosistemi naturali, ci sono molti modi differenti con i quali gli animali possono sopravvivere: cacciando sottoterra, brucando le foglie sugli alberi, pascolando e mangiando l’erba al suolo, e così via. Ogni specie differente si evolve per riempire ciascuna la sua cosiddetta nicchia ecologica. La speciazione è il processo nel quale una singola specie si differenzia in due o più specie che occupano differenti nicchie.
Negli algoritmi genetici, le nicchie rappresentano i massimi della funzione fitness: per garantire la localizzazione delle nicchie, si usano a volte delle funzioni di fitness multimodali. Sfortunatamente, gli algoritmi tradizionali, però, non riescono a fare questo, quindi ci si trova in una situazione in cui l’intera popolazione converge in un singolo picco.
Naturalmente, sarebbe necessario aspettarsi che la popolazione di un algoritmo genetico converga a un picco con alto fitness, ma possono esserci altri picchi uguale fitness e l’algoritmo andrà a finire su uno di questi: questo fenomeno è dovuto allo spostamento genetico. Sono state proposte alcune modifiche per l’algoritmo genetico canonico per risolvere questo problema, tutte basate sugli ecosistemi naturali, al fine di mantenere la diversità e per raggiungere il “costo” associato a una nicchia.
Cavicchio ha illustrato un meccanismo che ha introdotto la preselezione, in cui se un figlio ha un fitness maggiore del genitore con fitness più basso, lo rimpiazza: quindi c’è una competizione tra genitori e figli, il costo non viene condiviso, ma il vincitore lo prende tutto. Questo metodo aiuta la mantenere diversità in quanto le stringhe tendono a rimpiazzarne altre che sono simili a loro, e così si previene la convergenza in un singolo massimo.
Se nello spazio di ricerca esistono molti massimi locali con fitness vicino al massimo globale, il metodo delle nicchie può presentare diversi problemi. Una tecnica che distribuisce i membri della popolazione nei picchi in proporzione al fitness di questi ultimi non riesce a trovare facilmente il massimo globale se ci sono più picchi di quanti sono i membri della popolazione.
Un differente approccio è quello fornito da Breasley, Bull e Martin, noto come nicchie sequenziali, che si basa su esecuzioni multiple dell’algoritmo: ciascuna di esse localizza un picco e la sua funzione fitness viene modificata in modo che il picco venga cancellato: questa modalità operativa assicura che in una esecuzione successiva non venga ritrovato. L’algoritmo riparte quindi con una nuova popolazione e in questo modo viene localizzato un nuovo picco per ogni esecuzione.
Restricted Mating
Uno schema di mating restriction permette a un individuo di accoppiarsi con un altro solo se quest’ultimo appartiene alla stessa nicchia, oppure, se non ci sono altri nelle nicchia, con un individuo scelto a caso. Lo scopo è quello di incoraggiare la speciation e ridurre la popolazione di “letali”, cioè di individui figli di genitori di nicchie differenti. Infatti in questo caso, sebbene ciascun genitore possa avere alto fitness, la combinazione dei loro cromosomi può essere molto scadente se cade in una valle tra due massimi. La natura evita la formazione di “letali” evitando l’accoppiamento tra specie differenti o, anche nel caso si tratti di specie molto affini, rendendo sterili i figli che ne nascono.
La filosofia del Restricted Mating assume che se due genitori simili, cioè appartenenti alla stessa nicchia, sono accoppiati, allora i figli saranno simili a essi. Comunque questo dipende molto dallo schema di codifica, in particolare dall’esistenza di building block e bassa epistasi. Con queste ipotesi, usando gli operatori convenzionali di mutazione e crossover, due genitori con genotipo simile, produrranno sempre figli con genotipo simile. Ma se il cromosoma è altamente epistatico, non c’è garanzia che questi figli non abbiamo basso fitness, cioè siano letali, infatti somiglianze nel genotipo non implicano somiglianze nel fenotipo. Questi effetti limitano l’uso del restricted mating.
Elitismo
Quando si crea una nuova popolazione con crossover e mutazione si genera una grande probabilità di perdere il miglior cromosoma. L’elitismo è un metodo che prima copia il miglior cromosoma (o i pochi migliori) nella nuova popolazione e il resto viene fatto in maniera classica. L’elitsmo può far crescere rapidamente le performance degli algoritmi genetici perche’ evita la perdita della migliore soluzione trovata.
Tecniche basate sulla conoscenza
Molti ricercatori. al posto dei tradizionali operatori di crossover e mutazione. hanno designato dei nuovi operatori per ciascun task, usando la conoscenza del dominio. Questo rende ciascun algoritmo più specifico per il task, quindi meno robusto, ma può migliorare significativamente la performance. Quando un algoritmo genetico viene designato per affrontare un problema reale, e deve competere con altre tecniche di ricerca e ottimizzazione, l’utilizzo della conoscenza del dominio spesso ha senso.
La conoscenza del dominio può essere usata per scartare cromosomi poco adatti, o quelli che possono violare i vincoli del problema. Questo evita di perdere tempo a valutare questi individui e di introdurre individui scadenti nella popolazione.La conoscenza del dominio può essere utilizzata per introdurre operatori di miglioramento locale che mostrano esplorazioni più efficienti nello spazio della ricerca intorno a buoni punti. Questo può essere usato per fare inizializzazione euristica della popolazione, così la ricerca inizia con alcuni punti ragionevolmente buoni rispetto a un insieme scelto casualmente. Per aggiungere mutazione e crossover guidati dalla conoscenza si è proposta una ibridizzazione degli algoritmi genetici con altre tecniche di ricerca.
Selezione per rimpiazzamento
La selezione per il rimpiazzamento ha lo scopo di scegliere quali fra gli individui padri e gli individui figli costituiranno la nuova popolazione.
Nell’algoritmo genetico canonico, si assume che la generazione P(t+1) sia costituita dai figli, creati attraverso gli operatori di riproduzione, e da quegli individui nella popolazione intermedia P1 che non sono stati scelti per l’accoppiamento. Il numero di individui per ogni generazione è costante.
Un’altra possibilità è copiare un numero fissato di individui, ovviamente i migliori, da $P(t)$ in P(t+1) senza modificarli; ne consegue che questi individui parteciperanno anche alla selezione per la riproduzione.
Conclusioni
Con questo articolo si conclude l’analisi della pseudocodifica di un algoritmo genetico. Nel prossimo articolo verranno presentate alcune principali applicazioni pratiche di queste teorie, e successivamente, verrà presentata la progettazione e l’implementazione di alcuni metodi utilizzati dai GA.
Bibliografia
[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
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.