Appendix: Genetic Algorithms Code
#include <stdio.h>
#include <pvm3.h>
#define WALL -1 // Health value of a Wall.
#define SPACE 2 // Health value for a new space.
#define OLDSPACE 0 // Health value for an old.
#define RAT 1 // Health vaule for a rat.
#define EXIT 100 // Health vaule for a exit.
#define FOOD 10 // Health value for food.
#define CAT -50 // Health value for a cat.
#define CATRAT -20 // Numerical Rep. of a rat on a cat.
#define NORTH 0 // Numerical Representation of North
#define SOUTH 2 // Numerical Rep. of South
#define EAST 1 // Numerical Rep. of East
#define WEST 3 // Numerical Rep. of West
#define LEFT 4 // Numerical Rep. of Command to turn Left.
#define RIGHT 6 // Numerical Rep. of Command to turn Right.
#define FORWARD 8 // Numerical Rep. of command to move forward.
#define GONEW 2 // Numerical Rep. of command to take path less // travelled.
#define NUMRATS 64 // Number of Rats per Processor
#define NUMRULES 16 // Number of Rules Each Rat has
#define MAXMOVES 200 // Maximum moves a rat can make per game.
#define NUMVALS 26 // Number of bits in a rule - keep constant.
#define NUMGENS 100 // Number of generations a population will run.
#define NUMMAZES 4 // The Number of mazes to be used during one run
// NOTE: NUMMAZES must divide evenly into NUMGENS
// so that each maze is used for a constant // number of gens.
#define PRINTCODE 99 // How often to print the best genetic code.
#define MEMORY 15 // This is the amount of scent a rat drops in a // square when he moves there
#define MUTRATE 500 // The mutation rate = (1/MUTRATE)
int maze[12][12];
int travel[12][12];
void PrintMatrix(int direction, int health, int left, int right, int ahead);
int GetInput();
int IsLegal(int direction, int ratx, int raty);
void UpdateMaze(int *ratx,int *raty, int command,int *direction,int *health, int *left, int *right, int *ahead);
int decide(int rules[NUMRULES][NUMVALS],int right, int left, int ahead);
// Take as input the surrounding of the rat in the maze.
// Compare this to the rats rules.
// Decide what to do and return a command to the processor.
int decide(int rules[NUMRULES][NUMVALS],int right, int left, int ahead) {
int Surroundings[NUMVALS],i, j ,val,matched, bestrule, bestbits;
for(i=0;i<NUMVALS-2;i+=8) {
if (i==0) {
val = left;
} else if (i==8) {
val = ahead;
} else {
val=right;
}
switch (val) {
// Fill the appropriate 8-bits in Surroundings with the appropriate
// code.
case WALL: Surroundings[i+0]=0;
Surroundings[i+1]=1;
Surroundings[i+2]=1;
Surroundings[i+3]=0;
Surroundings[i+4]=1;
Surroundings[i+5]=0;
Surroundings[i+6]=0;
Surroundings[i+7]=0; break;
case CAT: Surroundings[i+0]=0;
Surroundings[i+1]=1;
Surroundings[i+2]=0;
Surroundings[i+3]=1;
Surroundings[i+4]=0;
Surroundings[i+5]=0;
Surroundings[i+6]=1;
Surroundings[i+7]=1; break;
case FOOD: Surroundings[i+0]=1;
Surroundings[i+1]=0;
Surroundings[i+2]=0;
Surroundings[i+3]=0;
Surroundings[i+4]=0;
Surroundings[i+5]=1;
Surroundings[i+6]=0;
Surroundings[i+7]=1; break;
case SPACE: case OLDSPACE:
Surroundings[i+0]=0;
Surroundings[i+1]=0;
Surroundings[i+2]=1;
Surroundings[i+3]=0;
Surroundings[i+4]=0;
Surroundings[i+5]=0;
Surroundings[i+6]=0;
Surroundings[i+7]=0; break;
default: break;
}
}
bestrule = 0; bestbits = 0;
// Compare the surroundings to the rules.
for(i=0;i<NUMRULES;i++) {
matched = 0;
for(j=0;j<NUMVALS-2;j++) {
// If a bit in Surrounding = a bit in Rules,
// increment the matches counter.
if (rules[i][j] == Surroundings[j])
matched++;
}
// If this rule has more matches than any other, make it the best //rule
if (matched > bestbits) {
bestrule = i;
bestbits = matched;
}
}
rules[bestrule][25]);
// Return the command that corresponds to the last
// two bits of the best rule.
if ((rules[bestrule][NUMVALS-2] == 0) && (rules[bestrule][NUMVALS- 1] == 0)) {
return 8;
}
else if ((rules[bestrule][NUMVALS-2] == 0) && (rules[bestrule][NUMVALS-1] == 1)){
return 2;
}
else if ((rules[bestrule][NUMVALS-2] == 1) && (rules[bestrule][NUMVALS-1] == 0)) {
return 6;
}
else
return 4;
}
// Print the Maze to the Screen.
// This function can be used to watch a small amount of rats exact movements.
// It can also be used to error check.
void PrintMatrix(int direction, int health, int left, int right, int ahead) {
int i,j;
for (i = 0; i<12;i=i+1) {
for (j = 0; j<12;j=j+1) {
if (maze[i][j]==WALL)
printf("X");
if (maze[i][j]==SPACE)
printf(" ");
if (maze[i][j]==RAT)
printf("R");
if (maze[i][j]==EXIT)
printf("E");
if (maze[i][j]==FOOD)
printf("f");
if (maze[i][j]==CAT)
printf("C");
if (maze[i][j]==CATRAT)
printf("R");
} printf("\n");
} if (direction == NORTH) {
printf(" \n Direction: North");
} else if (direction == SOUTH) {
printf(" \n Direction: South");
} else if (direction == EAST) {
printf(" \n Direction: East");
} else
printf(" \n Direction: West");
printf(" \n Health: %d", health);
printf(" \n Left: %d", left);
printf(" \n Right: %d", right);
printf(" \n Ahead: %d \n", ahead);
}
/* This function is also used for error checking.
It takes input from the user instead of the genetic code.
int GetInput() {
int x=5;
while(x != 4 && x != 6 && x != 8){
printf("\n What command do you want to give the rat? \n (8=move forward, 4=turn left,6=turn right): ");
scanf("%d", &x);
}
return x;
}
// This function Checks that a move will not put a rat on top of a wall.
// It takes the coordinates of the rat and the direction he is facing
// and returns 1 if the space straight ahead of him is not a wall.
// If it is a wall, it returns 0.
int IsLegal(int direction, int ratx, int raty) {
if (direction == NORTH && maze[ratx-1][raty] != WALL)
return 1;
else if (direction == EAST && maze[ratx][raty+1] != WALL)
return 1;
else if (direction == SOUTH && maze[ratx+1][raty] != WALL)
return 1;
else if (direction == WEST && maze[ratx][raty-1] != WALL)
return 1;
else
return 0;
}
// This function Updates the maze after each command is made.
void UpdateMaze(int *ratx,int *raty,int command,int *direction,int *health, int *left, int *right, int *ahead) {
int i,j;
// Assert: Command == LEFT,RIGHT, or FORWARD
// Assert: direction == NORTH,EAST,SOUTH, or WEST
// If the command to go to the space less travelled, change
// the command to the appropriate direction.
for(i=0;i<12;i++) {
for(j=0;j<12;j++) {
if (travel[i][j] != 0)
travel[i][j]--;
}
}
if (command==GONEW) {
switch(*direction) {
case NORTH:
if((travel[(*ratx)-1][*raty] < travel[*ratx][(*raty)+1]) && (travel[(*ratx)-1][*raty] < travel[*ratx][(*raty)-1])) {
command=FORWARD;
} else if ((travel[*ratx][(*raty)-1] < travel[(*ratx)-1][*raty]) && (travel[*ratx][(*raty)-1] < travel[*ratx][(*raty)+1])) {
command=LEFT;
} else if ((travel[*ratx][(*raty)+1] < travel[(*ratx)-1][*raty]) && (travel[*ratx][(*raty)+1] < travel[*ratx][(*raty)-1])) {
command=RIGHT;
} break;
case EAST:
if((travel[*ratx][(*raty)+1] < travel[(*ratx)-1][*raty]) && (travel[*ratx][(*raty)+1] < travel[(*ratx)+1][*raty])) {
command=FORWARD;
} else if ((travel[(*ratx)-1][*raty] < travel[*ratx][(*raty)+1]) && (travel[(*ratx)-1][*raty] < travel[(*ratx)+1][*raty])) {
command=LEFT;
} else if ((travel[(*ratx)+1][*raty] < travel[(*ratx)-1][*raty]) && (travel[(*ratx)+1][*raty] < travel[*ratx][(*raty)+1])) {
command=RIGHT;
} break;
case SOUTH:
if((travel[(*ratx)+1][*raty] < travel[*ratx][(*raty)+1]) && (travel[(*ratx)+1][*raty] < travel[*ratx][(*raty)-1])) {
command=FORWARD;
} else if ((travel[*ratx][(*raty)-1] < travel[*ratx][(*raty)+1]) && (travel[*ratx][(*raty)-1] < travel[(*ratx)+1][*raty])) {
command=RIGHT;
} else if ((travel[*ratx][(*raty)+1] < travel[(*ratx)+1][*raty]) && (travel[*ratx][(*raty)+1] < travel[*ratx][(*raty)-1])) {
command=LEFT;
} break;
case WEST:
if((travel[*ratx][(*raty)-1] < travel[(*ratx)-1][*raty]) && (travel[*ratx][(*raty)-1] < travel[(*ratx)+1][*raty])) {
command=FORWARD;
} else if ((travel[(*ratx)-1][*raty] < travel[*ratx][(*raty)-1]) && (travel[(*ratx)-1][*raty] < travel[(*ratx)+1][*raty])) {
command=RIGHT;
} else if ((travel[(*ratx)+1][*raty] < travel[(*ratx)-1][*raty]) && (travel[(*ratx)+1][*raty] < travel[*ratx][(*raty)-1])) {
command=LEFT;
} break;
default: break;
}
}
// If A turn command is issued, Turn.
// If you are facing 0 and you turn Left, turn to 3, and so on.
if ((command == LEFT) && ((*direction) != 0)) {
(*direction)--;
} else if ((command == LEFT) && ((*direction) == 0)) {
(*direction) = 3;
} else if ((command == RIGHT) && ((*direction) != 3)) {
(*direction)++;
} else if ((command == RIGHT) && ((*direction) == 3)) {
(*direction)=0;
} else { // command == FORWARD
// Move forward based on the direction that the rat is facing.
switch(*direction) {
case NORTH:// Update the rats health value based on where he // moved.
*health += maze[*ratx-1][*raty];
// If the next space is not a wall move,
// and handle the case that we are moving off a rat.
if (IsLegal(*direction, *ratx, *raty)) {
travel[*ratx][*raty] += MEMORY;
if (maze[*ratx][*raty]==CATRAT)
maze[*ratx][*raty]=CAT;
else
maze[*ratx][*raty]=OLDSPACE;
// Handle the case that we are moving onto a rat.
if (maze[*ratx-1][*raty] == CAT)
maze[*ratx-1][*raty] = CATRAT;
else if ((maze[*ratx-1][*raty] != EXIT))
maze[*ratx-1][*raty]=RAT;
// Update the Coordinate system.
(*ratx)--;
} break;
case EAST: *health += maze[*ratx][*raty+1];
if (IsLegal(*direction, *ratx, *raty)) {
travel[*ratx][*raty] += MEMORY;
if (maze[*ratx][*raty]==CATRAT)
maze[*ratx][*raty]=CAT;
else
maze[*ratx][*raty]=OLDSPACE;
if (maze[*ratx][*raty+1] == CAT)
maze[*ratx][*raty+1] = CATRAT;
else if ((maze[*ratx][*raty+1] != EXIT))
maze[*ratx][*raty+1]=RAT;
(*raty)++;
} break;
case SOUTH: *health += maze[*ratx+1][*raty];
if (IsLegal(*direction, *ratx, *raty)){
travel[*ratx][*raty] += MEMORY;
if (maze[*ratx][*raty]==CATRAT)
maze[*ratx][*raty]=CAT;
else
maze[*ratx][*raty]=OLDSPACE;
if (maze[*ratx+1][*raty] == CAT)
maze[*ratx+1][*raty] = CATRAT;
else if ((maze[*ratx+1][*raty] != EXIT))
maze[*ratx+1][*raty]=RAT;
(*ratx)++;
} break;
case WEST: *health += maze[*ratx][*raty-1];
if (IsLegal(*direction, *ratx, *raty)) {
travel[*ratx][*raty] += MEMORY;
if (maze[*ratx][*raty]==CATRAT)
maze[*ratx][*raty]=CAT;
else
maze[*ratx][*raty]=OLDSPACE;
if (maze[*ratx][*raty-1] == CAT)
maze[*ratx][*raty-1] = CATRAT;
else if (maze[*ratx][*raty-1] != EXIT)
maze[*ratx][*raty-1]=RAT;
(*raty)--;
} break;
default: break;
}
}
// Update what is to the left, right and straight ahead.
switch(*direction) {
case 0: *left = maze[*ratx][*raty-1];
*right= maze[*ratx][*raty+1];
*ahead= maze[*ratx-1][*raty]; break;
case 1: *right = maze[*ratx+1][*raty];
*ahead= maze[*ratx][*raty+1];
*left= maze[*ratx-1][*raty]; break;
case 2: *right = maze[*ratx][*raty-1];
*left= maze[*ratx][*raty+1];
*ahead= maze[*ratx+1][*raty]; break;
case 3: *left = maze[*ratx+1][*raty];
*right= maze[*ratx-1][*raty];
*ahead= maze[*ratx][*raty-1];
break;
default: break;
}
}
main()
{
//Pvm variable declarations
int mype = pvm_get_PE(pvm_mytid());
int npes = pvm_gsize(0);
int totrats = NUMRATS * npes;
int info, bufinfo, packinfo, sendinfo, mcastinfo, recvbuf,recvinfo;
int unpackinfo, bytes, tag, tid, recvproc;
//Loop variables
int a, b, c, i, j, k, n, x, bits, count, big, small, myrand;
//Temporary arrays
int temprules[NUMRATS/2][NUMRULES][NUMVALS], temprules2[NUMVALS];
int tempfitness[NUMRATS], fitness[NUMRATS];
int allrulestemp[NUMRULES][NUMVALS],
//Final arrays
int procrules[NUMRATS][NUMRULES][NUMVALS];
int allrules[NUMRATS * npes][NUMRULES][NUMVALS], allfitness[totrats];
//pvm destination arrays
int destpes[npes-1], dest_array[1];
//Misc. variables
int gennum, sum;
int command, ratx, raty, health, direction, left, right, ahead;
int ratnum, nummoves;
int rules[NUMRULES][NUMVALS];
char ch = 'a';
char filename[NUMMAZES][8];
FILE *fopen(), *fp;
ratnum=0;
srand(mype * time(NULL) + ratnum); //for fitness and rule
for( a = 0; a < NUMRATS; a++ ) {
for( b = 0; b < NUMRULES; b++ ) {
for( c = 0; c < NUMVALS; c++ ) { //generate random numbers
procrules[a][b][c] = (rand() % 2);
}
}
}
for (i=1;i<npes;i++)
destpes[i-1] = i;
if(mype == 0)
printf("SETTINGS: numrats: %d \t numrules: %d \t maxmoves: %d \t Mut. Rate: %d\n", NUMRATS, NUMRULES, MAXMOVES, MUTRATE);
// Get the name of the mazes to use
if (mype == 0) {
for(i=0;i < NUMMAZES; i++) {
printf("Please enter the name of maze %d: ", i);
scanf("%s", &filename[i]);
}
}
for(gennum = 0; gennum < NUMGENS; gennum++){
ratnum=0;
// open the maze. This has the effect of resetting the maze for each rat.
while (ratnum < NUMRATS) {
// Assert: The file will contain exactly 12X12
if (mype==0) {
fp = fopen(filename[gennum/(NUMGENS/NUMMAZES)],"r");
for(i = 0; i<12;i++){
for(j=0; j<12;j++) {
ch = getc(fp); // Get the next character.
// Interpret the character in the file and fill the matrix.
if (ch == 'X') {
maze[i][j]=WALL;
travel[i][j]=2000;
} else if (ch == 'R') {
maze[i][j]=RAT;
travel[i][j]=0;
} else if (ch == 'f') {
maze[i][j]=FOOD;
travel[i][j]=2000;
} else if (ch == 'C') {
maze[i][j]=CAT;
travel[i][j]=2000;
} else if (ch == 'E') {
maze[i][j]=EXIT;
travel[i][j]=2000;
} else {
maze[i][j]=SPACE;
travel[i][j]=0;
}
} ch = getc(fp);
}
fclose(fp); // Close the file.
bufinfo = pvm_initsend(PvmDataDefault);
for(i=0;i<12;i++) {
packinfo = pvm_pkint(maze[i],12,1);
} mcastinfo = pvm_mcast(destpes,npes-1,1);
} else {
recvbuf = pvm_recv(-1,-1);
for(i=0;i<12;i++) {
packinfo = pvm_upkint(maze[i],12,1);
}
} if (mype==0) {
bufinfo = pvm_initsend(PvmDataDefault);
for(i=0;i<12;i++) {
packinfo = pvm_pkint(travel[i],12,1);
} mcastinfo = pvm_mcast(destpes,npes-1,1);
} else {
recvbuf = pvm_recv(-1,-1);
for(i=0;i<12;i++) {
unpackinfo = pvm_upkint(travel[i],12,1);
}
}
// Copy the rules for the rat from the big rule matrix into
// into a 2-dimensional matrix that contains information specific
// to this rat.
for (i=0; i < NUMRULES; i++) {
for (j=0; j < NUMVALS; j++) {
rules[i][j] = procrules[ratnum][i][j];
}
}
// Initialize values for initial location, condition, and surroundings.
direction = 1;
ratx=1;
raty=1;
right = maze[ratx+1][raty];
ahead = maze[ratx][raty+1];
left = maze[ratx-1][raty];
health=0;
nummoves = 0;
while (maze[ratx][raty] != EXIT && nummoves < MAXMOVES) {
command = decide(rules, right, left, ahead);
UpdateMaze(&ratx, &raty,command,&direction,&health, &left, &right, & ahead);
nummoves++;
}
fitness[ratnum]=health;
ratnum++;
}
//************MESSAGE PASSING and SORTING***************
info = pvm_barrier(0, npes);
// PEs 1 to PE(npes-1) send their allrules arrays to PE 0
if (mype > 0) {
bufinfo = pvm_initsend(PvmDataDefault);
for (i = 0; i < NUMRATS; i++){
for (j = 0; j<NUMRULES; j++){
packinfo = pvm_pkint(procrules[i][j], NUMVALS, 1);
}
}
sendinfo = pvm_send(0, 1);
}
// PE 0 receives procrules from PE 1 to (npes-1) and unpacks each array into tempall,
// then places each element in the appropriate order in allrules
else {
for(i = 0; i < NUMRATS; i++) {
for(j = 0; j < NUMRULES; j++) {
for (k=0; k<NUMVALS; k++){
allrules[i][j][k] = procrules[i][j][k];
}
}
}
for(count = 1; count < npes; count++){
recvinfo = pvm_recv(-1, -1);
bufinfo = pvm_bufinfo(recvinfo, &bytes, &tag, &tid);
recvproc = pvm_get_PE(tid);
for(i = 0; i < NUMRATS; i++) {
for(j = 0; j < NUMRULES; j++) {
unpackinfo = pvm_upkint(temprules2, NUMVALS, 1);
for (k=0; k<NUMVALS; k++){
allrules[i+(NUMRATS*recvproc)][j][k] = temprules2[k];
}
}
}
}
}
info = pvm_barrier(0, npes);
// PEs 1 to PE(npes-1) send their fitness arrays to PE 0
if (mype > 0) {
bufinfo = pvm_initsend(PvmDataDefault);
packinfo = pvm_pkint(fitness, NUMRATS, 1);
sendinfo = pvm_send(0, 1);
}
// PE 0 receives fitness from PE 1 to (npes-1) and unpacks each array // into tempall, then places each element in appropriate order in // allfitness
else{
for(i = 0; i<NUMRATS; i++){
allfitness[i] = fitness[i];
}
for(n=1; n< npes; n++){
recvinfo = pvm_recv(-1, -1);
bufinfo = pvm_bufinfo(recvinfo, &bytes, &tag, &tid);
recvproc = pvm_get_PE(tid);
unpackinfo = pvm_upkint(tempfitness,NUMRATS, 1);
for( i = 0; i < NUMRATS; i++) {
allfitness[(recvproc * NUMRATS) + i] = tempfitness[i];
}
}
}
// At this point, PE 0 should contain (in order) ratrules from PE 1 to // PE(npes-1) in the allrules array and all of the fitness values in the // allfitness array
pvm_barrier(0, npes);
// The following algorithm (bubble sort) should arrange the fitness // values and the rules in order from the top down
if (mype == 0){
for (n=0; n<totrats; n++){
for (i = totrats-1; i>=n; i--){
if (allfitness[i]>allfitness[i-1]){
small = allfitness[i-1];
allfitness[i-1] = allfitness[i];
allfitness[i] = small;
for (j=0; j<NUMRULES; j++){
for (k=0; k<NUMVALS; k++){
allrulestemp[j][k] = allrules[i-1][j][k];
allrules[i-1][j][k] = allrules[i][j][k];
allrules[i][j][k] = allrulestemp[j][k];
}
}
}
}
}
//*************OUTPUT******************
sum = 0;
for(i=0; i < totrats;i++){
sum = allfitness[i] + sum;
}
printf("Gen: %d \t Best Health: %d \t Worst Health: %d \t Avg. Health: %d \n", gennum, allfitness[0], allfitness[totrats-1], sum/totrats);
if (gennum%PRINTCODE==0) {
printf("Best Code for gen %d: \n", gennum);
for(b = 0; b < NUMRULES; b++) {
for(c = 0; c < NUMVALS; c++) {
printf("%d ", allrules[a][b][c]);
}
printf("\n");
}
}
}
//************************************
pvm_barrier(0, npes);
if (mype == 0){
for (n = 1; n < npes; n++){
pvm_initsend(PvmDataDefault);
for (i = 0; i < (NUMRATS/2); i++){
for (j = 0; j < NUMRULES; j++){
for (k = 0; k < NUMVALS; k++){
temprules[i][j][k] = allrules[n + (i*npes)][j][k];
}
pvm_pkint(temprules[i][j], NUMVALS, 1);
}
}
pvm_send(n, 1);
}
for(i = 0; i <NUMRATS/2; i++){
for (j = 0; j < NUMRULES; j++){
for(k = 0; k<NUMVALS; k++){
temprules[i][j][k] = allrules[(i*npes)][j][k];
}
}
}
}
else{
recvbuf = pvm_recv(-1, -1);
for (i = 0; i < (NUMRATS/2); i++){
for (j = 0; j < NUMRULES; j++){
unpackinfo = pvm_upkint(temprules[i][j],NUMVALS, 1);
}
}
}
pvm_barrier(0, npes);
//***************END MESSAGE PASSING****************
//***************MATING******************
srand(mype-time(NULL));
for(i = 0; i < NUMRATS/2; i++){
for(j = 0; j < NUMRULES; j++){
for(k = 0; k < NUMVALS; k++){
procrules[i][j][k] = temprules[i][j][k];
}
}
}
for(i = 0; i < NUMRATS/2; i=i+2){
for(j = 0; j < NUMRULES; j++){
srand(mype+time(NULL));
myrand = (NUMVALS*rand())/32678;
for(k = 0; k < NUMVALS - myrand + 2; k++)
temprules[i][j][myrand+k] = temprules[i+1][j][myrand+k];
for(k = 0; k < myrand; k++)
temprules[i+1][j][k]=temprules[i][j][k];
}
}
for(i = 0; i < NUMRATS/2; i++){
for(j = 0; j < NUMRULES; j++){
for(k = 0; k < NUMVALS; k++){
procrules[i+(NUMRATS/2)][j][k] = temprules[i][j][k];
if(rand()%MUTRATE==0 && procrules[i+(NUMRATS/2)][j][k]==1)
procrules[i+(NUMRATS/2)][j][k]=0;
if(rand()%MUTRATE==0 && procrules[i+(NUMRATS/2)][j][k]==0)
procrules[i+(NUMRATS/2)][j][k]=1;
}
}
}
}
}