Simulazione di evoluzione biologica: regole e implementazione in C

Simulazione dell'evoluzione biologica

Un meccanismo biologico di evoluzione viene simulato supponendo che gli organismi che si considerano

occupino ciascuno una cella di una matrice di dimensioni pari a MAX righe e MAX colonne. Il meccanismo di

evoluzione è basato sulle seguenti regole che determinano il passaggio da una generazione alla successiva:

· un organismo sopravvive se nelle celle vicine ha 2 o 3 organismi viventi

· un organismo cessa di esistere se nelle celle vicine ha:

- 0 o 1 organismi viventi (solitudine) oppure

- da 4 a 8 organismi viventi (sovrappopolamento)

· un nuovo organismo nasce in una cella se nelle celle vicine coi sono 3 organismi viventi

Implementazione del programma in C

Realizzare un pgm C in grado, a partire da una configurazione iniziale, di mostrare l'evoluzione della specie.

SPECIFICHE

1) Configurazione iniziale:

· Leggere da tastiera le coordinate dei soli elementi vivi. L'input -1,-1 indica la terminazione di tale fase.

· (in alternativa) Generazione casuale degli elementi vivi.
2) Visualizzazione configurazione iniziale e generazioni successive:

Tabella di caratteri dove:

· Un asterisco indica la presenza di un organismo vivente

· Uno spazio indica assenza di vita

Esempio di evoluzione della specie

ESEMPIO

L'evoluzione di una specie risulta alquanto interessante dal punto di vista grafico. Sia l'input il seguente

(indicante la posizione dei soli elementi vivi)

2 1

2 2

2 3

-1 -1

L'evoluzione della popolazione di organismi risulta la seguente (in cui si è evidenziato il contorno della

matrice):

Configurazione Prima E così via …..

Iniziale generazione:

####### #######

# # # #

# # # * #

# *** # # * #

# # # * #

# # # #

####### #######

IPOTESI DI SOLUZIONE:

Ipotesi di soluzione con matrici

La soluzione prevede che in ciascun istante vengano memorizzate due generazioni della specie: la generazione

attuale e quella futura. Con il passaggio da una generazione a quella successiva la generazione futura diviene

quella attuale e una nuova generazione viene valutata. Questo meccanismo può essere realizzato mediante l'uso

di due matrici che contengono due generazioni successive e che si "scambino di ruolo" ad ogni iterazione. Una

soluzione particolarmente elegante può essere realizzata attraverso l'utilizzo di una matrice a tre dimensioni:

#define STATO 2

#define MAX 5

int vita [STATO][MAX][MAX]; //var globale

Una variabile (stato nel programma ) indica che la generazione attuale si trova nella matrice anteriore e quella

futura nella matrice posteriore ( se stato è uguale a 0) e la situazione inversa (se stato vale 1).

La matrice contiene 1 se l'organismo corrispondente è vivo, 0 altrimenti.

Determinazione dei vicini

Un ulteriore problema è la determinazione del numero di organismi vicini ad un organismo dato. Tale valore

può essere individuato, a partire dall'organismo nell'elemento (i,j), indicando gli offset, cioè gli scostamenti, sui

due indici.

i-1,j-1 i-1,j i-1,j+1

i,j-1 i,j i,j+1

i+1,j-1 i+1,j i+1,j+1

Tali offset (-1,0,+1) possono essere memorizzati in una coppia di vettori.

#define DIREZIONI 8

int scostX [DIREZIONI] = { 0, 1, 1, 1, 0, -1, -1, -1}; //var globale

int scostY [DIREZIONI] = { 1, 1 , 0, -1, -1, -1, 0, 1}; //var globale

int stato; //var booleana 0: stato attuale 1: stato futuro (locale alla funzione main())

Nel nostro caso quindi la var stato viene inizializzata a 0 (configurazione iniziale).

Sottoprogrammi del codice

Individuazione dei sottopgm:

void insert(); //inserimento della configurazione iniziale

void visualizza(int stato); //visualizza una generazione (compresa la configurazione iniziale)

void aggiorna (int stato); // calcolo di una nuova generazione (sulla base degli elementi vicini

// e se la casella è viva o morta)

int vicini(int x,int y,int stato); // calcola il numero di vicini vivi all'elemento x,y

int viva(int x,int,y,int stato); //determina se una casella è viva: 1 viva, 0 morta

void azzera(int stato); // azzera la matrice relativa alla generazione futura

// preparandola a contenere nuovi dati

6

Il pgm quando termina?

Mai, ciclo infinito (di evoluzioni)

while(1)

{

…..

}