Capire la natura con gli Automi Cellulari

Gli Automi Cellulari, un mondo matematico affascinante di cui non si parla molto, ma che certamente conoscerete o quantomeno avrete sentito. L’articolo è frutto di quanto sono riuscito a raccogliere in internet , spero che vi appassioni quanto ha appassionato me.

Prima di iniziare a leggere l’articolo consiglio la visione di questo video su YouTube:

Un automa cellulare è un sistema dinamico discreto. Spazio, tempo e stati del sistema sono discreti.

Perché sono interessanti? L’interesse principale per gli automi cellulari è dovuto al fatto che essi forniscono uno strumento matematico utile per la risoluzione di problemi fisici e naturali troppo complessi per essere affrontati tramite gli strumenti matematici tradizionali.

Ogni elemento dell’automa in una griglia spaziale regolare è detto cella e può essere in uno degli stati finiti che la cella può avere.

Gli stati delle celle variano secondo una regola locale, cioè lo stato di una cella ad un dato istante di tempo dipende dallo stato della cella stessa e dagli stati delle celle vicine all’istante precedente.

Gli stati di tutte le celle sono aggiornati contemporaneamente in maniera sincrona. L’insieme degli stati delle celle compongono lo stato dell’automa. Quindi, lo stato globale dell’automa evolve in passi temporali discreti.

Secondo questo modello un sistema viene rappresentato come composto da tante semplici parti ed ognuna di queste parti per evolvere ha una propria regola interna ed interagisce solo con le parti ad essa vicine.

L’evoluzione globale del sistema emerge dalla evoluzione di tutte le parti elementari.

Gli Automi Cellulari possono essere pensati come dei sistemi dinamici astratti che giocano un ruolo nella matematica discreta comparabile a quello delle equazioni differenziali parziali nella matematica del continuo.

Molti studiosi sono dell’opinione che le applicazioni più significative della teoria degli Automi Cellulari si avranno nella produzione di modelli in grado di simulare il comportamento intrinseco distribuito e di auto-organizzazione.

Il concetto di automa cellulare fa la sua comparsa nell’ambiente scientifico nel 1947 allorché ci si propose di studiare la complessità dei fenomeni biologici e in particolare i meccanismi di funzionamento e auto-riproduzione degli esseri viventi.

Già i primi studiosi di cibernetica cominciarono ad intuire la capacità di alcuni meccanismi di svolgere funzioni tipicamente umane, in modo particolare quelle relative ad alcune attività mentali elementari.

Il disegno sulla sinistra si produce eseguendo il più semplice automa cellulare non banale, la regola che, nella numerazione di Stephen Wolfram, occupa il trentesimo posto. Autore di Mathematica, il programma di calcolo e visualizzazione con cui è stato realizzato il disegno, Wolfram ha reso celebre questa regola nel suo libro A New Kind of Science (2002). Sulla destra in alto, la foto di una conchiglia tropicale (Conus textile). Sotto, il guscio della conchiglia simulato al computer. via

Col termine Automa si intende il modello astratto di un dispositivo il quale può assumere certi stati, può ricevere stimoli (input) secondo una scala discreta del tempo dall’ambiente in cui è immerso e reagisce a questi stimoli con una transizione di stato e con una risposta (output) secondo una logica prefissata.

Formalmente un automa consiste in una quintupla (X, Y, Q, t , s ) dove

• X è l’insieme finito dei simboli di input
• Y è l’insieme finito dei simboli di output
• Q è l’insieme degli stati interni dell’automa
• t : Q x X ® Q è la funzione di transizione di stato che programma la trasformazione degli stati in funzione dell’input
• s : Q x X ® Y è la funzione di uscita che programma l’uscita in funzione dell’input e dello stato interno.

Da tale definizione di deduce che un automa è completamente noto se si conosce il modo in cui reagisce ad ogni possibile assegnazione di input.

La sua effettiva realizzabilità è legata al fatto che il numero degli stati interni sia finito: si parla in questo senso di automa finito.

Un caso particolare di automa è fornito dalla Macchina di Turing.
Intuitivamente, un automa cellulare può essere pensato come una rete infinita di piccoli e identici automi finiti, o celle, connessi uniformemente e sincronizzati.

Il termine cellulare si riferisce alla sotto-unità ottenuta da tale costruzione e non deve implicare necessariamente una analogia con le cellule degli organismi viventi.
Ciascuna di queste sotto-unità è detta anche Automa Elementare (AE).

L’insieme delle celle formano uno spazio euclideo d-dimensionale. Ad ognuno di questi siti è associata una variabile stato, chiamato stato della cella, che può assumere valori in un insieme finito detto l’insieme degli stati.

Il tempo avanza in passi discreti.

L’evoluzione del sistema è dovuta ad una unica funzione, detta funzione di transizione, che viene usata ad ogni passo da ogni cella per determinare il suo nuovo stato a partire dallo stato corrente e dagli stati di alcune celle che compongono un vicinato della cella stessa. Il passaggio da uno stato a quello successivo è dovuto alla composizione di due operatori, il vicinato, che specifica quali celle influiscono sulla data cella, e la funzione di transizione.

Il vicinato o intorno della cella specifica le posizioni, relative alla cella generica, di un numero finito di celle. Tali vicini non necessitano di essere quelli fisicamente adiacenti, possono includere la stessa cella, oppure celle fisicamente distanti dalla cella considerata, l’importante è che le celle che compongono il vicinato siano in numero finito, e che il tipo di vicinato sia uguale per ogni cella che compone l’automa cellulare. Gli stati delle celle dell’intorno sono usati nella regola di transizione della cella centrale per calcolare il suo nuovo stato. In un automa cellulare gli intorni delle celle si sovrappongono e una data cella viene inclusa in diversi intorni delle celle ad essa adiacenti.

Una assegnazione di stati a tutte le celle è chiamata configurazione.

Un automa cellulare è reversibile o invertibile se la sua mappa globale è invertibile, cioè se ogni configurazione ha un unico successore ed un unico predecessore.
Automa Cellulare “reversibile”:

• Un automa reversibile che sia fatto evolvere da qualsiasi configurazione di partenza, per un qualsiasi numero di passi, se poi viene fermato e fatto evolvere all’inverso, per lo stesso numero di passi, tornerà alla configurazione iniziale.

Nel contesto dei sistemi dinamici, l’invertibilità coincide con quello che i fisici chiamano reversibilità microscopica.

Le configurazioni formate da un automa reversibile tipico hanno un aspetto qualitativamente differente rispetto alle configurazioni caratteristiche di un automa non reversibile. In particolare, se la configurazione iniziale è casuale, essa tende a rimanere casuale, cioè non compare nessuna struttura di auto-organizzazione.

Le regole di un automa cellulare sono locali (nessuna interazione a lunga distanza) e uniformi (la stessa regola è applicata a tutte le celle in un dato istante di tempo).
Tramite la funzione di transizione si può costruire l’esatta evoluzione del sistema in un tempo finito arbitrariamente grande.

Un esempio di semplice Automa Cellulare molto conosciuto è il Gioco della Vita o Life proposto da John Horton Conway.

Life simula una popolazione di organismi viventi o celle in una griglia bidimensionale che si sviluppano nel tempo sotto l’effetto di tendenze all’accrescimento ed all’estinzione. Ogni cella può avere due stati: vivente (1) o morta (0) ed ha un vicinato composto dalle otto celle adiacenti.

Le celle cambiano stato in base alle regole seguenti:

1. Una cella vivente può sopravvivere nella prossima generazione se e solo se ha 2 o 3 celle viventi nel proprio vicinato.
2. Una cella morta può tornare in vita nella prossima generazione se e solo se ha esattamente 3 celle viventi nel proprio vicinato.

In base a queste semplici regole, Conway ha costruito un automa cellulare molto interessante per gli effetti che si hanno nell’evoluzione di una popolazione di organismi viventi.

Rispetto alla definizione di automa cellulare standard, nel tempo sono state date delle definizioni sia in termini di modifiche strutturali che di estensioni funzionali.

Con il termine modifiche del modello degli Automi Cellulari ci si vuole riferire a modelli computazionali che differiscono dal modello degli Automi Cellulari, ma che possono simulare gli automi cellulari e possono essere simulati dagli automi cellulari con un costo addizionale lineare sia nel tempo sia nel numero di celle.

Con il termine estensioni o generalizzazioni del modello degli Automi Cellulari ci si riferisce a modelli computazionali che non possono essere simulati dagli Automi Cellulari in un tempo lineare. Mentre una modifica rappresenta solo un formalismo differente per definire la stessa cosa, una estensione è generalmente più potente del modello standard degli automi cellulari.

Esistono altri tipi di Automi Cellulari molto interessanti che qui di seguito elenco:

• Automi Cellulari non deterministici: rappresentano una generalizzazione del modello standard degli automi cellulari.

L’estensione importante consiste nel fatto che la funzione di transizione elementare di un automa non deterministico può generare stati scelti in maniera non deterministica in uno spazio degli stati molto più ampio.

• Automi Cellulari partizioni: rappresentano solo una modifica del modello standard. In un automa cellulare standard, una cella usa tutto lo stato delle celle del suo vicinato per calcolare il suo nuovo stato. In un automa cellulare partizionato, una cella legge solo la componente i-esima dello stato della cella i del suo vicinato.

Da un punto di vista pratico, gli automi cellulari partizionati hanno il vantaggio che il dominio della funzione di transizione ha una dimensione minore che nel caso standard.

Questo tipo di automi cellulari restringe i dati di input per la funzione di transizione di una cella, che riceve solo una parte di informazione da ognuna delle celle vicine. Questa proprietà in alcuni casi, in particolare nei casi in cui lo stato delle celle è complesso, può rendere possibile l’implementazione della funzione di transizione che nel caso standard sarebbe impossibile implementare a causa della dimensione del suo dominio.

• Automi Cellulari probabilistici: presentano delle similitudini con quelli non deterministici, seppure essi siano differenti. Gli automi cellulari probabilistici sono stati definiti per simulare fenomeni probabilistici osservati in natura. Ad esempio, fenomeni probabilistici si hanno nei gas reticolari dove certe configurazioni locali possono portare lo stato di una cella verso due possibili stati differenti con uguale probabilità. In un automa cellulare probabilistico, data una cella ed una particolare configurazione delle celle ad essa vicine, viene definita una probabilità per ogni possibile nuovo stato in cui una cella si potrà trovare nella prossima iterazione.

• Automa Cellulare asincrono: una cella ad ogni iterazione può decidere in maniera non deterministica se cambiare il proprio stato in base alla funzione di transizione oppure mantenere lo stato corrente. Negli automi cellulari asincroni la funzione di transizione elementare è simile a quella del modello standard, tuttavia la definizione della funzione di transizione globale è differente.

Questa classe di automi cellulari rappresenta una modifica rispetto al modello standard in quanto rilascia il vincolo dell’aggiornamento dello stato in maniera sincrona per tutte le celle e rappresenta un utile modello computazionale in quei casi in cui si simulano sistemi asincroni nei quali non è necessario che lo stato di tutte le componenti sia aggiornato contemporaneamente.

• Automi cellulari inomogenei: sono una generalizzazione degli automi cellulari standard, infatti essi sono computazionalmente più potenti. Negli automi cellulari si può non avere omogeneità sia dal punto di vista spaziale sia dal punto di vista temporale, ed ognuno di questi due casi non esclude l’altro. Nel caso di automi cellulari inomogenei spazialmente la funzione di transizione elementare delle celle può variare al variare delle coordinate delle celle. Quindi l’automa non è caratterizzato da una unica funzione s ma da un certo numero di differenti funzioni di transizione per differenti celle o regioni dell’automa ed a queste possono essere associate differenti relazioni di vicinato. Gli automi inomogenei spazialmente sono utili quando si vuole simulare sistemi in cui alcune loro parti svolgono un ruolo particolare, come una sorgente di particelle o un cratere di un vulcano, oppure quando si vuole restringere la computazione in una regione limitata dell’automa.

Nel caso di automi cellulari inomogenei temporalmente la funzione di transizione elementare delle celle può variare al variare del tempo. In questo caso le celle dell’automa possono aggiornare il loro stato per un certo numero di passi usando una funzione di transizione e poi per un altro numero di passi usando una diversa funzione di transizione e così via in funzione della computazione che l’automa cellulare deve eseguire.

Questo tipo di automi inomogenei sono utili nel caso in cui si vogliono simulare fenomeni che sono composti da più fasi computazionali tra loro differenti ed una di seguito all’altra.

• Automi Cellulari gerarchici: si intende automi cellulari in cui le singole celle non sono atomiche, ma sono composte da parti più semplici e quindi lo stato di una cella dipende dallo stato delle sue parti. Esso è basato sulla struttura di un grafo annidato, cioè un grafo composto da vertici ed archi, dove ogni vertice è a sua volta un grafo annidato. Gli automi cellulari gerarchici sono stati introdotti come modelli computazionali per sistemi multi-scala e per la simulazione di sistemi biologici multi-livello. In questi casi si ha a che fare con fenomeni composti in cui la scala del tempo e dello spazio per i sotto-fenomeni componenti sono molto differenti.

Il Cannone di Gosper, un classico esempio di automa cellulare in azione.

Lo strumento più usato per costruire un modello matematico del mondo naturale è fornito dalle equazioni differenziali, le quali possono descrivere il cambiamento di una certa grandezza come funzione della posizione e del tempo. In esse, le grandezze variano con continuità.

Studiare lo stesso problema in modo discreto spesso è più semplice e naturale. Il fatto che lo spazio reale, il tempo e molte variabili fisiche siano ritenuti continui anziché discreti non implica, generalmente, che le equazioni differenziali portino di per sé a dei modelli della natura più validi: spesso non è il valore numerico di una variabile ad essere significativo ma solo la dimensione globale.

Gli automi cellulari sono essenzialmente caratterizzati da quattro proprietà:

1. La geometria della matrice delle celle
2. L’intorno o vicinato di ogni cella
3. Il numero di stati per cella
4. La varietà delle regole di transizione

La geometria della matrice delle celle può essere bidimensionale tridimensionale o multidimensionale (a n dimensioni).

L’intorno di una cella può comprendere le celle fisicamente adiacenti oppure le celle determinate tramite una funzione metrica (distanza) definita nello spazio delle celle.

Si possono avere automi cellulari binari in cui vi sono solo due stati per cella (1 o 0) oppure si possono definire automi cellulari con un numero molto elevato di stati possibili. Per la simulazione di sistemi che presentano una notevole complessità è necessario poter definire celle con un numero di stati elevato.

Il numero di regole necessarie per stabilire il prossimo stato di una cella cresce esponenzialmente rispetto al numero dei possibili stati della cella.

I modelli ottenuti con le varie regole di transizione sono caratterizzati dall’avere comportamenti complessi, in base ai quali gli automi cellulari vengono classificati in quattro classi fondamentali.

La classe 1 è composta dagli automi cellulari la cui evoluzione, qualsiasi sia la configurazione iniziale, dopo un numero finito di passi porterà l’automa in uno stesso stato stabile ed omogeneo oppure in un ciclo definito.

Gli automi cellulari della classe 2 fanno sì che il valore dello stato di una cella, dopo un certo tempo, sarà determinato dai valori iniziali di alcune celle situate in una regione limitata e connessa. La conoscenza dello stato iniziale di una piccola regione è sufficiente per predire lo stato finale di una data regione di celle. Di solito le regole di questa classe danno luogo a semplici strutture che possono essere stabili o periodiche e che rimangono isolate una dall’altra. Gli automi cellulari appartenenti a questa classe funzionano come filtri che generano strutture semplici a partire da particolari valori di stato iniziale, per questa ragione, essi appaiono particolarmente utili per l’elaborazione di immagini.

Negli automi cellulari della classe 3 il valore di una cella dipenderà dai valori iniziali di un sempre crescente numero di celle. Una predizione dello stato finale richiede la conoscenza completa dello stato iniziale. In un automa cellulare di questo tipo, per quasi tutti i possibili stati iniziali, l’evoluzione porterà a configurazioni caotiche (aperiodiche) anche se non casuali. Dopo un numero sufficientemente grande di passi, le proprietà statistiche di queste configurazioni sono praticamente uguali per quasi tutti i possibili stati iniziali.

Negli automi cellulari della classe 4, ci sono poche regole di transizione che generano strutture di sostanziale complessità spaziale e temporale. Per questa classe di automi, in molti casi tutte le celle variano il loro stato dopo un numero finito di passi. In alcuni casi si osservano strutture periodiche o stabili che persistono per un numero elevato di passi. In altri casi si osservano delle strutture che si propagano.

Negli automi di classe 4, il valore di una cella dopo un numero grande di passi, dipende dal valore di un numero crescente di stati iniziali di altre celle. Il valore dello stato di una cella non può essere determinato tramite una procedura di calcolo più semplice della simulazione della sua evoluzione. Il comportamento degli automi cellulari della classe 4 non è predicibile anche conoscendo la configurazione degli stati iniziali.

Supponiamo di assegnare ad un automa cellulare una qualche configurazione iniziale scelta a caso e di farlo evolvere per molti passi nel tempo e quindi di registrare lo stato finale. Si torni ora alla configurazione di partenza, si cambi il valore di una singola cella e si faccia evolvere il sistema per lo stesso numero di passi.

Che effetto avrà il piccolo cambiamento sullo stato finale?

Per un automa della classe 1 non c’è alcuna conseguenza, infatti un sistema della prima classe raggiunge lo stesso stato finale indipendentemente dallo stato iniziale.

Un automa della classe 2 può mostrare qualche effetto, ma limitato ad una piccola area vicino al sito in cui è avvenuto il cambiamento.

In un sistema della classe 3, invece, l’alterazione di una singola cella può provocare un cambiamento che si propaga lungo tutto il reticolo.

Le regole della classe 4 sono le più rare e le più interessanti.

Alcune funzioni di transizione piuttosto semplici ricadono in questa classe. La sensibilità a piccole variazioni nelle condizioni iniziali è ancora maggiore che nella terza classe. Si ritiene che per prevedere lo stato futuro di un automa cellulare della quarta classe non vi sia nessuna procedura generale più efficace di quella che consiste nel lasciare all’evoluzione dell’automa stesso il compito di calcolare lo stato.

Una ipotesi legata alla considerazione precedente suggerisce che gli automi cellulari infiniti della classe 4 possano essere considerati dei calcolatori universali.
In base a questa ipotesi, gli automi cellulari della classe 4 sarebbero i più semplici calcolatori universali conosciuti.

Gli automi cellulari capaci di svolgere la computazione universale possono imitare il comportamento di qualsiasi calcolatore.

Supponendo che qualunque processo fisico possa essere rappresentato da un processo computazionale (come sembra verosimile ipotizzare), gli automi cellulari possono imitare anche il comportamento di qualunque sistema fisico.

Recentemente sono state proposte delle reti neurali cellulari. Le reti neurali cellulari (cellular neural networks CNN) sono un modello di elaborazione proposto da Chua e Yang nel 1988 definito come un insieme di circuiti non lineari in uno spazio n-dimensionale con una struttura di elaborazione parallela ed asincrona. Una CNN è un modello di rete neurale in cui ogni unità (cella o neurone) è connessa solo ad altre unità appartenenti ad una zona della rete ad essa contigua detta vicinato o intorno.

Le reti neurali cellulari sono un modello di calcolo che riassume alcune caratteristiche tipiche delle reti neurali e degli automi cellulari.

Infatti, una caratteristica delle CNN è la località delle connessioni tra le unità. In questo tipo di reti neurali l’informazione viene scambiata direttamente solo tra unità vicine. Questa caratteristica li rende in qualche modo simili agli automi cellulari e le differenzia dagli altri modelli di reti neurali proposti in letteratura.

Il fatto che la comunicazione sia locale non limita le capacità computazionali delle CNN, infatti è stato dimostrato che il modello CNN è universale essendo equivalente ad una macchina di Turing.

Le principali caratteristiche di una rete neurale cellulare sono:

• Una CNN è una griglia regolare n-dimensionale di elementi detti celle
• Ogni cella costituisce un elemento di elaborazione con più input e un singolo output
• Una cella è caratterizzata da un vicinato e da uno stato interno che in alcuni casi non è osservabile dall’esterno della cella
• I dati ed i parametri di una CNN hanno generalmente valori continui
• Una CNN può operare sia con valori temporali continui sia con valori temporali discreti
• Può essere definita più di una rete di connessione tra le celle con differenti dimensioni di vicinato
• Le CNN elaborano per più di una interazione e quindi appartengono alla classe delle reti di tipo recurrent.

Se il raggio r che definisce il vicinato è sufficientemente grande da fare in modo che il vicinato di ogni cella copra tutta la rete, una CNN viene sostanzialmente a coincidere con una rete di Hopfield a valori continui, in questo caso una CNN viene utilizzata come una memoria associativa.

I modelli di automa cellulare e rete CNN condividono la località delle connessioni come base topologica. Al contrario delle CNN, negli automi cellulari lo stato di ogni cella ha valori discreti. Le funzioni di transizione per gli automi cellulari, che sono definite da tavole di verità, possono essere paragonate alle maschere per le CNN a tempo discreto, in tal modo si mantiene una stretta analogia progettuale.

Le reti CNN sono un interessante e promettente incrocio tra i concetti di automa cellulare e rete neurale.

Le reti neurali rappresentano un modello di calcolo parallelo.

Il loro utilizzo per l’implementazione di applicazioni reali richiede l’utilizzo di sistemi di calcolo a parallelismo massiccio.

Nei sistemi ad elevato parallelismo una applicazione viene realizzata tramite un insieme di processi concorrenti che cooperano tramite lo scambio di messaggi.

Questo approccio metodologico si basa sul progetto e lo sviluppo di programmi concorrenti che implementano i vari modelli di reti neurali utilizzando la potenza computazionale offerta dalle macchine parallele composte da un elevato numero di nodi di elaborazione.

Non esiste un unico modo di implementare in maniera parallela una rete neurale e tra i vari modi esistenti non si può facilmente individuare quale di essi è il migliore in generale.

In una rete neurale ogni neurone potrebbe rappresentare una attività parallela; in pratica ciò non viene realizzato poiché la granularità del parallelismo esplicitabile dai sistemi paralleli è maggiore di quello di un singolo neurone ed in generale il numero dei processori è minore del numero di neuroni della rete che occorre implementare. Inoltre, i processori presentano un grado di interconnessione limitato rispetto al grado di interconnessione delle reti neurali. Nella realizzazione di reti neurali occorre usare delle metodologie per decomporre la rete e mappare i neuroni che la compongono sui nodi di elaborazione del sistema parallelo.

Per risolvere problemi reali occorrono reti neurali di grandi dimensioni, i sistemi paralleli possono offrire il supporto computazionale necessario.

Un diverso approccio, e complementare, alla ricerca di modelli computazionali nell’ambito dei sistemi complessi ci deriva dagli algoritmi genetici.

Recentemente, gli algoritmi genetici sono stati utilizzati con sempre maggiore frequenza in molti settori scientifici e ingegneristici per la loro capacità di risolvere problemi complessi. Inizialmente, il loro principale campo applicativo è stato quello dei problemi di ottimizzazione, ma rapidamente essi hanno mostrato di essere adatti a risolvere problemi in molti altri settori: robotica, machine vision, machine learning, data mining, evoluzione degli automi cellulari, apprendimento sia della topologia sia dei pesi delle reti neurali, sistemi intelligenti, evoluzione della cooperazione e comunicazione in sistemi multi-agenti.

Gli algoritmi genetici sono algoritmi di ricerca general-purpose che si ispirano ai meccanismi dell’evoluzione per affrontare la risoluzione di problemi complessi. In essi, come negli organismi viventi, l’evoluzione avviene attraverso due processi fondamentali: la selezione naturale e la riproduzione sessuale. Il processo di selezione determina quali elementi di una popolazione debbano sopravvivere per riprodursi, mentre il processo di riproduzione garantisce il mescolamento e la ricombinazione dei geni dei loro discendenti.

L’idea che è alla base degli algoritmi genetici è quella di far evolvere una popolazione di elementi, che rappresentano le soluzioni candidate di uno specifico problema, sia tramite competizione (favorendo la sopravvivenza delle soluzioni migliori) sia attraverso meccanismi di ricombinazione e mutazione.

Studi teorici hanno mostrato che il vantaggio computazionale degli algoritmi genetici, rispetto ad esempio alla ricerca di tipo random, è che essi tendono ad indirizzare la ricerca verso le regioni dello spazio delle soluzioni più promettenti (ad elevata fitness) utilizzando ad ogni generazione la conoscenza accumulata durante la ricerca precedente.

Un ulteriore aspetto interessante degli algoritmi genetici è che essi utilizzano un modello di computazione parallela in cui gli elementi di una popolazione evolvono in parallelo. Questa caratteristica li rende adatti ad essere implementati su macchine parallele e a trattare problemi di notevole complessità.

L’algoritmo genetico è una procedura iterativa che usa una popolazione di cromosomiche si evolvono e si riproducono. Per consentire la riproduzione dei cromosomi più adatti l’algoritmo genetico usa una funzione di fitness che assegna un punteggio ad ogni cromosoma della popolazione corrente. La fitness indica la bontà con cui un cromosoma risolve uno specifico problema.

Per ricombinare e alterare i cromosomi della popolazione l’algoritmo genetico usa gli operatori genetici di: selezione, crossover e mutazione.

L’operatore di selezione provvede a scegliere i cromosomi nella popolazione per la riproduzione. Gli elementi sono selezionati e replicati in maniera proporzionale alla loro probabilità di riproduzione. La probabilità di riproduzione dipende dalla funzione di fitness, i cromosomi che hanno i valori di fitness più elevati hanno una maggiore probabilità di riprodursi.

L’operazione di crossover implementa la funzione di ricombinazione fra due cromosomi, detti genitori, attraverso lo scambio di porzioni delle stringhe che li rappresentano. I cromosomi genitori sono scelti a caso nella popolazione ed accoppiati in modo da generare due nuovi cromosomi detti figli.

L’operatore di mutazione si applica a tutti gli elementi della popolazione con una certa probabilità, detta di mutazione, cambiando il valore di un gene scelto in maniera casuale.
Volendo risolvere un problema attraverso un algoritmo genetico, la prima cosa che dobbiamo definire è il meccanismo di codifica che ci consente di rappresentare le variabili del problema nella forma che l’algoritmo genetico è in grado di manipolare. Sebbene esistano diverse codifiche la più usata è quella che utilizza stringhe di bit.

Il passo successivo è quello di definire una funzione di fitness che consenta all’algoritmo genetico di calcolare la bontà di ogni stringa della popolazione come probabile soluzione.

La risoluzione di problemi complessi attraverso gli algoritmi genetici richiede elevati tempi di calcolo che sono determinati principalmente dai tempi necessari per la valutazione della fitness e dall’elevato numero di iterazioni necessarie per trovare la soluzione, inoltre in un algoritmo genetico occorre generare intere popolazioni di soluzioni candidate per molte generazioni successive.

Ci sarebbe sicuramente molto altro da dire, ma non basterebbe un’intera enciclopedia ed io non ho certo le competenze per poterne continuare a parlare, vi ringrazio per la lettura e un grande saluto a tutti.

Per approfondire:

• Automa cellulare (wikipedia.it)
• Automi cellulari (istanze.unibo.it)
• Algoritmo genetico (wikipedia.it)
• Rete neurale (wikipedia.it)
• Automi cellulari monodimensionali (immaginarioscientifico.it)