Tauon Barcadero

Archive for the ‘programmazione’ Category

Automi cellulari unidimensionali

with 3 comments

Automi di Wolfram

Gli automi cellulari unidimensionali sono uno degli esempi più ecclatanti di quanto delle regole di base molto semplici possano portare alla costruzione di pattern anche molto complicati, in special modo qui si parlerà degli automi studiati da Stephen Wolfram intorno agli inizi degli anni 80.

Regola 129

Gli automi sono distribuiti su una riga, da cui la classificazione di automi monodimensionali, e ognuno di essi può assumere due stati differenti rappresentabili con 1 e 0(bianco e nero). Data una configurazione di partenza della riga, la generazione successiva viene calcolata in modo dipendente dalla riga precedente attraverso le regole mostrate nell’immagine:

spiegazione regole generazione successiva Leggi il seguito di questo post »

Written by barcadero

8 agosto 2011 at 2:56 pm

La formica di Langton

leave a comment »

Un’altro automa cellulare

Come Life di Conway, anche la formica di Langton è un automa cellulare a stati finiti, ovvero possiamo immaginarlo come un “essere vivente” che segue alcune regole preimpostate e in base a queste si evolve. In questo caso particolare, la formica si trova su di una griglia bidimensionale(una matrice) in cui ogni casella(elemento della matrice) può assumere i valori “1” o bianco e “0” o nero. Essa può girarsi di 90 gradi per volta a sinistra o a destra e può avanzare di una casella per iterazione.

Immagine della formica di langton

Formica di Langton

Leggi il seguito di questo post »

Written by barcadero

15 marzo 2011 at 6:32 pm

Programmare il gioco della vita di Conway

with 2 comments

L’automa cellulare di Conway

Il gioco della vita è un famosissimo automa cellulare elaborato dal matematico John Conway negli anni sessanta;  si tratta sostanzialmente di una griglia costituita da celle e ognuna di esse può essere o viva o morta(piena o vuota). Data una situazione iniziale della griglia, le successive iterazioni dell’algoritmo seguono delle regole semplicissime per decidere quali celle si devono accendere( nascere o continuare a vivere ) e quali spegnere( morire ), a seconda del numero di “vicini” che si trovano nel quadrato 3×3 con centro nella cella considerata.

  • Una cella vuota diventa piena( nasce ) se  ha 3 vicini
  • Una cella piena sopravvive se ha 2 o 3 vicini, altrimenti muore per solitudine o sovrappopolazione.

Glider Cannon image

(Un cannone di “glider” di Gosper)

L’implementazione

L’implementazione è scritta in C++ e per la parte grafica, che comprende la creazione della finestra, il disegno della griglia e delle celle, è stata usata la libreria SDL.

Per tracciare le linee della griglia è stata usata SDL_gfx, un’estensione di SDL che permette il disegno di primitive 2D ben più complesse delle semplici linee.

Il codice sorgente può essere scaricato QUI. Un binario per linux compilato con CodeBlocks può essere scaricato QUI.

Leggi il seguito di questo post »

Written by barcadero

6 marzo 2011 at 10:58 pm

Un semplice algoritmo genetico

with 2 comments

Cosa è un algoritmo genetico?

Un algoritmo genetico è, nella sua definizione più generica, un metodo di ricerca euristico di una soluzione a un dato problema usando tecniche che si ispirano a quelle della selezione naturale e dell’evoluzione darwiniane.

Si parte creando una popolazione di individui, ciascuno di questi rappresenta una soluzione al problema da risolvere codificata in una stringa, detta gene; nella prima generazione i geni vengono generati in modo casuale. A ogni iterazione dell’algoritmo si rimescolano i geni tra i vari individui e definita una funzione detta fitness(), che restituisce la bontà di un certo individuo, ovvero un valore numerico che misura la sua capacità di risolvere il dato problema, si selezionano ad ogni iterazione gli individui migliori ed i loro geni vengono mescolati a quelli di nuovi individui generati dalla funzione che si occupa del crossing-over, ovvero del rimescolamento casuale dei geni di individui già esistenti per crearne di nuovi. Questo procedimento porta, in genere, a ottenere un’individuo con valore di fitness molto alto e quindi capace di risolvere in modo “ottimizzato” il dato problema. Non trattandosi di un procedimento strettamente rigoroso non sempre questo succede, ma si tratta sicuramente di un metodo interessante e potente che rivela le sue capacità soprattutto nell’ottimizzazione per esempio delle interfacce grafiche, dei modelli che operano all’interno di simulazioni fisiche e naturalmente nella programmazione genetica.

Un problema semplice semplice da risolvere

Ora vediamo una mia implementazione in C++ di questo algoritmo per un problema banale come trovare 4 numeri compresi tra 0 e 10 che abbiano somma massima, si lo so, non serve una algoritmo genetico per capirlo, la combinazione giusta è 10 + 10 + 10 + 10 = 40, ma volete mettere il fatto di arrivarci in un modo completamente fuori dal comune?

L’implementazione

Per scarica l’intero sorgente fare click QUI.

Definiamo subito alcune costanti globali dentro a un namespace anonimo, in modo da limitarne la visibilità al solo file in questione:

namespace {
 const int GENE_DIM = 4;                //numero di geni
 const int POPULATION_DIM = 50;        //numero di individui della popolazione
 const int MAX_FITNESS = 40;         //fitness da raggiungere per fermare algoritmo
}

Iniziamo col definire una struttura C++ che rappresenti il singolo individuo:

struct Individuo {

int gene[ GENE_DIM ];

 //costruttore: azzera i geni
 Individuo();

 //assegna valori casuali a gene
 void ramdomize_gene();

 //funzione che misura la bontà di un individuo
 int fitness() const;

 //stampa il gene
 void print() const;

};

Leggi il seguito di questo post »

Written by barcadero

3 marzo 2011 at 10:44 pm